Designing a hash test function

Here, we explore how to create arbitrary-dimensional subgrids in numpy, then compute a hash over them.



In [399]:

    
import numpy as np
from numba import autojit



In [400]:

    
size = (4,4)



In [401]:

    
A = np.random.randint(0,2,size)
print A



In [402]:

    
ng = (2, 2)
gridl = [s/n for s,n in zip(size,ng)]
print gridl









    



[2, 2]



In [403]:

    
gs = [[l * i for i in range(ngi)] for ngi,l in zip(ng,gridl)]
print gs









    



[[0, 2], [0, 2]]



In [404]:

    
import itertools



In [405]:

    
gs = list(itertools.product(*gs))
print gs









    



[(0, 0), (0, 2), (2, 0), (2, 2)]



In [406]:

    
slices = [[(slice(i,i+l)) for i, l in zip(gsi,gridl)] for gsi in gs]
sliceA = [slice(0,s) for s in size]
print slices
print sliceA









    



[[slice(0, 2, None), slice(0, 2, None)], [slice(0, 2, None), slice(2, 4, None)], [slice(2, 4, None), slice(0, 2, None)], [slice(2, 4, None), slice(2, 4, None)]]
[slice(0, 4, None), slice(0, 4, None)]



In [407]:

    
slicei = slices[0]
print slicei









    



[slice(0, 2, None), slice(0, 2, None)]



In [408]:

    
grids = [A[i] for i in slices]



In [409]:

    
print A
print sliceA
for grid, slice in zip(grids,slices):
    print grid
    print slice









    



[[0 1 1 1]
 [1 0 1 0]
 [0 1 0 0]
 [1 1 1 1]]
[slice(0, 4, None), slice(0, 4, None)]
[[0 1]
 [1 0]]
[slice(0, 2, None), slice(0, 2, None)]
[[1 1]
 [1 0]]
[slice(0, 2, None), slice(2, 4, None)]
[[0 1]
 [1 1]]
[slice(2, 4, None), slice(0, 2, None)]
[[0 0]
 [1 1]]
[slice(2, 4, None), slice(2, 4, None)]



In [410]:

    
def hashfun(g, s):
    """Given a grid and a slice defining its range, compute hash using a hash function that can be reduced over subgrids by summation """

    X = np.mgrid[s]
    h = 0
    for i in range(X.shape[0]):
        h += np.sum((X[i] + 1)*g)
    return h



In [411]:

    
hashes = [hashfun(g, s) for g, s in zip(grids, slices)]
print sum(hashes)
print hashfun(A, sliceA)



In [412]:

    
X = np.mgrid[s]
print X.shape









    



(2, 2, 2)



In [413]:

    
ranges = [np.arange(s.start, s.stop) for s in slicei]
print ranges









    



[array([0, 1]), array([0, 1])]



In [414]:

    
@autojit
def life_step(g, gnew):
    """Given a grid, compute one Game of Life step along the interior of the grid into gnew"""
    
    m,n = g.shape
    
    for i in range(1,m-1):
        for j in range(1,n-1):

            sum = 0

            for ii in range(i-1,i+2):
                for jj in range(j-1,j+2):
                    if ii == i and jj == j:
                        continue
                    sum += g[ii,jj]
            
            if sum < 2 or sum > 3:
                gnew[i,j] = 0
            elif sum == 3:
                gnew[i,j] = 1
            else:
                gnew[i,j] = g[i,j]



In [415]:

    
#A = np.ones(size, dtype=np.int64)
A = np.random.randint(0,2,size)
print A



In [416]:

    
B = np.zeros_like(A)



In [417]:

    
life_step(A, B)



In [418]:

    
print B

Designing Test Functions



In [419]:

    
import numpy.testing as npt

size = (4,4)
glide_size = (16,16)

def test_ones():
    """check that all ones gives right result"""
    A = np.ones(size, dtype=np.int64)
    B = np.zeros_like(A)

    life_step(A,B)

    npt.assert_equal(A, np.ones(size))
    npt.assert_equal(B, np.zeros(size))
    
    
def test_zeros():
    """check that all zeros gives right result"""
    
    A = np.zeros(size, dtype=np.int64)
    B = np.zeros_like(A)

    life_step(A,B)

    npt.assert_equal(A, np.zeros(size))
    npt.assert_equal(B, np.zeros(size))
    
    
def test_block():
    """check that an internal block gives the right result"""
    
    A = np.zeros(size, dtype=np.int64)
    A[1:2][1:2] = 1
    B = np.zeros_like(A)
    C = A.copy()
    
    life_step(A,B)

    npt.assert_equal(A, B)
    npt.assert_equal(A, C)    
    
    
def test_two_blocks():
    """check that an internal block is correctly preserved"""
    
    A = np.zeros(size, dtype=np.int64)
    A[1:2][1:2] = 1
    B = np.zeros_like(A)
    C = A.copy()

    life_step(A,B)
    life_step(B,A)
    
    npt.assert_equal(A, B)
    npt.assert_equal(A, C)
    
def test_glider():
    """check that a glider moves correctly"""

    G = np.zeros((3,3), dtype=np.int64)
    G[0,1] = 1
    G[1,2] = 1
    G[2,0:3] = 1
    
    A = np.zeros(glide_size, dtype=np.int64)
    B = np.zeros_like(A)

    A[1:4,1:4] = G
    
    life_step(A,B)
    
    C = np.zeros_like(A)
    C[2][[1,3]] = 1
    C[3,2:4] = 1
    C[4,2] = 1
    
    npt.assert_equal(B, C)



In [420]:

    
test_ones()
test_zeros()
test_block()
test_two_blocks()
test_glider()



In [421]:

    
G = np.zeros((3,3), dtype=np.int64)
G[0,1] = 1
G[1,2] = 1
G[2,0:3] = 1
print G

A = np.zeros((5,5), dtype=np.int64)
A[1:4,1:4] = G
print A









    



[[0 1 0]
 [0 0 1]
 [1 1 1]]
[[0 0 0 0 0]
 [0 0 1 0 0]
 [0 0 0 1 0]
 [0 1 1 1 0]
 [0 0 0 0 0]]

See the files test_life.py and bench_life.py