-
Notifications
You must be signed in to change notification settings - Fork 13
/
expanding_nebula.py
37 lines (32 loc) · 1.05 KB
/
expanding_nebula.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def generate(c1,c2,bitlen):
a = c1 & ~(1<<bitlen)
b = c2 & ~(1<<bitlen)
c = c1 >> 1
d = c2 >> 1
return (a&~b&~c&~d) | (~a&b&~c&~d) | (~a&~b&c&~d) | (~a&~b&~c&d)
from collections import defaultdict
def build_map(n, nums):
mapping = defaultdict(set)
nums = set(nums)
for i in range(1<<(n+1)):
for j in range(1<<(n+1)):
generation = generate(i,j,n)
if generation in nums:
mapping[(generation, i)].add(j)
return mapping
def solution(g):
g = list(zip(*g)) # transpose
nrows = len(g)
ncols = len(g[0])
# turn map into numbers
nums = [sum([1<<i if col else 0 for i, col in enumerate(row)]) for row in g]
mapping = build_map(ncols, nums)
preimage = {i: 1 for i in range(1<<(ncols+1))}
for row in nums:
next_row = defaultdict(int)
for c1 in preimage:
for c2 in mapping[(row, c1)]:
next_row[c2] += preimage[c1]
preimage = next_row
ret = sum(preimage.values())
return ret