Solution for google foobar: Expanding Nebula

expanding_nebula.py

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 answer(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

This is a pretty ingenious solution. I'm having a pretty hard time following the logic of it though. Would you mind explaining the theory behind the generate function?

The idea is to apply the cellar automata transfer function to all possible 2x(n+1) grids and check if the resulting 1xn row is one of the rows in your input grid. If so then this 2x(n+1) grid was a preimage for the row.

Can you please explain the logic behind build_map function?

Can you please explain the logic behind build_map function?

build_map returns a mapping from (row, first row of preimage) to (set of second rows of preimage)

Brilliant Solution! What does the zero fill left shift on lines on line 12 do? Is the generate function a bitmask? Thanks for the very efficient solution. A for me to learn!