{"cells":[{"metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","trusted":true},"cell_type":"markdown","source":"# Game of Life - Hashmap Solver\n\nThe theoretical state space for Reverse Game of Life is 2^(25\\*25) = 1.4\\*10^188.\n\nHowever there is a 5-step warmup period for the start boards, meaning many possible `T=-5` start patterns will naturally die out, thus reducing the state space for practical purposes. We can also take advantage of mirror/rotate/roll/flip symeteries of the board by using geometrically invarient hash functions.\n\n\nThis notebook attempts to solve the Reverse Game of Life problem using only dictionary lookup and geometric transforms of the test dataset.\n\n## Update\n\nI have updated the code to use a new [Geometric Invariant Hash Function](https://www.kaggle.com/jamesmcguigan/geometric-invariant-hash-functions) function that uses concentric circles rather than lines, and is better able to detect objects seperated by whitespace.\n\nI have also written a new [Image Segmentation Solver](https://www.kaggle.com/jamesmcguigan/game-of-life-image-segmentation-solver) which extends the ideas in this notebook to use image segmentation techniques. This gets a suprising high score of `0.08631` which is almost matches the `0.08549` score of my [Z3 Constraint Satisfaction Solver](https://www.kaggle.com/jamesmcguigan/game-of-life-z3-constraint-satisfaction) after 1000s of hours of CPU runtime."},{"metadata":{"trusted":true},"cell_type":"code","source":"# !pip3 install -q mergedeep","execution_count":null,"outputs":[]},{"metadata":{"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\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","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"notebook_start = time.perf_counter()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"!ls -la ../input","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"train_df             = pd.read_csv('../input/conways-reverse-game-of-life-2020/train.csv', index_col='id')\ntest_df              = pd.read_csv('../input/conways-reverse-game-of-life-2020/test.csv',  index_col='id')\nsample_submission_df = pd.read_csv('../input/conways-reverse-game-of-life-2020/sample_submission.csv',  index_col='id')\nsubmission_df        = pd.read_csv('../input/game-of-life-hashmap-solver/submission.csv',  index_col='id')","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Utility Functions\n\nSources:\n- https://www.kaggle.com/jamesmcguigan/game-of-life-z3-constraint-satisfaction/\n- https://github.com/JamesMcGuigan/ai-games/tree/master/puzzles/game_of_life/utils"},{"metadata":{"trusted":true},"cell_type":"code","source":"@clru_cache(None)\ndef csv_column_names(key='start'):\n    return [ f'{key}_{n}' for n in range(25**2) ]\n\n\ndef csv_to_delta(df, idx):\n    return int(df.loc[idx]['delta'])\n\ndef csv_to_delta_list(df):\n    return df['delta'].values\n\n\ndef csv_to_numpy(df, idx, key='start') -> np.ndarray:\n    try:\n        columns = csv_column_names(key)\n        board   = df.loc[idx][columns].values\n    except:\n        board = np.zeros((25, 25))\n    board = board.reshape((25,25)).astype(np.int8)\n    return board\n\n\ndef csv_to_numpy_list(df, key='start') -> np.ndarray:\n    try:\n        columns = csv_column_names(key)\n        output  = df[columns].values.reshape(-1,25,25)\n    except:\n        output  = np.zeros((0,25,25))\n    return output\n\n\n# noinspection PyTypeChecker,PyUnresolvedReferences\ndef numpy_to_dict(board: np.ndarray, key='start') -> Dict:\n    assert len(board.shape) == 2  # we want 2D solutions_3d[0] not 3D solutions_3d\n    assert key in { 'start', 'stop' }\n\n    board  = np.array(board).flatten().tolist()\n    output = { f\"{key}_{n}\": board[n] for n in range(len(board))}\n    return output\n\n\ndef numpy_to_series(board: np.ndarray, key='start') -> pd.Series:\n    solution_dict = numpy_to_dict(board, key)\n    return pd.Series(solution_dict)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# Functions for implementing Game of Life Forward Play\n\n# Source: https://www.kaggle.com/ianmoone0617/reversing-conways-game-of-life-tutorial\ndef life_step_1(X: np.ndarray):\n    \"\"\"Game of life step using generator expressions\"\"\"\n    nbrs_count = sum(np.roll(np.roll(X, i, 0), j, 1)\n                     for i in (-1, 0, 1) for j in (-1, 0, 1)\n                     if (i != 0 or j != 0))\n    return (nbrs_count == 3) | (X & (nbrs_count == 2))\n\n\n# Source: https://www.kaggle.com/ianmoone0617/reversing-conways-game-of-life-tutorial\ndef life_step_2(X: np.ndarray):\n    \"\"\"Game of life step using scipy tools\"\"\"\n    from scipy.signal import convolve2d\n    nbrs_count = convolve2d(X, np.ones((3, 3)), mode='same', boundary='wrap') - X\n    return (nbrs_count == 3) | (X & (nbrs_count == 2))\n\n\n\n# 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\n@njit\ndef life_neighbours(board: np.ndarray, max_value=3):\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            output[x,y] = life_neighbours_xy(board, x, y, max_value)\n    return output\n\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","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"def 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()","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Geometric Invariant Hash Functions\n\n\nGeometric Invariant Hash Functions are relevant to grid worlds experiencing wraparound (closed manifolds) in Conway's Reverse Game of Life and Halite and are also relevant to the Abstraction and Reasoning Corpus\n\nThey have the property of being invariant to np.roll() and optionally np.flip() and np.rot90()\n\nTo achieve this, we also need access to a set of Summable Prime Numbers. According to the Unique Factorization Theorem, the product of any combination of primes results in a unique number. This is not guaranteed to be true for summation, but it is possible through search to find a subset of prime numbers for which this property holds true. This property is important for preventing hash collisions.\n\nThese concepts are explored further in these notebooks: \n- https://www.kaggle.com/jamesmcguigan/summable-primes\n- https://www.kaggle.com/jamesmcguigan/geometric-invariant-hash-functions"},{"metadata":{"trusted":true},"cell_type":"code","source":"# Reference: The First 10,000 Primes - https://primes.utm.edu/lists/small/10000.txt\ndef generate_primes(count):\n    primes = [2]\n    for n in range(3, sys.maxsize, 2):\n        if len(primes) >= count: break\n        if all( n % i != 0 for i in range(3, int(math.sqrt(n))+1, 2) ):\n            primes.append(n)\n    return primes\n\nprimes     = generate_primes(10_000)\nprimes_np  = np.array(primes, dtype=np.int64)\nprimes_set = set(primes_np)\n\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)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"@njit()\ndef hash_geometric_linear(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@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\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 test_hash_geometric():\n    for idx in range(1000):\n        board = csv_to_numpy(train_df, idx)\n        transforms = {\n            \"identity\": board,\n            \"roll_0\":   np.roll(board, 1, axis=0),\n            \"roll_1\":   np.roll(board, 1, axis=1),\n            \"flip_0\":   np.flip(board, axis=0),\n            \"flip_1\":   np.flip(board, axis=1),\n            \"rot90\":    np.rot90(board, 1),\n            \"rot180\":   np.rot90(board, 2),\n            \"rot270\":   np.rot90(board, 3),\n        }\n        hashes = { f'{key:8s}': hash_geometric(value) for key, value in transforms.items()}\n\n        # all geometric transforms should produce the same hash\n        assert len(set(hashes.values())) == 1\n\n\ndef test_hash_translations():\n    for idx in range(1000):\n        board = csv_to_numpy(train_df, idx)\n        if np.count_nonzero(board) < 50: continue  # skip small symmetric boards\n        transforms = {\n            \"identity\": board,\n            \"roll_0\":   np.roll(board, 13, axis=0),\n            \"roll_1\":   np.roll(board, 13, axis=1),\n            \"flip_0\":   np.flip(board, axis=0),\n            \"flip_1\":   np.flip(board, axis=1),\n            \"rot90\":    np.rot90(board, 1),\n            \"rot180\":   np.rot90(board, 2),\n            \"rot270\":   np.rot90(board, 3),\n        }\n        hashes  = { key: hash_translations(value) for key, value in transforms.items()  }\n\n        # rolling the board should not change the hash, but other transforms should\n        assert hashes['identity'] == hashes['roll_0']\n        assert hashes['identity'] == hashes['roll_1']\n\n        # all other flip / rotate transformations should produce different hashes\n        assert hashes['identity'] != hashes['flip_0']\n        assert hashes['identity'] != hashes['flip_1']\n        assert hashes['identity'] != hashes['rot90']\n        assert hashes['identity'] != hashes['rot180']\n        assert hashes['identity'] != hashes['rot270']\n        assert hashes['flip_0'] != hashes['flip_1'] != hashes['rot90']  != hashes['rot180'] != hashes['rot270']\n        \n        \ntest_hash_geometric()\ntest_hash_translations()\nprint('All Tests Passed!')","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Enhanced Dataset\n\nWe can now create an enhanced version of the test and train.csv files with additional columns for geometric and translation invarient hashes"},{"metadata":{"trusted":true},"cell_type":"code","source":"from joblib import delayed\nfrom joblib import Parallel\n\ndef hashmap_dataframe(df: pd.DataFrame, key='start'):\n    boards                = csv_to_numpy_list(df, key=key)\n    geometric_hashes      = Parallel(-1)( delayed(hash_geometric)(board)    for board in boards )\n    translation_hashes    = Parallel(-1)( delayed(hash_translations)(board) for board in boards )\n\n    output = df.copy(deep=True)\n    output['id']                      = df.index\n    output[f'{key}_geometric_hash']   = geometric_hashes\n    output[f'{key}_translation_hash'] = translation_hashes\n\n    output = output.astype('int64')\n    output = output.astype({ col: 'int8' for col in csv_column_names(key) })\n    return output","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"%%time\nhashmap_train_df = train_df\nhashmap_test_df  = test_df \nhashmap_train_df = hashmap_dataframe(hashmap_train_df, key='start')\nhashmap_train_df = hashmap_dataframe(hashmap_train_df, key='stop')\nhashmap_test_df  = hashmap_dataframe(hashmap_test_df,  key='stop')\n\nhashmap_train_df.to_csv('./hashmap_train.csv')\nhashmap_test_df.to_csv('./hashmap_test.csv')","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"hashmap_train_df","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"hashmap_test_df","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Test Dataset Matches\n\nHere we create a dictionary lookup table for hash matches, and then count the number of matches"},{"metadata":{"trusted":true},"cell_type":"code","source":"def count_geometric_duplicates():\n    # Create hashtable index for train_df\n    train_stop_geometric_rows    = defaultdict(list)\n    train_stop_translation_rows  = defaultdict(list)\n    for idx, train_row in hashmap_train_df.iterrows():\n        delta                 = train_row['delta']\n        stop_geometric_hash   = train_row['stop_geometric_hash']\n        stop_translation_hash = train_row['stop_translation_hash']\n        train_stop_geometric_rows[stop_geometric_hash]     += [ train_row ]\n        train_stop_translation_rows[stop_translation_hash] += [ train_row ]\n\n\n    # Now count the number of hash matches in test_df\n    count_exact       = 0\n    count_geometric   = 0\n    count_translation = 0\n    count_total       = 0\n    for idx, test_row in hashmap_test_df.iterrows():\n        delta                      = test_row['delta']\n        test_stop_geometric_hash   = test_row['stop_geometric_hash']\n        test_stop_translation_hash = test_row['stop_translation_hash']\n\n        count_total += 1\n\n        # See if we find any geometric or translation hash matches\n        if test_stop_translation_hash in train_stop_translation_rows:\n            count_translation += 1\n\n        if test_stop_geometric_hash in train_stop_geometric_rows:\n            count_geometric += 1\n            for train_row in train_stop_geometric_rows[test_stop_geometric_hash]:\n                if train_row['delta'] == delta:\n                    count_exact += 1\n                    break\n\n    print(\" | \".join([\n        f'count_exact = {count_exact} ({100*count_exact/count_total:.1f}%)',\n        f'count_geometric = {count_geometric} ({100*count_geometric/count_total:.1f}%)',\n        f'count_translation = {count_translation} ({100*count_translation/count_total:.1f}%)',\n        f'count_total = {count_total}'\n    ]))","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Translation Solver\n\nWe have found that 11% of the test dataset has geometric duplicates in the training dataset, though only 2.2% of them are exact.  \n\nNow we need to solve for the translation\n\nThis code is inspired by my work on the [Abstraction and Reasoning Corupus](https://www.kaggle.com/c/abstraction-and-reasoning-challenge)\n- https://www.kaggle.com/jamesmcguigan/arc-geometry-solvers"},{"metadata":{"trusted":true},"cell_type":"code","source":"def identity(board): return board\ndef rot90(board):    return np.rot90(board, 1)\ndef rot180(board):   return np.rot90(board, 2)\ndef rot270(board):   return np.rot90(board, 3)\ndef flip(board):     return np.flip(board)\ndef flip90(board):   return np.flip(np.rot90(board, 1))\ndef flip180(board):  return np.flip(np.rot90(board, 2))\ndef flip270(board):  return np.flip(np.rot90(board, 3))\ngeometric_transforms = [identity, rot90, rot180, rot270, flip, flip90, flip180, flip270]\n\n\n\ndef solve_geometric(train_board, test_board) -> Callable:\n    \"\"\"\n    Find the function required to correctly orientate train_board to match test_board\n    This is a simple brute force search over geometric_transforms until matching hash_translations() are found\n    \"\"\"\n    assert hash_geometric(train_board) == hash_geometric(test_board)\n\n    geometric_fn = None\n    test_hash    = hash_translations(test_board)\n    for transform_fn in geometric_transforms:\n        train_transform = transform_fn(train_board)\n        train_hash      = hash_translations(train_transform)\n        if train_hash == test_hash:\n            geometric_fn = transform_fn\n            break  # we are lazily assuming there will be only one matching function\n\n    assert geometric_fn is not None\n    return geometric_fn\n\n\ndef solve_translation(train_board, test_board) -> Callable:\n    \"\"\"\n    Find the function required to correctly transform train_board to match test_board\n    We compute the sums of cell counts along each axis, then roll them until they match\n    \"\"\"\n    train_x_counts = np.count_nonzero(train_board, axis=1)  # == np.array([ np.count_nonzero(train_board[x,:]) for x in range(train_board.shape[0]) ])\n    train_y_counts = np.count_nonzero(train_board, axis=0)  # == np.array([ np.count_nonzero(train_board[:,y]) for y in range(train_board.shape[1]) ])\n    test_x_counts  = np.count_nonzero(test_board,  axis=1)  # == np.array([ np.count_nonzero(test_board[x,:])  for x in range(test_board.shape[0])  ])\n    test_y_counts  = np.count_nonzero(test_board,  axis=0)  # == np.array([ np.count_nonzero(test_board[:,y])  for y in range(test_board.shape[1])  ])\n    assert sorted(train_x_counts) == sorted(test_x_counts)\n    assert sorted(train_y_counts) == sorted(test_y_counts)\n\n    # This is a little bit inefficient, compared to comparing indexes of max values, but we are not CPU bound\n    x_roll_count = None\n    for n in range(len(train_x_counts)):\n        if np.roll(train_x_counts, n).tobytes() == test_x_counts.tobytes():\n            x_roll_count = n\n            break\n\n    y_roll_count = None\n    for n in range(len(train_y_counts)):\n        if np.roll(train_y_counts, n).tobytes() == test_y_counts.tobytes():\n            y_roll_count = n\n            break\n\n    assert x_roll_count is not None\n    assert y_roll_count is not None\n\n    def transform_fn(board):\n        return np.roll(np.roll(board, x_roll_count, axis=0), y_roll_count, axis=1)\n\n    assert np.all( transform_fn(train_board) == test_board )\n    return transform_fn\n\n\ndef solve_geometric_translation(train_board, test_board) -> Callable:\n    geometric_fn    = solve_geometric(train_board, test_board)\n    translation_fn  = solve_translation(geometric_fn(train_board), test_board)\n\n    def transform_fn(board):\n        return translation_fn( geometric_fn(board) )\n    assert np.all( transform_fn(train_board) == test_board )\n    return transform_fn\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Now we just need to iterate through our hashmap lookups and apply the solved `transform_fn()`\n\nThere is about a 29% failure rate, which is caused due to hash collisions for non-geometrically equlivant boards. This mostly occurs when there are two small shapes on the board seperated by whitespace, and none of the shapes can see each other horizontally or vertically.\n\nFuture Idea: it may be possible to fix the hashing function by taking the sum cells at X distance in concentric circles, rather than just summing horiontal and vertical lines"},{"metadata":{"trusted":true},"cell_type":"code","source":"def build_hashmap_database_from_pandas(\n        dfs: Union[pd.DataFrame, List[pd.DataFrame]],\n        hash_fn: Callable = hash_geometric,\n        future_count = 10,\n        keys = ['start', 'stop']\n):\n    boards = extract_boards_from_dataframe(dfs, keys)\n    lookup = build_hashmap_database_from_boards(boards, hash_fn=hash_fn, future_count=future_count)\n    return lookup\n\n\ndef extract_boards_from_dataframe(dfs: List[pd.DataFrame], keys = ['start', 'stop'] ):\n    boards = []\n    if not isinstance(dfs, list): dfs = [ dfs ]\n    for df in dfs:\n        for key in keys:\n            if f'{key}_0' not in df.columns: continue     # skip start on test_df\n            for board in csv_to_numpy_list(df, key=key):\n                if np.count_nonzero(board) == 0: continue  # skip empty boards\n                boards.append(board)\n    return boards\n\n\ndef build_hashmap_database_from_boards(\n        boards: List[np.ndarray],\n        hash_fn: Callable = hash_geometric,\n        future_count = 10,\n        max_delta    = 5,\n):\n    assert callable(hash_fn)\n\n    hashmap_database = defaultdict(lambda: defaultdict(dict))  # hashmap_database[stop_hash][delta] = { stop: np, start: np, delta: int }\n    future_hashes = Parallel(-1)(\n        delayed(build_future_hashes)(board, hash_fn, future_count)\n        for board in boards\n    )\n    for futures, hashes in future_hashes:\n        for t in range(len(futures)-max_delta):\n            for delta in range(1, max_delta+1):\n                start_board = futures[t]\n                stop_board  = futures[t + delta]\n                stop_hash   = hashes[t + delta]\n                hashmap_database[stop_hash][delta] = { 'start': start_board, 'stop': stop_board, 'delta': delta }\n    return hashmap_database\n\n\ndef build_future_hashes(board, hash_fn, future_count):\n    futures = [ board ]\n    for _ in range(future_count): futures += [ life_step(futures[-1]) ]\n    hashes  = [ hash_fn(board) for board in futures ]\n    return futures, hashes\n\n\ndef solve_hashmap_dataframe(hashmap_database=None, submission_df=None, verbose=True):\n    solved = 0\n    failed = 0\n    total  = len(test_df.index)\n    hashmap_database = hashmap_database or build_hashmap_database_from_pandas([ train_df, test_df ], hash_fn=hash_geometric)\n\n    submission_df = submission_df if submission_df is not None else sample_submission_df.copy()\n    for test_idx in test_df.index:\n        delta       = csv_to_delta(test_df, test_idx)\n        test_stop   = csv_to_numpy(test_df, test_idx, key='stop')\n        stop_hash   = hash_geometric(test_stop)\n        train_start = hashmap_database.get(stop_hash, {}).get(delta, {}).get('start', None)\n        train_stop  = hashmap_database.get(stop_hash, {}).get(delta, {}).get('stop', None)\n        if train_start is None: continue\n\n        try:\n            solution = solve_geometric_translation(train_stop, test_stop)(train_start)\n\n            solution_test = solution\n            for t in range(delta): solution_test = life_step(solution_test)\n            assert np.all( solution_test == test_stop )\n\n            submission_df.loc[test_idx] = numpy_to_series(solution)\n            solved += 1\n        except:\n            failed += 1\n\n    if verbose:\n        print(f'solved = {solved} ({100*solved/total:.1f}%) | failed = {failed} ({100*failed/(solved+failed):.1f}%)')\n\n    return submission_df","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Submission\n\nWe actually managed to solve 9.4% of the test dataset using only geometrically invarient hash functions, forward play, and dictionary based lookup. Thats actually quite impressive."},{"metadata":{"trusted":true},"cell_type":"code","source":"%%time\nhashmap_database = build_hashmap_database_from_pandas([ train_df, test_df ], hash_geometric)\nprint('len(hashmap_database) = ', len(hashmap_database))","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"%%time\nsubmission_df = solve_hashmap_dataframe(hashmap_database, submission_df=submission_df, verbose=True)\nsubmission_df.to_csv('./submission.csv')","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Extending with Generated Data\n\nSimilar results can be achieved using a generated dataset"},{"metadata":{"trusted":true},"cell_type":"code","source":"# RULES: https://www.kaggle.com/c/conway-s-reverse-game-of-life/data\ndef generate_random_board():\n    # An initial board was chosen by filling the board with a random density between 1% full (mostly zeros) and 99% full (mostly ones).\n    # DOCS: https://cmdlinetips.com/2019/02/how-to-create-random-sparse-matrix-of-specific-density/\n    density = np.random.random() * 0.98 + 0.01  \n    board   = scipy.sparse.random(25, 25, density=density, data_rvs=np.ones).toarray()\n    \n    # The starting board's state was recorded after the 5 \"warmup steps\". These are the values in the start variables.\n    for t in range(5): board = life_step(board)\n    return board\n\ndef generate_random_boards(count):\n    generated_boards = Parallel(-1)( delayed(generate_random_board)() for _ in range(count) )\n    return generated_boards ","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"%%time \ngenerated_boards   = generate_random_boards(1_000)\ngenerated_database = build_hashmap_database_from_boards(generated_boards, hash_geometric)\n_                  = solve_hashmap_dataframe(generated_database, verbose=True)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"%%time \ngenerated_boards   = generate_random_boards(10_000)\ngenerated_database = build_hashmap_database_from_boards(generated_boards, hash_geometric)\n_                  = solve_hashmap_dataframe(generated_database, verbose=True)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"%%time \ngenerated_boards   = generate_random_boards(100_000)\ngenerated_database = build_hashmap_database_from_boards(generated_boards, hash_geometric)\n_                  = solve_hashmap_dataframe(generated_database, verbose=True)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# Keep generating new sets of random boards, and hope this cancels out any hash collisions and finds new boards\nbatch_size = 100_000\nendtime    = time.perf_counter() + 6*60*60 - notebook_start\ntime_start = time.perf_counter()\n\ncount = 0\nwhile time.perf_counter() < endtime:\n    count             += batch_size\n    generated_boards   = generate_random_boards(batch_size)\n    generated_database = build_hashmap_database_from_boards(generated_boards, hash_geometric)\n    submission_df      = solve_hashmap_dataframe(generated_database, submission_df=submission_df, verbose=False)\n    submission_df.to_csv('./submission.csv')\n    \ntime_taken = time.perf_counter() - time_start\nprint(f'Generated {humanize.intword(count)} boards in {humanize.naturaldelta(time_taken)} = {1000 * time_taken/count:.3f}ms/board')","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 '../input/game-of-life-hashmap-solver/submission.csv' 'submission.csv'; do cat $FILE | grep ',1,' | wc -l | tr '\\n' ' '; echo $FILE; done) | sort -n;","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}