Expanding Nebula

Created: Oct 28, 2026

Last modified: Oct 28, 2026

* AI-generated from the code I used in Google Foobar

TL, DR.

Show challenge description

One of the escape pods drifted into a nebula and you lost track of it. Luckily, the nebula's gas changes by a simple rule, so if you can work out what it looked like a moment earlier, you can narrow down where to look. The challenge isn't finding that earlier state, though. It's counting how many different earlier states could have led to what you see now.

Just like Disorderly Escape, I didn't solve this one on my own: I got through both level 5 problems with outside help. What follows explains how the solution I submitted works.

# The rule

The nebula is a grid of cells that either have gas or are empty. To get the next state, each cell looks at the 2 × 2 block it forms with its neighbors to the right and below. If exactly one cell in that block has gas, the new cell has gas. With 0, 2, 3 or 4, it's empty. The cells in the last row and column don't have a full block, so the new state loses a row and a column.

On the left is the statement's previous state p, and on the right the current one, c. Click a cell of c to see which block decides it, and click the cells of p to add or remove gas and watch everything update.

Cell (0, 0) looks at a block with gas in 1 cell, so it has gas. This current state could have come from 4 different previous states.

# Going backwards

Going forward is easy, but going backwards the rule loses information. An empty block can come from 12 different combinations, and one with gas from 4. That's why the same current state comes from several earlier ones: the statement's c comes from p and its reflections, 4 in total.

Brute force is hopeless. The current state is up to 9 × 50, so the previous one is up to 10 × 51: that's 510 cells and 2⁵¹⁰ states to try. We need to use the shape of the problem.

# One column at a time

The key is that the grid is short: 9 rows at most, even if it's 50 columns wide. A column of the current state only depends on two neighboring columns of the previous state, the one in the same position and the one to its right. And a previous column, with 10 cells at most, can only take 2¹⁰ = 1,024 values. That's very manageable.

For each current column, precol finds every pair of previous columns (left, right) that produces it. It doesn't try them all; it builds them one row at a time. The first row comes from devol, which stores the 2 × 2 blocks that give each result, and every new row only has to follow the rule together with the row above it, which is what evol checks. At the end, bitlist turns each column into a number so it can be used as a dictionary key.

# Chaining them like dominoes

Here's the nice part. Two neighboring columns of the current state share a column of the previous state: the right column of one pair has to be the left column of the next, like dominoes. So all you need is to keep track of how many ways there are to build everything up to a given column, ending in each possible value:

To start, every column that can sit to the left of the first pair counts as 1. Then you move one column at a time, and at the end you add up all the counts. That's dynamic programming: no previous state is ever built in full; you only count the ways to reach each column.

# Step by step

Pick one of the statement's tests and move the slider. Each step handles one column of the current state (the highlighted one) and shows below it the previous columns that can go in the next position, drawn upright, with how many ways lead to each. Notice how, out of all the possible columns, only a few survive.

Before looking at any column: 7 of the 16 possible columns can go first, each in 1 way.

# The code

Here's the code I submitted, written for Python 2.7, which is what Foobar ran:

def solution(g):
    transposed = tuple(zip(*g))
    preimgs = precol(transposed[0])
    precount = dict()
    for pair in preimgs:
        precount[pair[0]] = 1
    for col in transposed:
        preimgs = precol(col)
        count = dict()
        for pair in preimgs:
            if pair[0] not in precount: precount[pair[0]] = 0
            if pair[1] not in count: count[pair[1]] = 0
            count[pair[1]] += precount[pair[0]]
        precount = count
    return sum(precount.values())


def precol(col):
    possib = ((0, 0), (0, 1), (1, 0), (1, 1))
    curr = devol[col[0]]
    for i in range(1, len(col)):
        new = []
        for tes in curr:
            for comb in possib:
                if evol[(tes[i], comb)] == col[i]:
                    new.append(tes+(comb,))
        curr = tuple(new)
    bin_ret = [tuple(zip(*i)) for i in curr]
    return [tuple([bitlist(nu) for nu in possibl]) for possibl in bin_ret]

def bitlist(bitsl):
    out = 0
    for bit in bitsl:
        out = (out << 1) | bit
    return out

evol = {((0, 0), (0, 0)): 0, ((0, 0), (0, 1)): 1, ((0, 0), (1, 0)): 1,
        ((0, 0), (1, 1)): 0, ((0, 1), (0, 0)): 1, ((0, 1), (0, 1)): 0,
        ((0, 1), (1, 0)): 0, ((0, 1), (1, 1)): 0, ((1, 0), (0, 0)): 1,
        ((1, 0), (0, 1)): 0, ((1, 0), (1, 0)): 0, ((1, 0), (1, 1)): 0,
        ((1, 1), (0, 0)): 0, ((1, 1), (0, 1)): 0, ((1, 1), (1, 0)): 0,
        ((1, 1), (1, 1)): 0}
devol = {0: (((0, 0), (0, 0)), ((0, 0), (1, 1)), ((0, 1), (0, 1)),
             ((0, 1), (1, 0)), ((0, 1), (1, 1)), ((1, 0), (0, 1)),
             ((1, 0), (1, 0)), ((1, 0), (1, 1)), ((1, 1), (0, 0)),
             ((1, 1), (0, 1)), ((1, 1), (1, 0)), ((1, 1), (1, 1))),
         1: (((1, 0), (0, 0)), ((0, 1), (0, 0)), ((0, 0), (1, 0)),
             ((0, 0), (0, 1)))}

# Wrapping up

When a grid is narrow in one direction, store each full row or column as a number with a few bits and run dynamic programming along the other direction. That way, what looked like 2⁵¹⁰ states turns into 50 steps with at most 1,024 possible columns each.