src/task7/pancake-sort-creation.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 1,
   6    "metadata": {},
   7    "outputs": [],
   8    "source": [
   9     "import random\n",
  10     "import collections"
  11    ]
  12   },
  13   {
  14    "cell_type": "code",
  15    "execution_count": 2,
  16    "metadata": {},
  17    "outputs": [],
  18    "source": [
  19     "def pancake_sort(items, debug=False):\n",
  20     "    if len(items) <= 1:\n",
  21     "        if debug: print('{} -> {}: {}'.format(items, items, []))\n",
  22     "        return items, []\n",
  23     "    elif len(items) == 2:\n",
  24     "        if items[0] < items[1]:\n",
  25     "            if debug: print('{} -> {}: {}'.format(items, items, []))\n",
  26     "            return items, []\n",
  27     "        else:\n",
  28     "            if debug: print('{} -> {}: {}'.format(items, list(reversed(items)), [2]))\n",
  29     "            return list(reversed(items)), [2]\n",
  30     "    else:\n",
  31     "        largest = max(items)\n",
  32     "        largest_index = items.index(largest)\n",
  33     "        flips = []\n",
  34     "        if largest_index == len(items) - 1:\n",
  35     "            items1 = items\n",
  36     "        elif largest_index == 0:\n",
  37     "            items1 = list(reversed(items))\n",
  38     "            flips = [len(items)]\n",
  39     "        else: # largest_index > 0\n",
  40     "            items1 = list(reversed(list(reversed(items[:largest_index+1])) + items[largest_index+1:]))\n",
  41     "            flips = [largest_index + 1, len(items)]\n",
  42     "        if debug: print('{} -> {}: {}'.format(items, items1, flips))\n",
  43     "        sorted_items, sorting_flips = pancake_sort(items1[:-1], debug=debug)\n",
  44     "        return sorted_items + items1[-1:], flips + sorting_flips"
  45    ]
  46   },
  47   {
  48    "cell_type": "code",
  49    "execution_count": 3,
  50    "metadata": {},
  51    "outputs": [],
  52    "source": [
  53     "def enflip(items, flips, burnt=False, debug=False):\n",
  54     "    if debug: i0 = items\n",
  55     "    for flip in flips:\n",
  56     "        if burnt:\n",
  57     "            items = [-i for i in reversed(items[:flip])] + items[flip:]\n",
  58     "        else:\n",
  59     "            items = [i for i in reversed(items[:flip])] + items[flip:]\n",
  60     "        if debug: print('{} -{}-> {}'.format(i0, flip, items))\n",
  61     "        if debug: i0 = items\n",
  62     "    return items\n",
  63     "\n",
  64     "def unflip(items, flips, burnt=False, debug=False):\n",
  65     "    return enflip(items, reversed(flips), burnt=burnt, debug=debug)"
  66    ]
  67   },
  68   {
  69    "cell_type": "code",
  70    "execution_count": 4,
  71    "metadata": {},
  72    "outputs": [],
  73    "source": [
  74     "def pancake_adjacent(higher, lower, sorted_items):\n",
  75     "    if sorted_items.index(higher) == sorted_items.index(lower) - 1:\n",
  76     "        return True\n",
  77     "    else:\n",
  78     "        return False"
  79    ]
  80   },
  81   {
  82    "cell_type": "code",
  83    "execution_count": 5,
  84    "metadata": {},
  85    "outputs": [],
  86    "source": [
  87     "def pancake_chunks(items):\n",
  88     "    atoms = [[i] for i in items]\n",
  89     "    sorted_items = list(sorted(items))\n",
  90     "    return coalesce(atoms)"
  91    ]
  92   },
  93   {
  94    "cell_type": "code",
  95    "execution_count": 6,
  96    "metadata": {},
  97    "outputs": [],
  98    "source": [
  99     "def coalesce(chunks):\n",
 100     "    items = sorted(merge_chunks(chunks), key=abs)\n",
 101     "    i = 0\n",
 102     "    while i < (len(chunks) - 1):\n",
 103     "        last_index = items.index(chunks[i][-1])\n",
 104     "        next_index = items.index(chunks[i+1][0])\n",
 105     "        if chunks[i][-1] > 0 and chunks[i+1][0] > 0 and last_index + 1 == next_index:\n",
 106     "            chunks = chunks[:i] + [chunks[i] + chunks[i+1]] + chunks[i+2:]\n",
 107     "        elif chunks[i][-1] < 0 and chunks[i+1][0] < 0 and last_index - 1 == next_index:\n",
 108     "            chunks = chunks[:i] + [chunks[i] + chunks[i+1]] + chunks[i+2:]\n",
 109     "        else:\n",
 110     "            i += 1\n",
 111     "    return chunks"
 112    ]
 113   },
 114   {
 115    "cell_type": "code",
 116    "execution_count": 7,
 117    "metadata": {},
 118    "outputs": [],
 119    "source": [
 120     "def chunk_bases(chunks):\n",
 121     "    return [c[-1] if c[-1] > 0 else c[0] for c in chunks]"
 122    ]
 123   },
 124   {
 125    "cell_type": "code",
 126    "execution_count": 8,
 127    "metadata": {},
 128    "outputs": [],
 129    "source": [
 130     "def merge_chunks(chunks):\n",
 131     "    return [i for c in chunks for i in c]"
 132    ]
 133   },
 134   {
 135    "cell_type": "code",
 136    "execution_count": 9,
 137    "metadata": {},
 138    "outputs": [],
 139    "source": [
 140     "def chunk_count_to_item_count(chunks, cpos):\n",
 141     "#     print(chunks, cpos, chunks[:cpos])\n",
 142     "    return len(merge_chunks(chunks[:cpos]))"
 143    ]
 144   },
 145   {
 146    "cell_type": "code",
 147    "execution_count": 10,
 148    "metadata": {},
 149    "outputs": [],
 150    "source": [
 151     "def chunk_index(chunks, item):\n",
 152     "    \"\"\"Return the index of the first chunk containing item\"\"\"\n",
 153     "    return [i for i, c in enumerate(chunks) if item in c][0]"
 154    ]
 155   },
 156   {
 157    "cell_type": "code",
 158    "execution_count": 11,
 159    "metadata": {},
 160    "outputs": [],
 161    "source": [
 162     "def enflip_chunks(chunks, flips, debug=False):\n",
 163     "    if debug: c0 = chunks\n",
 164     "    for flip in flips:\n",
 165     "        chunks = [[-i for i in reversed(c)] for c in reversed(chunks[:flip])] + chunks[flip:]\n",
 166     "        if debug: print('{} ={}=> {}'.format(c0, flip, chunks))\n",
 167     "        if debug: c0 = chunks\n",
 168     "    return chunks\n",
 169     "\n",
 170     "def unflip_chunks(chunks, flips, debug=False):\n",
 171     "    return enflip(chunks, reversed(flips), debug=debug)"
 172    ]
 173   },
 174   {
 175    "cell_type": "code",
 176    "execution_count": 12,
 177    "metadata": {},
 178    "outputs": [],
 179    "source": [
 180     "def burnt_pancake_step_case1(chunks, all_chunks, items, largest, largest_burntdown, debug=False):\n",
 181     "    largest_burntdown_index = chunk_index(chunks, largest_burntdown)\n",
 182     "    if largest_burntdown == largest: # case 1(c): largest pancake is facedown, move to bottom of stack\n",
 183     "        cflips = [largest_burntdown_index + 1, len(chunks)]\n",
 184     "        flips = [items.index(largest_burntdown) + 1, len(merge_chunks(chunks))]\n",
 185     "        done_chunks = enflip_chunks(chunks, cflips, debug=debug)\n",
 186     "    else:\n",
 187     "        largest_burntdown_partner = max(i for i in chunk_bases(chunks) if abs(i) > largest_burntdown)\n",
 188     "        largest_burntdown_partner_index = chunk_index(chunks, largest_burntdown_partner)\n",
 189     "        if largest_burntdown_partner_index > largest_burntdown_index: # case 1(a): partner is lower than this\n",
 190     "            chunks1 = enflip_chunks(all_chunks, [largest_burntdown_partner_index + 1], debug=debug)\n",
 191     "            new_lb_pos = chunk_index(chunks1, -largest_burntdown)\n",
 192     "            done_chunks = enflip_chunks(chunks1, [new_lb_pos], debug=debug)\n",
 193     "            flips = [chunk_count_to_item_count(all_chunks, largest_burntdown_partner_index + 1), \n",
 194     "                     chunk_count_to_item_count(chunks1, new_lb_pos)]\n",
 195     "        else:  # case 1(b): partner is higher than this\n",
 196     "            chunks1 = enflip_chunks(chunks, [largest_burntdown_index + 1], debug=debug)\n",
 197     "            new_lbi_pos = chunk_index(chunks1, -largest_burntdown_partner)\n",
 198     "            done_chunks = enflip_chunks(chunks1, [new_lbi_pos], debug=debug)\n",
 199     "            flips = [chunk_count_to_item_count(chunks, largest_burntdown_index + 1), \n",
 200     "                     chunk_count_to_item_count(chunks1, new_lbi_pos)]\n",
 201     "    return coalesce(done_chunks), flips"
 202    ]
 203   },
 204   {
 205    "cell_type": "code",
 206    "execution_count": 13,
 207    "metadata": {},
 208    "outputs": [],
 209    "source": [
 210     "def burnt_pancake_step_case2(chunks, all_chunks, debug=False):\n",
 211     "    items = merge_chunks(chunks)\n",
 212     "    \n",
 213     "    if items == list(reversed(sorted(items))):  # invoke -I special case\n",
 214     "        if debug: print(\"2: -I\")\n",
 215     "        n = len(items)\n",
 216     "        flips = [f for fp in [[n, n-1] for _ in range(n)] for f in fp if f != 0]\n",
 217     "        done_items = enflip(items, flips, burnt=True, debug=debug)\n",
 218     "        done_chunks = pancake_chunks(done_items)\n",
 219     "    elif items == sorted(items):  # items are in reverse order, upside down\n",
 220     "        if debug: print(\"2: rev\")\n",
 221     "        flips = [len(items)]\n",
 222     "        done_items = enflip(items, flips, burnt=True, debug=debug)\n",
 223     "        done_chunks = pancake_chunks(done_items)\n",
 224     "    else:\n",
 225     "        candidates = chunk_bases(chunks)\n",
 226     "        largest_unsorted = min(candidates)\n",
 227     "        next_largest_unsorted = min(i for i in candidates if i > largest_unsorted)\n",
 228     "        largest_unsorted_index = chunk_index(chunks, largest_unsorted)\n",
 229     "        next_largest_unsorted_index = chunk_index(chunks, next_largest_unsorted)\n",
 230     "#         print(largest_unsorted, next_largest_unsorted, largest_unsorted_index, next_largest_unsorted_index)\n",
 231     "        while next_largest_unsorted_index > largest_unsorted_index:\n",
 232     "            largest_unsorted = next_largest_unsorted\n",
 233     "            largest_unsorted_index = next_largest_unsorted_index\n",
 234     "            next_largest_unsorted = min(i for i in candidates if i > largest_unsorted)\n",
 235     "            next_largest_unsorted_index = chunk_index(chunks, next_largest_unsorted)\n",
 236     "        if debug: print(\"2: general, lu = {}, nlu = {}\".format(largest_unsorted, next_largest_unsorted))\n",
 237     "        chunks1 = enflip_chunks(chunks, [largest_unsorted_index + 1])\n",
 238     "        done_chunks = enflip_chunks(chunks1, [next_largest_unsorted_index], debug=debug)\n",
 239     "#         cflips = [largest_unsorted_index + 1, next_largest_unsorted_index]\n",
 240     "        flips = [chunk_count_to_item_count(chunks, largest_unsorted_index + 1), \n",
 241     "                     chunk_count_to_item_count(chunks1, next_largest_unsorted_index)]\n",
 242     "#         done_chunks = enflip_chunks(chunks, cflips, debug=debug)\n",
 243     "    return coalesce(done_chunks), flips"
 244    ]
 245   },
 246   {
 247    "cell_type": "code",
 248    "execution_count": 14,
 249    "metadata": {},
 250    "outputs": [],
 251    "source": [
 252     "def burnt_pancake_step(chunks0, items, debug=False):\n",
 253     "    chunks = chunks0\n",
 254     "    largest = max(abs(i) for c in chunks for i in c)\n",
 255     "    while chunks[-1][-1] >= largest:\n",
 256     "        chunks = chunks[:-1]\n",
 257     "        largest = max(abs(i[-1]) for i in chunks)\n",
 258     "    largest_burntdown = max(merge_chunks(chunks))\n",
 259     "    if debug: print('<<', chunks, chunks0, items, largest, largest_burntdown)\n",
 260     "    if largest_burntdown > 0:\n",
 261     "        return burnt_pancake_step_case1(chunks, chunks0, items, largest, largest_burntdown, debug=debug)\n",
 262     "    else:\n",
 263     "        return burnt_pancake_step_case2(chunks, chunks0, debug=debug)"
 264    ]
 265   },
 266   {
 267    "cell_type": "code",
 268    "execution_count": 15,
 269    "metadata": {},
 270    "outputs": [],
 271    "source": [
 272     "def burnt_pancake_sort(items, fudge_rate=0, debug=False):\n",
 273     "    flips = []\n",
 274     "    flip_limit = len(items) * 3\n",
 275     "    items0 = items\n",
 276     "    chunks = pancake_chunks(items)\n",
 277     "    while (any(i for i in items if i < 0) or sorted(items) != items) and len(flips) < flip_limit:\n",
 278     "        chunks, these_flips = burnt_pancake_step(chunks, items, debug=debug)\n",
 279     "        if debug: print('Got chunks:', chunks)\n",
 280     "        items = merge_chunks(chunks)\n",
 281     "        flips += these_flips\n",
 282     "        if random.random() < fudge_rate:\n",
 283     "            if debug: c_old = chunks\n",
 284     "            its = [abs(i) for i in merge_chunks(chunks)]\n",
 285     "            eits = sorted(i for i in items0 if i not in its)\n",
 286     "            chunks = coalesce(pancake_chunks(its + eits))\n",
 287     "            items = its + eits\n",
 288     "            if debug: print('!! Fudge: Converting {} to {}'.format(c_old, chunks))\n",
 289     "    return items, flips"
 290    ]
 291   },
 292   {
 293    "cell_type": "code",
 294    "execution_count": 16,
 295    "metadata": {},
 296    "outputs": [],
 297    "source": [
 298     "def equiv_case(base_unsorted, flips, burnt=False, max_value=10000):\n",
 299     "#     new_sample = random.sample(list(range(1, max_value)), k=len(base_unsorted))\n",
 300     "    valid = False\n",
 301     "    while not valid:\n",
 302     "        new_sample = random.sample(list(range(1, max_value)), k=len(base_unsorted))\n",
 303     "        valid = len(new_sample) == len(base_unsorted)\n",
 304     "    sample = sorted(new_sample)\n",
 305     "    return unflip(sample, flips, burnt=burnt)"
 306    ]
 307   },
 308   {
 309    "cell_type": "code",
 310    "execution_count": 17,
 311    "metadata": {},
 312    "outputs": [],
 313    "source": [
 314     "def burnt_sorted(pancakes):\n",
 315     "    return pancakes == sorted(pancakes)\n",
 316     "\n",
 317     "def unburnt_sorted(pancakes):\n",
 318     "    simple_pancakes = [abs(p) for p in pancakes]\n",
 319     "    return simple_pancakes == sorted(simple_pancakes)"
 320    ]
 321   },
 322   {
 323    "cell_type": "code",
 324    "execution_count": 18,
 325    "metadata": {},
 326    "outputs": [],
 327    "source": [
 328     "def inverted_count(pancakes):\n",
 329     "    return sum(1 for p in pancakes if p < 0)"
 330    ]
 331   },
 332   {
 333    "cell_type": "code",
 334    "execution_count": 19,
 335    "metadata": {},
 336    "outputs": [],
 337    "source": [
 338     "def cache_flips(start, flips, burnt=False):\n",
 339     "    positions = [{'pos': start}]\n",
 340     "    stack = start\n",
 341     "    for f in flips:\n",
 342     "        stack = enflip(stack, [f], burnt=burnt)\n",
 343     "        positions += [{'pos': stack, 'move': f}]\n",
 344     "    return positions"
 345    ]
 346   },
 347   {
 348    "cell_type": "code",
 349    "execution_count": 20,
 350    "metadata": {},
 351    "outputs": [],
 352    "source": [
 353     "def show_cached_flips(cache):\n",
 354     "    rows = len(cache[0]['pos'])\n",
 355     "    middle_row = (rows) // 2\n",
 356     "    for r in range(rows):\n",
 357     "        for c in cache:\n",
 358     "            if r == middle_row and 'move' in c:\n",
 359     "                print(' -{}-> '.format(c['move']), end='')\n",
 360     "            elif 'move' in c:\n",
 361     "                print('      ', end='')\n",
 362     "            if c['pos'][r] > 0:\n",
 363     "                print('{:2d} '.format(c['pos'][r]), end='')\n",
 364     "            else:\n",
 365     "                print('{:2d}*'.format(abs(c['pos'][r])), end='')\n",
 366     "        print('')"
 367    ]
 368   },
 369   {
 370    "cell_type": "markdown",
 371    "metadata": {},
 372    "source": [
 373     "Approach to developing test cases:\n",
 374     "\n",
 375     "1. Find a random pancake stack.\n",
 376     "2. Find the burnt pancake sort of that stack: `burnt_flips`\n",
 377     "3. Find an equivalent case for those flips: `pancakes`\n",
 378     "4. Find a bunch of fudged burnt sorts of the `pancakes`: `fudged`\n",
 379     "5. Find a bunch of random fudged pancake sorts: `padding`\n",
 380     "\n",
 381     "To assemble the test case, join together:\n",
 382     "* the `burnt_flips`\n",
 383     "* some `fudged`\n",
 384     "* enough `padding` to make a round number."
 385    ]
 386   },
 387   {
 388    "cell_type": "code",
 389    "execution_count": 21,
 390    "metadata": {},
 391    "outputs": [
 392     {
 393      "data": {
 394       "text/plain": [
 395        "4"
 396       ]
 397      },
 398      "execution_count": 21,
 399      "metadata": {},
 400      "output_type": "execute_result"
 401     }
 402    ],
 403    "source": [
 404     "ln = 50\n",
 405     "n_equivs = 100\n",
 406     "fudge_rate = 0.3\n",
 407     "\n",
 408     "start = [i for i in random.sample(list(range(1, ln+1)), k=ln)]\n",
 409     "test_flips = {}\n",
 410     "_, test_flips['burnt_flips'] = burnt_pancake_sort(start)\n",
 411     "test_flips['pancakes'] = equiv_case(start, test_flips['burnt_flips'], burnt=True)\n",
 412     "test_flips['fudged'] = [burnt_pancake_sort(start, fudge_rate=fudge_rate)[1] for _ in range(n_equivs)]\n",
 413     "test_flips['padding'] = [burnt_pancake_sort(random.sample(list(range(1, ln+1)), k=ln), fudge_rate=fudge_rate)[1] for _ in range(n_equivs)]\n",
 414     "len(test_flips)"
 415    ]
 416   },
 417   {
 418    "cell_type": "code",
 419    "execution_count": 22,
 420    "metadata": {},
 421    "outputs": [
 422     {
 423      "data": {
 424       "text/plain": [
 425        "99"
 426       ]
 427      },
 428      "execution_count": 22,
 429      "metadata": {},
 430      "output_type": "execute_result"
 431     }
 432    ],
 433    "source": [
 434     "test_data = [test_flips['burnt_flips']]\n",
 435     "test_data.extend(random.sample(test_flips['fudged'], k=random.randint(50, 70)))\n",
 436     "test_data.extend(random.sample(test_flips['padding'], k=(99-len(test_data))))\n",
 437     "len(test_data)"
 438    ]
 439   },
 440   {
 441    "cell_type": "code",
 442    "execution_count": 23,
 443    "metadata": {},
 444    "outputs": [],
 445    "source": [
 446     "random.shuffle(test_data)"
 447    ]
 448   },
 449   {
 450    "cell_type": "code",
 451    "execution_count": 24,
 452    "metadata": {},
 453    "outputs": [
 454     {
 455      "data": {
 456       "text/plain": [
 457        "55"
 458       ]
 459      },
 460      "execution_count": 24,
 461      "metadata": {},
 462      "output_type": "execute_result"
 463     }
 464    ],
 465    "source": [
 466     "sum(1 for f in test_data\n",
 467     "   if unburnt_sorted(\n",
 468     "       enflip(test_flips['pancakes'], f, burnt=False)))"
 469    ]
 470   },
 471   {
 472    "cell_type": "code",
 473    "execution_count": 25,
 474    "metadata": {},
 475    "outputs": [
 476     {
 477      "data": {
 478       "text/plain": [
 479        "1"
 480       ]
 481      },
 482      "execution_count": 25,
 483      "metadata": {},
 484      "output_type": "execute_result"
 485     }
 486    ],
 487    "source": [
 488     "sum(1 for f in test_data\n",
 489     "   if burnt_sorted(\n",
 490     "       enflip(test_flips['pancakes'], f, burnt=True)))"
 491    ]
 492   },
 493   {
 494    "cell_type": "code",
 495    "execution_count": 26,
 496    "metadata": {},
 497    "outputs": [
 498     {
 499      "data": {
 500       "text/plain": [
 501        "[61]"
 502       ]
 503      },
 504      "execution_count": 26,
 505      "metadata": {},
 506      "output_type": "execute_result"
 507     }
 508    ],
 509    "source": [
 510     "[i+1 for i, f in enumerate(test_data)\n",
 511     "   if burnt_sorted(\n",
 512     "       enflip(test_flips['pancakes'], f, burnt=True))]"
 513    ]
 514   },
 515   {
 516    "cell_type": "code",
 517    "execution_count": 27,
 518    "metadata": {},
 519    "outputs": [],
 520    "source": [
 521     "# random.shuffle(test_data)\n",
 522     "# with open('07-flips.txt', 'w') as tdf:\n",
 523     "#     tdf.write('burgers: {}\\n'.format(' '.join(str(i) for i in test_flips['pancakes'] if i > 0)))\n",
 524     "#     for i, c in enumerate(test_data):\n",
 525     "#         tdf.write('{:02}: {}\\n'.format(i+1, ' '.join(str(i) for i in c if i > 0)))"
 526    ]
 527   },
 528   {
 529    "cell_type": "code",
 530    "execution_count": null,
 531    "metadata": {},
 532    "outputs": [],
 533    "source": []
 534   },
 535   {
 536    "cell_type": "markdown",
 537    "metadata": {},
 538    "source": [
 539     "# Example cases"
 540    ]
 541   },
 542   {
 543    "cell_type": "code",
 544    "execution_count": 28,
 545    "metadata": {},
 546    "outputs": [
 547     {
 548      "data": {
 549       "text/plain": [
 550        "{'burnt_flips': [5, 6, 2, 1, 2, 5, 3, 2, 3, 2, 3, 2],\n",
 551        " 'pancakes': [8, 7, 5, 4, 11, 9],\n",
 552        " 'fudged': [[5, 6, 1, 5, 4, 3, 4, 3, 4, 3, 4, 3],\n",
 553        "  [5, 6, 1, 5, 4, 3, 4, 3, 4, 3, 4, 3],\n",
 554        "  [5, 6, 2, 1, 2, 5],\n",
 555        "  [5, 6, 1, 5],\n",
 556        "  [5, 6, 1, 5, 4, 3, 4, 3, 4, 3, 4, 3]],\n",
 557        " 'padding': [[1, 6, 5],\n",
 558        "  [5, 6, 1, 4, 1, 2],\n",
 559        "  [1, 6, 5, 0, 4, 5, 2, 4, 2, 1, 2, 1],\n",
 560        "  [2, 6, 2, 5, 2, 3, 1, 2],\n",
 561        "  [2, 6, 4, 0, 1, 4, 1, 3, 1, 2]]}"
 562       ]
 563      },
 564      "execution_count": 28,
 565      "metadata": {},
 566      "output_type": "execute_result"
 567     }
 568    ],
 569    "source": [
 570     "ln = 6\n",
 571     "n_equivs = 5\n",
 572     "fudge_rate = 0.7\n",
 573     "\n",
 574     "start = [i for i in random.sample(list(range(1, ln+1)), k=ln)]\n",
 575     "test_flips = {}\n",
 576     "_, test_flips['burnt_flips'] = burnt_pancake_sort(start)\n",
 577     "test_flips['pancakes'] = equiv_case(start, test_flips['burnt_flips'], burnt=True, max_value=ln*2)\n",
 578     "test_flips['fudged'] = [burnt_pancake_sort(start, fudge_rate=fudge_rate)[1] for _ in range(n_equivs)]\n",
 579     "test_flips['padding'] = [burnt_pancake_sort(random.sample(list(range(1, ln+1)), k=ln), fudge_rate=fudge_rate)[1] for _ in range(n_equivs)]\n",
 580     "test_flips"
 581    ]
 582   },
 583   {
 584    "cell_type": "code",
 585    "execution_count": 29,
 586    "metadata": {},
 587    "outputs": [],
 588    "source": [
 589     "# test_flips = {'burnt_flips': [4, 5, 2, 1, 2, 3, 1],\n",
 590     "#  'fudged': [[4, 5, 2, 1, 2, 3],\n",
 591     "#   [4, 5, 1, 3, 2, 1, 2, 1],\n",
 592     "#   [4, 5, 1, 3, 2, 1, 2, 1],\n",
 593     "#   [4, 5, 1, 3],\n",
 594     "#   [4, 5, 2, 1, 2, 3, 1]],\n",
 595     "#  'padding': [[2, 5, 1, 2],\n",
 596     "#   [2, 5, 2, 1, 3],\n",
 597     "#   [1, 3, 1, 2, 1],\n",
 598     "#   [2, 5, 4, 1, 2, 3],\n",
 599     "#   [4, 5, 3, 4, 3, 1]],\n",
 600     "#  'pancakes': [4, 2, 6, 7, 5]}"
 601    ]
 602   },
 603   {
 604    "cell_type": "code",
 605    "execution_count": 30,
 606    "metadata": {},
 607    "outputs": [],
 608    "source": [
 609     "test_flips = {'burnt_flips': [3, 5, 3, 2, 3, 2],\n",
 610     " 'pancakes': [9, 18, 22, 15, 13],\n",
 611     " 'fudged': [[3, 5, 2, 3],\n",
 612     "  [3, 5, 2, 3],\n",
 613     "  [3, 5, 2, 3],\n",
 614     "  [3, 5, 2, 3],\n",
 615     "  [3, 5, 2, 3]],\n",
 616     " 'padding': [[4, 5, 3, 4, 2, 3],\n",
 617     "  [3],\n",
 618     "  [3, 5, 4, 2, 3, 4, 2],\n",
 619     "  [2, 5, 2, 3, 2],\n",
 620     "  [3, 5, 3]]}"
 621    ]
 622   },
 623   {
 624    "cell_type": "code",
 625    "execution_count": 31,
 626    "metadata": {},
 627    "outputs": [
 628     {
 629      "data": {
 630       "text/plain": [
 631        "[3, 5, 3, 2, 3, 2]"
 632       ]
 633      },
 634      "execution_count": 31,
 635      "metadata": {},
 636      "output_type": "execute_result"
 637     }
 638    ],
 639    "source": [
 640     "bf = [f for f in test_flips['burnt_flips'] if f > 0]\n",
 641     "bf"
 642    ]
 643   },
 644   {
 645    "cell_type": "code",
 646    "execution_count": 32,
 647    "metadata": {},
 648    "outputs": [
 649     {
 650      "data": {
 651       "text/plain": [
 652        "[9, 13, 15, 18, 22]"
 653       ]
 654      },
 655      "execution_count": 32,
 656      "metadata": {},
 657      "output_type": "execute_result"
 658     }
 659    ],
 660    "source": [
 661     "enflip(test_flips['pancakes'], test_flips['burnt_flips'], burnt=True)"
 662    ]
 663   },
 664   {
 665    "cell_type": "code",
 666    "execution_count": 33,
 667    "metadata": {},
 668    "outputs": [
 669     {
 670      "data": {
 671       "text/plain": [
 672        "[-9, -13, -15, 18, 22]"
 673       ]
 674      },
 675      "execution_count": 33,
 676      "metadata": {},
 677      "output_type": "execute_result"
 678     }
 679    ],
 680    "source": [
 681     "enflip(test_flips['pancakes'], test_flips['fudged'][0], burnt=True)"
 682    ]
 683   },
 684   {
 685    "cell_type": "code",
 686    "execution_count": 34,
 687    "metadata": {},
 688    "outputs": [
 689     {
 690      "data": {
 691       "text/plain": [
 692        "[9, 13, 15, 18, 22]"
 693       ]
 694      },
 695      "execution_count": 34,
 696      "metadata": {},
 697      "output_type": "execute_result"
 698     }
 699    ],
 700    "source": [
 701     "enflip(test_flips['pancakes'], bf, burnt=True)"
 702    ]
 703   },
 704   {
 705    "cell_type": "code",
 706    "execution_count": 35,
 707    "metadata": {},
 708    "outputs": [
 709     {
 710      "name": "stdout",
 711      "output_type": "stream",
 712      "text": [
 713       " 9       22       13        9       15       13        9 \n",
 714       "18       18       15       15        9        9       13 \n",
 715       "22  -3->  9  -5->  9  -3-> 13  -2-> 13  -3-> 15  -2-> 15 \n",
 716       "15       15       18       18       18       18       18 \n",
 717       "13       13       22       22       22       22       22 \n"
 718      ]
 719     }
 720    ],
 721    "source": [
 722     "show_cached_flips(cache_flips(test_flips['pancakes'], bf))"
 723    ]
 724   },
 725   {
 726    "cell_type": "code",
 727    "execution_count": 36,
 728    "metadata": {},
 729    "outputs": [
 730     {
 731      "name": "stdout",
 732      "output_type": "stream",
 733      "text": [
 734       " 9 \n",
 735       "18 \n",
 736       "22 \n",
 737       "15 \n",
 738       "13 \n"
 739      ]
 740     }
 741    ],
 742    "source": [
 743     "show_cached_flips(cache_flips(test_flips['pancakes'], bf)[:1])"
 744    ]
 745   },
 746   {
 747    "cell_type": "code",
 748    "execution_count": 37,
 749    "metadata": {},
 750    "outputs": [
 751     {
 752      "name": "stdout",
 753      "output_type": "stream",
 754      "text": [
 755       " 9       22 \n",
 756       "18       18 \n",
 757       "22  -3->  9 \n",
 758       "15       15 \n",
 759       "13       13 \n"
 760      ]
 761     }
 762    ],
 763    "source": [
 764     "show_cached_flips(cache_flips(test_flips['pancakes'], bf)[:2])"
 765    ]
 766   },
 767   {
 768    "cell_type": "code",
 769    "execution_count": 38,
 770    "metadata": {},
 771    "outputs": [
 772     {
 773      "name": "stdout",
 774      "output_type": "stream",
 775      "text": [
 776       " 9       22*      13*       9*      15*      13*       9 \n",
 777       "18       18*      15*      15        9        9*      13 \n",
 778       "22  -3->  9* -5->  9  -3-> 13  -2-> 13  -3-> 15  -2-> 15 \n",
 779       "15       15       18       18       18       18       18 \n",
 780       "13       13       22       22       22       22       22 \n"
 781      ]
 782     }
 783    ],
 784    "source": [
 785     "show_cached_flips(cache_flips(test_flips['pancakes'], bf, burnt=True))"
 786    ]
 787   },
 788   {
 789    "cell_type": "code",
 790    "execution_count": 39,
 791    "metadata": {},
 792    "outputs": [
 793     {
 794      "name": "stdout",
 795      "output_type": "stream",
 796      "text": [
 797       " 9 \n",
 798       "18 \n",
 799       "22 \n",
 800       "15 \n",
 801       "13 \n"
 802      ]
 803     }
 804    ],
 805    "source": [
 806     "show_cached_flips(cache_flips(test_flips['pancakes'], test_flips['fudged'][0], burnt=False)[:1])"
 807    ]
 808   },
 809   {
 810    "cell_type": "code",
 811    "execution_count": 40,
 812    "metadata": {},
 813    "outputs": [
 814     {
 815      "name": "stdout",
 816      "output_type": "stream",
 817      "text": [
 818       " 9       22 \n",
 819       "18       18 \n",
 820       "22  -3->  9 \n",
 821       "15       15 \n",
 822       "13       13 \n"
 823      ]
 824     }
 825    ],
 826    "source": [
 827     "show_cached_flips(cache_flips(test_flips['pancakes'], test_flips['fudged'][0], burnt=False)[:2])"
 828    ]
 829   },
 830   {
 831    "cell_type": "code",
 832    "execution_count": 41,
 833    "metadata": {},
 834    "outputs": [
 835     {
 836      "name": "stdout",
 837      "output_type": "stream",
 838      "text": [
 839       " 9       22       13       15        9 \n",
 840       "18       18       15       13       13 \n",
 841       "22  -3->  9  -5->  9  -2->  9  -3-> 15 \n",
 842       "15       15       18       18       18 \n",
 843       "13       13       22       22       22 \n"
 844      ]
 845     }
 846    ],
 847    "source": [
 848     "show_cached_flips(cache_flips(test_flips['pancakes'], test_flips['fudged'][0], burnt=False))"
 849    ]
 850   },
 851   {
 852    "cell_type": "code",
 853    "execution_count": 42,
 854    "metadata": {},
 855    "outputs": [
 856     {
 857      "name": "stdout",
 858      "output_type": "stream",
 859      "text": [
 860       " 9       22*      13*      15        9*\n",
 861       "18       18*      15*      13       13*\n",
 862       "22  -3->  9* -5->  9  -2->  9  -3-> 15*\n",
 863       "15       15       18       18       18 \n",
 864       "13       13       22       22       22 \n"
 865      ]
 866     }
 867    ],
 868    "source": [
 869     "show_cached_flips(cache_flips(test_flips['pancakes'], test_flips['fudged'][0], burnt=True))"
 870    ]
 871   },
 872   {
 873    "cell_type": "code",
 874    "execution_count": 43,
 875    "metadata": {},
 876    "outputs": [
 877     {
 878      "name": "stdout",
 879      "output_type": "stream",
 880      "text": [
 881       " 9       22*      13*      15        9*\n",
 882       "18       18*      15*      13       13*\n",
 883       "22  -3->  9* -5->  9  -2->  9  -3-> 15*\n",
 884       "15       15       18       18       18 \n",
 885       "13       13       22       22       22 \n"
 886      ]
 887     }
 888    ],
 889    "source": [
 890     "show_cached_flips(cache_flips(test_flips['pancakes'], test_flips['fudged'][1], burnt=True))"
 891    ]
 892   },
 893   {
 894    "cell_type": "code",
 895    "execution_count": 44,
 896    "metadata": {},
 897    "outputs": [
 898     {
 899      "name": "stdout",
 900      "output_type": "stream",
 901      "text": [
 902       " 9       22       13       15        9 \n",
 903       "18       18       15       13       13 \n",
 904       "22  -3->  9  -5->  9  -2->  9  -3-> 15 \n",
 905       "15       15       18       18       18 \n",
 906       "13       13       22       22       22 \n"
 907      ]
 908     }
 909    ],
 910    "source": [
 911     "show_cached_flips(cache_flips(test_flips['pancakes'], test_flips['fudged'][3], burnt=False))"
 912    ]
 913   },
 914   {
 915    "cell_type": "code",
 916    "execution_count": 45,
 917    "metadata": {},
 918    "outputs": [
 919     {
 920      "name": "stdout",
 921      "output_type": "stream",
 922      "text": [
 923       " 9       22*      13*      15        9*\n",
 924       "18       18*      15*      13       13*\n",
 925       "22  -3->  9* -5->  9  -2->  9  -3-> 15*\n",
 926       "15       15       18       18       18 \n",
 927       "13       13       22       22       22 \n"
 928      ]
 929     }
 930    ],
 931    "source": [
 932     "show_cached_flips(cache_flips(test_flips['pancakes'], test_flips['fudged'][3], burnt=True))"
 933    ]
 934   },
 935   {
 936    "cell_type": "code",
 937    "execution_count": 46,
 938    "metadata": {},
 939    "outputs": [
 940     {
 941      "name": "stdout",
 942      "output_type": "stream",
 943      "text": [
 944       " 9       15       13       18       22       13        9 \n",
 945       "18       22        9        9       13       22       22 \n",
 946       "22  -4-> 18  -5-> 18  -3-> 13  -4->  9  -2->  9  -3-> 13 \n",
 947       "15        9       22       22       18       18       18 \n",
 948       "13       13       15       15       15       15       15 \n"
 949      ]
 950     }
 951    ],
 952    "source": [
 953     "show_cached_flips(cache_flips(test_flips['pancakes'], test_flips['padding'][0]))"
 954    ]
 955   },
 956   {
 957    "cell_type": "code",
 958    "execution_count": 47,
 959    "metadata": {},
 960    "outputs": [
 961     {
 962      "name": "stdout",
 963      "output_type": "stream",
 964      "text": [
 965       " 9       18       13       15       22       13 \n",
 966       "18        9       15       13       13       22 \n",
 967       "22  -2-> 22  -5-> 22  -2-> 22  -3-> 15  -2-> 15 \n",
 968       "15       15        9        9        9        9 \n",
 969       "13       13       18       18       18       18 \n"
 970      ]
 971     }
 972    ],
 973    "source": [
 974     "show_cached_flips(cache_flips(test_flips['pancakes'], test_flips['padding'][3]))"
 975    ]
 976   },
 977   {
 978    "cell_type": "code",
 979    "execution_count": 48,
 980    "metadata": {},
 981    "outputs": [
 982     {
 983      "data": {
 984       "text/plain": [
 985        "10"
 986       ]
 987      },
 988      "execution_count": 48,
 989      "metadata": {},
 990      "output_type": "execute_result"
 991     }
 992    ],
 993    "source": [
 994     "example_data = [test_flips['burnt_flips']]\n",
 995     "example_data.extend(random.sample(test_flips['fudged'], k=4))\n",
 996     "example_data.extend(random.sample(test_flips['padding'], k=5))\n",
 997     "len(example_data)"
 998    ]
 999   },
1000   {
1001    "cell_type": "code",
1002    "execution_count": 49,
1003    "metadata": {},
1004    "outputs": [],
1005    "source": [
1006     "random.shuffle(example_data)\n",
1007     "with open('07-example.txt', 'w') as tdf:\n",
1008     "    tdf.write('burgers: {}\\n'.format(' '.join(str(i) for i in test_flips['pancakes'] if i > 0)))\n",
1009     "    for i, c in enumerate(example_data):\n",
1010     "        tdf.write('{:02}: {}\\n'.format(i+1, ' '.join(str(i) for i in c if i > 0)))"
1011    ]
1012   },
1013   {
1014    "cell_type": "code",
1015    "execution_count": null,
1016    "metadata": {},
1017    "outputs": [],
1018    "source": []
1019   }
1020  ],
1021  "metadata": {
1022   "kernelspec": {
1023    "display_name": "Python 3",
1024    "language": "python",
1025    "name": "python3"
1026   },
1027   "language_info": {
1028    "codemirror_mode": {
1029     "name": "ipython",
1030     "version": 3
1031    },
1032    "file_extension": ".py",
1033    "mimetype": "text/x-python",
1034    "name": "python",
1035    "nbconvert_exporter": "python",
1036    "pygments_lexer": "ipython3",
1037    "version": "3.6.6"
1038   }
1039  },
1040  "nbformat": 4,
1041  "nbformat_minor": 2
1042 }