[Leetcode]957. Prison Cells After N Days

There are 8 prison cells in a row, and each cell is either occupied or vacant.
Each day, whether the cell is occupied or vacant changes according to the following rules:
1. If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
2. Otherwise, it becomes vacant.
(Note that because the prison is a row, the first and the last cells in the row can't have two adjacent neighbors.)
We describe the current state of the prison in the following way: cells[i] == 1 if the i-th cell is occupied, else cells[i] == 0.
Given the initial state of the prison, return the state of the prison after N days (and N such changes described above.)

Input: cells = [0,1,0,1,1,0,0,1], N = 7 Output: [0,0,1,1,0,0,0,0] Explanation: The following table summarizes the state of the prison on each day: 
Day 0: [0, 1, 0, 1, 1, 0, 0, 1] 
Day 1: [0, 1, 1, 0, 0, 0, 0, 0] 
Day 2: [0, 0, 0, 0, 1, 1, 1, 0] 
Day 3: [0, 1, 1, 0, 0, 1, 0, 0] 
Day 4: [0, 0, 0, 0, 0, 1, 0, 0] 
Day 5: [0, 1, 1, 1, 0, 1, 0, 0] 
Day 6: [0, 0, 1, 0, 1, 1, 0, 0] 
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

When I first came across this question I didn’t know where to start. The problem’s setup is not complex, yet at the first glance, I have no clue about which algorithm would work: BFS, DFS, binary search, dynamic programming, and etc..

At the last when I checked the solution provided by @lee215, I realized that, instead of mechanically applying algorithm templates, it’s critical to develop logical thinking so as to collect information, analyze it, and developing solutions.

Logic

This solution is inspired by @lee215. There are 8 numbers in the array and, since the first and the second will become 0 according to question, there are only 2^{6} possible results. Moreover, given a state s_0, after one day, state s_1 is fixed. Therefore there will be loops for the states.

Knowing there’s a loop, we can keep transforming the input and record the new states. When we find a repeated state at day M, we know there’s a loop with the range of (N-M), and therefore we can simply skip (N-M)*k days.

Code

class Solution:
    def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:
        seen = {}
        while N:
            seen.setdefault(str(cells),N)
            N -= 1
            cells = [0] + [cells[i - 1] ^ cells[i + 1] ^ 1 for i in range(1, 7)] + [0]
            if str(cells) in seen:
                N %= seen[str(cells)] - N
        return cells