Problem 599928 · hard · Level 05 Advanced Algorithms & Graphs

Make the Failing Input Small Enough to Read

py-debugging · py-testing · test-case reduction · greedy search · slicing

A randomised test found a list of 200 numbers on which a function misbehaves. Nobody can debug that by hand, so write the tool that makes it small: shrink(fails, case). fails(xs) returns True when the list xs still shows the bug, and fails(case) is True at the start. Return a simpler failing list, found by repeating the following, where cur starts as a copy of case:

  1. Remove a chunk. For chunk sizes s = len(cur) // 2, then halved again (s // 2), and so on down to 1, and for each size for the starts i = 0, s, 2s, ... (while i < len(cur)), try cur without cur[i:i + s]. The first candidate for which fails is True becomes cur, and you start again at step 1.
  2. Simplify a number. If no removal works, go through the positions i from left to right, and for the value v at each position try replacing it by each of these candidates in turn: 0, int(v / 2), v - 1 if v > 0 or v + 1 if v < 0, and -v. Skip a candidate that equals v, that was already tried for this position, or that is not simpler than v: it must be closer to zero, or equally close and positive where v is negative. The first replacement for which fails is True becomes cur, and you start again at step 1.
  3. If neither step changes anything, return cur.

Never change case itself. The judge shrink_suspect(name, n, seed) builds a failing random list of length n for one of the predicates in SUSPECTS ("sum_over_100", "unique", "window", "big_then_negative" and "sorted_pair"), shrinks it with your function and returns (your result, fails(result), case unchanged). It allows at most 20000 calls of fails per shrink and raises TooManyCalls beyond that.

Examples

Input:  shrink(lambda xs: len(xs) >= 3, [5, -2, 7, 9])
Output: [0, 0, 0]

Input:  shrink(lambda xs: sum(xs) > 100, [30, 40, 50, 60])
Output: [41, 60]
Explanation: removing [30, 40] leaves [50, 60]; then 50 cannot become 0 or 25 (sum 60, 85),
but 49, 48, ... are tried one step at a time until 41; 40 would give 100, which does not fail.

Constraints

  • 1 <= len(case) <= 200, values between -10**4 and 10**4. fails has no side effects.

Goals

  • Automate the "shrink the failing input" step of debugging
  • Follow a precisely specified search order so the result is reproducible
  • Treat a predicate as a black box and call it economically
Starting Python…