{"cells":[{"metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","trusted":true},"cell_type":"markdown","source":"# Game Of Life - Repeating Patterns\n\nThe notebook explores the range of repeating and static patterns found in [Conway's Game of Life](https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life).\n\nShapes are extracted from the train and test datasets, as well as all 4x4 starting positions, then extrapolated forward to see if repeating/static patterns are found, and these are visualized below.\n\nThe underlying aim here to generate a dataset of additional constraints that could potentually be added to a SAT constraint solver, potentually localized subproblems to be solved in O(1) time, thus reducing the NP-hard search space of possible solutions. \n- https://www.kaggle.com/jamesmcguigan/game-of-life-z3-constraint-satisfaction/\n\nThese patterns are essentially time crystals in 3D space (2D space + time), so if we see any of these 2D shapes within the stop state (with a whitespace bounding box), then we already know how this pattern evolves going both forward and backwards in time. This reduces the state space from all the thousands of noise states that could possibly produce such a crystal, down to a singular ordered crystalline state (which is O(1) to solve for). In chemistry, crystals are said to have low entropy."},{"metadata":{"trusted":true},"cell_type":"code","source":"import numpy  as np\nimport pandas as pd\nimport math\nimport matplotlib.pyplot as plt\nfrom itertools import chain, product\nfrom scipy.signal import convolve2d\nfrom numba import njit\nfrom joblib import delayed\nfrom joblib import Parallel\nfrom typing import Union, List, Dict, Tuple, FrozenSet, Set\nfrom collections import defaultdict","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Dataset"},{"metadata":{"trusted":true},"cell_type":"code","source":"input_directory = f'../input/conways-reverse-game-of-life-2020/'\ntrain_file      = f'{input_directory}/train.csv'\ntest_file       = f'{input_directory}/test.csv'\n\ntrain_df        = pd.read_csv(train_file, index_col='id')\ntest_df         = pd.read_csv(test_file,  index_col='id')","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Utility Functions"},{"metadata":{"trusted":true},"cell_type":"code","source":"# NOTE: @njit doesn't like np.roll(axis=) so reimplement explictly\n@njit\ndef life_neighbours_xy(board: np.ndarray, x, y, max_value=3):\n    size_x = board.shape[0]\n    size_y = board.shape[1]\n    neighbours = 0\n    for i in (-1, 0, 1):\n        for j in (-1, 0, 1):\n            if i == j == 0: continue    # ignore self\n            xi = (x + i) % size_x\n            yj = (y + j) % size_y\n            neighbours += board[xi, yj]\n            if neighbours > max_value:  # shortcircuit return 4 if overpopulated\n                return neighbours\n    return neighbours\n\n@njit\ndef life_step(board: np.ndarray):\n    \"\"\"Game of life step using generator expressions\"\"\"\n    size_x = board.shape[0]\n    size_y = board.shape[1]\n    output = np.zeros(board.shape, dtype=np.int8)\n    for x in range(size_x):\n        for y in range(size_y):\n            cell       = board[x,y]\n            neighbours = life_neighbours_xy(board, x, y, max_value=3)\n            if ( (cell == 0 and      neighbours == 3 )\n              or (cell == 1 and 2 <= neighbours <= 3 )\n            ):\n                output[x, y] = 1\n    return output\n\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"def csv_to_numpy(df, idx, key='start') -> np.ndarray:\n    columns = [col for col in df if col.startswith(key)]\n    size    = int(math.sqrt(len(columns)))\n    board   = df.loc[idx][columns].values\n    if len(board) == 0: board = np.zeros((size, size))\n    board = board.reshape((size,size)).astype(np.int8)\n    return board\n\n\ndef plot_3d(solution_3d: np.ndarray, size=4, max_cols=6):\n    cols = np.min([ len(solution_3d), max_cols ])\n    rows = len(solution_3d) // cols + 1\n    plt.figure(figsize=(cols*size, rows*size))\n    for t in range(len(solution_3d)):\n        board = solution_3d[t]\n        plt.subplot(rows, cols, t + 1)\n        plt.imshow(board, cmap='binary'); plt.title(f't={t}')\n    plt.show()\n\n\ndef crop_inner(grid,tol=0):\n    mask = grid > tol\n    return grid[np.ix_(mask.any(1),mask.any(0))]\n\n\ndef crop_outer(grid,tol=0):\n    mask = grid>tol\n    m,n  = grid.shape\n    mask0,mask1 = mask.any(0), mask.any(1)\n    col_start,col_end = mask0.argmax(),n-mask0[::-1].argmax()\n    row_start,row_end = mask1.argmax(),m-mask1[::-1].argmax()\n    return grid[row_start:row_end,col_start:col_end]\n\n\ndef crop_and_center(board: np.ndarray, shape=(25,25)) -> Union[np.ndarray, None]:\n    cropped = crop_outer(board)\n    offset  = ( (shape[0]-cropped.shape[0])//2, (shape[1]-cropped.shape[1])//2 ) \n    zeros   = np.zeros(shape, dtype=np.int8)\n    zeros[ offset[0]:offset[0]+cropped.shape[0], offset[1]:offset[1]+cropped.shape[1] ] = cropped\n    return zeros\n    \n\ndef filter_crop_and_center(board: np.ndarray, max_size=6, 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: continue  # exclude multi-piece shapes\n        if cropped.shape[0] <= max_size and cropped.shape[1] <= max_size:\n            offset = ( (shape[0]-cropped.shape[0])//2, (shape[1]-cropped.shape[1])//2 ) \n            zeros  = np.zeros(shape)\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 crop_outer_3d(solution_3d: np.ndarray, tol=0) -> np.ndarray:\n    assert len(solution_3d.shape) == 3\n    size_t,size_x,size_y = solution_3d.shape\n\n    mask_t = np.array([ np.any(grid) for grid in solution_3d ])\n    mask_x = np.any([ grid.any(axis=0) for grid in solution_3d ], axis=0)\n    mask_y = np.any([ grid.any(axis=1) for grid in solution_3d ], axis=0)\n\n    t_start,   t_end   = mask_t.argmax(), size_t - mask_t[::-1].argmax()\n    col_start, col_end = mask_x.argmax(), size_x - mask_x[::-1].argmax()\n    row_start, row_end = mask_y.argmax(), size_y - mask_y[::-1].argmax()\n    output = solution_3d[ t_start:t_end, col_start:col_end, row_start:row_end ]\n    return output\n\n\ndef crop_and_center_3d(solution_3d: np.ndarray, shape=(25,25)) -> Union[np.ndarray, None]:\n    cropped = crop_outer_3d(solution_3d)\n    offset  = ( (shape[0]-cropped[0].shape[0])//2, (shape[1]-cropped[0].shape[1])//2 )\n    zeros   = np.zeros((cropped.shape[0], *shape), dtype=np.int8)\n    zeros[ :, offset[0]:offset[0]+cropped[0].shape[0], offset[1]:offset[1]+cropped[0].shape[1] ] = cropped\n    return zeros","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Geometric invarient hash functions to deduplicate the dataset"},{"metadata":{"trusted":true},"cell_type":"code","source":"import numpy as np\nfrom numba import njit\n\n# First 625 prime numbers\nprimes_np = np.array([ \n    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637\n], dtype=np.int64)\n\n# Hashable primes that don't have summation collisions for permutations=2 \nhashable_primes = np.array([\n        2,     7,    23,    47,    61,     83,    131,    163,    173,    251,\n      457,   491,   683,   877,   971,   2069,   2239,   2927,   3209,   3529,\n     4451,  4703,  6379,  8501,  9293,  10891,  11587,  13457,  13487,  17117,\n    18869, 23531, 23899, 25673, 31387,  31469,  36251,  42853,  51797,  72797,\n    76667, 83059, 87671, 95911, 99767, 100801, 100931, 100937, 100987, 100999,\n], dtype=np.int64)\n\n\n@njit()\ndef hash_geometric(board: np.ndarray) -> int:\n    \"\"\"\n    Takes the 1D pixelwise view from each pixel (up, down, left, right) 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    assert board.shape[0] == board.shape[1]  # assumes square board\n    size     = board.shape[0]\n    l_primes = hashable_primes[:size//2+1]   # each distance index is represented by a different prime\n    r_primes = l_primes[::-1]                # symmetric distance values in reversed direction from center\n\n    hashed = 0\n    for x in range(size):\n        for y in range(size):\n            # current pixel is moved to center [13] index\n            horizontal = np.roll( board[:,y], size//2 - x)\n            vertical   = np.roll( board[x,:], size//2 - y)\n            left       = np.sum( horizontal[size//2:]   * l_primes )\n            right      = np.sum( horizontal[:size//2+1] * r_primes )\n            down       = np.sum( vertical[size//2:]     * l_primes )\n            up         = np.sum( vertical[:size//2+1]   * r_primes )\n            hashed    += left * right * down * up\n    return hashed\n\n\n@njit()\ndef hash_translations(board: np.ndarray) -> int:\n    \"\"\"\n    Takes the 1D pixelwise view from each pixel (left, down) with wraparound\n    by only using two directions, this hash is only invariant for roll operations, but not flip or rotate\n    this allows determining which operations are required to solve a transform\n\n    NOTE: np.rot180() produces the same sum as board, but with different numbers which is fixed via: sorted * primes\n    \"\"\"\n    assert board.shape[0] == board.shape[1]\n    hashes = hash_translations_board(board)\n    sorted = np.sort(hashes.flatten())\n    hashed = np.sum(sorted[::-1] * primes_np[:len(sorted)])  # multiply big with small numbers | hashable_primes is too small\n    return int(hashed)\n\n\n@njit()\ndef hash_translations_board(board: np.ndarray) -> np.ndarray:\n    \"\"\" Returns a board with hash values for individual cells \"\"\"\n    assert board.shape[0] == board.shape[1]  # assumes square board\n    size = board.shape[0]\n\n    # NOTE: using the same list of primes for each direction, results in the following identity splits:\n    # NOTE: np.rot180() produces the same np.sum() hash, but using different numbers which is fixed via: sorted * primes\n    #   with v_primes == h_primes and NOT sorted * primes:\n    #       identity == np.roll(axis=0) == np.roll(axis=1) == np.rot180()\n    #       np.flip(axis=0) == np.flip(axis=1) == np.rot90() == np.rot270() != np.rot180()\n    #   with v_primes == h_primes and sorted * primes:\n    #       identity == np.roll(axis=0) == np.roll(axis=1)\n    #       np.flip(axis=0) == np.rot270()\n    #       np.flip(axis=1) == np.rot90()\n    h_primes = hashable_primes[ 0*size : 1*size ]\n    v_primes = hashable_primes[ 1*size : 2*size ]\n    output   = np.zeros(board.shape, dtype=np.int64)\n    for x in range(size):\n        for y in range(size):\n            # current pixel is moved to left [0] index\n            horizontal  = np.roll( board[:,y], -x )\n            vertical    = np.roll( board[x,:], -y )\n            left        = np.sum( horizontal * h_primes )\n            down        = np.sum( vertical   * v_primes )\n            output[x,y] = left * down\n    return output","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"def find_repeating_patterns(start_board: np.ndarray, delta=16, geometric=False) -> Union[np.ndarray, None]:\n    \"\"\" Take 10 steps forward and check to see if the same pattern repeats \"\"\"\n    def hash_fn(board):\n        return hash_geometric(board) if geometric else hash_translations(board)\n    def is_symmetric(board): \n        return np.all( board == np.flip(board, axis=0) ) or np.all( board == np.flip(board, axis=0) )\n    \n    solution_3d = [ start_board ]\n    hashes      = [ hash_fn(start_board) ]\n    symmetric   = is_symmetric(start_board)\n    for t in range(delta):\n        next_board = life_step(solution_3d[-1])\n        next_hash  = hash_fn(next_board)\n        symmetric  = symmetric and is_symmetric(next_board)\n        solution_3d.append(next_board)\n        hashes.append( hash_fn(next_board) )\n        if np.count_nonzero(next_board) == 0: break  # ignore dead boards\n        if next_hash in hashes[:-1]:\n            return crop_and_center_3d(np.array(solution_3d))\n        \n    if symmetric and len(solution_3d) > 5:\n        return crop_and_center_3d(np.array(solution_3d))\n    return None","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"def dataset_patterns() -> List[np.ndarray]:\n    boards = [\n        *[ csv_to_numpy(train_df, idx, key='start') for idx in train_df.index ],\n        *[ csv_to_numpy(train_df, idx, key='stop')  for idx in train_df.index ],\n        *[ csv_to_numpy(test_df,  idx, key='stop')  for idx in test_df.index  ],\n    ]\n    boards = [ filter_crop_and_center(board, max_size=6, shape=(25,25)) for board in boards ]\n    boards = [ board for board in boards if board is not None ]\n    hashes = Parallel(-1)([ delayed(hash_geometric)(board) for board in boards ])\n    boards = list({ hashed: board for hashed, board in zip(hashes, boards) }.values())  # deduplicate\n    patterns = Parallel(-1)([ delayed(find_repeating_patterns)(board, delta=16, geometric=False) for board in boards ])\n    patterns = [ pattern for pattern in patterns if pattern is not None ]\n    return patterns\n\n\n\n@njit\ndef tail_repeating_pattern(pattern):\n    \"\"\" Here we just want to show the actual repeating part \"\"\"\n    for t in range(len(pattern)):\n        if np.all( pattern[t] == pattern[-1] ):\n            return pattern[t:]\n\n        \ndef tail_repeating_patterns(patterns):\n    tails  = Parallel(-1)( delayed(tail_repeating_pattern)(pattern) for pattern in patterns )\n    output = list({\n        pattern.tobytes(): pattern\n        for pattern in tails\n        if len(pattern) > 1\n    }.values())  # make unique\n    return output","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Repeating Patterns In Kaggle Dataset\n\nGenerate a list of geometrically unique board positions, that can be cropped and centered to a size of 6 or less"},{"metadata":{"trusted":true},"cell_type":"code","source":"patterns       = dataset_patterns()\npatterns_tails = tail_repeating_patterns(patterns)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"for solution_3d in patterns_tails: plot_3d(solution_3d)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Known Sequences In Kaggle Dataset"},{"metadata":{"trusted":true},"cell_type":"code","source":"for solution_3d in patterns: plot_3d(solution_3d)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# All Repeating Patterns from 4x4 + 5x3 Boards"},{"metadata":{"trusted":true},"cell_type":"code","source":"%%time\n\ndef generate_boards(shape=(4,4)):\n    \"\"\"Generate all possible board combinations of 1s and 0s, geometrically deduplicated\"\"\"\n    sequences = product(range(2), repeat=np.product(shape)) \n    boards    = ( np.array(list(sequence), dtype=np.int8).reshape(shape) for sequence in sequences )\n    boards    = ( crop_and_center(board) for board in boards )\n    unique    = { board.tobytes(): board for board in boards }\n    unique    = { hash_geometric(board): board for board in unique.values() }\n    output = unique.values()\n    return list(output)\n  \n    \ndef generated_patterns(shape=(4,4)) -> List[np.ndarray]:\n    \"\"\"All possible 3D boards with repeating/static patterns \"\"\"\n    boards   = generate_boards(shape=shape)\n    boards   = list({ board.tobytes(): board for board in boards }.values())\n    patterns = Parallel(-1)([ delayed(find_repeating_patterns)(board, delta=16, geometric=False) for board in boards ])\n    patterns = [ pattern for pattern in patterns if pattern is not None ]\n    return patterns\n\n\ndef grouped_patterns(patterns: List[np.ndarray]) -> Dict[bytes, np.ndarray]:\n    \"\"\"Group patterns by their final state\"\"\"\n    \n    # Group by 3D geometric hash\n    index = {}\n    for pattern_3d in patterns:\n        t0_key = np.product([ hash_geometric(board) for board in pattern_3d[:] ])\n        index[t0_key] = pattern_3d\n\n    # Remove any patterns that have duplicates at T=1 \n    while True:\n        is_deduped = True\n        dedup = {}\n        for t0_key, pattern_3d in index.items():\n            t1_key = np.product([ hash_geometric(board) for board in pattern_3d[1:] ])\n            if t1_key not in index:\n                dedup[t0_key] = pattern_3d \n            else:\n                is_deduped = False\n        index = dedup\n        if is_deduped: break\n        \n    # Group by last frame\n    grouped  = defaultdict(list)\n    for pattern_3d in index.values():\n        order_key = hash_geometric(pattern_3d[-1])\n        grouped[order_key].append(pattern_3d)\n    grouped = { **grouped }  # remove defaultdict\n    return grouped\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"patterns       = generated_patterns(shape=(5,3)) + generated_patterns(shape=(4,4))\npatterns_tails = tail_repeating_patterns(patterns)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"for solution_3d in patterns_tails: plot_3d(solution_3d)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# All Sequences from 4x4 + 5x3 Boards"},{"metadata":{"trusted":true},"cell_type":"code","source":"pattern_groups = grouped_patterns(patterns)\nprint('len(patterns)',                len(patterns))\nprint('len(pattern_groups.values())', len(list(chain(*pattern_groups.values()))))\nprint('len(pattern_groups)',          len(pattern_groups))\nfor solution_3d in chain(*pattern_groups.values()): plot_3d(solution_3d)","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}