From 3916abfa63f3d32c364f31dbf1388fc0e059ca79 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Sat, 6 Oct 2018 20:46:42 +0100 Subject: [PATCH] Added pancake sort creation --- src/task7/07-example.txt | 11 + src/task7/pancake-sort-creation.ipynb | 1042 +++++++++++++++++++++++++ 2 files changed, 1053 insertions(+) create mode 100644 src/task7/07-example.txt create mode 100644 src/task7/pancake-sort-creation.ipynb diff --git a/src/task7/07-example.txt b/src/task7/07-example.txt new file mode 100644 index 0000000..4a55c1b --- /dev/null +++ b/src/task7/07-example.txt @@ -0,0 +1,11 @@ +burgers: 9 18 22 15 13 +01: 3 5 2 3 +02: 3 5 3 +03: 3 5 3 2 3 2 +04: 3 5 2 3 +05: 2 5 2 3 2 +06: 3 +07: 3 5 2 3 +08: 3 5 2 3 +09: 3 5 4 2 3 4 2 +10: 4 5 3 4 2 3 diff --git a/src/task7/pancake-sort-creation.ipynb b/src/task7/pancake-sort-creation.ipynb new file mode 100644 index 0000000..cf56e53 --- /dev/null +++ b/src/task7/pancake-sort-creation.ipynb @@ -0,0 +1,1042 @@ +{ + "cells": [ + { + "cell_type": "code", + "execution_count": 1, + "metadata": {}, + "outputs": [], + "source": [ + "import random\n", + "import collections" + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "metadata": {}, + "outputs": [], + "source": [ + "def pancake_sort(items, debug=False):\n", + " if len(items) <= 1:\n", + " if debug: print('{} -> {}: {}'.format(items, items, []))\n", + " return items, []\n", + " elif len(items) == 2:\n", + " if items[0] < items[1]:\n", + " if debug: print('{} -> {}: {}'.format(items, items, []))\n", + " return items, []\n", + " else:\n", + " if debug: print('{} -> {}: {}'.format(items, list(reversed(items)), [2]))\n", + " return list(reversed(items)), [2]\n", + " else:\n", + " largest = max(items)\n", + " largest_index = items.index(largest)\n", + " flips = []\n", + " if largest_index == len(items) - 1:\n", + " items1 = items\n", + " elif largest_index == 0:\n", + " items1 = list(reversed(items))\n", + " flips = [len(items)]\n", + " else: # largest_index > 0\n", + " items1 = list(reversed(list(reversed(items[:largest_index+1])) + items[largest_index+1:]))\n", + " flips = [largest_index + 1, len(items)]\n", + " if debug: print('{} -> {}: {}'.format(items, items1, flips))\n", + " sorted_items, sorting_flips = pancake_sort(items1[:-1], debug=debug)\n", + " return sorted_items + items1[-1:], flips + sorting_flips" + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "metadata": {}, + "outputs": [], + "source": [ + "def enflip(items, flips, burnt=False, debug=False):\n", + " if debug: i0 = items\n", + " for flip in flips:\n", + " if burnt:\n", + " items = [-i for i in reversed(items[:flip])] + items[flip:]\n", + " else:\n", + " items = [i for i in reversed(items[:flip])] + items[flip:]\n", + " if debug: print('{} -{}-> {}'.format(i0, flip, items))\n", + " if debug: i0 = items\n", + " return items\n", + "\n", + "def unflip(items, flips, burnt=False, debug=False):\n", + " return enflip(items, reversed(flips), burnt=burnt, debug=debug)" + ] + }, + { + "cell_type": "code", + "execution_count": 4, + "metadata": {}, + "outputs": [], + "source": [ + "def pancake_adjacent(higher, lower, sorted_items):\n", + " if sorted_items.index(higher) == sorted_items.index(lower) - 1:\n", + " return True\n", + " else:\n", + " return False" + ] + }, + { + "cell_type": "code", + "execution_count": 5, + "metadata": {}, + "outputs": [], + "source": [ + "def pancake_chunks(items):\n", + " atoms = [[i] for i in items]\n", + " sorted_items = list(sorted(items))\n", + " return coalesce(atoms)" + ] + }, + { + "cell_type": "code", + "execution_count": 6, + "metadata": {}, + "outputs": [], + "source": [ + "def coalesce(chunks):\n", + " items = sorted(merge_chunks(chunks), key=abs)\n", + " i = 0\n", + " while i < (len(chunks) - 1):\n", + " last_index = items.index(chunks[i][-1])\n", + " next_index = items.index(chunks[i+1][0])\n", + " if chunks[i][-1] > 0 and chunks[i+1][0] > 0 and last_index + 1 == next_index:\n", + " chunks = chunks[:i] + [chunks[i] + chunks[i+1]] + chunks[i+2:]\n", + " elif chunks[i][-1] < 0 and chunks[i+1][0] < 0 and last_index - 1 == next_index:\n", + " chunks = chunks[:i] + [chunks[i] + chunks[i+1]] + chunks[i+2:]\n", + " else:\n", + " i += 1\n", + " return chunks" + ] + }, + { + "cell_type": "code", + "execution_count": 7, + "metadata": {}, + "outputs": [], + "source": [ + "def chunk_bases(chunks):\n", + " return [c[-1] if c[-1] > 0 else c[0] for c in chunks]" + ] + }, + { + "cell_type": "code", + "execution_count": 8, + "metadata": {}, + "outputs": [], + "source": [ + "def merge_chunks(chunks):\n", + " return [i for c in chunks for i in c]" + ] + }, + { + "cell_type": "code", + "execution_count": 9, + "metadata": {}, + "outputs": [], + "source": [ + "def chunk_count_to_item_count(chunks, cpos):\n", + "# print(chunks, cpos, chunks[:cpos])\n", + " return len(merge_chunks(chunks[:cpos]))" + ] + }, + { + "cell_type": "code", + "execution_count": 10, + "metadata": {}, + "outputs": [], + "source": [ + "def chunk_index(chunks, item):\n", + " \"\"\"Return the index of the first chunk containing item\"\"\"\n", + " return [i for i, c in enumerate(chunks) if item in c][0]" + ] + }, + { + "cell_type": "code", + "execution_count": 11, + "metadata": {}, + "outputs": [], + "source": [ + "def enflip_chunks(chunks, flips, debug=False):\n", + " if debug: c0 = chunks\n", + " for flip in flips:\n", + " chunks = [[-i for i in reversed(c)] for c in reversed(chunks[:flip])] + chunks[flip:]\n", + " if debug: print('{} ={}=> {}'.format(c0, flip, chunks))\n", + " if debug: c0 = chunks\n", + " return chunks\n", + "\n", + "def unflip_chunks(chunks, flips, debug=False):\n", + " return enflip(chunks, reversed(flips), debug=debug)" + ] + }, + { + "cell_type": "code", + "execution_count": 12, + "metadata": {}, + "outputs": [], + "source": [ + "def burnt_pancake_step_case1(chunks, all_chunks, items, largest, largest_burntdown, debug=False):\n", + " largest_burntdown_index = chunk_index(chunks, largest_burntdown)\n", + " if largest_burntdown == largest: # case 1(c): largest pancake is facedown, move to bottom of stack\n", + " cflips = [largest_burntdown_index + 1, len(chunks)]\n", + " flips = [items.index(largest_burntdown) + 1, len(merge_chunks(chunks))]\n", + " done_chunks = enflip_chunks(chunks, cflips, debug=debug)\n", + " else:\n", + " largest_burntdown_partner = max(i for i in chunk_bases(chunks) if abs(i) > largest_burntdown)\n", + " largest_burntdown_partner_index = chunk_index(chunks, largest_burntdown_partner)\n", + " if largest_burntdown_partner_index > largest_burntdown_index: # case 1(a): partner is lower than this\n", + " chunks1 = enflip_chunks(all_chunks, [largest_burntdown_partner_index + 1], debug=debug)\n", + " new_lb_pos = chunk_index(chunks1, -largest_burntdown)\n", + " done_chunks = enflip_chunks(chunks1, [new_lb_pos], debug=debug)\n", + " flips = [chunk_count_to_item_count(all_chunks, largest_burntdown_partner_index + 1), \n", + " chunk_count_to_item_count(chunks1, new_lb_pos)]\n", + " else: # case 1(b): partner is higher than this\n", + " chunks1 = enflip_chunks(chunks, [largest_burntdown_index + 1], debug=debug)\n", + " new_lbi_pos = chunk_index(chunks1, -largest_burntdown_partner)\n", + " done_chunks = enflip_chunks(chunks1, [new_lbi_pos], debug=debug)\n", + " flips = [chunk_count_to_item_count(chunks, largest_burntdown_index + 1), \n", + " chunk_count_to_item_count(chunks1, new_lbi_pos)]\n", + " return coalesce(done_chunks), flips" + ] + }, + { + "cell_type": "code", + "execution_count": 13, + "metadata": {}, + "outputs": [], + "source": [ + "def burnt_pancake_step_case2(chunks, all_chunks, debug=False):\n", + " items = merge_chunks(chunks)\n", + " \n", + " if items == list(reversed(sorted(items))): # invoke -I special case\n", + " if debug: print(\"2: -I\")\n", + " n = len(items)\n", + " flips = [f for fp in [[n, n-1] for _ in range(n)] for f in fp if f != 0]\n", + " done_items = enflip(items, flips, burnt=True, debug=debug)\n", + " done_chunks = pancake_chunks(done_items)\n", + " elif items == sorted(items): # items are in reverse order, upside down\n", + " if debug: print(\"2: rev\")\n", + " flips = [len(items)]\n", + " done_items = enflip(items, flips, burnt=True, debug=debug)\n", + " done_chunks = pancake_chunks(done_items)\n", + " else:\n", + " candidates = chunk_bases(chunks)\n", + " largest_unsorted = min(candidates)\n", + " next_largest_unsorted = min(i for i in candidates if i > largest_unsorted)\n", + " largest_unsorted_index = chunk_index(chunks, largest_unsorted)\n", + " next_largest_unsorted_index = chunk_index(chunks, next_largest_unsorted)\n", + "# print(largest_unsorted, next_largest_unsorted, largest_unsorted_index, next_largest_unsorted_index)\n", + " while next_largest_unsorted_index > largest_unsorted_index:\n", + " largest_unsorted = next_largest_unsorted\n", + " largest_unsorted_index = next_largest_unsorted_index\n", + " next_largest_unsorted = min(i for i in candidates if i > largest_unsorted)\n", + " next_largest_unsorted_index = chunk_index(chunks, next_largest_unsorted)\n", + " if debug: print(\"2: general, lu = {}, nlu = {}\".format(largest_unsorted, next_largest_unsorted))\n", + " chunks1 = enflip_chunks(chunks, [largest_unsorted_index + 1])\n", + " done_chunks = enflip_chunks(chunks1, [next_largest_unsorted_index], debug=debug)\n", + "# cflips = [largest_unsorted_index + 1, next_largest_unsorted_index]\n", + " flips = [chunk_count_to_item_count(chunks, largest_unsorted_index + 1), \n", + " chunk_count_to_item_count(chunks1, next_largest_unsorted_index)]\n", + "# done_chunks = enflip_chunks(chunks, cflips, debug=debug)\n", + " return coalesce(done_chunks), flips" + ] + }, + { + "cell_type": "code", + "execution_count": 14, + "metadata": {}, + "outputs": [], + "source": [ + "def burnt_pancake_step(chunks0, items, debug=False):\n", + " chunks = chunks0\n", + " largest = max(abs(i) for c in chunks for i in c)\n", + " while chunks[-1][-1] >= largest:\n", + " chunks = chunks[:-1]\n", + " largest = max(abs(i[-1]) for i in chunks)\n", + " largest_burntdown = max(merge_chunks(chunks))\n", + " if debug: print('<<', chunks, chunks0, items, largest, largest_burntdown)\n", + " if largest_burntdown > 0:\n", + " return burnt_pancake_step_case1(chunks, chunks0, items, largest, largest_burntdown, debug=debug)\n", + " else:\n", + " return burnt_pancake_step_case2(chunks, chunks0, debug=debug)" + ] + }, + { + "cell_type": "code", + "execution_count": 15, + "metadata": {}, + "outputs": [], + "source": [ + "def burnt_pancake_sort(items, fudge_rate=0, debug=False):\n", + " flips = []\n", + " flip_limit = len(items) * 3\n", + " items0 = items\n", + " chunks = pancake_chunks(items)\n", + " while (any(i for i in items if i < 0) or sorted(items) != items) and len(flips) < flip_limit:\n", + " chunks, these_flips = burnt_pancake_step(chunks, items, debug=debug)\n", + " if debug: print('Got chunks:', chunks)\n", + " items = merge_chunks(chunks)\n", + " flips += these_flips\n", + " if random.random() < fudge_rate:\n", + " if debug: c_old = chunks\n", + " its = [abs(i) for i in merge_chunks(chunks)]\n", + " eits = sorted(i for i in items0 if i not in its)\n", + " chunks = coalesce(pancake_chunks(its + eits))\n", + " items = its + eits\n", + " if debug: print('!! Fudge: Converting {} to {}'.format(c_old, chunks))\n", + " return items, flips" + ] + }, + { + "cell_type": "code", + "execution_count": 16, + "metadata": {}, + "outputs": [], + "source": [ + "def equiv_case(base_unsorted, flips, burnt=False, max_value=10000):\n", + "# new_sample = random.sample(list(range(1, max_value)), k=len(base_unsorted))\n", + " valid = False\n", + " while not valid:\n", + " new_sample = random.sample(list(range(1, max_value)), k=len(base_unsorted))\n", + " valid = len(new_sample) == len(base_unsorted)\n", + " sample = sorted(new_sample)\n", + " return unflip(sample, flips, burnt=burnt)" + ] + }, + { + "cell_type": "code", + "execution_count": 17, + "metadata": {}, + "outputs": [], + "source": [ + "def burnt_sorted(pancakes):\n", + " return pancakes == sorted(pancakes)\n", + "\n", + "def unburnt_sorted(pancakes):\n", + " simple_pancakes = [abs(p) for p in pancakes]\n", + " return simple_pancakes == sorted(simple_pancakes)" + ] + }, + { + "cell_type": "code", + "execution_count": 18, + "metadata": {}, + "outputs": [], + "source": [ + "def inverted_count(pancakes):\n", + " return sum(1 for p in pancakes if p < 0)" + ] + }, + { + "cell_type": "code", + "execution_count": 19, + "metadata": {}, + "outputs": [], + "source": [ + "def cache_flips(start, flips, burnt=False):\n", + " positions = [{'pos': start}]\n", + " stack = start\n", + " for f in flips:\n", + " stack = enflip(stack, [f], burnt=burnt)\n", + " positions += [{'pos': stack, 'move': f}]\n", + " return positions" + ] + }, + { + "cell_type": "code", + "execution_count": 20, + "metadata": {}, + "outputs": [], + "source": [ + "def show_cached_flips(cache):\n", + " rows = len(cache[0]['pos'])\n", + " middle_row = (rows) // 2\n", + " for r in range(rows):\n", + " for c in cache:\n", + " if r == middle_row and 'move' in c:\n", + " print(' -{}-> '.format(c['move']), end='')\n", + " elif 'move' in c:\n", + " print(' ', end='')\n", + " if c['pos'][r] > 0:\n", + " print('{:2d} '.format(c['pos'][r]), end='')\n", + " else:\n", + " print('{:2d}*'.format(abs(c['pos'][r])), end='')\n", + " print('')" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "Approach to developing test cases:\n", + "\n", + "1. Find a random pancake stack.\n", + "2. Find the burnt pancake sort of that stack: `burnt_flips`\n", + "3. Find an equivalent case for those flips: `pancakes`\n", + "4. Find a bunch of fudged burnt sorts of the `pancakes`: `fudged`\n", + "5. Find a bunch of random fudged pancake sorts: `padding`\n", + "\n", + "To assemble the test case, join together:\n", + "* the `burnt_flips`\n", + "* some `fudged`\n", + "* enough `padding` to make a round number." + ] + }, + { + "cell_type": "code", + "execution_count": 21, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "4" + ] + }, + "execution_count": 21, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "ln = 50\n", + "n_equivs = 100\n", + "fudge_rate = 0.3\n", + "\n", + "start = [i for i in random.sample(list(range(1, ln+1)), k=ln)]\n", + "test_flips = {}\n", + "_, test_flips['burnt_flips'] = burnt_pancake_sort(start)\n", + "test_flips['pancakes'] = equiv_case(start, test_flips['burnt_flips'], burnt=True)\n", + "test_flips['fudged'] = [burnt_pancake_sort(start, fudge_rate=fudge_rate)[1] for _ in range(n_equivs)]\n", + "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", + "len(test_flips)" + ] + }, + { + "cell_type": "code", + "execution_count": 22, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "99" + ] + }, + "execution_count": 22, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "test_data = [test_flips['burnt_flips']]\n", + "test_data.extend(random.sample(test_flips['fudged'], k=random.randint(50, 70)))\n", + "test_data.extend(random.sample(test_flips['padding'], k=(99-len(test_data))))\n", + "len(test_data)" + ] + }, + { + "cell_type": "code", + "execution_count": 23, + "metadata": {}, + "outputs": [], + "source": [ + "random.shuffle(test_data)" + ] + }, + { + "cell_type": "code", + "execution_count": 24, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "55" + ] + }, + "execution_count": 24, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "sum(1 for f in test_data\n", + " if unburnt_sorted(\n", + " enflip(test_flips['pancakes'], f, burnt=False)))" + ] + }, + { + "cell_type": "code", + "execution_count": 25, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "1" + ] + }, + "execution_count": 25, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "sum(1 for f in test_data\n", + " if burnt_sorted(\n", + " enflip(test_flips['pancakes'], f, burnt=True)))" + ] + }, + { + "cell_type": "code", + "execution_count": 26, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[61]" + ] + }, + "execution_count": 26, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "[i+1 for i, f in enumerate(test_data)\n", + " if burnt_sorted(\n", + " enflip(test_flips['pancakes'], f, burnt=True))]" + ] + }, + { + "cell_type": "code", + "execution_count": 27, + "metadata": {}, + "outputs": [], + "source": [ + "# random.shuffle(test_data)\n", + "# with open('07-flips.txt', 'w') as tdf:\n", + "# tdf.write('burgers: {}\\n'.format(' '.join(str(i) for i in test_flips['pancakes'] if i > 0)))\n", + "# for i, c in enumerate(test_data):\n", + "# tdf.write('{:02}: {}\\n'.format(i+1, ' '.join(str(i) for i in c if i > 0)))" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": {}, + "outputs": [], + "source": [] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# Example cases" + ] + }, + { + "cell_type": "code", + "execution_count": 28, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "{'burnt_flips': [5, 6, 2, 1, 2, 5, 3, 2, 3, 2, 3, 2],\n", + " 'pancakes': [8, 7, 5, 4, 11, 9],\n", + " 'fudged': [[5, 6, 1, 5, 4, 3, 4, 3, 4, 3, 4, 3],\n", + " [5, 6, 1, 5, 4, 3, 4, 3, 4, 3, 4, 3],\n", + " [5, 6, 2, 1, 2, 5],\n", + " [5, 6, 1, 5],\n", + " [5, 6, 1, 5, 4, 3, 4, 3, 4, 3, 4, 3]],\n", + " 'padding': [[1, 6, 5],\n", + " [5, 6, 1, 4, 1, 2],\n", + " [1, 6, 5, 0, 4, 5, 2, 4, 2, 1, 2, 1],\n", + " [2, 6, 2, 5, 2, 3, 1, 2],\n", + " [2, 6, 4, 0, 1, 4, 1, 3, 1, 2]]}" + ] + }, + "execution_count": 28, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "ln = 6\n", + "n_equivs = 5\n", + "fudge_rate = 0.7\n", + "\n", + "start = [i for i in random.sample(list(range(1, ln+1)), k=ln)]\n", + "test_flips = {}\n", + "_, test_flips['burnt_flips'] = burnt_pancake_sort(start)\n", + "test_flips['pancakes'] = equiv_case(start, test_flips['burnt_flips'], burnt=True, max_value=ln*2)\n", + "test_flips['fudged'] = [burnt_pancake_sort(start, fudge_rate=fudge_rate)[1] for _ in range(n_equivs)]\n", + "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", + "test_flips" + ] + }, + { + "cell_type": "code", + "execution_count": 29, + "metadata": {}, + "outputs": [], + "source": [ + "# test_flips = {'burnt_flips': [4, 5, 2, 1, 2, 3, 1],\n", + "# 'fudged': [[4, 5, 2, 1, 2, 3],\n", + "# [4, 5, 1, 3, 2, 1, 2, 1],\n", + "# [4, 5, 1, 3, 2, 1, 2, 1],\n", + "# [4, 5, 1, 3],\n", + "# [4, 5, 2, 1, 2, 3, 1]],\n", + "# 'padding': [[2, 5, 1, 2],\n", + "# [2, 5, 2, 1, 3],\n", + "# [1, 3, 1, 2, 1],\n", + "# [2, 5, 4, 1, 2, 3],\n", + "# [4, 5, 3, 4, 3, 1]],\n", + "# 'pancakes': [4, 2, 6, 7, 5]}" + ] + }, + { + "cell_type": "code", + "execution_count": 30, + "metadata": {}, + "outputs": [], + "source": [ + "test_flips = {'burnt_flips': [3, 5, 3, 2, 3, 2],\n", + " 'pancakes': [9, 18, 22, 15, 13],\n", + " 'fudged': [[3, 5, 2, 3],\n", + " [3, 5, 2, 3],\n", + " [3, 5, 2, 3],\n", + " [3, 5, 2, 3],\n", + " [3, 5, 2, 3]],\n", + " 'padding': [[4, 5, 3, 4, 2, 3],\n", + " [3],\n", + " [3, 5, 4, 2, 3, 4, 2],\n", + " [2, 5, 2, 3, 2],\n", + " [3, 5, 3]]}" + ] + }, + { + "cell_type": "code", + "execution_count": 31, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[3, 5, 3, 2, 3, 2]" + ] + }, + "execution_count": 31, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "bf = [f for f in test_flips['burnt_flips'] if f > 0]\n", + "bf" + ] + }, + { + "cell_type": "code", + "execution_count": 32, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[9, 13, 15, 18, 22]" + ] + }, + "execution_count": 32, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "enflip(test_flips['pancakes'], test_flips['burnt_flips'], burnt=True)" + ] + }, + { + "cell_type": "code", + "execution_count": 33, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[-9, -13, -15, 18, 22]" + ] + }, + "execution_count": 33, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "enflip(test_flips['pancakes'], test_flips['fudged'][0], burnt=True)" + ] + }, + { + "cell_type": "code", + "execution_count": 34, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[9, 13, 15, 18, 22]" + ] + }, + "execution_count": 34, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "enflip(test_flips['pancakes'], bf, burnt=True)" + ] + }, + { + "cell_type": "code", + "execution_count": 35, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + " 9 22 13 9 15 13 9 \n", + "18 18 15 15 9 9 13 \n", + "22 -3-> 9 -5-> 9 -3-> 13 -2-> 13 -3-> 15 -2-> 15 \n", + "15 15 18 18 18 18 18 \n", + "13 13 22 22 22 22 22 \n" + ] + } + ], + "source": [ + "show_cached_flips(cache_flips(test_flips['pancakes'], bf))" + ] + }, + { + "cell_type": "code", + "execution_count": 36, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + " 9 \n", + "18 \n", + "22 \n", + "15 \n", + "13 \n" + ] + } + ], + "source": [ + "show_cached_flips(cache_flips(test_flips['pancakes'], bf)[:1])" + ] + }, + { + "cell_type": "code", + "execution_count": 37, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + " 9 22 \n", + "18 18 \n", + "22 -3-> 9 \n", + "15 15 \n", + "13 13 \n" + ] + } + ], + "source": [ + "show_cached_flips(cache_flips(test_flips['pancakes'], bf)[:2])" + ] + }, + { + "cell_type": "code", + "execution_count": 38, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + " 9 22* 13* 9* 15* 13* 9 \n", + "18 18* 15* 15 9 9* 13 \n", + "22 -3-> 9* -5-> 9 -3-> 13 -2-> 13 -3-> 15 -2-> 15 \n", + "15 15 18 18 18 18 18 \n", + "13 13 22 22 22 22 22 \n" + ] + } + ], + "source": [ + "show_cached_flips(cache_flips(test_flips['pancakes'], bf, burnt=True))" + ] + }, + { + "cell_type": "code", + "execution_count": 39, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + " 9 \n", + "18 \n", + "22 \n", + "15 \n", + "13 \n" + ] + } + ], + "source": [ + "show_cached_flips(cache_flips(test_flips['pancakes'], test_flips['fudged'][0], burnt=False)[:1])" + ] + }, + { + "cell_type": "code", + "execution_count": 40, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + " 9 22 \n", + "18 18 \n", + "22 -3-> 9 \n", + "15 15 \n", + "13 13 \n" + ] + } + ], + "source": [ + "show_cached_flips(cache_flips(test_flips['pancakes'], test_flips['fudged'][0], burnt=False)[:2])" + ] + }, + { + "cell_type": "code", + "execution_count": 41, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + " 9 22 13 15 9 \n", + "18 18 15 13 13 \n", + "22 -3-> 9 -5-> 9 -2-> 9 -3-> 15 \n", + "15 15 18 18 18 \n", + "13 13 22 22 22 \n" + ] + } + ], + "source": [ + "show_cached_flips(cache_flips(test_flips['pancakes'], test_flips['fudged'][0], burnt=False))" + ] + }, + { + "cell_type": "code", + "execution_count": 42, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + " 9 22* 13* 15 9*\n", + "18 18* 15* 13 13*\n", + "22 -3-> 9* -5-> 9 -2-> 9 -3-> 15*\n", + "15 15 18 18 18 \n", + "13 13 22 22 22 \n" + ] + } + ], + "source": [ + "show_cached_flips(cache_flips(test_flips['pancakes'], test_flips['fudged'][0], burnt=True))" + ] + }, + { + "cell_type": "code", + "execution_count": 43, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + " 9 22* 13* 15 9*\n", + "18 18* 15* 13 13*\n", + "22 -3-> 9* -5-> 9 -2-> 9 -3-> 15*\n", + "15 15 18 18 18 \n", + "13 13 22 22 22 \n" + ] + } + ], + "source": [ + "show_cached_flips(cache_flips(test_flips['pancakes'], test_flips['fudged'][1], burnt=True))" + ] + }, + { + "cell_type": "code", + "execution_count": 44, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + " 9 22 13 15 9 \n", + "18 18 15 13 13 \n", + "22 -3-> 9 -5-> 9 -2-> 9 -3-> 15 \n", + "15 15 18 18 18 \n", + "13 13 22 22 22 \n" + ] + } + ], + "source": [ + "show_cached_flips(cache_flips(test_flips['pancakes'], test_flips['fudged'][3], burnt=False))" + ] + }, + { + "cell_type": "code", + "execution_count": 45, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + " 9 22* 13* 15 9*\n", + "18 18* 15* 13 13*\n", + "22 -3-> 9* -5-> 9 -2-> 9 -3-> 15*\n", + "15 15 18 18 18 \n", + "13 13 22 22 22 \n" + ] + } + ], + "source": [ + "show_cached_flips(cache_flips(test_flips['pancakes'], test_flips['fudged'][3], burnt=True))" + ] + }, + { + "cell_type": "code", + "execution_count": 46, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + " 9 15 13 18 22 13 9 \n", + "18 22 9 9 13 22 22 \n", + "22 -4-> 18 -5-> 18 -3-> 13 -4-> 9 -2-> 9 -3-> 13 \n", + "15 9 22 22 18 18 18 \n", + "13 13 15 15 15 15 15 \n" + ] + } + ], + "source": [ + "show_cached_flips(cache_flips(test_flips['pancakes'], test_flips['padding'][0]))" + ] + }, + { + "cell_type": "code", + "execution_count": 47, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + " 9 18 13 15 22 13 \n", + "18 9 15 13 13 22 \n", + "22 -2-> 22 -5-> 22 -2-> 22 -3-> 15 -2-> 15 \n", + "15 15 9 9 9 9 \n", + "13 13 18 18 18 18 \n" + ] + } + ], + "source": [ + "show_cached_flips(cache_flips(test_flips['pancakes'], test_flips['padding'][3]))" + ] + }, + { + "cell_type": "code", + "execution_count": 48, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "10" + ] + }, + "execution_count": 48, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "example_data = [test_flips['burnt_flips']]\n", + "example_data.extend(random.sample(test_flips['fudged'], k=4))\n", + "example_data.extend(random.sample(test_flips['padding'], k=5))\n", + "len(example_data)" + ] + }, + { + "cell_type": "code", + "execution_count": 49, + "metadata": {}, + "outputs": [], + "source": [ + "random.shuffle(example_data)\n", + "with open('07-example.txt', 'w') as tdf:\n", + " tdf.write('burgers: {}\\n'.format(' '.join(str(i) for i in test_flips['pancakes'] if i > 0)))\n", + " for i, c in enumerate(example_data):\n", + " tdf.write('{:02}: {}\\n'.format(i+1, ' '.join(str(i) for i in c if i > 0)))" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": {}, + "outputs": [], + "source": [] + } + ], + "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.6.6" + } + }, + "nbformat": 4, + "nbformat_minor": 2 +} -- 2.34.1