Greenhouse vents

A vent controller with no memory rewrites the whole row every night. Simulating a billion nights is out of the question, so find the night it starts repeating itself.

The problem

A greenhouse has eight roof vents in a row, each open or closed. Every night the controller rewrites the whole row at once from the row it saw at dusk:

• A vent with two neighbours is open at dawn if those two were in the same state at dusk — both open, or both closed — and closed otherwise.
• The two end vents have one neighbour each, so they always close.

Every vent is decided from the dusk row, never from a half-rewritten one. Given today's dusk row and a number of nights, report the row the gardener finds.

Input. vents — eight integers, 1 for open and 0 for closed. nights — how many nights to run the controller.

Output. A list of eight integers, the row after nights nights.

Example.

vents = [1, 0, 0, 1, 0, 0, 1, 0], nights = 1   ->  [0, 0, 0, 1, 0, 0, 1, 0]

Vent 3 opens because vents 2 and 4 were both closed, and vent 6 because vents 5 and 7 were. Every other vent sees a mismatched pair, and both ends close.

A second example, which shows the row cannot simply be simulated:

vents = [1, 0, 0, 1, 0, 0, 1, 0], nights = 1000000000   ->  [0, 0, 1, 1, 1, 1, 1, 0]
vents = [1, 0, 1, 0, 1, 0, 1, 0], nights = 999999937     ->  [0, 1, 1, 0, 0, 1, 1, 0]

The first row settles into a loop of length 14, the second into one of length 7. The loop length depends on where you start.

Constraints.

• len(vents) == 8
• vents[i] is 0 or 1
• 1 <= nights <= 10^9

Hints

Approach

Brute force

Run the rule nights times. Each night is eight comparisons, so a billion nights is 8 x 10^9 operations — minutes of work for an eight-bit answer.

The insight

From the first dawn onward both ends are closed, so only the six inner vents vary and at most 64 different rows can ever appear — the walk has to revisit one within 65 nights, and from there it repeats forever.

Determinism is the precondition: one row has exactly one successor, so the moment a row appears twice the stretch between the sightings is a loop that runs unchanged from then on. Whole loops can then be skipped without simulating them, leaving fewer than one loop of nights to walk by hand.

Algorithm

1. Keep a map from row to the night it first appeared, and a night counter.
2. Before each night, look the current row up.
3. On a miss, record it and simulate one night.
4. On a hit, the loop length is the gap between now and the recorded night. Jump the counter forward by as many whole loops as fit in the nights left.
5. Empty the map so the jump is never retried, then simulate the few nights left.

Complexity

Time O(S) where S is the number of reachable rows — at most 64 here, so the controller runs about 130 times at most, whatever nights is. Space O(S), one entry per row seen.

Solution

"""Greenhouse vents — skip the repeats by remembering every state in a hash map."""


def next_state(vents):
    """One night of the controller rule; the two end vents always close."""
    return [0] + [1 if vents[i - 1] == vents[i + 1] else 0
                  for i in range(1, len(vents) - 1)] + [0]


def solve(vents, nights):
    seen = {}                       # state tuple -> the night it first appeared
    state = list(vents)
    night = 0
    while night < nights:
        key = tuple(state)
        if key in seen:
            # invariant: the rule is deterministic, so a repeated state means
            # every later night repeats too, with this period.
            period = night - seen[key]
            night += ((nights - night) // period) * period
            seen = {}               # stop looking; only the tail is left to walk
        else:
            seen[key] = night
        if night < nights:
            state = next_state(state)
            night += 1
    return state

TESTS = [
    (([1, 0, 0, 1, 0, 0, 1, 0], 1), [0, 0, 0, 1, 0, 0, 1, 0]),
    (([1, 0, 0, 1, 0, 0, 1, 0], 5), [0, 0, 1, 0, 1, 0, 1, 0]),
    (([1, 0, 0, 1, 0, 0, 1, 0], 1000000000), [0, 0, 1, 1, 1, 1, 1, 0]),
    (([1, 0, 1, 0, 1, 0, 1, 0], 999999937), [0, 1, 1, 0, 0, 1, 1, 0]),
    (([0, 0, 0, 0, 0, 0, 0, 0], 3), [0, 0, 0, 1, 1, 0, 0, 0]),
    (([1, 1, 1, 1, 1, 1, 1, 1], 2), [0, 0, 1, 1, 1, 1, 0, 0]),
    (([0, 1, 1, 0, 1, 1, 0, 1], 14), [0, 0, 1, 1, 1, 0, 0, 0]),
    (([0, 1, 1, 0, 1, 1, 0, 1], 1), [0, 0, 0, 1, 0, 0, 1, 0]),
]

Pitfalls

• Rewriting the row in place. Storing vent 1 before reading vent 2 makes later vents read a row that is half tomorrow. From eight open vents, one night should give [0, 1, 1, 1, 1, 1, 1, 0]; in place it gives eight zeros.
• Reducing nights modulo the loop length before the loop is entered. A starting row with open ends never appears again, so it sits outside the loop: fourteen nights from [0, 1, 1, 0, 1, 1, 0, 1] is not the row you started with.
• Wrapping the ends around. Vent 0 has one neighbour, not two. Treating vent 7 as its left neighbour builds a different machine with a different loop. A list also cannot be a map key at all; freeze each row into a tuple.

Variants

• The badge scanned once — a map that remembers what has been seen, keyed on arriving values rather than whole states.
• Settlement blocks — also collapses a huge space into a small one, by remainder rather than by reachability.