{"cells":[{"metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","trusted":true},"cell_type":"markdown","source":"# Geometric Invariant Hash Functions\n\nGeometric Invariant Hash Functions are relevant to grid worlds experiencing wraparound (closed manifolds) in [Conway's Reverse Game of Life](https://www.kaggle.com/c/conway-s-reverse-game-of-life) and [Halite](https://www.kaggle.com/c/halite) and are also relevant to the [Abstraction and Reasoning Corpus](https://www.kaggle.com/c/abstraction-and-reasoning-challenge)\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- https://www.kaggle.com/jamesmcguigan/summable-primes/\n\n\nI would like to propose two geometric invariant hash functions suitable for binary pixel images with wraparound.\n\n\nThe underlying concept is to take 1-dimentional views of the board from the perspective of each pixel in each up/down/left/right direction, and compare if the sum of pixelwise views is the same, regardless of the individual xy coordinates for each pixel. The hash value will remain invarient through geometric transforms such as `np.roll()`, `np.flip()` and `np.rot90()`.\n\nIf we encoded each view-direction-array as a binary number and summed the view from each direction, then there would be multiple combinations of views that could result in the same hash code, ie: \n`b100 == b100 + b000 == b011 + b001 == b001 + b011 == b010 + b010`\n\nIf we encode the pixel distances using a set of summable prime numbers, then we can create a unique hash for each pixelwise view of the board which is invarient to geometric transforms. If we apply the lesser constraint that no 2-pair of prime numbers in the set has the same sum (rather than any combination), then in practice, the hash algorithm still works, but we are not gaurenteed to be free of hash collisions.\n\n\n## Hash Functions Limitations\n\nWhen `hash_geometric_linear()` and `hash_translations()` functions where applied to [Conway's Reverse Game of Life](https://www.kaggle.com/c/conway-s-reverse-game-of-life), it was discoverd that hash collisions occured in about 29% of the dataset. This was mostly the result of boards containing multiple self-contained objects seperated by whitespace such that the pixels could not see each other horizontally or vertically. In such cases, the hash function matches when the shape and number individual objects are the same, but it cannot detect differences in whitespace gaps between the objects.\n- https://www.kaggle.com/jamesmcguigan/game-of-life-hashmap-solver\n\n`hash_geometric_concentric()` has now been implemented that replaces horizontal and vertical lines, with concentric circles emanating from each pixel.\nThis allows the hash function to \"see\" in all directions and detect self-contained objects seperated by whitespace, but at a 2x runtime performance cost."},{"metadata":{"trusted":true},"cell_type":"code","source":"import os\nimport sys\nimport math\nimport time\nimport matplotlib.pyplot as plt\nimport pandas as pd\nimport numpy as np\nfrom typing import Tuple\nfrom numba import njit\nfrom fastcache import clru_cache","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Primes"},{"metadata":{"trusted":true},"cell_type":"code","source":"def 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_np = np.array( generate_primes(625), dtype=np.int64 )  # first 625 primes \n\n\n# 50 Summable Primes\n# with the lesser constraint that: \n#     no 2-pair of prime numbers in the set has the same sum (rather than any combination)\n# This works in practice, but is not gaurenteed prevent hash collisions\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":{},"cell_type":"markdown","source":"# Geometric Invarient Hash \n\nGiven that the board experiences wraparound, this is equlivant to saying that the image is a [Closed Manifold](https://en.wikipedia.org/wiki/Closed_manifold).\n\nA view from each pixel (in each direction) is encoded using the set of Summable Primes. The directions are combined by taking the product. \nThe hash for the board is the sum of all pixel views.\n\nThe location of each pixel has not been encoded into the hash, only the relative distances of each pixel to each other pixel. As such this hash in invarient to geometric transforms such as `identity`, `np.roll`, `np.rot90` and `np.flip`."},{"metadata":{"_uuid":"d629ff2d2480ee46fbb7e2d37f6b5fab8052498a","_cell_guid":"79c7e3d0-c299-4dcb-8224-4455121ee9b0","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","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"@njit()\ndef get_concentric_prime_mask(shape: Tuple[int,int]=(25,25), pattern='diamond') -> np.ndarray:\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@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","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## Visualization\n\nThis is a visualization of how the hash function applies itself to each pixel\n\nNOTE: When `hash_geometric_linear()` and `hash_translations()` functions where applied to [Conway's Reverse Game of Life](https://www.kaggle.com/c/conway-s-reverse-game-of-life), it was discoverd that hash collisions occured in about 29% of the dataset. This was mostly the result of boards containing multiple self-contained objects seperated by whitespace such that the pixels could not see each other horizontally or vertically. In such cases, the hash function matches when the shape and number individual objects are the same, but it cannot detect differences in whitespace gaps between the objects."},{"metadata":{"trusted":true},"cell_type":"code","source":"# Hashable Primes: 2, 7, 23, 47, 61\ngeometric_hash_pattern = np.array([\n    [0,0,0,0,61,0,0,0,0],\n    [0,0,0,0,47,0,0,0,0],\n    [0,0,0,0,23,0,0,0,0],\n    [0,0,0,0, 7,0,0,0,0],\n [61,47,23,7, 2,7,23,47,61],\n    [0,0,0,0, 7,0,0,0,0],\n    [0,0,0,0,23,0,0,0,0],\n    [0,0,0,0,47,0,0,0,0],\n    [0,0,0,0,61,0,0,0,0],\n])\ntransforms = {\n    'identity': geometric_hash_pattern,\n    'flip':     np.flip(geometric_hash_pattern),\n    'rot90':    np.rot90(geometric_hash_pattern),\n    'roll':     np.roll(np.roll(geometric_hash_pattern, -2, axis=0), -1, axis=1),    \n}\n\nplt.figure(figsize=(len(transforms)*5, 5))\nfor i, (name, grid) in enumerate(transforms.items()):\n    plt.subplot(1, len(transforms), i+1)\n    plt.title(name)\n    plt.imshow(grid, cmap='nipy_spectral')","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"`hash_geometric_concentric()` replaces horizontal and vertical lines, with concentric circles emanating from each pixel.\nThis allows the hash function to \"see\" in all directions and detect self-contained objects seperated by whitespace, but at the cost of a 2x runtime performance cost."},{"metadata":{"trusted":true},"cell_type":"code","source":"for pattern in [ 'diamond', 'oval' ]:\n    geometric_hash_pattern = get_concentric_prime_mask((9,9), pattern=pattern)\n    transforms = {\n        'identity': geometric_hash_pattern,\n        'flip':     np.flip(geometric_hash_pattern),\n        'rot90':    np.rot90(geometric_hash_pattern),\n        'roll':     np.roll(np.roll(geometric_hash_pattern, 3, axis=0), 3, axis=1),    \n    }\n    get_concentric_prime_mask((9,9))\n    plt.figure(figsize=(len(transforms)*5, 5))\n    for i, (name, grid) in enumerate(transforms.items()):\n        plt.subplot(1, len(transforms), i+1)\n        plt.title(f'{pattern} - {name}')\n        #plt.imshow(grid, cmap='nipy_spectral')\n        plt.imshow(grid)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## Tests\nWe can test this using the Conway's Reverse Game of Life Dataset "},{"metadata":{"trusted":true},"cell_type":"code","source":"train_file = f'../input/conways-reverse-game-of-life-2020/train.csv'\ntest_file  = f'../input/conways-reverse-game-of-life-2020/test.csv'\n\ntrain_df   = pd.read_csv(train_file, index_col='id')\ntest_df    = pd.read_csv(test_file,  index_col='id')\n\ndef csv_to_numpy_list(df, key='start') -> np.ndarray:\n    return df[[ f'{key}_{n}' for n in range(25**2) ]].values.reshape(-1,25,25)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"def test_hash_geometric(hash_fn):\n    count  = 1000 if os.environ.get('KAGGLE_KERNEL_RUN_TYPE') == 'Interactive' else sys.maxsize\n    boards = csv_to_numpy_list(train_df, key='start')[:count]\n    for board in boards:\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_linear(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    return len(boards)\n        \ncount = test_hash_geometric(hash_fn=hash_geometric_linear)\nprint(f'hash_geometric_linear()     - {count} tests passed')\n\ncount = test_hash_geometric(hash_fn=hash_geometric_concentric)\nprint(f'hash_geometric_concentric() - {count} tests passed')","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Translation Invarient Hash \n\nHowever sometimes we may wish to distinguish between a `np.roll` translations and `np.flip` or `np.rot90` geometric transforms.\n\nWe can modify the above hash to be orientation specific, by only using views in the left and down directions  \n\nNOTE: Here, simply taking the sum of pixel hashes from `hash_translations_board()`, causes \n\nca we get hash collisions between `identity` and `rot180`. \nThe pixelwise views still produce different numbers, but their numbers somehow sum to the same. \nThis can be be fixed by sorting the pixel hashes by value and multiplying by an array of prime numbers. "},{"metadata":{"trusted":true},"cell_type":"code","source":"@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":{},"cell_type":"markdown","source":"## Visualization\n\nThis ia visualiztion of what is happening"},{"metadata":{"trusted":true},"cell_type":"code","source":"# Hashable Primes: 2, 7, 23, 47, 61, 83, 131, 163, 173, 251\ntranslation_hash_pattern = np.array([\n       [0,0,0,0, 83,0,0,0,0],\n       [0,0,0,0,131,0,0,0,0],\n       [0,0,0,0,163,0,0,0,0],\n       [0,0,0,0,173,0,0,0,0],\n[83,131,163,173,  2,7,23,47,61],\n       [0,0,0,0,  7,0,0,0,0],\n       [0,0,0,0, 23,0,0,0,0],\n       [0,0,0,0, 47,0,0,0,0],\n       [0,0,0,0, 61,0,0,0,0],\n])\ntransforms = {\n    'identity': translation_hash_pattern,\n    'flip':     np.flip(translation_hash_pattern),\n    'rot90':    np.rot90(translation_hash_pattern),\n    'roll':     np.roll(np.roll(translation_hash_pattern, -2, axis=0), -1, axis=1),    \n}\n\nplt.figure(figsize=(len(transforms)*5, 5))\nfor i, (name, grid) in enumerate(transforms.items()):\n    plt.subplot(1, len(transforms), i+1)\n    plt.title(name)\n    plt.imshow(grid, cmap='nipy_spectral')","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"board = csv_to_numpy_list(test_df.loc[85291], key='stop')[0]\nfor transforms in [\n    {\n        \"identity\": board,\n        \"np.roll(0)\":   np.roll(board, 10, axis=0),\n        \"np.roll(1)\":   np.roll(board, 10, axis=1),\n        \"np.rot180()\":  np.rot90(board, 2),\n    },\n    {\n        \"np.flip(0)\":   np.flip(board, axis=0),\n        \"np.flip(1)\":   np.flip(board, axis=1),\n        \"np.rot90()\":   np.rot90(board, 1),\n        \"np.rot180()\":  np.rot90(board, 2),\n        \"np.rot270()\":  np.rot90(board, 3),\n    }    \n]:\n    figure = plt.figure(figsize=(len(transforms)*5, 5*2))\n    figure.tight_layout(pad=10.0)\n    for i, (name, grid) in enumerate(transforms.items()):\n        plt.subplot(2, len(transforms), i+1)\n        plt.title(name)\n        plt.imshow(grid, cmap = 'binary')\n\n    for i, (name, grid) in enumerate(transforms.items()):\n        hashmap          = hash_translations_board(grid)\n        sum_hash         = np.sum(hashmap)\n        sum_x_prime_hash = hash_translations(grid)\n\n        plt.subplot(2, len(transforms), len(transforms) + i+1)\n        plt.title(f'sum = {sum_hash}\\nsum * primes = {sum_x_prime_hash}')\n        plt.imshow(hashmap, cmap = 'nipy_spectral')","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## Tests"},{"metadata":{"trusted":true},"cell_type":"code","source":"def test_hash_translations():\n    count  = 1000 if os.environ.get('KAGGLE_KERNEL_RUN_TYPE') == 'Interactive' else sys.maxsize\n    boards = csv_to_numpy_list(train_df, key='start')[:count]\n    for board in boards:\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    return len(boards)\n\ncount = test_hash_translations()\nprint(f'{count} tests passed')","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Profiler Performance"},{"metadata":{"trusted":true},"cell_type":"code","source":"count  = 10000 if os.environ.get('KAGGLE_KERNEL_RUN_TYPE') == 'Interactive' else sys.maxsize\nboards = csv_to_numpy_list(train_df, key='start')[:count]\n\ntime_start = time.perf_counter()\nhashes     = [ hash_geometric_linear(board) for board in boards ]\ntime_taken = time.perf_counter() - time_start\nprint(f'{1000 * time_taken/len(boards):0.3f}ms = hash_geometric_linear()')\n\ntime_start = time.perf_counter()\nhashes     = [ hash_geometric_concentric(board) for board in boards ]\ntime_taken = time.perf_counter() - time_start\nprint(f'{1000 * time_taken/len(boards):0.3f}ms = hash_geometric_concentric()')\n\ntime_start = time.perf_counter()\nhashes     = [ hash_translations(board) for board in boards ]\ntime_taken = time.perf_counter() - time_start\n\nprint(f'{1000 * time_taken/len(boards):0.3f}ms = hash_translations()')","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}