import numpy as np to_tuple3d = lambda it: tuple( tuple(tuple(j) for j in i) for i in it) def rotations24(polycube): def rotations4(polycube, axes): for i in range(4): yield np.rot90(polycube, i, axes) yield from rotations4(polycube, (1,2)) yield from rotations4(np.rot90(polycube, 2, axes=(0,2)), (1,2)) yield from rotations4(np.rot90(polycube, axes=(0,2)), (0,1)) yield from rotations4(np.rot90(polycube, -1, axes=(0,2)), (0,1)) yield from rotations4(np.rot90(polycube, axes=(0,1)), (0,2)) yield from rotations4(np.rot90(polycube, -1, axes=(0,1)), (0,2)) def to_points(arr): return list(map(tuple, np.transpose(np.nonzero(arr)))) def to_arr(points): min_x = min(point[0] for point in points) max_x = max(point[0] for point in points) min_y = min(point[1] for point in points) max_y = max(point[1] for point in points) min_z = min(point[2] for point in points) max_z = max(point[2] for point in points) #print(min_x,max_x, min_y,max_y, min_z,max_z) m = np.zeros((max_x-min_x+1, max_y-min_y+1, max_z-min_z+1), dtype = int) for a,b,c in points:m[a - min_x,b - min_y,c - min_z] = 1 return m def canonical_h(p): start_m = to_arr(p) rot = sorted(list(map(to_tuple3d, rotations24(start_m))))[0] return rot def near(x,y,z): yield (x+1,y,z) yield (x-1,y,z) yield (x,y+1,z) yield (x,y-1,z) yield (x,y,z+1) yield (x,y,z-1) def check_ortconnected(P): temp_p = P.copy() q = [temp_p[0]] temp_p = temp_p[1:] r = len(P) count = 1 while True: if len(q)==0:break for d in near(*q[0]): if d in temp_p: temp_p.remove(d) q.append(d) count +=1 q = q[1:] if count < r: return False else: return True out = set() memo = set() hole_seed = [(1,1,1),] seed_cells_one_hole = [(0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 2), (1, 2, 1), (2, 1, 1)] def dfs_polyomino_search(seed,n_cells_left): cand = set() for k in seed: for d in near(*k): if d not in seed and d not in hole_seed: cand.add(d) if n_cells_left == 1: for k in cand: temp_seed = seed.copy() temp_seed.append(k) h = canonical_h(temp_seed) if h not in out and check_ortconnected(temp_seed): out.add(h) #print(h) else: for k in cand: temp_seed = seed.copy() temp_seed.append(k) h = canonical_h(temp_seed) if h not in memo: memo.add(h) dfs_polyomino_search(temp_seed, n_cells_left-1) big_n = 11 dfs_polyomino_search(seed_cells_one_hole, big_n - 6) #6 in seed print(out) print(len(out)) # with open('data1.txt', 'a') as a_writer: # a_writer.write(f'n:{14}; found: {len(out)}')