{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Designing a better simplifier\n",
"\n",
"This is a notebook talking through some of the considerations in the design of Hypothesis's approach to simplification.\n",
"\n",
"It doesn't perfectly mirror what actually happens in Hypothesis, but it should give some consideration to the sort of things that Hypothesis does and why it takes a particular approach.\n",
"\n",
"In order to simplify the scope of this document we are only going to\n",
"concern ourselves with lists of integers. There are a number of API considerations involved in expanding beyond that point, however most of the algorithmic considerations are the same.\n",
"\n",
"The big difference between lists of integers and the general case is that integers can never be too complex. In particular we will rapidly get to the point where individual elements can be simplified in usually only log(n) calls. When dealing with e.g. lists of lists this is a much more complicated proposition. That may be covered in another notebook.\n",
"\n",
"Our objective here is to minimize the number of times we check the condition. We won't be looking at actual timing performance, because usually the speed of the condition is the bottleneck there (and where it's not, everything is fast enough that we need not worry)."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def greedy_shrink(ls, constraint, shrink):\n",
" \"\"\"\n",
" This is the \"classic\" QuickCheck algorithm which takes a shrink function\n",
" which will iterate over simpler versions of an example. We are trying\n",
" to find a local minima: That is an example ls such that condition(ls)\n",
" is True but that constraint(t) is False for each t in shrink(ls).\n",
" \"\"\"\n",
" while True:\n",
" for s in shrink(ls):\n",
" if constraint(s):\n",
" ls = s\n",
" break\n",
" else:\n",
" return ls"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def shrink1(ls):\n",
" \"\"\"\n",
" This is our prototype shrink function. It is very bad. It makes the\n",
" mistake of only making very small changes to an example each time.\n",
"\n",
" Most people write something like this the first time they come to\n",
" implement example shrinking. In particular early Hypothesis very much\n",
" made this mistake.\n",
"\n",
" What this does:\n",
"\n",
" For each index, if the value of the index is non-zero we try\n",
" decrementing it by 1.\n",
"\n",
" We then (regardless of if it's zero) try the list with the value at\n",
" that index deleted.\n",
" \"\"\"\n",
" for i in range(len(ls)):\n",
" s = list(ls)\n",
" if s[i] > 0:\n",
" s[i] -= 1\n",
" yield list(s)\n",
" del s[i]\n",
" yield list(s)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def show_trace(start, constraint, simplifier):\n",
" \"\"\"\n",
" This is a debug function. You shouldn't concern yourself with\n",
" its implementation too much.\n",
"\n",
" What it does is print out every intermediate step in applying a\n",
" simplifier (a function of the form (list, constraint) -> list)\n",
" along with whether it is a successful shrink or not.\n",
" \"\"\"\n",
" if start is None:\n",
" while True:\n",
" start = gen_list()\n",
" if constraint(start):\n",
" break\n",
"\n",
" shrinks = [0]\n",
" tests = [0]\n",
"\n",
" def print_shrink(ls):\n",
" tests[0] += 1\n",
" if constraint(ls):\n",
" shrinks[0] += 1\n",
" print(\"✓\", ls)\n",
" return True\n",
" else:\n",
" print(\"✗\", ls)\n",
" return False\n",
" print(\"✓\", start)\n",
" simplifier(start, print_shrink)\n",
" print()\n",
" print(\"%d shrinks with %d function calls\" % (\n",
" shrinks[0], tests[0]))"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"from functools import partial"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"✓ [5, 5]\n",
"✓ [4, 5]\n",
"✓ [3, 5]\n",
"✓ [2, 5]\n",
"✓ [1, 5]\n",
"✓ [0, 5]\n",
"✗ [5]\n",
"✓ [0, 4]\n",
"✗ [4]\n",
"✓ [0, 3]\n",
"✗ [3]\n",
"✓ [0, 2]\n",
"✗ [2]\n",
"✓ [0, 1]\n",
"✗ [1]\n",
"✓ [0, 0]\n",
"✗ [0]\n",
"✗ [0]\n",
"\n",
"10 shrinks with 17 function calls\n"
]
}
],
"source": [
"show_trace([5, 5], lambda x: len(x) >= 2, partial(greedy_shrink, shrink=shrink1))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"That worked reasonably well, but it sure was a lot of function calls for such a small amount of shrinking. What would have happened if we'd started with [100, 100]?"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def shrink2(ls):\n",
" \"\"\"\n",
" Here is an improved shrink function. We first try deleting each element\n",
" and then we try making each element smaller, but we do so from the left\n",
" hand side instead of the right. This means we will always find the\n",
" smallest value that can go in there, but we will do so much sooner.\n",
" \"\"\"\n",
" for i in range(len(ls)):\n",
" s = list(ls)\n",
" del s[i]\n",
" yield list(s)\n",
"\n",
" for i in range(len(ls)):\n",
" for x in range(ls[i]):\n",
" s = list(ls)\n",
" s[i] = x\n",
" yield s"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"✓ [5, 5]\n",
"✗ [5]\n",
"✗ [5]\n",
"✓ [0, 5]\n",
"✗ [5]\n",
"✗ [0]\n",
"✓ [0, 0]\n",
"✗ [0]\n",
"✗ [0]\n",
"\n",
"2 shrinks with 8 function calls\n"
]
}
],
"source": [
"show_trace([5, 5], lambda x: len(x) >= 2, partial(\n",
" greedy_shrink, shrink=shrink2))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This did indeed reduce the number of function calls significantly - we immediately determine that the value in the cell doesn't matter and we can just put zero there. \n",
"\n",
"But what would have happened if the value *did* matter?"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"✓ [1000]\n",
"✗ []\n",
"✗ [0]\n",
"✗ [1]\n",
"✗ [2]\n",
"✗ [3]\n",
"✗ [4]\n",
"✗ [5]\n",
"✗ [6]\n",
"✗ [7]\n",
"✗ [8]\n",
"✗ [9]\n",
"✗ [10]\n",
"✗ [11]\n",
"✗ [12]\n",
"✗ [13]\n",
"✗ [14]\n",
"✗ [15]\n",
"✗ [16]\n",
"✗ [17]\n",
"✗ [18]\n",
"✗ [19]\n",
"✗ [20]\n",
"✗ [21]\n",
"✗ [22]\n",
"✗ [23]\n",
"✗ [24]\n",
"✗ [25]\n",
"✗ [26]\n",
"✗ [27]\n",
"✗ [28]\n",
"✗ [29]\n",
"✗ [30]\n",
"✗ [31]\n",
"✗ [32]\n",
"✗ [33]\n",
"✗ [34]\n",
"✗ [35]\n",
"✗ [36]\n",
"✗ [37]\n",
"✗ [38]\n",
"✗ [39]\n",
"✗ [40]\n",
"✗ [41]\n",
"✗ [42]\n",
"✗ [43]\n",
"✗ [44]\n",
"✗ [45]\n",
"✗ [46]\n",
"✗ [47]\n",
"✗ [48]\n",
"✗ [49]\n",
"✗ [50]\n",
"✗ [51]\n",
"✗ [52]\n",
"✗ [53]\n",
"✗ [54]\n",
"✗ [55]\n",
"✗ [56]\n",
"✗ [57]\n",
"✗ [58]\n",
"✗ [59]\n",
"✗ [60]\n",
"✗ [61]\n",
"✗ [62]\n",
"✗ [63]\n",
"✗ [64]\n",
"✗ [65]\n",
"✗ [66]\n",
"✗ [67]\n",
"✗ [68]\n",
"✗ [69]\n",
"✗ [70]\n",
"✗ [71]\n",
"✗ [72]\n",
"✗ [73]\n",
"✗ [74]\n",
"✗ [75]\n",
"✗ [76]\n",
"✗ [77]\n",
"✗ [78]\n",
"✗ [79]\n",
"✗ [80]\n",
"✗ [81]\n",
"✗ [82]\n",
"✗ [83]\n",
"✗ [84]\n",
"✗ [85]\n",
"✗ [86]\n",
"✗ [87]\n",
"✗ [88]\n",
"✗ [89]\n",
"✗ [90]\n",
"✗ [91]\n",
"✗ [92]\n",
"✗ [93]\n",
"✗ [94]\n",
"✗ [95]\n",
"✗ [96]\n",
"✗ [97]\n",
"✗ [98]\n",
"✗ [99]\n",
"✗ [100]\n",
"✗ [101]\n",
"✗ [102]\n",
"✗ [103]\n",
"✗ [104]\n",
"✗ [105]\n",
"✗ [106]\n",
"✗ [107]\n",
"✗ [108]\n",
"✗ [109]\n",
"✗ [110]\n",
"✗ [111]\n",
"✗ [112]\n",
"✗ [113]\n",
"✗ [114]\n",
"✗ [115]\n",
"✗ [116]\n",
"✗ [117]\n",
"✗ [118]\n",
"✗ [119]\n",
"✗ [120]\n",
"✗ [121]\n",
"✗ [122]\n",
"✗ [123]\n",
"✗ [124]\n",
"✗ [125]\n",
"✗ [126]\n",
"✗ [127]\n",
"✗ [128]\n",
"✗ [129]\n",
"✗ [130]\n",
"✗ [131]\n",
"✗ [132]\n",
"✗ [133]\n",
"✗ [134]\n",
"✗ [135]\n",
"✗ [136]\n",
"✗ [137]\n",
"✗ [138]\n",
"✗ [139]\n",
"✗ [140]\n",
"✗ [141]\n",
"✗ [142]\n",
"✗ [143]\n",
"✗ [144]\n",
"✗ [145]\n",
"✗ [146]\n",
"✗ [147]\n",
"✗ [148]\n",
"✗ [149]\n",
"✗ [150]\n",
"✗ [151]\n",
"✗ [152]\n",
"✗ [153]\n",
"✗ [154]\n",
"✗ [155]\n",
"✗ [156]\n",
"✗ [157]\n",
"✗ [158]\n",
"✗ [159]\n",
"✗ [160]\n",
"✗ [161]\n",
"✗ [162]\n",
"✗ [163]\n",
"✗ [164]\n",
"✗ [165]\n",
"✗ [166]\n",
"✗ [167]\n",
"✗ [168]\n",
"✗ [169]\n",
"✗ [170]\n",
"✗ [171]\n",
"✗ [172]\n",
"✗ [173]\n",
"✗ [174]\n",
"✗ [175]\n",
"✗ [176]\n",
"✗ [177]\n",
"✗ [178]\n",
"✗ [179]\n",
"✗ [180]\n",
"✗ [181]\n",
"✗ [182]\n",
"✗ [183]\n",
"✗ [184]\n",
"✗ [185]\n",
"✗ [186]\n",
"✗ [187]\n",
"✗ [188]\n",
"✗ [189]\n",
"✗ [190]\n",
"✗ [191]\n",
"✗ [192]\n",
"✗ [193]\n",
"✗ [194]\n",
"✗ [195]\n",
"✗ [196]\n",
"✗ [197]\n",
"✗ [198]\n",
"✗ [199]\n",
"✗ [200]\n",
"✗ [201]\n",
"✗ [202]\n",
"✗ [203]\n",
"✗ [204]\n",
"✗ [205]\n",
"✗ [206]\n",
"✗ [207]\n",
"✗ [208]\n",
"✗ [209]\n",
"✗ [210]\n",
"✗ [211]\n",
"✗ [212]\n",
"✗ [213]\n",
"✗ [214]\n",
"✗ [215]\n",
"✗ [216]\n",
"✗ [217]\n",
"✗ [218]\n",
"✗ [219]\n",
"✗ [220]\n",
"✗ [221]\n",
"✗ [222]\n",
"✗ [223]\n",
"✗ [224]\n",
"✗ [225]\n",
"✗ [226]\n",
"✗ [227]\n",
"✗ [228]\n",
"✗ [229]\n",
"✗ [230]\n",
"✗ [231]\n",
"✗ [232]\n",
"✗ [233]\n",
"✗ [234]\n",
"✗ [235]\n",
"✗ [236]\n",
"✗ [237]\n",
"✗ [238]\n",
"✗ [239]\n",
"✗ [240]\n",
"✗ [241]\n",
"✗ [242]\n",
"✗ [243]\n",
"✗ [244]\n",
"✗ [245]\n",
"✗ [246]\n",
"✗ [247]\n",
"✗ [248]\n",
"✗ [249]\n",
"✗ [250]\n",
"✗ [251]\n",
"✗ [252]\n",
"✗ [253]\n",
"✗ [254]\n",
"✗ [255]\n",
"✗ [256]\n",
"✗ [257]\n",
"✗ [258]\n",
"✗ [259]\n",
"✗ [260]\n",
"✗ [261]\n",
"✗ [262]\n",
"✗ [263]\n",
"✗ [264]\n",
"✗ [265]\n",
"✗ [266]\n",
"✗ [267]\n",
"✗ [268]\n",
"✗ [269]\n",
"✗ [270]\n",
"✗ [271]\n",
"✗ [272]\n",
"✗ [273]\n",
"✗ [274]\n",
"✗ [275]\n",
"✗ [276]\n",
"✗ [277]\n",
"✗ [278]\n",
"✗ [279]\n",
"✗ [280]\n",
"✗ [281]\n",
"✗ [282]\n",
"✗ [283]\n",
"✗ [284]\n",
"✗ [285]\n",
"✗ [286]\n",
"✗ [287]\n",
"✗ [288]\n",
"✗ [289]\n",
"✗ [290]\n",
"✗ [291]\n",
"✗ [292]\n",
"✗ [293]\n",
"✗ [294]\n",
"✗ [295]\n",
"✗ [296]\n",
"✗ [297]\n",
"✗ [298]\n",
"✗ [299]\n",
"✗ [300]\n",
"✗ [301]\n",
"✗ [302]\n",
"✗ [303]\n",
"✗ [304]\n",
"✗ [305]\n",
"✗ [306]\n",
"✗ [307]\n",
"✗ [308]\n",
"✗ [309]\n",
"✗ [310]\n",
"✗ [311]\n",
"✗ [312]\n",
"✗ [313]\n",
"✗ [314]\n",
"✗ [315]\n",
"✗ [316]\n",
"✗ [317]\n",
"✗ [318]\n",
"✗ [319]\n",
"✗ [320]\n",
"✗ [321]\n",
"✗ [322]\n",
"✗ [323]\n",
"✗ [324]\n",
"✗ [325]\n",
"✗ [326]\n",
"✗ [327]\n",
"✗ [328]\n",
"✗ [329]\n",
"✗ [330]\n",
"✗ [331]\n",
"✗ [332]\n",
"✗ [333]\n",
"✗ [334]\n",
"✗ [335]\n",
"✗ [336]\n",
"✗ [337]\n",
"✗ [338]\n",
"✗ [339]\n",
"✗ [340]\n",
"✗ [341]\n",
"✗ [342]\n",
"✗ [343]\n",
"✗ [344]\n",
"✗ [345]\n",
"✗ [346]\n",
"✗ [347]\n",
"✗ [348]\n",
"✗ [349]\n",
"✗ [350]\n",
"✗ [351]\n",
"✗ [352]\n",
"✗ [353]\n",
"✗ [354]\n",
"✗ [355]\n",
"✗ [356]\n",
"✗ [357]\n",
"✗ [358]\n",
"✗ [359]\n",
"✗ [360]\n",
"✗ [361]\n",
"✗ [362]\n",
"✗ [363]\n",
"✗ [364]\n",
"✗ [365]\n",
"✗ [366]\n",
"✗ [367]\n",
"✗ [368]\n",
"✗ [369]\n",
"✗ [370]\n",
"✗ [371]\n",
"✗ [372]\n",
"✗ [373]\n",
"✗ [374]\n",
"✗ [375]\n",
"✗ [376]\n",
"✗ [377]\n",
"✗ [378]\n",
"✗ [379]\n",
"✗ [380]\n",
"✗ [381]\n",
"✗ [382]\n",
"✗ [383]\n",
"✗ [384]\n",
"✗ [385]\n",
"✗ [386]\n",
"✗ [387]\n",
"✗ [388]\n",
"✗ [389]\n",
"✗ [390]\n",
"✗ [391]\n",
"✗ [392]\n",
"✗ [393]\n",
"✗ [394]\n",
"✗ [395]\n",
"✗ [396]\n",
"✗ [397]\n",
"✗ [398]\n",
"✗ [399]\n",
"✗ [400]\n",
"✗ [401]\n",
"✗ [402]\n",
"✗ [403]\n",
"✗ [404]\n",
"✗ [405]\n",
"✗ [406]\n",
"✗ [407]\n",
"✗ [408]\n",
"✗ [409]\n",
"✗ [410]\n",
"✗ [411]\n",
"✗ [412]\n",
"✗ [413]\n",
"✗ [414]\n",
"✗ [415]\n",
"✗ [416]\n",
"✗ [417]\n",
"✗ [418]\n",
"✗ [419]\n",
"✗ [420]\n",
"✗ [421]\n",
"✗ [422]\n",
"✗ [423]\n",
"✗ [424]\n",
"✗ [425]\n",
"✗ [426]\n",
"✗ [427]\n",
"✗ [428]\n",
"✗ [429]\n",
"✗ [430]\n",
"✗ [431]\n",
"✗ [432]\n",
"✗ [433]\n",
"✗ [434]\n",
"✗ [435]\n",
"✗ [436]\n",
"✗ [437]\n",
"✗ [438]\n",
"✗ [439]\n",
"✗ [440]\n",
"✗ [441]\n",
"✗ [442]\n",
"✗ [443]\n",
"✗ [444]\n",
"✗ [445]\n",
"✗ [446]\n",
"✗ [447]\n",
"✗ [448]\n",
"✗ [449]\n",
"✗ [450]\n",
"✗ [451]\n",
"✗ [452]\n",
"✗ [453]\n",
"✗ [454]\n",
"✗ [455]\n",
"✗ [456]\n",
"✗ [457]\n",
"✗ [458]\n",
"✗ [459]\n",
"✗ [460]\n",
"✗ [461]\n",
"✗ [462]\n",
"✗ [463]\n",
"✗ [464]\n",
"✗ [465]\n",
"✗ [466]\n",
"✗ [467]\n",
"✗ [468]\n",
"✗ [469]\n",
"✗ [470]\n",
"✗ [471]\n",
"✗ [472]\n",
"✗ [473]\n",
"✗ [474]\n",
"✗ [475]\n",
"✗ [476]\n",
"✗ [477]\n",
"✗ [478]\n",
"✗ [479]\n",
"✗ [480]\n",
"✗ [481]\n",
"✗ [482]\n",
"✗ [483]\n",
"✗ [484]\n",
"✗ [485]\n",
"✗ [486]\n",
"✗ [487]\n",
"✗ [488]\n",
"✗ [489]\n",
"✗ [490]\n",
"✗ [491]\n",
"✗ [492]\n",
"✗ [493]\n",
"✗ [494]\n",
"✗ [495]\n",
"✗ [496]\n",
"✗ [497]\n",
"✗ [498]\n",
"✗ [499]\n",
"✓ [500]\n",
"✗ []\n",
"✗ [0]\n",
"✗ [1]\n",
"✗ [2]\n",
"✗ [3]\n",
"✗ [4]\n",
"✗ [5]\n",
"✗ [6]\n",
"✗ [7]\n",
"✗ [8]\n",
"✗ [9]\n",
"✗ [10]\n",
"✗ [11]\n",
"✗ [12]\n",
"✗ [13]\n",
"✗ [14]\n",
"✗ [15]\n",
"✗ [16]\n",
"✗ [17]\n",
"✗ [18]\n",
"✗ [19]\n",
"✗ [20]\n",
"✗ [21]\n",
"✗ [22]\n",
"✗ [23]\n",
"✗ [24]\n",
"✗ [25]\n",
"✗ [26]\n",
"✗ [27]\n",
"✗ [28]\n",
"✗ [29]\n",
"✗ [30]\n",
"✗ [31]\n",
"✗ [32]\n",
"✗ [33]\n",
"✗ [34]\n",
"✗ [35]\n",
"✗ [36]\n",
"✗ [37]\n",
"✗ [38]\n",
"✗ [39]\n",
"✗ [40]\n",
"✗ [41]\n",
"✗ [42]\n",
"✗ [43]\n",
"✗ [44]\n",
"✗ [45]\n",
"✗ [46]\n",
"✗ [47]\n",
"✗ [48]\n",
"✗ [49]\n",
"✗ [50]\n",
"✗ [51]\n",
"✗ [52]\n",
"✗ [53]\n",
"✗ [54]\n",
"✗ [55]\n",
"✗ [56]\n",
"✗ [57]\n",
"✗ [58]\n",
"✗ [59]\n",
"✗ [60]\n",
"✗ [61]\n",
"✗ [62]\n",
"✗ [63]\n",
"✗ [64]\n",
"✗ [65]\n",
"✗ [66]\n",
"✗ [67]\n",
"✗ [68]\n",
"✗ [69]\n",
"✗ [70]\n",
"✗ [71]\n",
"✗ [72]\n",
"✗ [73]\n",
"✗ [74]\n",
"✗ [75]\n",
"✗ [76]\n",
"✗ [77]\n",
"✗ [78]\n",
"✗ [79]\n",
"✗ [80]\n",
"✗ [81]\n",
"✗ [82]\n",
"✗ [83]\n",
"✗ [84]\n",
"✗ [85]\n",
"✗ [86]\n",
"✗ [87]\n",
"✗ [88]\n",
"✗ [89]\n",
"✗ [90]\n",
"✗ [91]\n",
"✗ [92]\n",
"✗ [93]\n",
"✗ [94]\n",
"✗ [95]\n",
"✗ [96]\n",
"✗ [97]\n",
"✗ [98]\n",
"✗ [99]\n",
"✗ [100]\n",
"✗ [101]\n",
"✗ [102]\n",
"✗ [103]\n",
"✗ [104]\n",
"✗ [105]\n",
"✗ [106]\n",
"✗ [107]\n",
"✗ [108]\n",
"✗ [109]\n",
"✗ [110]\n",
"✗ [111]\n",
"✗ [112]\n",
"✗ [113]\n",
"✗ [114]\n",
"✗ [115]\n",
"✗ [116]\n",
"✗ [117]\n",
"✗ [118]\n",
"✗ [119]\n",
"✗ [120]\n",
"✗ [121]\n",
"✗ [122]\n",
"✗ [123]\n",
"✗ [124]\n",
"✗ [125]\n",
"✗ [126]\n",
"✗ [127]\n",
"✗ [128]\n",
"✗ [129]\n",
"✗ [130]\n",
"✗ [131]\n",
"✗ [132]\n",
"✗ [133]\n",
"✗ [134]\n",
"✗ [135]\n",
"✗ [136]\n",
"✗ [137]\n",
"✗ [138]\n",
"✗ [139]\n",
"✗ [140]\n",
"✗ [141]\n",
"✗ [142]\n",
"✗ [143]\n",
"✗ [144]\n",
"✗ [145]\n",
"✗ [146]\n",
"✗ [147]\n",
"✗ [148]\n",
"✗ [149]\n",
"✗ [150]\n",
"✗ [151]\n",
"✗ [152]\n",
"✗ [153]\n",
"✗ [154]\n",
"✗ [155]\n",
"✗ [156]\n",
"✗ [157]\n",
"✗ [158]\n",
"✗ [159]\n",
"✗ [160]\n",
"✗ [161]\n",
"✗ [162]\n",
"✗ [163]\n",
"✗ [164]\n",
"✗ [165]\n",
"✗ [166]\n",
"✗ [167]\n",
"✗ [168]\n",
"✗ [169]\n",
"✗ [170]\n",
"✗ [171]\n",
"✗ [172]\n",
"✗ [173]\n",
"✗ [174]\n",
"✗ [175]\n",
"✗ [176]\n",
"✗ [177]\n",
"✗ [178]\n",
"✗ [179]\n",
"✗ [180]\n",
"✗ [181]\n",
"✗ [182]\n",
"✗ [183]\n",
"✗ [184]\n",
"✗ [185]\n",
"✗ [186]\n",
"✗ [187]\n",
"✗ [188]\n",
"✗ [189]\n",
"✗ [190]\n",
"✗ [191]\n",
"✗ [192]\n",
"✗ [193]\n",
"✗ [194]\n",
"✗ [195]\n",
"✗ [196]\n",
"✗ [197]\n",
"✗ [198]\n",
"✗ [199]\n",
"✗ [200]\n",
"✗ [201]\n",
"✗ [202]\n",
"✗ [203]\n",
"✗ [204]\n",
"✗ [205]\n",
"✗ [206]\n",
"✗ [207]\n",
"✗ [208]\n",
"✗ [209]\n",
"✗ [210]\n",
"✗ [211]\n",
"✗ [212]\n",
"✗ [213]\n",
"✗ [214]\n",
"✗ [215]\n",
"✗ [216]\n",
"✗ [217]\n",
"✗ [218]\n",
"✗ [219]\n",
"✗ [220]\n",
"✗ [221]\n",
"✗ [222]\n",
"✗ [223]\n",
"✗ [224]\n",
"✗ [225]\n",
"✗ [226]\n",
"✗ [227]\n",
"✗ [228]\n",
"✗ [229]\n",
"✗ [230]\n",
"✗ [231]\n",
"✗ [232]\n",
"✗ [233]\n",
"✗ [234]\n",
"✗ [235]\n",
"✗ [236]\n",
"✗ [237]\n",
"✗ [238]\n",
"✗ [239]\n",
"✗ [240]\n",
"✗ [241]\n",
"✗ [242]\n",
"✗ [243]\n",
"✗ [244]\n",
"✗ [245]\n",
"✗ [246]\n",
"✗ [247]\n",
"✗ [248]\n",
"✗ [249]\n",
"✗ [250]\n",
"✗ [251]\n",
"✗ [252]\n",
"✗ [253]\n",
"✗ [254]\n",
"✗ [255]\n",
"✗ [256]\n",
"✗ [257]\n",
"✗ [258]\n",
"✗ [259]\n",
"✗ [260]\n",
"✗ [261]\n",
"✗ [262]\n",
"✗ [263]\n",
"✗ [264]\n",
"✗ [265]\n",
"✗ [266]\n",
"✗ [267]\n",
"✗ [268]\n",
"✗ [269]\n",
"✗ [270]\n",
"✗ [271]\n",
"✗ [272]\n",
"✗ [273]\n",
"✗ [274]\n",
"✗ [275]\n",
"✗ [276]\n",
"✗ [277]\n",
"✗ [278]\n",
"✗ [279]\n",
"✗ [280]\n",
"✗ [281]\n",
"✗ [282]\n",
"✗ [283]\n",
"✗ [284]\n",
"✗ [285]\n",
"✗ [286]\n",
"✗ [287]\n",
"✗ [288]\n",
"✗ [289]\n",
"✗ [290]\n",
"✗ [291]\n",
"✗ [292]\n",
"✗ [293]\n",
"✗ [294]\n",
"✗ [295]\n",
"✗ [296]\n",
"✗ [297]\n",
"✗ [298]\n",
"✗ [299]\n",
"✗ [300]\n",
"✗ [301]\n",
"✗ [302]\n",
"✗ [303]\n",
"✗ [304]\n",
"✗ [305]\n",
"✗ [306]\n",
"✗ [307]\n",
"✗ [308]\n",
"✗ [309]\n",
"✗ [310]\n",
"✗ [311]\n",
"✗ [312]\n",
"✗ [313]\n",
"✗ [314]\n",
"✗ [315]\n",
"✗ [316]\n",
"✗ [317]\n",
"✗ [318]\n",
"✗ [319]\n",
"✗ [320]\n",
"✗ [321]\n",
"✗ [322]\n",
"✗ [323]\n",
"✗ [324]\n",
"✗ [325]\n",
"✗ [326]\n",
"✗ [327]\n",
"✗ [328]\n",
"✗ [329]\n",
"✗ [330]\n",
"✗ [331]\n",
"✗ [332]\n",
"✗ [333]\n",
"✗ [334]\n",
"✗ [335]\n",
"✗ [336]\n",
"✗ [337]\n",
"✗ [338]\n",
"✗ [339]\n",
"✗ [340]\n",
"✗ [341]\n",
"✗ [342]\n",
"✗ [343]\n",
"✗ [344]\n",
"✗ [345]\n",
"✗ [346]\n",
"✗ [347]\n",
"✗ [348]\n",
"✗ [349]\n",
"✗ [350]\n",
"✗ [351]\n",
"✗ [352]\n",
"✗ [353]\n",
"✗ [354]\n",
"✗ [355]\n",
"✗ [356]\n",
"✗ [357]\n",
"✗ [358]\n",
"✗ [359]\n",
"✗ [360]\n",
"✗ [361]\n",
"✗ [362]\n",
"✗ [363]\n",
"✗ [364]\n",
"✗ [365]\n",
"✗ [366]\n",
"✗ [367]\n",
"✗ [368]\n",
"✗ [369]\n",
"✗ [370]\n",
"✗ [371]\n",
"✗ [372]\n",
"✗ [373]\n",
"✗ [374]\n",
"✗ [375]\n",
"✗ [376]\n",
"✗ [377]\n",
"✗ [378]\n",
"✗ [379]\n",
"✗ [380]\n",
"✗ [381]\n",
"✗ [382]\n",
"✗ [383]\n",
"✗ [384]\n",
"✗ [385]\n",
"✗ [386]\n",
"✗ [387]\n",
"✗ [388]\n",
"✗ [389]\n",
"✗ [390]\n",
"✗ [391]\n",
"✗ [392]\n",
"✗ [393]\n",
"✗ [394]\n",
"✗ [395]\n",
"✗ [396]\n",
"✗ [397]\n",
"✗ [398]\n",
"✗ [399]\n",
"✗ [400]\n",
"✗ [401]\n",
"✗ [402]\n",
"✗ [403]\n",
"✗ [404]\n",
"✗ [405]\n",
"✗ [406]\n",
"✗ [407]\n",
"✗ [408]\n",
"✗ [409]\n",
"✗ [410]\n",
"✗ [411]\n",
"✗ [412]\n",
"✗ [413]\n",
"✗ [414]\n",
"✗ [415]\n",
"✗ [416]\n",
"✗ [417]\n",
"✗ [418]\n",
"✗ [419]\n",
"✗ [420]\n",
"✗ [421]\n",
"✗ [422]\n",
"✗ [423]\n",
"✗ [424]\n",
"✗ [425]\n",
"✗ [426]\n",
"✗ [427]\n",
"✗ [428]\n",
"✗ [429]\n",
"✗ [430]\n",
"✗ [431]\n",
"✗ [432]\n",
"✗ [433]\n",
"✗ [434]\n",
"✗ [435]\n",
"✗ [436]\n",
"✗ [437]\n",
"✗ [438]\n",
"✗ [439]\n",
"✗ [440]\n",
"✗ [441]\n",
"✗ [442]\n",
"✗ [443]\n",
"✗ [444]\n",
"✗ [445]\n",
"✗ [446]\n",
"✗ [447]\n",
"✗ [448]\n",
"✗ [449]\n",
"✗ [450]\n",
"✗ [451]\n",
"✗ [452]\n",
"✗ [453]\n",
"✗ [454]\n",
"✗ [455]\n",
"✗ [456]\n",
"✗ [457]\n",
"✗ [458]\n",
"✗ [459]\n",
"✗ [460]\n",
"✗ [461]\n",
"✗ [462]\n",
"✗ [463]\n",
"✗ [464]\n",
"✗ [465]\n",
"✗ [466]\n",
"✗ [467]\n",
"✗ [468]\n",
"✗ [469]\n",
"✗ [470]\n",
"✗ [471]\n",
"✗ [472]\n",
"✗ [473]\n",
"✗ [474]\n",
"✗ [475]\n",
"✗ [476]\n",
"✗ [477]\n",
"✗ [478]\n",
"✗ [479]\n",
"✗ [480]\n",
"✗ [481]\n",
"✗ [482]\n",
"✗ [483]\n",
"✗ [484]\n",
"✗ [485]\n",
"✗ [486]\n",
"✗ [487]\n",
"✗ [488]\n",
"✗ [489]\n",
"✗ [490]\n",
"✗ [491]\n",
"✗ [492]\n",
"✗ [493]\n",
"✗ [494]\n",
"✗ [495]\n",
"✗ [496]\n",
"✗ [497]\n",
"✗ [498]\n",
"✗ [499]\n",
"\n",
"1 shrinks with 1003 function calls\n"
]
}
],
"source": [
"show_trace([1000], lambda x: sum(x) >= 500,\n",
" partial(greedy_shrink, shrink=shrink2))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Because we're trying every intermediate value, what we have amounts to a linear probe up to the smallest value that will work. If that smallest value is large, this will take a long time. Our shrinking is still O(n), but n is now the size of the smallest value that will work rather than the starting value. This is still pretty suboptimal.\n",
"\n",
"What we want to do is try to replace our linear probe with a binary search. What we'll get isn't exactly a binary search, but it's close enough."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def shrink_integer(n):\n",
" \"\"\"\n",
" Shrinker for individual integers.\n",
"\n",
" What happens is that we start from the left, first probing upwards in powers of two.\n",
"\n",
" When this would take us past our target value we then binary chop towards it.\n",
" \"\"\"\n",
" if not n:\n",
" return\n",
" for k in range(64):\n",
" probe = 2 ** k\n",
" if probe >= n:\n",
" break\n",
" yield probe - 1\n",
" probe //= 2\n",
" while True:\n",
" probe = (probe + n) // 2\n",
" yield probe\n",
" if probe == n - 1:\n",
" break\n",
"\n",
"\n",
"def shrink3(ls):\n",
" for i in range(len(ls)):\n",
" s = list(ls)\n",
" del s[i]\n",
" yield list(s)\n",
" for x in shrink_integer(ls[i]):\n",
" s = list(ls)\n",
" s[i] = x\n",
" yield s"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[0, 1, 3, 7, 15, 31, 63, 127, 255, 378, 439, 469, 484, 492, 496, 498, 499]"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"list(shrink_integer(500))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This gives us a reasonable distribution of O(log(n)) values in the middle while still making sure we start with 0 and finish with n - 1.\n",
"\n",
"In Hypothesis's actual implementation we also try random values in the probe region in case there's something special about things near powers of two, but we won't worry about that here."
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"✓ [1000]\n",
"✗ []\n",
"✗ [0]\n",
"✗ [1]\n",
"✗ [3]\n",
"✗ [7]\n",
"✗ [15]\n",
"✗ [31]\n",
"✗ [63]\n",
"✗ [127]\n",
"✗ [255]\n",
"✓ [511]\n",
"✗ []\n",
"✗ [0]\n",
"✗ [1]\n",
"✗ [3]\n",
"✗ [7]\n",
"✗ [15]\n",
"✗ [31]\n",
"✗ [63]\n",
"✗ [127]\n",
"✗ [255]\n",
"✗ [383]\n",
"✗ [447]\n",
"✗ [479]\n",
"✗ [495]\n",
"✓ [503]\n",
"✗ []\n",
"✗ [0]\n",
"✗ [1]\n",
"✗ [3]\n",
"✗ [7]\n",
"✗ [15]\n",
"✗ [31]\n",
"✗ [63]\n",
"✗ [127]\n",
"✗ [255]\n",
"✗ [379]\n",
"✗ [441]\n",
"✗ [472]\n",
"✗ [487]\n",
"✗ [495]\n",
"✗ [499]\n",
"✓ [501]\n",
"✗ []\n",
"✗ [0]\n",
"✗ [1]\n",
"✗ [3]\n",
"✗ [7]\n",
"✗ [15]\n",
"✗ [31]\n",
"✗ [63]\n",
"✗ [127]\n",
"✗ [255]\n",
"✗ [378]\n",
"✗ [439]\n",
"✗ [470]\n",
"✗ [485]\n",
"✗ [493]\n",
"✗ [497]\n",
"✗ [499]\n",
"✓ [500]\n",
"✗ []\n",
"✗ [0]\n",
"✗ [1]\n",
"✗ [3]\n",
"✗ [7]\n",
"✗ [15]\n",
"✗ [31]\n",
"✗ [63]\n",
"✗ [127]\n",
"✗ [255]\n",
"✗ [378]\n",
"✗ [439]\n",
"✗ [469]\n",
"✗ [484]\n",
"✗ [492]\n",
"✗ [496]\n",
"✗ [498]\n",
"✗ [499]\n",
"\n",
"4 shrinks with 79 function calls\n"
]
}
],
"source": [
"show_trace([1000], lambda x: sum(x) >= 500, partial(\n",
" greedy_shrink, shrink=shrink3))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This now runs in a much more reasonable number of function calls.\n",
"\n",
"Now we want to look at how to reduce the number of elements in the list more efficiently. We're currently making the same mistake we did with n umbers. Only reducing one at a time."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✓ [2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✓ [2, 2, 2, 2, 2, 2, 2, 2]\n",
"✓ [2, 2, 2, 2, 2, 2, 2]\n",
"✓ [2, 2, 2, 2, 2, 2]\n",
"✓ [2, 2, 2, 2, 2]\n",
"✓ [2, 2, 2, 2]\n",
"✓ [2, 2, 2]\n",
"✓ [2, 2]\n",
"✗ [2]\n",
"✗ [0, 2]\n",
"✓ [1, 2]\n",
"✗ [2]\n",
"✗ [0, 2]\n",
"✗ [1]\n",
"✗ [1, 0]\n",
"✗ [1, 1]\n",
"\n",
"19 shrinks with 26 function calls\n"
]
}
],
"source": [
"show_trace([2] * 20, lambda x: sum(x) >= 3, partial(\n",
" greedy_shrink, shrink=shrink3))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We won't try too hard here, because typically our lists are not *that* long. We will just attempt to start by finding a shortish initial prefix that demonstrates the behaviour:"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def shrink_to_prefix(ls):\n",
" i = 1\n",
" while i < len(ls):\n",
" yield ls[:i]\n",
" i *= 2\n",
"\n",
"\n",
"def delete_individual_elements(ls):\n",
" for i in range(len(ls)):\n",
" s = list(ls)\n",
" del s[i]\n",
" yield list(s)\n",
"\n",
"\n",
"def shrink_individual_elements(ls):\n",
" for i in range(len(ls)):\n",
" for x in shrink_integer(ls[i]):\n",
" s = list(ls)\n",
" s[i] = x\n",
" yield s\n",
"\n",
"def shrink4(ls):\n",
" yield from shrink_to_prefix(ls)\n",
" yield from delete_individual_elements(ls)\n",
" yield from shrink_individual_elements(ls)"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✗ [2]\n",
"✓ [2, 2]\n",
"✗ [2]\n",
"✗ [2]\n",
"✗ [2]\n",
"✗ [0, 2]\n",
"✓ [1, 2]\n",
"✗ [1]\n",
"✗ [2]\n",
"✗ [1]\n",
"✗ [0, 2]\n",
"✗ [1, 0]\n",
"✗ [1, 1]\n",
"\n",
"2 shrinks with 13 function calls\n"
]
}
],
"source": [
"show_trace([2] * 20, lambda x: sum(x) >= 3, partial(\n",
" greedy_shrink, shrink=shrink4))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The problem we now want to address is the fact that when we're shrinking elements we're only shrinking them one at a time. This means that even though we're only O(log(k)) in each element, we're O(log(k)^n) in the whole list where n is the length of the list. For even very modest k this is bad.\n",
"\n",
"In general we may not be able to fix this, but in practice for a lot of common structures we can exploit similarity to try to do simultaneous shrinking.\n",
"\n",
"Here is our starting example: We start and finish with all identical values. We would like to be able to shortcut through a lot of the uninteresting intermediate examples somehow."
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"✓ [20, 20, 20, 20, 20, 20, 20]\n",
"✗ [20]\n",
"✗ [20, 20]\n",
"✗ [20, 20, 20, 20]\n",
"✓ [20, 20, 20, 20, 20, 20]\n",
"✗ [20]\n",
"✗ [20, 20]\n",
"✗ [20, 20, 20, 20]\n",
"✓ [20, 20, 20, 20, 20]\n",
"✗ [20]\n",
"✗ [20, 20]\n",
"✗ [20, 20, 20, 20]\n",
"✗ [20, 20, 20, 20]\n",
"✗ [20, 20, 20, 20]\n",
"✗ [20, 20, 20, 20]\n",
"✗ [20, 20, 20, 20]\n",
"✗ [20, 20, 20, 20]\n",
"✗ [0, 20, 20, 20, 20]\n",
"✗ [1, 20, 20, 20, 20]\n",
"✗ [3, 20, 20, 20, 20]\n",
"✓ [7, 20, 20, 20, 20]\n",
"✗ [7]\n",
"✗ [7, 20]\n",
"✗ [7, 20, 20, 20]\n",
"✗ [20, 20, 20, 20]\n",
"✗ [7, 20, 20, 20]\n",
"✗ [7, 20, 20, 20]\n",
"✗ [7, 20, 20, 20]\n",
"✗ [7, 20, 20, 20]\n",
"✗ [0, 20, 20, 20, 20]\n",
"✗ [1, 20, 20, 20, 20]\n",
"✗ [3, 20, 20, 20, 20]\n",
"✓ [5, 20, 20, 20, 20]\n",
"✗ [5]\n",
"✗ [5, 20]\n",
"✗ [5, 20, 20, 20]\n",
"✗ [20, 20, 20, 20]\n",
"✗ [5, 20, 20, 20]\n",
"✗ [5, 20, 20, 20]\n",
"✗ [5, 20, 20, 20]\n",
"✗ [5, 20, 20, 20]\n",
"✗ [0, 20, 20, 20, 20]\n",
"✗ [1, 20, 20, 20, 20]\n",
"✗ [3, 20, 20, 20, 20]\n",
"✗ [4, 20, 20, 20, 20]\n",
"✗ [5, 0, 20, 20, 20]\n",
"✗ [5, 1, 20, 20, 20]\n",
"✗ [5, 3, 20, 20, 20]\n",
"✓ [5, 7, 20, 20, 20]\n",
"✗ [5]\n",
"✗ [5, 7]\n",
"✗ [5, 7, 20, 20]\n",
"✗ [7, 20, 20, 20]\n",
"✗ [5, 20, 20, 20]\n",
"✗ [5, 7, 20, 20]\n",
"✗ [5, 7, 20, 20]\n",
"✗ [5, 7, 20, 20]\n",
"✗ [0, 7, 20, 20, 20]\n",
"✗ [1, 7, 20, 20, 20]\n",
"✗ [3, 7, 20, 20, 20]\n",
"✗ [4, 7, 20, 20, 20]\n",
"✗ [5, 0, 20, 20, 20]\n",
"✗ [5, 1, 20, 20, 20]\n",
"✗ [5, 3, 20, 20, 20]\n",
"✓ [5, 5, 20, 20, 20]\n",
"✗ [5]\n",
"✗ [5, 5]\n",
"✗ [5, 5, 20, 20]\n",
"✗ [5, 20, 20, 20]\n",
"✗ [5, 20, 20, 20]\n",
"✗ [5, 5, 20, 20]\n",
"✗ [5, 5, 20, 20]\n",
"✗ [5, 5, 20, 20]\n",
"✗ [0, 5, 20, 20, 20]\n",
"✗ [1, 5, 20, 20, 20]\n",
"✗ [3, 5, 20, 20, 20]\n",
"✗ [4, 5, 20, 20, 20]\n",
"✗ [5, 0, 20, 20, 20]\n",
"✗ [5, 1, 20, 20, 20]\n",
"✗ [5, 3, 20, 20, 20]\n",
"✗ [5, 4, 20, 20, 20]\n",
"✗ [5, 5, 0, 20, 20]\n",
"✗ [5, 5, 1, 20, 20]\n",
"✗ [5, 5, 3, 20, 20]\n",
"✓ [5, 5, 7, 20, 20]\n",
"✗ [5]\n",
"✗ [5, 5]\n",
"✗ [5, 5, 7, 20]\n",
"✗ [5, 7, 20, 20]\n",
"✗ [5, 7, 20, 20]\n",
"✗ [5, 5, 20, 20]\n",
"✗ [5, 5, 7, 20]\n",
"✗ [5, 5, 7, 20]\n",
"✗ [0, 5, 7, 20, 20]\n",
"✗ [1, 5, 7, 20, 20]\n",
"✗ [3, 5, 7, 20, 20]\n",
"✗ [4, 5, 7, 20, 20]\n",
"✗ [5, 0, 7, 20, 20]\n",
"✗ [5, 1, 7, 20, 20]\n",
"✗ [5, 3, 7, 20, 20]\n",
"✗ [5, 4, 7, 20, 20]\n",
"✗ [5, 5, 0, 20, 20]\n",
"✗ [5, 5, 1, 20, 20]\n",
"✗ [5, 5, 3, 20, 20]\n",
"✓ [5, 5, 5, 20, 20]\n",
"✗ [5]\n",
"✗ [5, 5]\n",
"✗ [5, 5, 5, 20]\n",
"✗ [5, 5, 20, 20]\n",
"✗ [5, 5, 20, 20]\n",
"✗ [5, 5, 20, 20]\n",
"✗ [5, 5, 5, 20]\n",
"✗ [5, 5, 5, 20]\n",
"✗ [0, 5, 5, 20, 20]\n",
"✗ [1, 5, 5, 20, 20]\n",
"✗ [3, 5, 5, 20, 20]\n",
"✗ [4, 5, 5, 20, 20]\n",
"✗ [5, 0, 5, 20, 20]\n",
"✗ [5, 1, 5, 20, 20]\n",
"✗ [5, 3, 5, 20, 20]\n",
"✗ [5, 4, 5, 20, 20]\n",
"✗ [5, 5, 0, 20, 20]\n",
"✗ [5, 5, 1, 20, 20]\n",
"✗ [5, 5, 3, 20, 20]\n",
"✗ [5, 5, 4, 20, 20]\n",
"✗ [5, 5, 5, 0, 20]\n",
"✗ [5, 5, 5, 1, 20]\n",
"✗ [5, 5, 5, 3, 20]\n",
"✓ [5, 5, 5, 7, 20]\n",
"✗ [5]\n",
"✗ [5, 5]\n",
"✗ [5, 5, 5, 7]\n",
"✗ [5, 5, 7, 20]\n",
"✗ [5, 5, 7, 20]\n",
"✗ [5, 5, 7, 20]\n",
"✗ [5, 5, 5, 20]\n",
"✗ [5, 5, 5, 7]\n",
"✗ [0, 5, 5, 7, 20]\n",
"✗ [1, 5, 5, 7, 20]\n",
"✗ [3, 5, 5, 7, 20]\n",
"✗ [4, 5, 5, 7, 20]\n",
"✗ [5, 0, 5, 7, 20]\n",
"✗ [5, 1, 5, 7, 20]\n",
"✗ [5, 3, 5, 7, 20]\n",
"✗ [5, 4, 5, 7, 20]\n",
"✗ [5, 5, 0, 7, 20]\n",
"✗ [5, 5, 1, 7, 20]\n",
"✗ [5, 5, 3, 7, 20]\n",
"✗ [5, 5, 4, 7, 20]\n",
"✗ [5, 5, 5, 0, 20]\n",
"✗ [5, 5, 5, 1, 20]\n",
"✗ [5, 5, 5, 3, 20]\n",
"✓ [5, 5, 5, 5, 20]\n",
"✗ [5]\n",
"✗ [5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 20]\n",
"✗ [5, 5, 5, 20]\n",
"✗ [5, 5, 5, 20]\n",
"✗ [5, 5, 5, 20]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [0, 5, 5, 5, 20]\n",
"✗ [1, 5, 5, 5, 20]\n",
"✗ [3, 5, 5, 5, 20]\n",
"✗ [4, 5, 5, 5, 20]\n",
"✗ [5, 0, 5, 5, 20]\n",
"✗ [5, 1, 5, 5, 20]\n",
"✗ [5, 3, 5, 5, 20]\n",
"✗ [5, 4, 5, 5, 20]\n",
"✗ [5, 5, 0, 5, 20]\n",
"✗ [5, 5, 1, 5, 20]\n",
"✗ [5, 5, 3, 5, 20]\n",
"✗ [5, 5, 4, 5, 20]\n",
"✗ [5, 5, 5, 0, 20]\n",
"✗ [5, 5, 5, 1, 20]\n",
"✗ [5, 5, 5, 3, 20]\n",
"✗ [5, 5, 5, 4, 20]\n",
"✗ [5, 5, 5, 5, 0]\n",
"✗ [5, 5, 5, 5, 1]\n",
"✗ [5, 5, 5, 5, 3]\n",
"✓ [5, 5, 5, 5, 7]\n",
"✗ [5]\n",
"✗ [5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 7]\n",
"✗ [5, 5, 5, 7]\n",
"✗ [5, 5, 5, 7]\n",
"✗ [5, 5, 5, 7]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [0, 5, 5, 5, 7]\n",
"✗ [1, 5, 5, 5, 7]\n",
"✗ [3, 5, 5, 5, 7]\n",
"✗ [4, 5, 5, 5, 7]\n",
"✗ [5, 0, 5, 5, 7]\n",
"✗ [5, 1, 5, 5, 7]\n",
"✗ [5, 3, 5, 5, 7]\n",
"✗ [5, 4, 5, 5, 7]\n",
"✗ [5, 5, 0, 5, 7]\n",
"✗ [5, 5, 1, 5, 7]\n",
"✗ [5, 5, 3, 5, 7]\n",
"✗ [5, 5, 4, 5, 7]\n",
"✗ [5, 5, 5, 0, 7]\n",
"✗ [5, 5, 5, 1, 7]\n",
"✗ [5, 5, 5, 3, 7]\n",
"✗ [5, 5, 5, 4, 7]\n",
"✗ [5, 5, 5, 5, 0]\n",
"✗ [5, 5, 5, 5, 1]\n",
"✗ [5, 5, 5, 5, 3]\n",
"✓ [5, 5, 5, 5, 5]\n",
"✗ [5]\n",
"✗ [5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [0, 5, 5, 5, 5]\n",
"✗ [1, 5, 5, 5, 5]\n",
"✗ [3, 5, 5, 5, 5]\n",
"✗ [4, 5, 5, 5, 5]\n",
"✗ [5, 0, 5, 5, 5]\n",
"✗ [5, 1, 5, 5, 5]\n",
"✗ [5, 3, 5, 5, 5]\n",
"✗ [5, 4, 5, 5, 5]\n",
"✗ [5, 5, 0, 5, 5]\n",
"✗ [5, 5, 1, 5, 5]\n",
"✗ [5, 5, 3, 5, 5]\n",
"✗ [5, 5, 4, 5, 5]\n",
"✗ [5, 5, 5, 0, 5]\n",
"✗ [5, 5, 5, 1, 5]\n",
"✗ [5, 5, 5, 3, 5]\n",
"✗ [5, 5, 5, 4, 5]\n",
"✗ [5, 5, 5, 5, 0]\n",
"✗ [5, 5, 5, 5, 1]\n",
"✗ [5, 5, 5, 5, 3]\n",
"✗ [5, 5, 5, 5, 4]\n",
"\n",
"12 shrinks with 236 function calls\n"
]
}
],
"source": [
"show_trace([20] * 7,\n",
" lambda x: len([t for t in x if t >= 5]) >= 5,\n",
" partial(greedy_shrink, shrink=shrink4))"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def shrink_shared(ls):\n",
" \"\"\"\n",
" Look for all sets of shared indices and try to perform a simultaneous shrink on\n",
" their value, replacing all of them at once.\n",
"\n",
" In actual Hypothesis we also try replacing only subsets of the values when there\n",
" are more than two shared values, but we won't worry about that here.\n",
" \"\"\"\n",
" shared_indices = {}\n",
" for i in range(len(ls)):\n",
" shared_indices.setdefault(ls[i], []).append(i)\n",
" for sharing in shared_indices.values():\n",
" if len(sharing) > 1:\n",
" for v in shrink_integer(ls[sharing[0]]):\n",
" s = list(ls)\n",
" for i in sharing:\n",
" s[i] = v\n",
" yield s\n",
"\n",
"\n",
"def shrink5(ls):\n",
" yield from shrink_to_prefix(ls)\n",
" yield from delete_individual_elements(ls)\n",
" yield from shrink_shared(ls)\n",
" yield from shrink_individual_elements(ls)"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"✓ [20, 20, 20, 20, 20, 20, 20]\n",
"✗ [20]\n",
"✗ [20, 20]\n",
"✗ [20, 20, 20, 20]\n",
"✓ [20, 20, 20, 20, 20, 20]\n",
"✗ [20]\n",
"✗ [20, 20]\n",
"✗ [20, 20, 20, 20]\n",
"✓ [20, 20, 20, 20, 20]\n",
"✗ [20]\n",
"✗ [20, 20]\n",
"✗ [20, 20, 20, 20]\n",
"✗ [20, 20, 20, 20]\n",
"✗ [20, 20, 20, 20]\n",
"✗ [20, 20, 20, 20]\n",
"✗ [20, 20, 20, 20]\n",
"✗ [20, 20, 20, 20]\n",
"✗ [0, 0, 0, 0, 0]\n",
"✗ [1, 1, 1, 1, 1]\n",
"✗ [3, 3, 3, 3, 3]\n",
"✓ [7, 7, 7, 7, 7]\n",
"✗ [7]\n",
"✗ [7, 7]\n",
"✗ [7, 7, 7, 7]\n",
"✗ [7, 7, 7, 7]\n",
"✗ [7, 7, 7, 7]\n",
"✗ [7, 7, 7, 7]\n",
"✗ [7, 7, 7, 7]\n",
"✗ [7, 7, 7, 7]\n",
"✗ [0, 0, 0, 0, 0]\n",
"✗ [1, 1, 1, 1, 1]\n",
"✗ [3, 3, 3, 3, 3]\n",
"✓ [5, 5, 5, 5, 5]\n",
"✗ [5]\n",
"✗ [5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [0, 0, 0, 0, 0]\n",
"✗ [1, 1, 1, 1, 1]\n",
"✗ [3, 3, 3, 3, 3]\n",
"✗ [4, 4, 4, 4, 4]\n",
"✗ [0, 5, 5, 5, 5]\n",
"✗ [1, 5, 5, 5, 5]\n",
"✗ [3, 5, 5, 5, 5]\n",
"✗ [4, 5, 5, 5, 5]\n",
"✗ [5, 0, 5, 5, 5]\n",
"✗ [5, 1, 5, 5, 5]\n",
"✗ [5, 3, 5, 5, 5]\n",
"✗ [5, 4, 5, 5, 5]\n",
"✗ [5, 5, 0, 5, 5]\n",
"✗ [5, 5, 1, 5, 5]\n",
"✗ [5, 5, 3, 5, 5]\n",
"✗ [5, 5, 4, 5, 5]\n",
"✗ [5, 5, 5, 0, 5]\n",
"✗ [5, 5, 5, 1, 5]\n",
"✗ [5, 5, 5, 3, 5]\n",
"✗ [5, 5, 5, 4, 5]\n",
"✗ [5, 5, 5, 5, 0]\n",
"✗ [5, 5, 5, 5, 1]\n",
"✗ [5, 5, 5, 5, 3]\n",
"✗ [5, 5, 5, 5, 4]\n",
"\n",
"4 shrinks with 64 function calls\n"
]
}
],
"source": [
"show_trace([20] * 7,\n",
" lambda x: len([t for t in x if t >= 5]) >= 5,\n",
" partial(greedy_shrink, shrink=shrink5))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This achieves the desired result. We rapidly progress through all of the intermediate stages. We do still have to perform individual shrinks at the end unfortunately (this is unavoidable), but the size of the elements is much smaller now so it takes less time.\n",
"\n",
"Unfortunately while this solves the problem in this case it's almost useless, because unless you find yourself in the exact right starting position it never does anything."
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"✓ [20, 21, 22, 23, 24, 25, 26]\n",
"✗ [20]\n",
"✗ [20, 21]\n",
"✗ [20, 21, 22, 23]\n",
"✓ [21, 22, 23, 24, 25, 26]\n",
"✗ [21]\n",
"✗ [21, 22]\n",
"✗ [21, 22, 23, 24]\n",
"✓ [22, 23, 24, 25, 26]\n",
"✗ [22]\n",
"✗ [22, 23]\n",
"✗ [22, 23, 24, 25]\n",
"✗ [23, 24, 25, 26]\n",
"✗ [22, 24, 25, 26]\n",
"✗ [22, 23, 25, 26]\n",
"✗ [22, 23, 24, 26]\n",
"✗ [22, 23, 24, 25]\n",
"✗ [0, 23, 24, 25, 26]\n",
"✗ [1, 23, 24, 25, 26]\n",
"✗ [3, 23, 24, 25, 26]\n",
"✓ [7, 23, 24, 25, 26]\n",
"✗ [7]\n",
"✗ [7, 23]\n",
"✗ [7, 23, 24, 25]\n",
"✗ [23, 24, 25, 26]\n",
"✗ [7, 24, 25, 26]\n",
"✗ [7, 23, 25, 26]\n",
"✗ [7, 23, 24, 26]\n",
"✗ [7, 23, 24, 25]\n",
"✗ [0, 23, 24, 25, 26]\n",
"✗ [1, 23, 24, 25, 26]\n",
"✗ [3, 23, 24, 25, 26]\n",
"✓ [5, 23, 24, 25, 26]\n",
"✗ [5]\n",
"✗ [5, 23]\n",
"✗ [5, 23, 24, 25]\n",
"✗ [23, 24, 25, 26]\n",
"✗ [5, 24, 25, 26]\n",
"✗ [5, 23, 25, 26]\n",
"✗ [5, 23, 24, 26]\n",
"✗ [5, 23, 24, 25]\n",
"✗ [0, 23, 24, 25, 26]\n",
"✗ [1, 23, 24, 25, 26]\n",
"✗ [3, 23, 24, 25, 26]\n",
"✗ [4, 23, 24, 25, 26]\n",
"✗ [5, 0, 24, 25, 26]\n",
"✗ [5, 1, 24, 25, 26]\n",
"✗ [5, 3, 24, 25, 26]\n",
"✓ [5, 7, 24, 25, 26]\n",
"✗ [5]\n",
"✗ [5, 7]\n",
"✗ [5, 7, 24, 25]\n",
"✗ [7, 24, 25, 26]\n",
"✗ [5, 24, 25, 26]\n",
"✗ [5, 7, 25, 26]\n",
"✗ [5, 7, 24, 26]\n",
"✗ [5, 7, 24, 25]\n",
"✗ [0, 7, 24, 25, 26]\n",
"✗ [1, 7, 24, 25, 26]\n",
"✗ [3, 7, 24, 25, 26]\n",
"✗ [4, 7, 24, 25, 26]\n",
"✗ [5, 0, 24, 25, 26]\n",
"✗ [5, 1, 24, 25, 26]\n",
"✗ [5, 3, 24, 25, 26]\n",
"✓ [5, 5, 24, 25, 26]\n",
"✗ [5]\n",
"✗ [5, 5]\n",
"✗ [5, 5, 24, 25]\n",
"✗ [5, 24, 25, 26]\n",
"✗ [5, 24, 25, 26]\n",
"✗ [5, 5, 25, 26]\n",
"✗ [5, 5, 24, 26]\n",
"✗ [5, 5, 24, 25]\n",
"✗ [0, 0, 24, 25, 26]\n",
"✗ [1, 1, 24, 25, 26]\n",
"✗ [3, 3, 24, 25, 26]\n",
"✗ [4, 4, 24, 25, 26]\n",
"✗ [0, 5, 24, 25, 26]\n",
"✗ [1, 5, 24, 25, 26]\n",
"✗ [3, 5, 24, 25, 26]\n",
"✗ [4, 5, 24, 25, 26]\n",
"✗ [5, 0, 24, 25, 26]\n",
"✗ [5, 1, 24, 25, 26]\n",
"✗ [5, 3, 24, 25, 26]\n",
"✗ [5, 4, 24, 25, 26]\n",
"✗ [5, 5, 0, 25, 26]\n",
"✗ [5, 5, 1, 25, 26]\n",
"✗ [5, 5, 3, 25, 26]\n",
"✓ [5, 5, 7, 25, 26]\n",
"✗ [5]\n",
"✗ [5, 5]\n",
"✗ [5, 5, 7, 25]\n",
"✗ [5, 7, 25, 26]\n",
"✗ [5, 7, 25, 26]\n",
"✗ [5, 5, 25, 26]\n",
"✗ [5, 5, 7, 26]\n",
"✗ [5, 5, 7, 25]\n",
"✗ [0, 0, 7, 25, 26]\n",
"✗ [1, 1, 7, 25, 26]\n",
"✗ [3, 3, 7, 25, 26]\n",
"✗ [4, 4, 7, 25, 26]\n",
"✗ [0, 5, 7, 25, 26]\n",
"✗ [1, 5, 7, 25, 26]\n",
"✗ [3, 5, 7, 25, 26]\n",
"✗ [4, 5, 7, 25, 26]\n",
"✗ [5, 0, 7, 25, 26]\n",
"✗ [5, 1, 7, 25, 26]\n",
"✗ [5, 3, 7, 25, 26]\n",
"✗ [5, 4, 7, 25, 26]\n",
"✗ [5, 5, 0, 25, 26]\n",
"✗ [5, 5, 1, 25, 26]\n",
"✗ [5, 5, 3, 25, 26]\n",
"✓ [5, 5, 5, 25, 26]\n",
"✗ [5]\n",
"✗ [5, 5]\n",
"✗ [5, 5, 5, 25]\n",
"✗ [5, 5, 25, 26]\n",
"✗ [5, 5, 25, 26]\n",
"✗ [5, 5, 25, 26]\n",
"✗ [5, 5, 5, 26]\n",
"✗ [5, 5, 5, 25]\n",
"✗ [0, 0, 0, 25, 26]\n",
"✗ [1, 1, 1, 25, 26]\n",
"✗ [3, 3, 3, 25, 26]\n",
"✗ [4, 4, 4, 25, 26]\n",
"✗ [0, 5, 5, 25, 26]\n",
"✗ [1, 5, 5, 25, 26]\n",
"✗ [3, 5, 5, 25, 26]\n",
"✗ [4, 5, 5, 25, 26]\n",
"✗ [5, 0, 5, 25, 26]\n",
"✗ [5, 1, 5, 25, 26]\n",
"✗ [5, 3, 5, 25, 26]\n",
"✗ [5, 4, 5, 25, 26]\n",
"✗ [5, 5, 0, 25, 26]\n",
"✗ [5, 5, 1, 25, 26]\n",
"✗ [5, 5, 3, 25, 26]\n",
"✗ [5, 5, 4, 25, 26]\n",
"✗ [5, 5, 5, 0, 26]\n",
"✗ [5, 5, 5, 1, 26]\n",
"✗ [5, 5, 5, 3, 26]\n",
"✓ [5, 5, 5, 7, 26]\n",
"✗ [5]\n",
"✗ [5, 5]\n",
"✗ [5, 5, 5, 7]\n",
"✗ [5, 5, 7, 26]\n",
"✗ [5, 5, 7, 26]\n",
"✗ [5, 5, 7, 26]\n",
"✗ [5, 5, 5, 26]\n",
"✗ [5, 5, 5, 7]\n",
"✗ [0, 0, 0, 7, 26]\n",
"✗ [1, 1, 1, 7, 26]\n",
"✗ [3, 3, 3, 7, 26]\n",
"✗ [4, 4, 4, 7, 26]\n",
"✗ [0, 5, 5, 7, 26]\n",
"✗ [1, 5, 5, 7, 26]\n",
"✗ [3, 5, 5, 7, 26]\n",
"✗ [4, 5, 5, 7, 26]\n",
"✗ [5, 0, 5, 7, 26]\n",
"✗ [5, 1, 5, 7, 26]\n",
"✗ [5, 3, 5, 7, 26]\n",
"✗ [5, 4, 5, 7, 26]\n",
"✗ [5, 5, 0, 7, 26]\n",
"✗ [5, 5, 1, 7, 26]\n",
"✗ [5, 5, 3, 7, 26]\n",
"✗ [5, 5, 4, 7, 26]\n",
"✗ [5, 5, 5, 0, 26]\n",
"✗ [5, 5, 5, 1, 26]\n",
"✗ [5, 5, 5, 3, 26]\n",
"✓ [5, 5, 5, 5, 26]\n",
"✗ [5]\n",
"✗ [5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 26]\n",
"✗ [5, 5, 5, 26]\n",
"✗ [5, 5, 5, 26]\n",
"✗ [5, 5, 5, 26]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [0, 0, 0, 0, 26]\n",
"✗ [1, 1, 1, 1, 26]\n",
"✗ [3, 3, 3, 3, 26]\n",
"✗ [4, 4, 4, 4, 26]\n",
"✗ [0, 5, 5, 5, 26]\n",
"✗ [1, 5, 5, 5, 26]\n",
"✗ [3, 5, 5, 5, 26]\n",
"✗ [4, 5, 5, 5, 26]\n",
"✗ [5, 0, 5, 5, 26]\n",
"✗ [5, 1, 5, 5, 26]\n",
"✗ [5, 3, 5, 5, 26]\n",
"✗ [5, 4, 5, 5, 26]\n",
"✗ [5, 5, 0, 5, 26]\n",
"✗ [5, 5, 1, 5, 26]\n",
"✗ [5, 5, 3, 5, 26]\n",
"✗ [5, 5, 4, 5, 26]\n",
"✗ [5, 5, 5, 0, 26]\n",
"✗ [5, 5, 5, 1, 26]\n",
"✗ [5, 5, 5, 3, 26]\n",
"✗ [5, 5, 5, 4, 26]\n",
"✗ [5, 5, 5, 5, 0]\n",
"✗ [5, 5, 5, 5, 1]\n",
"✗ [5, 5, 5, 5, 3]\n",
"✓ [5, 5, 5, 5, 7]\n",
"✗ [5]\n",
"✗ [5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 7]\n",
"✗ [5, 5, 5, 7]\n",
"✗ [5, 5, 5, 7]\n",
"✗ [5, 5, 5, 7]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [0, 0, 0, 0, 7]\n",
"✗ [1, 1, 1, 1, 7]\n",
"✗ [3, 3, 3, 3, 7]\n",
"✗ [4, 4, 4, 4, 7]\n",
"✗ [0, 5, 5, 5, 7]\n",
"✗ [1, 5, 5, 5, 7]\n",
"✗ [3, 5, 5, 5, 7]\n",
"✗ [4, 5, 5, 5, 7]\n",
"✗ [5, 0, 5, 5, 7]\n",
"✗ [5, 1, 5, 5, 7]\n",
"✗ [5, 3, 5, 5, 7]\n",
"✗ [5, 4, 5, 5, 7]\n",
"✗ [5, 5, 0, 5, 7]\n",
"✗ [5, 5, 1, 5, 7]\n",
"✗ [5, 5, 3, 5, 7]\n",
"✗ [5, 5, 4, 5, 7]\n",
"✗ [5, 5, 5, 0, 7]\n",
"✗ [5, 5, 5, 1, 7]\n",
"✗ [5, 5, 5, 3, 7]\n",
"✗ [5, 5, 5, 4, 7]\n",
"✗ [5, 5, 5, 5, 0]\n",
"✗ [5, 5, 5, 5, 1]\n",
"✗ [5, 5, 5, 5, 3]\n",
"✓ [5, 5, 5, 5, 5]\n",
"✗ [5]\n",
"✗ [5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [0, 0, 0, 0, 0]\n",
"✗ [1, 1, 1, 1, 1]\n",
"✗ [3, 3, 3, 3, 3]\n",
"✗ [4, 4, 4, 4, 4]\n",
"✗ [0, 5, 5, 5, 5]\n",
"✗ [1, 5, 5, 5, 5]\n",
"✗ [3, 5, 5, 5, 5]\n",
"✗ [4, 5, 5, 5, 5]\n",
"✗ [5, 0, 5, 5, 5]\n",
"✗ [5, 1, 5, 5, 5]\n",
"✗ [5, 3, 5, 5, 5]\n",
"✗ [5, 4, 5, 5, 5]\n",
"✗ [5, 5, 0, 5, 5]\n",
"✗ [5, 5, 1, 5, 5]\n",
"✗ [5, 5, 3, 5, 5]\n",
"✗ [5, 5, 4, 5, 5]\n",
"✗ [5, 5, 5, 0, 5]\n",
"✗ [5, 5, 5, 1, 5]\n",
"✗ [5, 5, 5, 3, 5]\n",
"✗ [5, 5, 5, 4, 5]\n",
"✗ [5, 5, 5, 5, 0]\n",
"✗ [5, 5, 5, 5, 1]\n",
"✗ [5, 5, 5, 5, 3]\n",
"✗ [5, 5, 5, 5, 4]\n",
"\n",
"12 shrinks with 264 function calls\n"
]
}
],
"source": [
"show_trace([20 + i for i in range(7)],\n",
" lambda x: len([t for t in x if t >= 5]) >= 5,\n",
" partial(greedy_shrink, shrink=shrink5))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So what we're going to try to do is to try a simplification first which *creates* that exact right starting condition. Further it's one that will be potentially very useful even if we don't actually have the situation where we have shared shrinks.\n",
"\n",
"What we're going to do is we're going to use values from the list to act as evidence for how complex things need to be. Starting from the smallest, we'll try capping the array at each individual value and see what happens.\n",
"\n",
"As well as being potentially a very rapid shrink, this creates lists with lots of duplicates, which enables the simultaneous shrinking to shine."
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def replace_with_simpler(ls):\n",
" if not ls:\n",
" return\n",
" values = set(ls)\n",
" values.remove(max(ls))\n",
" values = sorted(values)\n",
" for v in values:\n",
" yield [min(v, l) for l in ls]\n",
"\n",
"\n",
"def shrink6(ls):\n",
" yield from shrink_to_prefix(ls)\n",
" yield from delete_individual_elements(ls)\n",
" yield from replace_with_simpler(ls)\n",
" yield from shrink_shared(ls)\n",
" yield from shrink_individual_elements(ls)"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"✓ [20, 21, 22, 23, 24, 25, 26]\n",
"✗ [20]\n",
"✗ [20, 21]\n",
"✗ [20, 21, 22, 23]\n",
"✓ [21, 22, 23, 24, 25, 26]\n",
"✗ [21]\n",
"✗ [21, 22]\n",
"✗ [21, 22, 23, 24]\n",
"✓ [22, 23, 24, 25, 26]\n",
"✗ [22]\n",
"✗ [22, 23]\n",
"✗ [22, 23, 24, 25]\n",
"✗ [23, 24, 25, 26]\n",
"✗ [22, 24, 25, 26]\n",
"✗ [22, 23, 25, 26]\n",
"✗ [22, 23, 24, 26]\n",
"✗ [22, 23, 24, 25]\n",
"✓ [22, 22, 22, 22, 22]\n",
"✗ [22]\n",
"✗ [22, 22]\n",
"✗ [22, 22, 22, 22]\n",
"✗ [22, 22, 22, 22]\n",
"✗ [22, 22, 22, 22]\n",
"✗ [22, 22, 22, 22]\n",
"✗ [22, 22, 22, 22]\n",
"✗ [22, 22, 22, 22]\n",
"✗ [0, 0, 0, 0, 0]\n",
"✗ [1, 1, 1, 1, 1]\n",
"✗ [3, 3, 3, 3, 3]\n",
"✓ [7, 7, 7, 7, 7]\n",
"✗ [7]\n",
"✗ [7, 7]\n",
"✗ [7, 7, 7, 7]\n",
"✗ [7, 7, 7, 7]\n",
"✗ [7, 7, 7, 7]\n",
"✗ [7, 7, 7, 7]\n",
"✗ [7, 7, 7, 7]\n",
"✗ [7, 7, 7, 7]\n",
"✗ [0, 0, 0, 0, 0]\n",
"✗ [1, 1, 1, 1, 1]\n",
"✗ [3, 3, 3, 3, 3]\n",
"✓ [5, 5, 5, 5, 5]\n",
"✗ [5]\n",
"✗ [5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✗ [0, 0, 0, 0, 0]\n",
"✗ [1, 1, 1, 1, 1]\n",
"✗ [3, 3, 3, 3, 3]\n",
"✗ [4, 4, 4, 4, 4]\n",
"✗ [0, 5, 5, 5, 5]\n",
"✗ [1, 5, 5, 5, 5]\n",
"✗ [3, 5, 5, 5, 5]\n",
"✗ [4, 5, 5, 5, 5]\n",
"✗ [5, 0, 5, 5, 5]\n",
"✗ [5, 1, 5, 5, 5]\n",
"✗ [5, 3, 5, 5, 5]\n",
"✗ [5, 4, 5, 5, 5]\n",
"✗ [5, 5, 0, 5, 5]\n",
"✗ [5, 5, 1, 5, 5]\n",
"✗ [5, 5, 3, 5, 5]\n",
"✗ [5, 5, 4, 5, 5]\n",
"✗ [5, 5, 5, 0, 5]\n",
"✗ [5, 5, 5, 1, 5]\n",
"✗ [5, 5, 5, 3, 5]\n",
"✗ [5, 5, 5, 4, 5]\n",
"✗ [5, 5, 5, 5, 0]\n",
"✗ [5, 5, 5, 5, 1]\n",
"✗ [5, 5, 5, 5, 3]\n",
"✗ [5, 5, 5, 5, 4]\n",
"\n",
"5 shrinks with 73 function calls\n"
]
}
],
"source": [
"show_trace([20 + i for i in range(7)],\n",
" lambda x: len([t for t in x if t >= 5]) >= 5,\n",
" partial(greedy_shrink, shrink=shrink6))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we're going to start looking at some numbers.\n",
"\n",
"What we'll do is we'll generate 1000 random lists satisfying some predicate, and then simplify them down to the smallest possible examples satisfying those predicates. This lets us verify that these aren't just cherry-picked examples and our methods help in the general case. We fix the set of examples per predicate so that we're comparing like for like.\n",
"\n",
"A more proper statistical treatment would probably be a good idea."
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"from collections import OrderedDict\n",
"\n",
"conditions = OrderedDict([\n",
" (\"length >= 2\", lambda xs: len(xs) >= 2),\n",
" (\"sum >= 500\", lambda xs: sum(xs) >= 500),\n",
" (\"sum >= 3\", lambda xs: sum(xs) >= 3),\n",
" (\"At least 10 by 5\", lambda xs: len(\n",
" [t for t in xs if t >= 5]) >= 10),\n",
"])"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[17861213645196285187,\n",
" 15609796832515195084,\n",
" 8808697621832673046,\n",
" 1013319847337885109,\n",
" 1252281976438780211,\n",
" 15526909770962854196,\n",
" 2065337703776048239,\n",
" 11654092230944134701,\n",
" 5554896851708700201,\n",
" 17485190250805381572,\n",
" 7700396730246958474,\n",
" 402840882133605445,\n",
" 5303116940477413125,\n",
" 7459257850255946545,\n",
" 10349184495871650178,\n",
" 4361155591615075311,\n",
" 15194020468024244632,\n",
" 14428821588688846242,\n",
" 5754975712549869618,\n",
" 13740966788951413307,\n",
" 15209704957418077856,\n",
" 12562588328524673262,\n",
" 8415556016795311987,\n",
" 3993098291779210741,\n",
" 16874756914619597640,\n",
" 7932421182532982309,\n",
" 1080869529149674704,\n",
" 13878842261614060122,\n",
" 229976195287031921,\n",
" 8378461140013520338,\n",
" 6189522326946191255,\n",
" 16684625600934047114,\n",
" 12533448641134015292,\n",
" 10459192142175991903,\n",
" 15688511015570391481,\n",
" 3091340728247101611,\n",
" 4034760776171697910,\n",
" 6258572097778886531,\n",
" 13555449085571665140,\n",
" 6727488149749641424,\n",
" 7125107819562430884,\n",
" 1557872425804423698,\n",
" 4810250441100696888,\n",
" 10500486959813930693,\n",
" 841300069403644975,\n",
" 9278626999406014662,\n",
" 17219731431761688449,\n",
" 15650446646901259126,\n",
" 8683172055034528265,\n",
" 5138373693056086816,\n",
" 4055877702343936882,\n",
" 5696765901584750542,\n",
" 7133363948804979946,\n",
" 988518370429658551,\n",
" 16302597472193523184,\n",
" 579078764159525857,\n",
" 10678347012503400890,\n",
" 8433836779160269996,\n",
" 13884258181758870664,\n",
" 13594877609651310055]"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import random\n",
"\n",
"N_EXAMPLES = 1000\n",
"\n",
"datasets = {}\n",
"\n",
"def gen_list(rnd):\n",
" return [\n",
" random.getrandbits(64)\n",
" for _ in range(random.randint(0, 100))\n",
" ]\n",
"\n",
"def dataset_for(condition):\n",
" if condition in datasets:\n",
" return datasets[condition]\n",
" constraint = conditions[condition]\n",
" dataset = []\n",
" rnd = random.Random(condition)\n",
" while len(dataset) < N_EXAMPLES:\n",
" ls = gen_list(rnd)\n",
" if constraint(ls):\n",
" dataset.append(ls)\n",
" datasets[condition] = dataset\n",
" return dataset\n",
"\n",
"dataset_for(\"sum >= 3\")[1]"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"13"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# In order to avoid run-away cases where things will take basically forever\n",
"# we cap at 5000 as \"you've taken too long. Stop it\". Because we're only ever\n",
"# showing the worst case scenario we'll just display this as > 5000 if we ever\n",
"# hit it and it won't distort statistics.\n",
"MAX_COUNT = 5000\n",
"\n",
"class MaximumCountExceeded(Exception):\n",
" pass\n",
"\n",
"def call_counts(condition, simplifier):\n",
" constraint = conditions[condition]\n",
" dataset = dataset_for(condition)\n",
" counts = []\n",
"\n",
" for ex in dataset:\n",
" counter = 0\n",
"\n",
" def run_and_count(ls):\n",
" nonlocal counter\n",
" counter += 1\n",
" if counter > MAX_COUNT:\n",
" raise MaximumCountExceeded\n",
" return constraint(ls)\n",
"\n",
" try:\n",
" simplifier(ex, run_and_count)\n",
" counts.append(counter)\n",
" except MaximumCountExceeded:\n",
" counts.append(MAX_COUNT + 1)\n",
" break\n",
" return counts\n",
"\n",
"def worst_case(condition, simplifier):\n",
" return max(call_counts(condition, simplifier))\n",
"\n",
"worst_case(\n",
" \"length >= 2\",\n",
" partial(greedy_shrink, shrink=shrink6))"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"from IPython.display import HTML\n",
"\n",
"def compare_simplifiers(named_simplifiers):\n",
" \"\"\"\n",
" Given a list of (name, simplifier) pairs, output a table comparing\n",
" the worst case performance of each on our current set of examples.\n",
" \"\"\"\n",
" html_fragments = []\n",
" html_fragments.append(\"\\n\\n\")\n",
" header = [\"Condition\"]\n",
" header.extend(name for name, _ in named_simplifiers)\n",
" for h in header:\n",
" html_fragments.append(\"| %s | \" % (h,))\n",
" html_fragments.append(\"
\\n\\n\")\n",
"\n",
" for name in conditions:\n",
" bits = [name.replace(\">\", \">\")]\n",
" for _, simplifier in named_simplifiers:\n",
" value = worst_case(name, simplifier)\n",
" if value <= MAX_COUNT:\n",
" bits.append(str(value))\n",
" else:\n",
" bits.append(\" > %d\" % (MAX_COUNT,))\n",
" html_fragments.append(\" \")\n",
" html_fragments.append(' '.join(\n",
" \"| %s | \" % (b,) for b in bits))\n",
" html_fragments.append(\"
\")\n",
" html_fragments.append(\"\\n
\")\n",
" return HTML('\\n'.join(html_fragments))"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"| Condition | \n",
"2 | \n",
"3 | \n",
"4 | \n",
"5 | \n",
"6 | \n",
"
\n",
"\n",
"\n",
" \n",
"| length >= 2 | 106 | 105 | 13 | 13 | 13 | \n",
"
\n",
" \n",
"| sum >= 500 | 1102 | 178 | 80 | 80 | 80 | \n",
"
\n",
" \n",
"| sum >= 3 | 108 | 107 | 9 | 9 | 9 | \n",
"
\n",
" \n",
"| At least 10 by 5 | 535 | 690 | 809 | 877 | 144 | \n",
"
\n",
"\n",
"
"
],
"text/plain": [
""
]
},
"execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"compare_simplifiers([\n",
" (f.__name__[-1], partial(greedy_shrink, shrink=f))\n",
" for f in [shrink2, shrink3, shrink4, shrink5, shrink6]\n",
"])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So you can see from the above table, the iterations 2 through 5 were a little ambiguous ion that they helped a lot in the cases they were designed to help with but hurt in other cases. 6 however is clearly the best of the lot, being no worse than any of the others on any of the cases and often significantly better.\n",
"\n",
"Rather than continuing to refine our shrink further, we instead look to improvements to how we use shrinking. We'll start by noting a simple optimization: If you look at our traces above, we often checked the same example twice. We're only interested in deterministic conditions, so this isn't useful to do. So we'll start by simply pruning out all duplicates. This should have exactly the same set and order of successful shrinks but will avoid a bunch of redundant work."
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def greedy_shrink_with_dedupe(ls, constraint, shrink):\n",
" seen = set()\n",
" while True:\n",
" for s in shrink(ls):\n",
" key = tuple(s)\n",
" if key in seen:\n",
" continue\n",
" seen.add(key)\n",
" if constraint(s):\n",
" ls = s\n",
" break\n",
" else:\n",
" return ls"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"| Condition | \n",
"Normal | \n",
"Deduped | \n",
"
\n",
"\n",
"\n",
" \n",
"| length >= 2 | 13 | 6 | \n",
"
\n",
" \n",
"| sum >= 500 | 80 | 35 | \n",
"
\n",
" \n",
"| sum >= 3 | 9 | 6 | \n",
"
\n",
" \n",
"| At least 10 by 5 | 144 | 107 | \n",
"
\n",
"\n",
"
"
],
"text/plain": [
""
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"compare_simplifiers([\n",
" (\"Normal\", partial(greedy_shrink, shrink=shrink6)),\n",
" (\"Deduped\", partial(greedy_shrink_with_dedupe,\n",
" shrink=shrink6)),\n",
"\n",
"])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As expected, this is a significant improvement in some cases. It is logically impossible that it could ever make things worse, but it's nice that it makes it better.\n",
"\n",
"So far we've only looked at things where the interaction between elements was fairly light - the sum cases the values of other elements mattered a bit, but shrinking an integer could never enable other shrinks. Lets look at one where this is not the case: Where our condition is that we have at least 10 distinct elements."
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"✓ [100, 101, 102, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [100]\n",
"✗ [100, 101]\n",
"✗ [100, 101, 102, 103]\n",
"✗ [100, 101, 102, 103, 104, 105, 106, 107]\n",
"✗ [101, 102, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [100, 102, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [100, 101, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [100, 101, 102, 104, 105, 106, 107, 108, 109]\n",
"✗ [100, 101, 102, 103, 105, 106, 107, 108, 109]\n",
"✗ [100, 101, 102, 103, 104, 106, 107, 108, 109]\n",
"✗ [100, 101, 102, 103, 104, 105, 107, 108, 109]\n",
"✗ [100, 101, 102, 103, 104, 105, 106, 108, 109]\n",
"✗ [100, 101, 102, 103, 104, 105, 106, 107, 109]\n",
"✗ [100, 101, 102, 103, 104, 105, 106, 107, 108]\n",
"✗ [100, 100, 100, 100, 100, 100, 100, 100, 100, 100]\n",
"✗ [100, 101, 101, 101, 101, 101, 101, 101, 101, 101]\n",
"✗ [100, 101, 102, 102, 102, 102, 102, 102, 102, 102]\n",
"✗ [100, 101, 102, 103, 103, 103, 103, 103, 103, 103]\n",
"✗ [100, 101, 102, 103, 104, 104, 104, 104, 104, 104]\n",
"✗ [100, 101, 102, 103, 104, 105, 105, 105, 105, 105]\n",
"✗ [100, 101, 102, 103, 104, 105, 106, 106, 106, 106]\n",
"✗ [100, 101, 102, 103, 104, 105, 106, 107, 107, 107]\n",
"✗ [100, 101, 102, 103, 104, 105, 106, 107, 108, 108]\n",
"✓ [0, 101, 102, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0]\n",
"✗ [0, 101]\n",
"✗ [0, 101, 102, 103]\n",
"✗ [0, 101, 102, 103, 104, 105, 106, 107]\n",
"✗ [101, 102, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 102, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 101, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 101, 102, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 101, 102, 103, 105, 106, 107, 108, 109]\n",
"✗ [0, 101, 102, 103, 104, 106, 107, 108, 109]\n",
"✗ [0, 101, 102, 103, 104, 105, 107, 108, 109]\n",
"✗ [0, 101, 102, 103, 104, 105, 106, 108, 109]\n",
"✗ [0, 101, 102, 103, 104, 105, 106, 107, 109]\n",
"✗ [0, 101, 102, 103, 104, 105, 106, 107, 108]\n",
"✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
"✗ [0, 101, 101, 101, 101, 101, 101, 101, 101, 101]\n",
"✗ [0, 101, 102, 102, 102, 102, 102, 102, 102, 102]\n",
"✗ [0, 101, 102, 103, 103, 103, 103, 103, 103, 103]\n",
"✗ [0, 101, 102, 103, 104, 104, 104, 104, 104, 104]\n",
"✗ [0, 101, 102, 103, 104, 105, 105, 105, 105, 105]\n",
"✗ [0, 101, 102, 103, 104, 105, 106, 106, 106, 106]\n",
"✗ [0, 101, 102, 103, 104, 105, 106, 107, 107, 107]\n",
"✗ [0, 101, 102, 103, 104, 105, 106, 107, 108, 108]\n",
"✗ [0, 0, 102, 103, 104, 105, 106, 107, 108, 109]\n",
"✓ [0, 1, 102, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0]\n",
"✗ [0, 1]\n",
"✗ [0, 1, 102, 103]\n",
"✗ [0, 1, 102, 103, 104, 105, 106, 107]\n",
"✗ [1, 102, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 102, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 102, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 102, 103, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 102, 103, 104, 106, 107, 108, 109]\n",
"✗ [0, 1, 102, 103, 104, 105, 107, 108, 109]\n",
"✗ [0, 1, 102, 103, 104, 105, 106, 108, 109]\n",
"✗ [0, 1, 102, 103, 104, 105, 106, 107, 109]\n",
"✗ [0, 1, 102, 103, 104, 105, 106, 107, 108]\n",
"✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
"✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
"✗ [0, 1, 102, 102, 102, 102, 102, 102, 102, 102]\n",
"✗ [0, 1, 102, 103, 103, 103, 103, 103, 103, 103]\n",
"✗ [0, 1, 102, 103, 104, 104, 104, 104, 104, 104]\n",
"✗ [0, 1, 102, 103, 104, 105, 105, 105, 105, 105]\n",
"✗ [0, 1, 102, 103, 104, 105, 106, 106, 106, 106]\n",
"✗ [0, 1, 102, 103, 104, 105, 106, 107, 107, 107]\n",
"✗ [0, 1, 102, 103, 104, 105, 106, 107, 108, 108]\n",
"✗ [0, 0, 102, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 0, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 1, 103, 104, 105, 106, 107, 108, 109]\n",
"✓ [0, 1, 3, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0]\n",
"✗ [0, 1]\n",
"✗ [0, 1, 3, 103]\n",
"✗ [0, 1, 3, 103, 104, 105, 106, 107]\n",
"✗ [1, 3, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 3, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 3, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 3, 103, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 3, 103, 104, 106, 107, 108, 109]\n",
"✗ [0, 1, 3, 103, 104, 105, 107, 108, 109]\n",
"✗ [0, 1, 3, 103, 104, 105, 106, 108, 109]\n",
"✗ [0, 1, 3, 103, 104, 105, 106, 107, 109]\n",
"✗ [0, 1, 3, 103, 104, 105, 106, 107, 108]\n",
"✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
"✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
"✗ [0, 1, 3, 3, 3, 3, 3, 3, 3, 3]\n",
"✗ [0, 1, 3, 103, 103, 103, 103, 103, 103, 103]\n",
"✗ [0, 1, 3, 103, 104, 104, 104, 104, 104, 104]\n",
"✗ [0, 1, 3, 103, 104, 105, 105, 105, 105, 105]\n",
"✗ [0, 1, 3, 103, 104, 105, 106, 106, 106, 106]\n",
"✗ [0, 1, 3, 103, 104, 105, 106, 107, 107, 107]\n",
"✗ [0, 1, 3, 103, 104, 105, 106, 107, 108, 108]\n",
"✗ [0, 0, 3, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 0, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 1, 103, 104, 105, 106, 107, 108, 109]\n",
"✓ [0, 1, 2, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0]\n",
"✗ [0, 1]\n",
"✗ [0, 1, 2, 103]\n",
"✗ [0, 1, 2, 103, 104, 105, 106, 107]\n",
"✗ [1, 2, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 2, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 103, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 103, 104, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 103, 104, 105, 107, 108, 109]\n",
"✗ [0, 1, 2, 103, 104, 105, 106, 108, 109]\n",
"✗ [0, 1, 2, 103, 104, 105, 106, 107, 109]\n",
"✗ [0, 1, 2, 103, 104, 105, 106, 107, 108]\n",
"✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
"✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
"✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✗ [0, 1, 2, 103, 103, 103, 103, 103, 103, 103]\n",
"✗ [0, 1, 2, 103, 104, 104, 104, 104, 104, 104]\n",
"✗ [0, 1, 2, 103, 104, 105, 105, 105, 105, 105]\n",
"✗ [0, 1, 2, 103, 104, 105, 106, 106, 106, 106]\n",
"✗ [0, 1, 2, 103, 104, 105, 106, 107, 107, 107]\n",
"✗ [0, 1, 2, 103, 104, 105, 106, 107, 108, 108]\n",
"✗ [0, 0, 2, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 0, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 1, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 0, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 1, 104, 105, 106, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 104, 105, 106, 107, 108, 109]\n",
"✗ [0]\n",
"✗ [0, 1]\n",
"✗ [0, 1, 2, 3]\n",
"✗ [0, 1, 2, 3, 104, 105, 106, 107]\n",
"✗ [1, 2, 3, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 2, 3, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 3, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 104, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 104, 105, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 104, 105, 106, 108, 109]\n",
"✗ [0, 1, 2, 3, 104, 105, 106, 107, 109]\n",
"✗ [0, 1, 2, 3, 104, 105, 106, 107, 108]\n",
"✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
"✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
"✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
"✗ [0, 1, 2, 3, 104, 104, 104, 104, 104, 104]\n",
"✗ [0, 1, 2, 3, 104, 105, 105, 105, 105, 105]\n",
"✗ [0, 1, 2, 3, 104, 105, 106, 106, 106, 106]\n",
"✗ [0, 1, 2, 3, 104, 105, 106, 107, 107, 107]\n",
"✗ [0, 1, 2, 3, 104, 105, 106, 107, 108, 108]\n",
"✗ [0, 0, 2, 3, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 0, 3, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 1, 3, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 0, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 1, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 2, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 0, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 1, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 3, 105, 106, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 7, 105, 106, 107, 108, 109]\n",
"✗ [0]\n",
"✗ [0, 1]\n",
"✗ [0, 1, 2, 3]\n",
"✗ [0, 1, 2, 3, 7, 105, 106, 107]\n",
"✗ [1, 2, 3, 7, 105, 106, 107, 108, 109]\n",
"✗ [0, 2, 3, 7, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 3, 7, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 7, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 7, 105, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 7, 105, 106, 108, 109]\n",
"✗ [0, 1, 2, 3, 7, 105, 106, 107, 109]\n",
"✗ [0, 1, 2, 3, 7, 105, 106, 107, 108]\n",
"✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
"✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
"✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
"✗ [0, 1, 2, 3, 7, 7, 7, 7, 7, 7]\n",
"✗ [0, 1, 2, 3, 7, 105, 105, 105, 105, 105]\n",
"✗ [0, 1, 2, 3, 7, 105, 106, 106, 106, 106]\n",
"✗ [0, 1, 2, 3, 7, 105, 106, 107, 107, 107]\n",
"✗ [0, 1, 2, 3, 7, 105, 106, 107, 108, 108]\n",
"✗ [0, 0, 2, 3, 7, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 0, 3, 7, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 1, 3, 7, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 0, 7, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 1, 7, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 2, 7, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 0, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 1, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 3, 105, 106, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 5, 105, 106, 107, 108, 109]\n",
"✗ [0]\n",
"✗ [0, 1]\n",
"✗ [0, 1, 2, 3]\n",
"✗ [0, 1, 2, 3, 5, 105, 106, 107]\n",
"✗ [1, 2, 3, 5, 105, 106, 107, 108, 109]\n",
"✗ [0, 2, 3, 5, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 3, 5, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 5, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 5, 105, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 5, 105, 106, 108, 109]\n",
"✗ [0, 1, 2, 3, 5, 105, 106, 107, 109]\n",
"✗ [0, 1, 2, 3, 5, 105, 106, 107, 108]\n",
"✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
"✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
"✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
"✗ [0, 1, 2, 3, 5, 5, 5, 5, 5, 5]\n",
"✗ [0, 1, 2, 3, 5, 105, 105, 105, 105, 105]\n",
"✗ [0, 1, 2, 3, 5, 105, 106, 106, 106, 106]\n",
"✗ [0, 1, 2, 3, 5, 105, 106, 107, 107, 107]\n",
"✗ [0, 1, 2, 3, 5, 105, 106, 107, 108, 108]\n",
"✗ [0, 0, 2, 3, 5, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 0, 3, 5, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 1, 3, 5, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 0, 5, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 1, 5, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 2, 5, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 0, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 1, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 3, 105, 106, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 4, 105, 106, 107, 108, 109]\n",
"✗ [0]\n",
"✗ [0, 1]\n",
"✗ [0, 1, 2, 3]\n",
"✗ [0, 1, 2, 3, 4, 105, 106, 107]\n",
"✗ [1, 2, 3, 4, 105, 106, 107, 108, 109]\n",
"✗ [0, 2, 3, 4, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 3, 4, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 4, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 105, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 105, 106, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 105, 106, 107, 109]\n",
"✗ [0, 1, 2, 3, 4, 105, 106, 107, 108]\n",
"✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
"✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
"✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
"✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
"✗ [0, 1, 2, 3, 4, 105, 105, 105, 105, 105]\n",
"✗ [0, 1, 2, 3, 4, 105, 106, 106, 106, 106]\n",
"✗ [0, 1, 2, 3, 4, 105, 106, 107, 107, 107]\n",
"✗ [0, 1, 2, 3, 4, 105, 106, 107, 108, 108]\n",
"✗ [0, 0, 2, 3, 4, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 0, 3, 4, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 1, 3, 4, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 0, 4, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 1, 4, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 2, 4, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 0, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 1, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 3, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 0, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 1, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 3, 106, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 4, 7, 106, 107, 108, 109]\n",
"✗ [0]\n",
"✗ [0, 1]\n",
"✗ [0, 1, 2, 3]\n",
"✗ [0, 1, 2, 3, 4, 7, 106, 107]\n",
"✗ [1, 2, 3, 4, 7, 106, 107, 108, 109]\n",
"✗ [0, 2, 3, 4, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 3, 4, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 4, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 7, 106, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 7, 106, 107, 109]\n",
"✗ [0, 1, 2, 3, 4, 7, 106, 107, 108]\n",
"✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
"✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
"✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
"✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
"✗ [0, 1, 2, 3, 4, 7, 7, 7, 7, 7]\n",
"✗ [0, 1, 2, 3, 4, 7, 106, 106, 106, 106]\n",
"✗ [0, 1, 2, 3, 4, 7, 106, 107, 107, 107]\n",
"✗ [0, 1, 2, 3, 4, 7, 106, 107, 108, 108]\n",
"✗ [0, 0, 2, 3, 4, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 0, 3, 4, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 1, 3, 4, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 0, 4, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 1, 4, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 2, 4, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 0, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 1, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 3, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 0, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 1, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 3, 106, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 106, 107, 108, 109]\n",
"✗ [0]\n",
"✗ [0, 1]\n",
"✗ [0, 1, 2, 3]\n",
"✗ [0, 1, 2, 3, 4, 5, 106, 107]\n",
"✗ [1, 2, 3, 4, 5, 106, 107, 108, 109]\n",
"✗ [0, 2, 3, 4, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 3, 4, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 4, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 106, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 106, 107, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 106, 107, 108]\n",
"✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
"✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
"✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
"✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
"✗ [0, 1, 2, 3, 4, 5, 106, 106, 106, 106]\n",
"✗ [0, 1, 2, 3, 4, 5, 106, 107, 107, 107]\n",
"✗ [0, 1, 2, 3, 4, 5, 106, 107, 108, 108]\n",
"✗ [0, 0, 2, 3, 4, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 0, 3, 4, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 1, 3, 4, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 0, 4, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 1, 4, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 2, 4, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 0, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 1, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 3, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 0, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 1, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 3, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 4, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 0, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 1, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 3, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 7, 107, 108, 109]\n",
"✗ [0]\n",
"✗ [0, 1]\n",
"✗ [0, 1, 2, 3]\n",
"✗ [0, 1, 2, 3, 4, 5, 7, 107]\n",
"✗ [1, 2, 3, 4, 5, 7, 107, 108, 109]\n",
"✗ [0, 2, 3, 4, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 3, 4, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 4, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 7, 107, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 7, 107, 108]\n",
"✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
"✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
"✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
"✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
"✗ [0, 1, 2, 3, 4, 5, 7, 7, 7, 7]\n",
"✗ [0, 1, 2, 3, 4, 5, 7, 107, 107, 107]\n",
"✗ [0, 1, 2, 3, 4, 5, 7, 107, 108, 108]\n",
"✗ [0, 0, 2, 3, 4, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 0, 3, 4, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 1, 3, 4, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 0, 4, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 1, 4, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 2, 4, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 0, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 1, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 3, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 0, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 1, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 3, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 4, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 0, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 1, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 3, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 107, 108, 109]\n",
"✗ [0]\n",
"✗ [0, 1]\n",
"✗ [0, 1, 2, 3]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 107]\n",
"✗ [1, 2, 3, 4, 5, 6, 107, 108, 109]\n",
"✗ [0, 2, 3, 4, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 3, 4, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 4, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 107, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 107, 108]\n",
"✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
"✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
"✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
"✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 6, 6]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 107, 107, 107]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 107, 108, 108]\n",
"✗ [0, 0, 2, 3, 4, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 0, 3, 4, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 1, 3, 4, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 0, 4, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 1, 4, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 2, 4, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 0, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 1, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 3, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 0, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 1, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 3, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 4, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 0, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 1, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 3, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 0, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 1, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 3, 108, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 108, 109]\n",
"✗ [0]\n",
"✗ [0, 1]\n",
"✗ [0, 1, 2, 3]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7]\n",
"✗ [1, 2, 3, 4, 5, 6, 7, 108, 109]\n",
"✗ [0, 2, 3, 4, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 3, 4, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 4, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 108]\n",
"✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
"✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
"✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
"✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 6, 6]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 7]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 108, 108]\n",
"✗ [0, 0, 2, 3, 4, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 0, 3, 4, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 1, 3, 4, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 0, 4, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 1, 4, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 2, 4, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 0, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 1, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 3, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 0, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 1, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 3, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 4, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 0, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 1, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 3, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 0, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 1, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 3, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 5, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 15, 109]\n",
"✗ [0]\n",
"✗ [0, 1]\n",
"✗ [0, 1, 2, 3]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7]\n",
"✗ [1, 2, 3, 4, 5, 6, 7, 15, 109]\n",
"✗ [0, 2, 3, 4, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 3, 4, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 4, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 15]\n",
"✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
"✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
"✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
"✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 6, 6]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 7]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 15, 15]\n",
"✗ [0, 0, 2, 3, 4, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 0, 3, 4, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 1, 3, 4, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 0, 4, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 1, 4, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 2, 4, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 0, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 1, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 3, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 0, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 1, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 3, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 4, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 0, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 1, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 3, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 0, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 1, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 3, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 5, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 11, 109]\n",
"✗ [0]\n",
"✗ [0, 1]\n",
"✗ [0, 1, 2, 3]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7]\n",
"✗ [1, 2, 3, 4, 5, 6, 7, 11, 109]\n",
"✗ [0, 2, 3, 4, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 3, 4, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 4, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 11]\n",
"✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
"✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
"✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
"✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 6, 6]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 7]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 11, 11]\n",
"✗ [0, 0, 2, 3, 4, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 0, 3, 4, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 1, 3, 4, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 0, 4, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 1, 4, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 2, 4, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 0, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 1, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 3, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 0, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 1, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 3, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 4, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 0, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 1, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 3, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 0, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 1, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 3, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 5, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 9, 109]\n",
"✗ [0]\n",
"✗ [0, 1]\n",
"✗ [0, 1, 2, 3]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7]\n",
"✗ [1, 2, 3, 4, 5, 6, 7, 9, 109]\n",
"✗ [0, 2, 3, 4, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 3, 4, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 4, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 9]\n",
"✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
"✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
"✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
"✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 6, 6]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 7]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 9, 9]\n",
"✗ [0, 0, 2, 3, 4, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 0, 3, 4, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 1, 3, 4, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 0, 4, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 1, 4, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 2, 4, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 0, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 1, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 3, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 0, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 1, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 3, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 4, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 0, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 1, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 3, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 0, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 1, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 3, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 5, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 109]\n",
"✗ [0]\n",
"✗ [0, 1]\n",
"✗ [0, 1, 2, 3]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7]\n",
"✗ [1, 2, 3, 4, 5, 6, 7, 8, 109]\n",
"✗ [0, 2, 3, 4, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 3, 4, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 4, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8]\n",
"✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
"✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
"✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
"✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 6, 6]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 7]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 8]\n",
"✗ [0, 0, 2, 3, 4, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 0, 3, 4, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 1, 3, 4, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 0, 4, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 1, 4, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 2, 4, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 0, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 1, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 3, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 0, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 1, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 3, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 4, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 0, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 1, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 3, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 0, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 1, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 3, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 5, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 6, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 1]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 3]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 7]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 15]\n",
"✗ [0]\n",
"✗ [0, 1]\n",
"✗ [0, 1, 2, 3]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7]\n",
"✗ [1, 2, 3, 4, 5, 6, 7, 8, 15]\n",
"✗ [0, 2, 3, 4, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 3, 4, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 4, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8]\n",
"✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
"✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
"✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
"✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 6, 6]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 7]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 8]\n",
"✗ [0, 0, 2, 3, 4, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 0, 3, 4, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 1, 3, 4, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 0, 4, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 1, 4, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 2, 4, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 0, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 1, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 3, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 0, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 1, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 3, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 4, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 0, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 1, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 3, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 0, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 1, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 3, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 5, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 6, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 1]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 3]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 7]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 11]\n",
"✗ [0]\n",
"✗ [0, 1]\n",
"✗ [0, 1, 2, 3]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7]\n",
"✗ [1, 2, 3, 4, 5, 6, 7, 8, 11]\n",
"✗ [0, 2, 3, 4, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 3, 4, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 4, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8]\n",
"✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
"✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
"✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
"✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 6, 6]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 7]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 8]\n",
"✗ [0, 0, 2, 3, 4, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 0, 3, 4, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 1, 3, 4, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 0, 4, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 1, 4, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 2, 4, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 0, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 1, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 3, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 0, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 1, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 3, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 4, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 0, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 1, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 3, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 0, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 1, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 3, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 5, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 6, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 1]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 3]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 7]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
"✗ [0]\n",
"✗ [0, 1]\n",
"✗ [0, 1, 2, 3]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7]\n",
"✗ [1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
"✗ [0, 2, 3, 4, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 3, 4, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 4, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8]\n",
"✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
"✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
"✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
"✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
"✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 6, 6]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 7]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 8]\n",
"✗ [0, 0, 2, 3, 4, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 0, 3, 4, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 1, 3, 4, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 0, 4, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 1, 4, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 2, 4, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 0, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 1, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 3, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 0, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 1, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 3, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 4, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 0, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 1, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 3, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 0, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 1, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 3, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 5, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 6, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 1]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 3]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 7]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 8]\n",
"\n",
"20 shrinks with 848 function calls\n"
]
}
],
"source": [
"show_trace([100 + i for i in range(10)],\n",
" lambda x: len(set(x)) >= 10,\n",
" partial(greedy_shrink, shrink=shrink6))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This does not do very well at all.\n",
"\n",
"The reason it doesn't is that we keep trying useless shrinks. e.g. none of the shrinks done by shrink\\_to\\_prefix, replace\\_with\\_simpler or shrink\\_shared will ever do anything useful here.\n",
"\n",
"So lets switch to an approach where we try shrink types until they stop working and then we move on to the next type:"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def multicourse_shrink1(ls, constraint):\n",
" seen = set()\n",
" for shrink in [\n",
" shrink_to_prefix,\n",
" replace_with_simpler,\n",
" shrink_shared,\n",
" shrink_individual_elements,\n",
" ]:\n",
" while True:\n",
" for s in shrink(ls):\n",
" key = tuple(s)\n",
" if key in seen:\n",
" continue\n",
" seen.add(key)\n",
" if constraint(s):\n",
" ls = s\n",
" break\n",
" else:\n",
" break\n",
" return ls"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"✓ [100, 101, 102, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [100]\n",
"✗ [100, 101]\n",
"✗ [100, 101, 102, 103]\n",
"✗ [100, 101, 102, 103, 104, 105, 106, 107]\n",
"✗ [100, 100, 100, 100, 100, 100, 100, 100, 100, 100]\n",
"✗ [100, 101, 101, 101, 101, 101, 101, 101, 101, 101]\n",
"✗ [100, 101, 102, 102, 102, 102, 102, 102, 102, 102]\n",
"✗ [100, 101, 102, 103, 103, 103, 103, 103, 103, 103]\n",
"✗ [100, 101, 102, 103, 104, 104, 104, 104, 104, 104]\n",
"✗ [100, 101, 102, 103, 104, 105, 105, 105, 105, 105]\n",
"✗ [100, 101, 102, 103, 104, 105, 106, 106, 106, 106]\n",
"✗ [100, 101, 102, 103, 104, 105, 106, 107, 107, 107]\n",
"✗ [100, 101, 102, 103, 104, 105, 106, 107, 108, 108]\n",
"✓ [0, 101, 102, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 0, 102, 103, 104, 105, 106, 107, 108, 109]\n",
"✓ [0, 1, 102, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 0, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 1, 103, 104, 105, 106, 107, 108, 109]\n",
"✓ [0, 1, 3, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 0, 3, 103, 104, 105, 106, 107, 108, 109]\n",
"✓ [0, 1, 2, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 0, 2, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 0, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 1, 104, 105, 106, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 0, 2, 3, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 0, 3, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 1, 3, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 2, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 0, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 1, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 3, 105, 106, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 7, 105, 106, 107, 108, 109]\n",
"✗ [0, 0, 2, 3, 7, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 0, 3, 7, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 1, 3, 7, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 0, 7, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 1, 7, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 2, 7, 105, 106, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 5, 105, 106, 107, 108, 109]\n",
"✗ [0, 0, 2, 3, 5, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 0, 3, 5, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 1, 3, 5, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 0, 5, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 1, 5, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 2, 5, 105, 106, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 4, 105, 106, 107, 108, 109]\n",
"✗ [0, 0, 2, 3, 4, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 0, 3, 4, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 1, 3, 4, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 0, 4, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 1, 4, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 2, 4, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 0, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 1, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 3, 106, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 4, 7, 106, 107, 108, 109]\n",
"✗ [0, 0, 2, 3, 4, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 0, 3, 4, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 1, 3, 4, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 0, 4, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 1, 4, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 2, 4, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 0, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 1, 7, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 3, 7, 106, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 106, 107, 108, 109]\n",
"✗ [0, 0, 2, 3, 4, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 0, 3, 4, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 1, 3, 4, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 0, 4, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 1, 4, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 2, 4, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 0, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 1, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 3, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 4, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 0, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 1, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 3, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 7, 107, 108, 109]\n",
"✗ [0, 0, 2, 3, 4, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 0, 3, 4, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 1, 3, 4, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 0, 4, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 1, 4, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 2, 4, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 0, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 1, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 3, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 0, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 1, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 3, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 4, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 107, 108, 109]\n",
"✗ [0, 0, 2, 3, 4, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 0, 3, 4, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 1, 3, 4, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 0, 4, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 1, 4, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 2, 4, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 0, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 1, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 3, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 0, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 1, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 3, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 4, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 0, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 1, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 3, 108, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 108, 109]\n",
"✗ [0, 0, 2, 3, 4, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 0, 3, 4, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 1, 3, 4, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 0, 4, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 1, 4, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 2, 4, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 0, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 1, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 3, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 0, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 1, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 3, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 4, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 0, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 1, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 3, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 5, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 15, 109]\n",
"✗ [0, 0, 2, 3, 4, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 0, 3, 4, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 1, 3, 4, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 0, 4, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 1, 4, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 2, 4, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 0, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 1, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 3, 5, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 0, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 1, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 3, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 4, 6, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 0, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 1, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 3, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 7, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 0, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 1, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 3, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 5, 15, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 15, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 11, 109]\n",
"✗ [0, 0, 2, 3, 4, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 0, 3, 4, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 1, 3, 4, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 0, 4, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 1, 4, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 2, 4, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 0, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 1, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 3, 5, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 0, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 1, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 3, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 4, 6, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 0, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 1, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 3, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 7, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 0, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 1, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 3, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 5, 11, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 11, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 9, 109]\n",
"✗ [0, 0, 2, 3, 4, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 0, 3, 4, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 1, 3, 4, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 0, 4, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 1, 4, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 2, 4, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 0, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 1, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 3, 5, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 0, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 1, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 3, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 4, 6, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 0, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 1, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 3, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 7, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 0, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 1, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 3, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 5, 9, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 9, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 109]\n",
"✗ [0, 0, 2, 3, 4, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 0, 3, 4, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 1, 3, 4, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 0, 4, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 1, 4, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 2, 4, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 0, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 1, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 3, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 0, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 1, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 3, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 4, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 0, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 1, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 3, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 0, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 1, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 3, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 5, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 6, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 1]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 3]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 7]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 15]\n",
"✗ [0, 0, 2, 3, 4, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 0, 3, 4, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 1, 3, 4, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 0, 4, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 1, 4, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 2, 4, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 0, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 1, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 3, 5, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 0, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 1, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 3, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 4, 6, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 0, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 1, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 3, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 7, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 0, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 1, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 3, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 5, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 8, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 6, 15]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 15]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 11]\n",
"✗ [0, 0, 2, 3, 4, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 0, 3, 4, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 1, 3, 4, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 0, 4, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 1, 4, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 2, 4, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 0, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 1, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 3, 5, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 0, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 1, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 3, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 4, 6, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 0, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 1, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 3, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 7, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 0, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 1, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 3, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 5, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 8, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 6, 11]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 11]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
"✗ [0, 0, 2, 3, 4, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 0, 3, 4, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 1, 3, 4, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 0, 4, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 1, 4, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 2, 4, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 0, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 1, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 3, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 0, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 1, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 3, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 4, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 0, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 1, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 3, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 0, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 1, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 3, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 5, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 6, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 8]\n",
"\n",
"20 shrinks with 318 function calls\n"
]
}
],
"source": [
"show_trace([100 + i for i in range(10)],\n",
" lambda x: len(set(x)) >= 10,\n",
" multicourse_shrink1)"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"conditions[\"10 distinct elements\"] = lambda xs: len(set(xs)) >= 10"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"| Condition | \n",
"Single pass | \n",
"Multi pass | \n",
"
\n",
"\n",
"\n",
" \n",
"| length >= 2 | 6 | 4 | \n",
"
\n",
" \n",
"| sum >= 500 | 35 | 34 | \n",
"
\n",
" \n",
"| sum >= 3 | 6 | 5 | \n",
"
\n",
" \n",
"| At least 10 by 5 | 107 | 58 | \n",
"
\n",
" \n",
"| 10 distinct elements | 623 | 320 | \n",
"
\n",
"\n",
"
"
],
"text/plain": [
""
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"compare_simplifiers([\n",
" (\"Single pass\", partial(greedy_shrink_with_dedupe,\n",
" shrink=shrink6)),\n",
" (\"Multi pass\", multicourse_shrink1)\n",
"])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So that helped, but not as much as we'd have liked. It's saved us about half the calls, when really we wanted to save 90% of the calls.\n",
"\n",
"We're on the right track though. The problem is not that our solution isn't good, it's that it didn't go far enough: We're *still* making an awful lot of useless calls. The problem is that each time we shrink the element at index i we try shrinking the elements at indexes 0 through i - 1, and this will never work. So what we want to do is to break shrinking elements into a separate shrinker for each index:"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def simplify_index(i):\n",
" def accept(ls):\n",
" if i >= len(ls):\n",
" return\n",
" for v in shrink_integer(ls[i]):\n",
" s = list(ls)\n",
" s[i] = v\n",
" yield s\n",
" return accept\n",
"\n",
"def shrinkers_for(ls):\n",
" yield shrink_to_prefix\n",
" yield delete_individual_elements\n",
" yield replace_with_simpler\n",
" yield shrink_shared\n",
" for i in range(len(ls)):\n",
" yield simplify_index(i)\n",
"\n",
"def multicourse_shrink2(ls, constraint):\n",
" seen = set()\n",
" for shrink in shrinkers_for(ls):\n",
" while True:\n",
" for s in shrink(ls):\n",
" key = tuple(s)\n",
" if key in seen:\n",
" continue\n",
" seen.add(key)\n",
" if constraint(s):\n",
" ls = s\n",
" break\n",
" else:\n",
" break\n",
" return ls"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"✓ [100, 101, 102, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [100]\n",
"✗ [100, 101]\n",
"✗ [100, 101, 102, 103]\n",
"✗ [100, 101, 102, 103, 104, 105, 106, 107]\n",
"✗ [101, 102, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [100, 102, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [100, 101, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [100, 101, 102, 104, 105, 106, 107, 108, 109]\n",
"✗ [100, 101, 102, 103, 105, 106, 107, 108, 109]\n",
"✗ [100, 101, 102, 103, 104, 106, 107, 108, 109]\n",
"✗ [100, 101, 102, 103, 104, 105, 107, 108, 109]\n",
"✗ [100, 101, 102, 103, 104, 105, 106, 108, 109]\n",
"✗ [100, 101, 102, 103, 104, 105, 106, 107, 109]\n",
"✗ [100, 101, 102, 103, 104, 105, 106, 107, 108]\n",
"✗ [100, 100, 100, 100, 100, 100, 100, 100, 100, 100]\n",
"✗ [100, 101, 101, 101, 101, 101, 101, 101, 101, 101]\n",
"✗ [100, 101, 102, 102, 102, 102, 102, 102, 102, 102]\n",
"✗ [100, 101, 102, 103, 103, 103, 103, 103, 103, 103]\n",
"✗ [100, 101, 102, 103, 104, 104, 104, 104, 104, 104]\n",
"✗ [100, 101, 102, 103, 104, 105, 105, 105, 105, 105]\n",
"✗ [100, 101, 102, 103, 104, 105, 106, 106, 106, 106]\n",
"✗ [100, 101, 102, 103, 104, 105, 106, 107, 107, 107]\n",
"✗ [100, 101, 102, 103, 104, 105, 106, 107, 108, 108]\n",
"✓ [0, 101, 102, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 0, 102, 103, 104, 105, 106, 107, 108, 109]\n",
"✓ [0, 1, 102, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 0, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 1, 103, 104, 105, 106, 107, 108, 109]\n",
"✓ [0, 1, 3, 103, 104, 105, 106, 107, 108, 109]\n",
"✓ [0, 1, 2, 103, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 0, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 1, 104, 105, 106, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 2, 104, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 0, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 1, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 3, 105, 106, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 7, 105, 106, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 5, 105, 106, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 4, 105, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 0, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 1, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 3, 106, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 4, 7, 106, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 4, 106, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 0, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 1, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 3, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 7, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 5, 107, 108, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 107, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 0, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 1, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 3, 108, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 5, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 6, 108, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 15, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 11, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 9, 109]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 6, 109]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 1]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 3]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 7]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 15]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 11]\n",
"✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
"✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 8]\n",
"\n",
"20 shrinks with 75 function calls\n"
]
}
],
"source": [
"show_trace([100 + i for i in range(10)],\n",
" lambda x: len(set(x)) >= 10,\n",
" multicourse_shrink2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This worked great! It saved us a huge number of function calls.\n",
"\n",
"Unfortunately it's wrong. Actually the previous one was wrong too, but this one is more obviously wrong. The problem is that shrinking later elements can unlock more shrinks for earlier elements and we'll never be able to benefit from that here:"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"✓ [101, 100]\n",
"✗ [101]\n",
"✗ [100]\n",
"✗ [100, 100]\n",
"✗ [0, 100]\n",
"✗ [1, 100]\n",
"✗ [3, 100]\n",
"✗ [7, 100]\n",
"✗ [15, 100]\n",
"✗ [31, 100]\n",
"✗ [63, 100]\n",
"✗ [82, 100]\n",
"✗ [91, 100]\n",
"✗ [96, 100]\n",
"✗ [98, 100]\n",
"✗ [99, 100]\n",
"✓ [101, 0]\n",
"\n",
"1 shrinks with 16 function calls\n"
]
}
],
"source": [
"show_trace([101, 100],\n",
" lambda x: len(x) >= 2 and x[0] > x[1],\n",
" multicourse_shrink2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Armed with this example we can also show an example where the previous one is wrong because a later simplification unlocks an earlier one because shrinking values allows us to delete more elements:"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"✓ [5, 5, 5, 5, 5, 5, 5, 5, 5, 5]\n",
"✗ [5]\n",
"✗ [5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✓ [5, 5, 5, 5, 5, 5, 5, 5]\n",
"✓ [0, 0, 0, 0, 0, 0, 0, 0]\n",
"\n",
"2 shrinks with 5 function calls\n"
]
}
],
"source": [
"show_trace([5] * 10,\n",
" lambda x: x and len(x) > max(x),\n",
" multicourse_shrink1)"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"conditions[\"First > Second\"] = lambda xs: len(xs) >= 2 and xs[0] > xs[1]"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# Note: We modify this to mask off the high bits because otherwise the probability of\n",
"# hitting the condition at random is too low.\n",
"conditions[\"Size > max & 63\"] = lambda xs: xs and len(xs) > (max(xs) & 63)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So what we'll try doing is iterating this to a fixed point and see what happens:"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def multicourse_shrink3(ls, constraint):\n",
" seen = set()\n",
" while True:\n",
" old_ls = ls\n",
" for shrink in shrinkers_for(ls):\n",
" while True:\n",
" for s in shrink(ls):\n",
" key = tuple(s)\n",
" if key in seen:\n",
" continue\n",
" seen.add(key)\n",
" if constraint(s):\n",
" ls = s\n",
" break\n",
" else:\n",
" break\n",
" if ls == old_ls:\n",
" return ls"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"✓ [101, 100]\n",
"✗ [101]\n",
"✗ [100]\n",
"✗ [100, 100]\n",
"✗ [0, 100]\n",
"✗ [1, 100]\n",
"✗ [3, 100]\n",
"✗ [7, 100]\n",
"✗ [15, 100]\n",
"✗ [31, 100]\n",
"✗ [63, 100]\n",
"✗ [82, 100]\n",
"✗ [91, 100]\n",
"✗ [96, 100]\n",
"✗ [98, 100]\n",
"✗ [99, 100]\n",
"✓ [101, 0]\n",
"✗ [0]\n",
"✗ [0, 0]\n",
"✓ [1, 0]\n",
"✗ [1]\n",
"\n",
"2 shrinks with 20 function calls\n"
]
}
],
"source": [
"show_trace([101, 100],\n",
" lambda xs: len(xs) >= 2 and xs[0] > xs[1],\n",
" multicourse_shrink3)"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"✓ [5, 5, 5, 5, 5, 5, 5, 5, 5, 5]\n",
"✗ [5]\n",
"✗ [5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✓ [5, 5, 5, 5, 5, 5, 5, 5]\n",
"✓ [5, 5, 5, 5, 5, 5, 5]\n",
"✓ [5, 5, 5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5, 5]\n",
"✓ [0, 0, 0, 0, 0, 0]\n",
"✓ [0]\n",
"✗ []\n",
"\n",
"5 shrinks with 10 function calls\n"
]
}
],
"source": [
"show_trace([5] * 10,\n",
" lambda x: x and len(x) > max(x),\n",
" multicourse_shrink3)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So that worked. Yay!\n",
"\n",
"Lets compare how this does to our single pass implementation."
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"| Condition | \n",
"Single pass | \n",
"Multi pass | \n",
"
\n",
"\n",
"\n",
" \n",
"| length >= 2 | 6 | 6 | \n",
"
\n",
" \n",
"| sum >= 500 | 35 | 35 | \n",
"
\n",
" \n",
"| sum >= 3 | 6 | 6 | \n",
"
\n",
" \n",
"| At least 10 by 5 | 107 | 73 | \n",
"
\n",
" \n",
"| 10 distinct elements | 623 | 131 | \n",
"
\n",
" \n",
"| First > Second | 1481 | 1445 | \n",
"
\n",
" \n",
"| Size > max & 63 | 600 | > 5000 | \n",
"
\n",
"\n",
"
"
],
"text/plain": [
""
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"compare_simplifiers([\n",
" (\"Single pass\", partial(greedy_shrink_with_dedupe,\n",
" shrink=shrink6)),\n",
" (\"Multi pass\", multicourse_shrink3)\n",
"\n",
"])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So the answer is generally favourably but *ouch* that last one.\n",
"\n",
"What's happening there is that because later shrinks are opening up potentially very large improvements accessible to the lower shrinks, the original greedy algorithm can exploit that much better, while the multi pass algorithm spends a lot of time in the later stages with their incremental shrinks.\n",
"\n",
"Lets see another similar example before we try to fix this:"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"import hashlib\n",
"\n",
"conditions[\"Messy\"] = lambda xs: hashlib.md5(repr(xs).encode('utf-8')).hexdigest()[0] == '0'"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"| Condition | \n",
"Single pass | \n",
"Multi pass | \n",
"
\n",
"\n",
"\n",
" \n",
"| length >= 2 | 6 | 6 | \n",
"
\n",
" \n",
"| sum >= 500 | 35 | 35 | \n",
"
\n",
" \n",
"| sum >= 3 | 6 | 6 | \n",
"
\n",
" \n",
"| At least 10 by 5 | 107 | 73 | \n",
"
\n",
" \n",
"| 10 distinct elements | 623 | 131 | \n",
"
\n",
" \n",
"| First > Second | 1481 | 1445 | \n",
"
\n",
" \n",
"| Size > max & 63 | 600 | > 5000 | \n",
"
\n",
" \n",
"| Messy | 1032 | > 5000 | \n",
"
\n",
"\n",
"
"
],
"text/plain": [
""
]
},
"execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"compare_simplifiers([\n",
" (\"Single pass\", partial(greedy_shrink_with_dedupe,\n",
" shrink=shrink6)),\n",
" (\"Multi pass\", multicourse_shrink3)\n",
"\n",
"])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This one is a bit different in that the problem is not that the structure is one we're ill suited to exploiting, it's that there is no structure at all so we have no hope of exploiting it. Literally any change at all will unlock earlier shrinks we could have done.\n",
"\n",
"What we're going to try to do is hybridize the two approaches. If we notice we're performing an awful lot of shrinks we can take that as a hint that we should be trying again from earlier stages.\n",
"\n",
"Here is our first approach. We simply restart the whole process every five shrinks:"
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"MAX_SHRINKS_PER_RUN = 2\n",
"\n",
"\n",
"def multicourse_shrink4(ls, constraint):\n",
" seen = set()\n",
" while True:\n",
" old_ls = ls\n",
" shrinks_this_run = 0\n",
" for shrink in shrinkers_for(ls):\n",
" while shrinks_this_run < MAX_SHRINKS_PER_RUN:\n",
" for s in shrink(ls):\n",
" key = tuple(s)\n",
" if key in seen:\n",
" continue\n",
" seen.add(key)\n",
" if constraint(s):\n",
" shrinks_this_run += 1\n",
" ls = s\n",
" break\n",
" else:\n",
" break\n",
" if ls == old_ls:\n",
" return ls"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"| Condition | \n",
"Single pass | \n",
"Multi pass | \n",
"Multi pass with restart | \n",
"
\n",
"\n",
"\n",
" \n",
"| length >= 2 | 6 | 6 | 6 | \n",
"
\n",
" \n",
"| sum >= 500 | 35 | 35 | 35 | \n",
"
\n",
" \n",
"| sum >= 3 | 6 | 6 | 6 | \n",
"
\n",
" \n",
"| At least 10 by 5 | 107 | 73 | 90 | \n",
"
\n",
" \n",
"| 10 distinct elements | 623 | 131 | 396 | \n",
"
\n",
" \n",
"| First > Second | 1481 | 1445 | 1463 | \n",
"
\n",
" \n",
"| Size > max & 63 | 600 | > 5000 | > 5000 | \n",
"
\n",
" \n",
"| Messy | 1032 | > 5000 | 1423 | \n",
"
\n",
"\n",
"
"
],
"text/plain": [
""
]
},
"execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"compare_simplifiers([\n",
" (\"Single pass\", partial(greedy_shrink_with_dedupe,\n",
" shrink=shrink6)),\n",
" (\"Multi pass\", multicourse_shrink3),\n",
" (\"Multi pass with restart\", multicourse_shrink4)\n",
"\n",
"])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"That works OK, but it's pretty unsatisfying as it loses us most of the benefits of the multi pass shrinking - we're now at most twice as good as the greedy one.\n",
"\n",
"So what we're going to do is bet on the multi pass working and then gradually degrade to the greedy algorithm as it fails to work."
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def multicourse_shrink5(ls, constraint):\n",
" seen = set()\n",
" max_shrinks_per_run = 10\n",
" while True:\n",
" shrinks_this_run = 0\n",
" for shrink in shrinkers_for(ls):\n",
" while shrinks_this_run < max_shrinks_per_run:\n",
" for s in shrink(ls):\n",
" key = tuple(s)\n",
" if key in seen:\n",
" continue\n",
" seen.add(key)\n",
" if constraint(s):\n",
" shrinks_this_run += 1\n",
" ls = s\n",
" break\n",
" else:\n",
" break\n",
" if max_shrinks_per_run > 1:\n",
" max_shrinks_per_run -= 2\n",
" if not shrinks_this_run:\n",
" return ls"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"✓ [5, 5, 5, 5, 5, 5, 5, 5, 5, 5]\n",
"✗ [5]\n",
"✗ [5, 5]\n",
"✗ [5, 5, 5, 5]\n",
"✓ [5, 5, 5, 5, 5, 5, 5, 5]\n",
"✓ [5, 5, 5, 5, 5, 5, 5]\n",
"✓ [5, 5, 5, 5, 5, 5]\n",
"✗ [5, 5, 5, 5, 5]\n",
"✓ [0, 0, 0, 0, 0, 0]\n",
"✓ [0]\n",
"✗ []\n",
"\n",
"5 shrinks with 10 function calls\n"
]
}
],
"source": [
"show_trace([5] * 10,\n",
" lambda x: x and len(x) > max(x),\n",
" multicourse_shrink5)"
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"| Condition | \n",
"Single pass | \n",
"Multi pass | \n",
"Multi pass with restart | \n",
"Multi pass with variable restart | \n",
"
\n",
"\n",
"\n",
" \n",
"| length >= 2 | 6 | 6 | 6 | 6 | \n",
"
\n",
" \n",
"| sum >= 500 | 35 | 35 | 35 | 35 | \n",
"
\n",
" \n",
"| sum >= 3 | 6 | 6 | 6 | 6 | \n",
"
\n",
" \n",
"| At least 10 by 5 | 107 | 73 | 90 | 73 | \n",
"
\n",
" \n",
"| 10 distinct elements | 623 | 131 | 396 | 212 | \n",
"
\n",
" \n",
"| First > Second | 1481 | 1445 | 1463 | 1168 | \n",
"
\n",
" \n",
"| Size > max & 63 | 600 | > 5000 | > 5000 | 1002 | \n",
"
\n",
" \n",
"| Messy | 1032 | > 5000 | 1423 | 824 | \n",
"
\n",
"\n",
"
"
],
"text/plain": [
""
]
},
"execution_count": 49,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"compare_simplifiers([\n",
" (\"Single pass\", partial(greedy_shrink_with_dedupe,\n",
" shrink=shrink6)),\n",
" (\"Multi pass\", multicourse_shrink3),\n",
" (\"Multi pass with restart\", multicourse_shrink4),\n",
" (\"Multi pass with variable restart\", multicourse_shrink5)\n",
"])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This is now more or less the current state of the art (it's actually a bit different from the Hypothesis state of the art at the time of this writing. I'm planning to merge some of the things I figured out in the course of writing this back in). We've got something that is able to adaptively take advantage of structure where it is present, but degrades reasonably gracefully back to the more aggressive version that works better in unstructured examples.\n",
"\n",
"Surprisingly, on some examples it seems to even be best of all of them. I think that's more coincidence than truth though."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.4.3"
}
},
"nbformat": 4,
"nbformat_minor": 0
}