{"cells":[{"metadata":{},"cell_type":"markdown","source":"# Problem statement\n\nThis Kernel is an attempt to find some clues to solve more generic problem, that can give solution for this competition and can be defined as:\n* Define maximum \"ancestral\" depth as maximum number of turns we can go backwards in time in game of life among all possible parent states\n* Find algorithm that for any board state will return one of the immediate parent states with maximum \"ancestral\" depth\n\nFor example if some board state has grandparents but not grand-grandparents, hypotetical algorithm will return any parent state that also has parent.\n\nWe know that all \"stop\" states in the train and test data have \"ancestral\" depth of at least \"delta(1-5) + warmup(5)\".\nSo algorithm that returns parent state with maximum depth for any initial state will guarantee, that it can be applied recursively at least delta times, giving us desired \"start\" state (one of).\n\nHere is one of statements, that could help determine desired algorithm:\n* Any initial state has infinite \"ancestral\" depth if and only if there is a cycle of states that includes initial state\n\nLet's try to find more patterns or properties like the one above. \n\n\n# Reduce board size\n\nIn attempt to find patterns that can help formulate such algorithm, I decided to reduce board size to be fully solvable in memory and still meaningful.\n* 1x1 the only cell is own neighbour 8 times\n* 2x2 cells have same other cells as 2 or 4 of their neighbours\n* 3x3 Every cell is a neighbour of any other cell\n* 3x4 Cells in each row share all same neighbours\n\nSo, 4x4 is a first board size that starts to show some properties that possibly can be generalized to larger boards."},{"metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","trusted":true,"_kg_hide-input":true,"_kg_hide-output":true},"cell_type":"code","source":"import numpy as np\nfrom scipy.signal import convolve2d\nfrom tqdm.auto import tqdm\nimport matplotlib.pyplot as plt\nfrom pprint import pprint\n\nwindow = np.ones((3, 3))\n\ndef plot_3d(solution_3d: np.ndarray, title, size=3, max_cols=10, has_target=False):\n    N = len(solution_3d)\n    if N <= 0:\n        return\n    cols = min(N, max_cols)\n    rows = (N - 1) // max_cols + 1\n    plt.figure(figsize=(cols*size, rows*size))\n    plt.suptitle(title)\n    for t in range(N):\n        board = solution_3d[t]\n        plt.subplot(rows, cols, t + 1)\n        plt.imshow(board, cmap='binary')\n        plt.title('target' if t == 0 and has_target else f'source {t}')\n    plt.show()\n\ndef life_step(X: np.ndarray):\n    C = convolve2d(X, window, mode='same', boundary='wrap')\n    return (C == 3) | (X & (C == 4))\n\nSIZE = 4\n\nempty_board = np.zeros((SIZE,SIZE), dtype=bool)\nm2i = np.array([2**i for i in range(SIZE**2)]).reshape(SIZE,SIZE)\n\ndef is_d_step_child(n0, d, children):\n    n1 = n0\n    while d > 0:\n        n1 = children[n1]\n        d -= 1\n        if n1 == n0:\n            return d == 0\n    return n1 == n0\n\nr = np.array([2**i for i in range(SIZE)], dtype=int)\nrr = np.cumsum(np.array([2**(i-1) for i in range(SIZE)], dtype=int))\nc = np.array([2**(i*SIZE) for i in range(SIZE)], dtype=int)\ncc = np.cumsum(np.array([2**((i-1)*SIZE) for i in range(SIZE)], dtype=int))\nsr = np.sum(r)\nsc = np.sum(c)\nmr = 2**SIZE\nmc = 2**(SIZE*SIZE)\n\ndef h_flip(x):\n    x = ((x & 0x5555) << 1) | ((x & 0xAAAA) >> 1)\n    x = ((x & 0x3333) << 2) | ((x & 0xCCCC) >> 2)\n    return x\n    \ndef v_flip(x):\n    x = ((x & 0x0F0F) << 4) | ((x & 0xF0F0) >> 4)\n    x = ((x & 0x00FF) << 8) | ((x & 0xFF00) >> 8)\n    return x\n\ndef d_flip(x):\n    x = ((x & 0x0001) << 15) | ((x & 0x0012) << 10) | ((x & 0x0124) << 5) | (x & 0x1248) | ((x & 0x2480) >> 5) | ((x & 0x4800) >> 10) | ((x & 0x8000) >> 15) \n    return x\n\ndef hash(n):\n    dn = d_flip(n)\n    hn = h_flip(n)\n    hdn = h_flip(dn)\n    n = np.array([n, v_flip(n), hn, v_flip(hn), dn, v_flip(dn), hdn, v_flip(hdn)]).reshape((1,-1,1))\n    n = (n & (cc * sr)) * mc // c + (n & ((sc - cc) * sr)) // c\n    n = n.T\n    n = (n & (rr * sc)) * mr // r + (n & ((sr - rr) * sc)) // r\n    return np.min(n)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"There are 2^16 possible states of 4x4 board. We can code each state as a single number in range 0-65535.\n\nTo further reduce number of dirrerent states we will consider states equal if we can get one state from another by translation (E.g. using \"numpy.roll\") \n\nFirst let's find next state for every initial state and build direct and inverse index - dictionary, that for every possible child state stores list of all parent states."},{"metadata":{"_kg_hide-output":true,"trusted":true},"cell_type":"code","source":"N = 2**(SIZE**2)\nboard = np.tile(empty_board, (2, 1, 1))\nchildren = np.zeros(N, dtype=int)\nmapping = {}\nfor n0 in tqdm(range(N), total=N):\n    board[0] = (m2i & n0) != 0\n    board[1] = life_step(board[0])\n    n1 = np.sum(board[1] * m2i)\n    children[n0] = n1\n    n1 = hash(n1)\n    if n1 not in mapping:\n        mapping[n1] = set()\n    mapping[n1].add(hash(n0))","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"If for some state child state is the same state, let's call this state \"Static\". For static states we can ignore all other parent states.\n\nLet's see what \"Static\" states exists on 4x4 board."},{"metadata":{"trusted":true},"cell_type":"code","source":"static = list(set([hash(n0) for n0 in range(N) if is_d_step_child(n0, 1, children)]))\nS = len(static)\nboard = np.tile(empty_board, (S, 1, 1))\nfor s in tqdm(range(S), total=S):\n    board[s] = (m2i & static[s]) != 0\nplot_3d(board, f'Static boards')","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Similarly we can define \"Cyclic\" boards, that return to initial state after 2,3,... steps."},{"metadata":{"trusted":true},"cell_type":"code","source":"D = 16\ncyclic = [[]]*D\nfor d in tqdm(range(D), total=D):\n    cyclic[d] = list(set([hash(n0) for n0 in range(N) if is_d_step_child(n0, d+1, children)]))\nprint({d+1:len(cyclic[d]) for d in range(D)})","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"for d in tqdm(range(D), total=D):\n    S = len(cyclic[d])\n    board = np.tile(empty_board, (S, 1, 1))\n    for s in tqdm(range(S), total=S):\n        board[s] = (m2i & cyclic[d][s]) != 0\n    plot_3d(board, f'{d+1}-step cyclic boards')","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Cyclic states can not be parent to any non-cyclic states (there is no way forward out of the loop), so we can exclude them from inverse index"},{"metadata":{"trusted":true},"cell_type":"code","source":"mapping = {k:mapping[k] for k in mapping if all(k not in cyclic[d] for d in range(D))}\npprint({n1:len(mapping[n1]) for n1 in mapping})","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"There are no more cycles in the inverse index. Now we can calculate maximum \"ancestral\" depth for remaining states. It's guaranteed to be finite (less than 2^16)."},{"metadata":{"trusted":true},"cell_type":"code","source":"depth = {n1:0 for n1 in range(N)}\nchanged = True\nwhile changed:\n    changed = False\n    for n1 in range(N):\n        if n1 in mapping:\n            for n0 in mapping[n1]:\n                if n0 != n1 and depth[n1] < depth[n0] + 1:\n                    depth[n1] = depth[n0] + 1\n                    changed = True","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Now we can only keep in inverse index previous states that have maximum \"ancestral\" depth"},{"metadata":{"trusted":true},"cell_type":"code","source":"for n1 in range(N):\n    if n1 in mapping:\n        max_depth = max(depth[n0] for n0 in mapping[n1])\n        mapping[n1] = [n0 for n0 in mapping[n1] if depth[n0] == max_depth]","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Finally we can see, which parent state we would need to choose for every non-cyclic state to be able to get as deep as maximum \"ancestral\" depth steps into the past. (Output can show states that can be obtained from exact parent state by translations and flips)"},{"metadata":{"trusted":true},"cell_type":"code","source":"keys = sorted(mapping.keys())\nM = len(keys)\nfor n1 in tqdm(keys, total=M):\n    board = np.tile(empty_board, (len(mapping[n1])+1, 1, 1))\n    board[0] = (m2i & n1) != 0\n    board[1:] = [(m2i & n0) != 0 for n0 in mapping[n1]]\n    plot_3d(board, f'{n1} (depth {depth[n1]})', has_target=True)","execution_count":null,"outputs":[]}],"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}