{"cells":[{"metadata":{"_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","papermill":{"duration":0.010858,"end_time":"2020-10-07T16:56:30.171685","exception":false,"start_time":"2020-10-07T16:56:30.160827","status":"completed"},"tags":[]},"cell_type":"markdown","source":"# Game of Life - Image Segmentation Solver\n\nThis is an extension of my previous [Hashmap Solver](https://www.kaggle.com/jamesmcguigan/game-of-life-hashmap-solver/) idea, but rather than treat the board as a single object, we can use [skimage.measure.label](https://scikit-image.org/docs/dev/api/skimage.measure.html#skimage.measure.label) to segment the board into objects, and then try to solve the board by parts."},{"metadata":{"papermill":{"duration":0.00981,"end_time":"2020-10-07T16:56:30.191515","exception":false,"start_time":"2020-10-07T16:56:30.181705","status":"completed"},"tags":[]},"cell_type":"markdown","source":"# Utility Functions"},{"metadata":{"_cell_guid":"79c7e3d0-c299-4dcb-8224-4455121ee9b0","_uuid":"d629ff2d2480ee46fbb7e2d37f6b5fab8052498a","execution":{"iopub.execute_input":"2020-10-07T16:56:30.220291Z","iopub.status.busy":"2020-10-07T16:56:30.219499Z","iopub.status.idle":"2020-10-07T16:56:32.140199Z","shell.execute_reply":"2020-10-07T16:56:32.140707Z"},"papermill":{"duration":1.939329,"end_time":"2020-10-07T16:56:32.140871","exception":false,"start_time":"2020-10-07T16:56:30.201542","status":"completed"},"tags":[],"trusted":true},"cell_type":"code","source":"from collections import defaultdict\nfrom fastcache import clru_cache\nfrom joblib import Parallel\nfrom joblib import delayed\n# from mergedeep import merge\nfrom numba import njit, prange\nfrom scipy.signal import convolve2d\nfrom typing import Union, List, Tuple, Dict, Callable\nfrom itertools import chain, product\n\nimport humanize\nimport itertools\nimport math\nimport matplotlib.pyplot as plt\nimport numpy as np\nimport os\nimport pandas as pd\nimport scipy\nimport scipy.sparse\nimport sys\nimport time\nimport skimage\nimport skimage.measure\nimport pydash\n\nnotebook_start = time.perf_counter()\n\n\n### Don't wrap console output text\nfrom IPython.display import display, HTML\ndisplay(HTML(\"\"\"\n<style>\ndiv.output_area pre {\n    white-space: pre;\n    width: 100%;\n}\n</style>\n\"\"\"))\n\n\n%load_ext autoreload\n%autoreload 2","execution_count":null,"outputs":[]},{"metadata":{"execution":{"iopub.execute_input":"2020-10-07T16:56:32.168327Z","iopub.status.busy":"2020-10-07T16:56:32.167701Z","iopub.status.idle":"2020-10-07T16:56:47.390512Z","shell.execute_reply":"2020-10-07T16:56:47.38979Z"},"papermill":{"duration":15.238002,"end_time":"2020-10-07T16:56:47.390636","exception":false,"start_time":"2020-10-07T16:56:32.152634","status":"completed"},"tags":[],"trusted":true},"cell_type":"code","source":"# TODO: add z3-solver to kaggle-docker image\n! python3 -m pip install -q z3-solver\n! apt-get install -qq tree moreutils","execution_count":null,"outputs":[]},{"metadata":{"execution":{"iopub.execute_input":"2020-10-07T16:56:47.436702Z","iopub.status.busy":"2020-10-07T16:56:47.432639Z","iopub.status.idle":"2020-10-07T16:57:02.899074Z","shell.execute_reply":"2020-10-07T16:57:02.898099Z"},"papermill":{"duration":15.493841,"end_time":"2020-10-07T16:57:02.899207","exception":false,"start_time":"2020-10-07T16:56:47.405366","status":"completed"},"tags":[],"trusted":true},"cell_type":"code","source":"# Download git repository and copy to local directory\n!rm -rf /ai-games/\n!git clone https://github.com/JamesMcGuigan/ai-games/ /ai-games/\n!cp -rf /ai-games/puzzles/game_of_life/* ./   # copy code to kaggle notebook\n!rm -rf /kaggle/working/neural_networks/      # not relevant to this notebook\n!cd /ai-games/; git log -n1 ","execution_count":null,"outputs":[]},{"metadata":{"execution":{"iopub.execute_input":"2020-10-07T16:57:02.959772Z","iopub.status.busy":"2020-10-07T16:57:02.959072Z","iopub.status.idle":"2020-10-07T16:57:19.163126Z","shell.execute_reply":"2020-10-07T16:57:19.16239Z"},"papermill":{"duration":16.238401,"end_time":"2020-10-07T16:57:19.163252","exception":false,"start_time":"2020-10-07T16:57:02.924851","status":"completed"},"tags":[],"trusted":true},"cell_type":"code","source":"from utils.util import *\nfrom utils.plot import *\nfrom utils.game import *\nfrom utils.datasets import *\nfrom utils.tuplize import *\nfrom hashmaps.crop import *\nfrom hashmaps.hash_functions import *\nfrom hashmaps.translation_solver import *\nfrom hashmaps.repeating_patterns import *\nfrom constraint_satisfaction.fix_submission import *","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Geometrically Invarient Hash Functions\n\nThis allows us to detect geometrically translations / rotations / rolls / flips using a hash function. This is explained further here:\n- https://www.kaggle.com/jamesmcguigan/geometric-invariant-hash-functions/"},{"metadata":{"trusted":true},"cell_type":"code","source":"@njit()\ndef get_concentric_prime_mask(shape: Tuple[int,int]=(25,25)) -> np.ndarray:\n    pattern = 'diamond'\n    assert shape[0] == shape[1]\n    assert pattern in [ 'diamond', 'oval' ]\n\n    # Center coordinates\n    x     = (shape[0])//2\n    y     = (shape[1])//2\n    max_r = max(shape) + 1 if max(shape) % 2 == 0 else max(shape)   \n    \n    # Create diagonal lines of primes (r_mask) in the bottom right quadrant\n    mask = np.zeros(shape, dtype=np.int64)\n    for r in range(max_r):\n        primes = hashable_primes[:r+1]\n        for dr in range(r+1): \n            if   pattern == 'diamond':  prime = primes[r]                 # creates symmetric diamond\n            elif pattern == 'oval':     prime = primes[r] + primes[dr]    # creates rotation senstive oval\n            \n            coords = {\n                (x+(r-dr),y+(dr)), # bottom right\n                (x-(r-dr),y+(dr)), # bottom left\n                (x+(r-dr),y-(dr)), # top    right\n                (x-(r-dr),y-(dr)), # top    left\n            }\n            for coord in coords:\n                if min(coord) >= 0 and max(coord) < min(shape): \n                    mask[coord] = prime \n    return mask\n        \n    \n@njit()\ndef hash_geometric_concentric(board: np.ndarray) -> int:\n    \"\"\"\n    Takes the concentric diamond/circle pixelwise view from each pixel with wraparound\n    the distance to each pixel is encoded as a prime number, the sum of these is the hash for each view direction\n    the hash for each cell is the product of view directions and the hash of the board is the sum of these products\n    this produces a geometric invariant hash that will be identical for roll / flip / rotate operations\n    \n    The concentric version of this function allows the hash function to \"see\" in all directions \n    and detect self-contained objects seperated by whitespace, but at a 2x runtime performance cost.\n    \"\"\"\n    assert board.shape[0] == board.shape[1]  # assumes square board\n    mask = get_concentric_prime_mask(shape=board.shape)\n\n    hashed = 0\n    for x in range(board.shape[0]):\n        for y in range(board.shape[1]):\n            for dx in range(mask.shape[0]):\n                for dy in range(mask.shape[1]):\n                    coords  = ( (x+dx)%board.shape[0], (y+dy)%board.shape[1] )\n                    hashed += board[coords] * mask[dx,dy]\n    return hashed\n\n\nhash_geometric = hash_geometric_concentric","execution_count":null,"outputs":[]},{"metadata":{"papermill":{"duration":0.024511,"end_time":"2020-10-07T16:57:19.214629","exception":false,"start_time":"2020-10-07T16:57:19.190118","status":"completed"},"tags":[]},"cell_type":"markdown","source":"# Image Segmentation\n\nThe goal here is to segment the board into groups of neighbouring cells.\n\nThere are two problems with `skimage.measure.label()`. The first is that it can only group cells that are directly touching, and breaks on patterns containing small whitespace gaps. The second is that it doesn't understand the concept of wraparound, thus images on the border will multiple labels.\n\nThe whitespace problem can be fixed by running `scipy.ndimage.convolve(board, np.ones()).astype(np.bool).astype(np.int8)`. Convolve counts the number of neighbouring cells (including self), which is then cast back to a boolean 1 or 0. The net effect of this is to expand each cell to fill its neighbours and create a 1 whitespace border around the outside of the cluster. These are our object masks.\n\nThe wraparound border issue requires a 3x3 tessellation of the (25,25) board to (75,75). Labelling is performed on the tessellation, which can then be 3x3 sliced back into (9,25,25) view of the original board. Each cell is converted into a set of 9 labels. The top and bottom half of a border image will have different labels, but somehwere in the tessellation the object will have been seen as a contiguious whole. Each cell is then compared with every other cell, and if two cells share a common label then their label sets are merged. Thus all cells will have all the labels generated for the same object throughout the tessellation. This can be cast back to a unique integer label using `min()`. The labels themselves can be remapped to a list of sequential numbers by using `sorted(set(cells)).index(cell)`."},{"metadata":{"trusted":true},"cell_type":"code","source":"import itertools\nfrom itertools import product\n\nimport numpy as np\n\n\ndef tessellate_board(board):\n    \"\"\" Create a 75x75 (3x) tesselation of the board to account for edge objects \"\"\"\n    shape        = board.shape\n    tessellation = np.zeros((shape[0]*3, shape[1]*3), dtype=np.int8)\n    for x,y in product( range(3), range(3) ):\n        tessellation[ shape[0]*x : shape[0]*(x+1), shape[1]*y : shape[1]*(y+1) ] = board\n    return tessellation\n\n\ndef detessellate_board(tessellation):\n    \"\"\" Merge 3x tesselation back into 25x25 grid, by working out sets of overlapping regions \"\"\"\n    shape = tessellation.shape[0] // 3, tessellation.shape[1] // 3\n    views = np.stack([\n        tessellation[ shape[0]*x : shape[0]*(x+1), shape[1]*y : shape[1]*(y+1) ].flatten()\n        for x,y in product( range(3), range(3) )\n    ])\n    cells = [ set(views[:,n]) - {0} for n in range(len(views[0])) ]\n    for cell1, cell2 in itertools.product(cells, cells):\n        if cell1 & cell2:\n            cell1 |= cell2  # merge overlapping regions\n            cell2 |= cell1\n    cells  = np.array([ min(cell) if cell else 0 for cell in cells ])\n    labels = sorted(set(cells))\n    cells  = np.array([ labels.index(cell) for cell in cells ])  # map back to sequential numbers\n    return cells.reshape(shape)\n","execution_count":null,"outputs":[]},{"metadata":{"execution":{"iopub.execute_input":"2020-10-07T16:57:19.278661Z","iopub.status.busy":"2020-10-07T16:57:19.277827Z","iopub.status.idle":"2020-10-07T16:57:19.313918Z","shell.execute_reply":"2020-10-07T16:57:19.313257Z"},"papermill":{"duration":0.073849,"end_time":"2020-10-07T16:57:19.314034","exception":false,"start_time":"2020-10-07T16:57:19.240185","status":"completed"},"tags":[],"trusted":true},"cell_type":"code","source":"from typing import List\n\nimport numpy as np\nimport scipy\nimport scipy.ndimage\nimport scipy.sparse\nimport skimage\nimport skimage.measure\n\n# from image_segmentation.tessellation import detessellate_board\n# from image_segmentation.tessellation import tessellate_board\n\n\ndef label_board(board):\n    \"\"\"  \"\"\"\n    tessellation = tessellate_board(board)\n    tessellation = scipy.ndimage.convolve(tessellation, [[0,1,0],[1,1,1],[0,1,0]]).astype(np.bool).astype(np.int8)\n    labeled = skimage.measure.label(tessellation, background=0, connectivity=2)\n    labeled = detessellate_board(labeled)\n    return labeled\n\n\ndef extract_clusters(board: np.ndarray) -> List[np.ndarray]:\n    labeled  = label_board(board)\n    return extract_clusters_from_labels(board, labeled)\n\n\ndef extract_clusters_from_labels(board: np.ndarray, labeled: np.ndarray) -> List[np.ndarray]:\n    labels   = np.unique(labeled)\n    clusters = []\n    for label in labels:\n        # if label == 0: continue  # preserve index order with labels\n        cluster = board * ( labeled == label )\n        clusters.append(cluster)\n    return clusters","execution_count":null,"outputs":[]},{"metadata":{"papermill":{"duration":0.024254,"end_time":"2020-10-07T16:57:19.362732","exception":false,"start_time":"2020-10-07T16:57:19.338478","status":"completed"},"tags":[]},"cell_type":"markdown","source":"A visual demonstration is shown below.\n- The first image shows a shared label object experiencing wraparound \n- The second image shows detection of two seperate objects\n- The third image is a testcase for using `convolve([[0,1,0],[1,1,1],[0,1,0]])` over `convolve([[0,1,0],[1,1,1],[0,1,0]])`\n- The fourth image shows a single mass of cells that spans the entire board (these will have to be excluded from the solver)"},{"metadata":{"execution":{"iopub.execute_input":"2020-10-07T16:57:19.421166Z","iopub.status.busy":"2020-10-07T16:57:19.420441Z","iopub.status.idle":"2020-10-07T16:57:22.268258Z","shell.execute_reply":"2020-10-07T16:57:22.267685Z"},"papermill":{"duration":2.87983,"end_time":"2020-10-07T16:57:22.268373","exception":false,"start_time":"2020-10-07T16:57:19.388543","status":"completed"},"tags":[],"trusted":true},"cell_type":"code","source":"for n, board in enumerate([\n    csv_to_numpy(test_df,  50022, key='stop'),\n    csv_to_numpy(train_df, 43612, key='stop'),\n    csv_to_numpy(train_df, 22282, key='stop'),\n    csv_to_numpy(test_df,  90081, key='stop'),\n]):\n    clusters = extract_clusters(board)\n\n    plt.figure(figsize=((len(clusters)+2)*4, 4))\n    plt.subplot(1, 2+len(clusters), 1)\n    plt.imshow(board, cmap='binary')\n    plt.subplot(1, 2+len(clusters), 2)\n    plt.imshow(label_board(board))\n    \n    for n, cluster in enumerate(clusters):\n        plt.subplot(1, 2+len(clusters), n+3)\n        plt.imshow(cluster, cmap='binary')","execution_count":null,"outputs":[]},{"metadata":{"papermill":{"duration":0.026868,"end_time":"2020-10-07T16:57:22.322887","exception":false,"start_time":"2020-10-07T16:57:22.296019","status":"completed"},"tags":[]},"cell_type":"markdown","source":"# Object Database\n\nBy looping through the test, train and self-generated datasets, we extract out any objects smaller than half the board, then use forward play to generate a reverse lookup table keyed using a [Geometric Invariant Hash](https://www.kaggle.com/jamesmcguigan/geometric-invariant-hash-functions)."},{"metadata":{"execution":{"iopub.execute_input":"2020-10-07T16:57:22.562142Z","iopub.status.busy":"2020-10-07T16:57:22.561147Z","iopub.status.idle":"2020-10-07T16:57:22.592626Z","shell.execute_reply":"2020-10-07T16:57:22.59195Z"},"papermill":{"duration":0.242737,"end_time":"2020-10-07T16:57:22.592741","exception":false,"start_time":"2020-10-07T16:57:22.350004","status":"completed"},"tags":[],"trusted":true},"cell_type":"code","source":"from collections import defaultdict\n\nimport pydash\nfrom joblib import delayed\nfrom joblib import Parallel\n\n# from hashmaps.hash_functions import hash_geometric\n# from image_segmentation.clusters import extract_clusters\nfrom utils.game import life_step_3d\n\n\ndef filter_crop_and_center(board: np.ndarray, max_size=25, shape=(25,25)) -> Union[np.ndarray, None]:\n    for _ in range(2):\n        cropped = crop_outer(board)\n        if ( cropped.shape    == crop_inner(cropped).shape  # exclude multi-piece shapes\n         and cropped.shape[0] <= max_size and cropped.shape[1] <= max_size\n        ):\n            offset = ( (shape[0]-cropped.shape[0])//2, (shape[1]-cropped.shape[1])//2 )\n            zeros  = np.zeros(shape, dtype=np.int)\n            zeros[ offset[0]:offset[0]+cropped.shape[0], offset[1]:offset[1]+cropped.shape[1] ] = cropped\n            return zeros\n        else:\n            # roll viewpoint and try again\n            board = np.roll(np.roll(board, shape[0]//2, axis=0), shape[1]//2, axis=1)\n    return None\n\n\ndef get_cluster_history_lookup(boards, forward_play=25, max_size=25):\n    \"\"\"\n    return history[now_hash][delta][past_hash] = {\n        \"start\": past_cluster,\n        \"stop\":  now_cluster,\n        \"delta\": delta,\n        \"count\": 1\n    }\n    \"\"\"\n    history  = defaultdict(lambda: defaultdict(lambda: defaultdict(dict)))\n    clusters = Parallel(-1)( delayed(extract_clusters)(board)                 for board in boards )\n    clusters = Parallel(-1)( delayed(filter_crop_and_center)(board, max_size) for board in pydash.flatten(clusters) )\n    clusters = [ cluster for cluster in clusters if cluster is not None ]\n    hashes   = Parallel(-1)( delayed(hash_geometric)(board)         for board in clusters )\n    clusters = { hashed: cluster for hashed, cluster in zip(hashes, clusters) }  # dedup\n    for cluster in clusters.values():\n        futures = life_step_3d(cluster, forward_play)\n        hashes  = Parallel(-1)( delayed(hash_geometric)(future) for future in futures )\n        for t in range(1, forward_play+1):\n            past_cluster = futures[t]\n            past_hash    = hashes[t]\n            for delta in range(1,5+1):\n                if t + delta >= len(futures): continue\n                now_cluster = futures[t + delta]\n                now_hash    = hashes[t + delta]\n                if not past_hash in history[now_hash][delta]:\n                    history[now_hash][delta][past_hash] = {\n                        \"start\": past_cluster,\n                        \"stop\":  now_cluster,\n                        \"delta\": delta,\n                        \"count\": 1\n                    }\n                else:\n                    history[now_hash][delta][past_hash]['count'] += 1\n\n\n    # remove defaultdict and sort by count\n    history = { now_hash: { delta: dict(sorted(d2.items(), key=lambda pair: pair[1]['count'], reverse=True ))\n                for delta,     d2 in d1.items()      }\n                for now_hash,  d1 in history.items() }\n\n    # # Remove any past boards with less than quarter the frequency of the most common board\n    # for now_hash, d1 in history.items():\n    #     for delta, d2 in d1.items():\n    #         max_count = max([ values['count'] for values in d2.values() ])\n    #         for past_hash, values in list(d2.items()):\n    #             if values['count'] < max_count/4: del history[now_hash][delta][past_hash]\n    return history\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# Only process a small dataset size for debugging when running in Interactive mode, else process everything  \ndataset_size = 100 if os.environ.get('KAGGLE_KERNEL_RUN_TYPE') == 'Interactive' else 400_000\nprint(f'dataset_size = {dataset_size}')","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"import gzip\nimport os\nimport pickle\nfrom typing import Any\n\nimport humanize\n\n\ndef read_gzip_pickle_file(filename: str) -> Any:\n    try:\n        if not os.path.exists(filename): raise FileNotFoundError\n        with open(filename, 'rb') as file:\n            data = file.read()\n            try:    data = gzip.decompress(data)\n            except: pass\n            data = pickle.loads(data)\n    except Exception as exception:\n        data = None\n    return data\n\n\ndef save_gzip_pickle_file(data: Any, filename: str, verbose=True) -> int:\n    try:\n        with open(filename, 'wb') as file:\n            data = pickle.dumps(data)\n            data = gzip.compress(data)\n            file.write(data)\n            file.close()\n        filesize = os.path.getsize(filename)\n        if verbose: print(f'wrote: {filename} = {humanize.naturalsize(filesize)}')\n        return filesize\n    except:\n        return 0","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# Source: https://www.kaggle.com/jamesmcguigan/game-of-life-image-segmentation-solver\nimport gzip\nimport os\nimport pickle\nimport time\n\nimport humanize\nimport numpy as np\n\n# from image_segmentation.history_lookup import get_cluster_history_lookup\n# from utils.datasets import output_directory\n# from utils.datasets import test_df\n# from utils.datasets import train_df\n# from utils.game import generate_random_boards\n# from utils.gzip_pickle_file import read_gzip_pickle_file\n# from utils.gzip_pickle_file import save_gzip_pickle_file\n# from utils.util import csv_to_numpy_list\n\n\ndef generate_cluster_history_lookup(dataset_size=3_000_000//25, forward_play=25, verbose=True):\n    time_start = time.perf_counter()\n\n    csv_size = len(train_df.index) # + len(test_df.index)\n    dataset = np.concatenate([\n        csv_to_numpy_list(train_df, key='start'),\n        # csv_to_numpy_list(test_df,  key='stop'),\n        generate_random_boards(max(1, dataset_size - csv_size))\n    ])[:dataset_size]\n    cluster_history_lookup = get_cluster_history_lookup(dataset, forward_play=forward_play)\n\n    time_taken = time.perf_counter() - time_start\n    if verbose: print(f'{len(cluster_history_lookup)} unique clusters in {time_taken:.1f}s = {1000*time_taken/len(dataset):.0f}ms/board')\n    return cluster_history_lookup\n\n\n\ncluster_history_lookup_cachefile = f'{output_directory}/cluster_history_lookup.pickle'\ncluster_history_lookup = read_gzip_pickle_file(cluster_history_lookup_cachefile)\n\nif __name__ == '__main__':\n    cluster_history_lookup = generate_cluster_history_lookup(dataset_size=dataset_size)\n    save_gzip_pickle_file(cluster_history_lookup, cluster_history_lookup_cachefile)\n","execution_count":null,"outputs":[]},{"metadata":{"papermill":{"duration":0.027457,"end_time":"2020-10-07T19:30:44.699711","exception":false,"start_time":"2020-10-07T19:30:44.672254","status":"completed"},"tags":[]},"cell_type":"markdown","source":"# Image Segmentation Solver\n\nFor each board in the test dataset, we split it into labelled clusters. For each cluster we perform a lookup on `history[delta][now_hash]`. If a history match is found we solve the geometric transform to rotate and roll it back into position, else we default to the existing stop board state. Then we copy/paste all the candidate `new_clusters` onto a zero'ed canvas and check to see if we have a valid solution."},{"metadata":{"execution":{"iopub.execute_input":"2020-10-07T19:30:44.777483Z","iopub.status.busy":"2020-10-07T19:30:44.776756Z","iopub.status.idle":"2020-10-07T19:30:44.820177Z","shell.execute_reply":"2020-10-07T19:30:44.820697Z"},"papermill":{"duration":0.092886,"end_time":"2020-10-07T19:30:44.820865","exception":false,"start_time":"2020-10-07T19:30:44.727979","status":"completed"},"tags":[],"trusted":true},"cell_type":"code","source":"import time\n\nimport numpy as np\nfrom joblib import delayed\nfrom joblib import Parallel\n\nfrom constraint_satisfaction.fix_submission import is_valid_solution\nfrom hashmaps.hash_functions import hash_geometric\nfrom hashmaps.translation_solver import solve_translation\n# from image_segmentation.clusters import extract_clusters_from_labels\n# from image_segmentation.clusters import label_board\n# from image_segmentation.history_lookup_cache import cluster_history_lookup\nfrom utils.datasets import sample_submission_df\nfrom utils.util import csv_to_delta_list\nfrom utils.util import csv_to_numpy_list\nfrom utils.util import numpy_to_series\n\n\ndef image_segmentation_dataframe_solver( df, history, submission_df=None, exact=False, blank_missing=True, verbose=True ):\n    time_start = time.perf_counter()\n    stats      = { \"partial\": 0, \"exact\": 0, \"total\": 0 }\n\n    submission_df = submission_df if submission_df is not None else sample_submission_df.copy()\n    idxs       = df.index\n    deltas     = csv_to_delta_list(df)\n    boards     = csv_to_numpy_list(df, key='stop')\n    labeleds   = Parallel(-1)( delayed(label_board)(board)                          for board in boards )\n    clustereds = Parallel(-1)( delayed(extract_clusters_from_labels)(board, labels) for board, labels in zip(boards, labeleds) )\n\n    for idx, delta, stop_board, labels, clusters in zip(idxs, deltas, boards, labeleds, clustereds):\n        start_board = image_segmentation_solver(\n            stop_board, delta, history=history, blank_missing=blank_missing,\n            labels=labels, clusters=clusters\n        )\n\n        is_valid = is_valid_solution( start_board, stop_board, delta )\n        if   is_valid:                         stats['exact']   += 1\n        elif np.count_nonzero( start_board ):  stats['partial'] += 1\n        stats['total'] += 1\n\n        if is_valid or not exact:\n            submission_df.loc[idx] = numpy_to_series(start_board, key='start')\n\n\n    time_taken = time.perf_counter() - time_start\n    stats['time_seconds'] = int(time_taken)\n    stats['time_hours']   = round(time_taken/60/60, 2)\n    if verbose: print('image_segmentation_solver()', stats)\n    return submission_df\n\n\n\ndef image_segmentation_solver(stop_board, delta, history=None, blank_missing=True, labels=None, clusters=None):\n    history  = history  if history  is not None else cluster_history_lookup\n    labels   = labels   if labels   is not None else label_board(stop_board)\n    clusters = clusters if clusters is not None else extract_clusters_from_labels(stop_board, labels)\n\n    labels       = np.unique(labels)\n    now_hashes   = Parallel(-1)( delayed(hash_geometric)(cluster) for cluster in clusters )\n    new_clusters = {}\n    for label, now_cluster, now_hash in zip(labels, clusters, now_hashes):\n        if label == 0: continue\n        if np.count_nonzero(now_cluster) == 0: continue\n        if history.get(now_hash,{}).get(delta,None):\n            for past_hash in history[now_hash][delta].keys():  # sorted by count\n                try:\n                    start_cluster = history[now_hash][delta][past_hash]['start']\n                    stop_cluster  = history[now_hash][delta][past_hash]['stop']\n                    transform_fn  = solve_translation(stop_cluster, now_cluster) # assert np.all( transform_fn(train_board) == test_board )\n                    past_cluster  = transform_fn(start_cluster)\n                    new_clusters[label] = past_cluster\n                    break\n                except Exception as exception:\n                    pass\n        if not label in new_clusters:\n            if blank_missing: new_clusters[label] = np.zeros(now_cluster.shape, dtype=np.int8)\n            else:             new_clusters[label] = now_cluster\n\n    # TODO: return list of all possible cluster permutations\n    start_board = np.zeros( stop_board.shape, dtype=np.int8 )\n    for cluster in new_clusters.values():\n        start_board += cluster\n    start_board = start_board.astype(np.bool).astype(np.int8)\n    return start_board","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"This version of the notebook outputs partial solved boards. For a version that only outputs 100% accurate boards I have created this fork [Game of Life - Image Segmentation Solver - Exact](https://www.kaggle.com/jamesmcguigan/game-of-life-image-segmentation-solver-exact), which can be reused as part of the [Z3 Constraint Satisfaction Solved](https://www.kaggle.com/jamesmcguigan/game-of-life-z3-constraint-satisfaction) dataset reimport loop."},{"metadata":{"execution":{"iopub.execute_input":"2020-10-07T19:30:44.881727Z","iopub.status.busy":"2020-10-07T19:30:44.88075Z","iopub.status.idle":"2020-10-07T20:16:24.318945Z","shell.execute_reply":"2020-10-07T20:16:24.31794Z"},"papermill":{"duration":2739.470641,"end_time":"2020-10-07T20:16:24.319185","exception":false,"start_time":"2020-10-07T19:30:44.848544","status":"completed"},"tags":[],"trusted":true},"cell_type":"code","source":"submission_df = image_segmentation_dataframe_solver( test_df[:dataset_size], history=cluster_history_lookup, exact=False )\nsubmission_df.to_csv('submission.csv')","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# Count number of non-zero entries in each submission.csv file\n!( for FILE in $(find ./ ../input/ -name 'submission.csv' | sort ); do cat $FILE | grep ',1' | wc -l | tr '\\n' ' '; echo $FILE; done) | sort -n;\n\n# Merge submission files from various sources into a single file. Reverse sort puts non-zero entries first, then use awk to deduplicate on id\n!find ./ ../input/ -name 'submission.csv' | xargs cat | sort -nr | uniq | awk -F',' '!a[$1]++' | sort -n > ./submission.csv\n\n# Count number of non-zero entries in each submission.csv file\n!( for FILE in $(find ./ ../input/ -name 'submission.csv' | sort ); do cat $FILE | grep ',1' | wc -l | tr '\\n' ' '; echo $FILE; done) | sort -n;\n\n# BUGFIX: previous version of the code was computing to delta=-1, so replay submission.csv forward one step if required and validate we have the correct delta\n# This also generates stats\n!PYTHONPATH='.' python3 ./constraint_satisfaction/fix_submission.py","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Further Reading\n\nI have written an interactive playable demo of the forward version of this game in React Javascript:\n- https://life.jamesmcguigan.com/\n\n\nThis notebook is part of series exploring the Neural Network implementions of the Game of Life Foward Problem\n- [Pytorch Game of Life - First Attempt](https://www.kaggle.com/jamesmcguigan/pytorch-game-of-life-first-attempt)\n- [Pytorch Game of Life - Hardcoding Network Weights](https://www.kaggle.com/jamesmcguigan/pytorch-game-of-life-hardcoding-network-weights)\n- [Its Easy for Neural Networks To Learn Game of Life](https://www.kaggle.com/jamesmcguigan/its-easy-for-neural-networks-to-learn-game-of-life)\n\nThis is preliminary research towards the harder Reverse Game of Life problem, for which I have already designed a novel Ouroboros loss function: \n- [OuroborosLife - Function Reversal GAN](https://www.kaggle.com/jamesmcguigan/ouroboroslife-function-reversal-gan)\n\n\nI also have an extended series of Notebooks exploring different approaches to the Reverse Game of Life problem\n\nMy first attempt was to use the Z3 Constraint Satisfaction SAT solver. This gets 100% accuracy on most boards, but there are a few which it cannot solve. This approach can be slow for boards with large cell counts and large deltas. I managed to figure out how to get cluster compute working inside Kaggle Notebooks, but this solution is estimated to require 10,000+ hours of CPU time to complete.    \n- [Game of Life - Z3 Constraint Satisfaction](https://www.kaggle.com/jamesmcguigan/game-of-life-z3-constraint-satisfaction)\n\nSecond approach was to create a Geometrically Invarient Hash function using Summable Primes, then use forward play and a dictionary lookup table to create a database of known states. For known input/output states at a given delta, the problem is reduced to simply solving the geometric transform between inputs and applying the same function to the outputs. The Hashmap Solver was able to solve about 10% of the test dataset. \n- [Summable Primes](https://www.kaggle.com/jamesmcguigan/summable-primes)\n- [Geometric Invariant Hash Functions](https://www.kaggle.com/jamesmcguigan/geometric-invariant-hash-functions)\n- [Game of Life - Repeating Patterns](https://www.kaggle.com/jamesmcguigan/game-of-life-repeating-patterns)\n- [Game of Life - Hashmap Solver](https://www.kaggle.com/jamesmcguigan/game-of-life-hashmap-solver)\n- [Game of Life - Image Segmentation Solver](https://www.kaggle.com/jamesmcguigan/game-of-life-image-segmentation-solver)"}],"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat":4,"nbformat_minor":4}