import numpy as np
m = np.array([[1,1,0],
[0,1,0,],
[0,1,0]])
stored_shapes = {}
def generate_super_shape(array, counter = 1, shapes=None): # get rotated versions of input shape and input rotated 90 degrees
if shapes == None:
shapes = []
shapes.append(array)
shapes.append(np.fliplr(array))
shapes.append(np.flipud(array))
shapes.append(np.rot90(array, 2))
if counter == 2:
return shapes
else:
return generate_super_shape(np.rot90(array), counter = counter + 1, shapes=shapes)
def is_shape_stored(array, hashmap):
res = generate_super_shape(array)
super_shape_1 = np.array([res[0], res[1], res[2], res[3]])
super_shape_2 = np.array([res[4], res[5], res[6], res[7]])
final_super_shape = np.array([super_shape_1, super_shape_2])
oned_final_super_shape = final_super_shape.ravel()
oned_final_super_shape = tuple(oned_final_super_shape.tolist())
if oned_final_super_shape in hashmap:
return True
else:
hashmap[oned_final_super_shape] = 1
return False
The idea is to hopefully make it so that you only spend time generating the superposed shape which is composed of all possible rotations and then store this in a hashtable for O(1) lookup time. This means that the next time you generate a shape, to check if its already had a rotated counterpart stored, just generate the superposed shape and lookup the hashtable for it. In theory the superposed shape should be the same if I use a rotated version of a shape I have already seen as the superposed version overlays all the shapes into one (combining all the 2d arrays into one flattened array).
The issue is that I'm not sure how to make it so that the arrays are always aligned correctly as the superposed shape will be in a different order depending on the input shape and that will mean looking it up in the hash table will result in a false result as the superposed shape will be different.
Not sure if this works at all and if it's even faster, just had an idea.
The idea is to hopefully make it so that you only spend time generating the superposed shape which is composed of all possible rotations and then store this in a hashtable for O(1) lookup time. This means that the next time you generate a shape, to check if its already had a rotated counterpart stored, just generate the superposed shape and lookup the hashtable for it. In theory the superposed shape should be the same if I use a rotated version of a shape I have already seen as the superposed version overlays all the shapes into one (combining all the 2d arrays into one flattened array).
The issue is that I'm not sure how to make it so that the arrays are always aligned correctly as the superposed shape will be in a different order depending on the input shape and that will mean looking it up in the hash table will result in a false result as the superposed shape will be different.
Not sure if this works at all and if it's even faster, just had an idea.
Drawing Example: