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 thei
-th cell is occupied, elsecells[i] == 0
. Given the initial state of the prison, return the state of the prison afterN
days (andN
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