Prison Cells After N Days
Problem
There are 8 prison cells in a row, each either occupied (1) or vacant (0). Every day the cells change at once: a cell becomes occupied if its two adjacent neighbors are both occupied or both vacant, otherwise it becomes vacant. The two cells at the ends have only one neighbor, so they always become vacant. Given the initial state and an integer n, return the state after n days. Because the state space is tiny, the sequence is eventually periodic, so we detect the cycle and skip ahead instead of simulating every day.
cells = [0,1,0,1,1,0,0,1], n = 7[0,0,1,1,0,0,0,0]def prison_after_n_days(cells, n):
def step(c):
return [0] + [1 if c[i - 1] == c[i + 1] else 0
for i in range(1, 7)] + [0]
seen = {}
while n > 0:
key = tuple(cells)
if key in seen:
n %= seen[key] - n
seen[key] = n
if n >= 1:
n -= 1
cells = step(cells)
return cellsfunction prisonAfterNDays(cells, n) {
const step = (c) => c.map((_, i) =>
(i === 0 || i === 7) ? 0 : (c[i - 1] === c[i + 1] ? 1 : 0));
const seen = new Map();
while (n > 0) {
const key = cells.join("");
if (seen.has(key)) n %= seen.get(key) - n;
seen.set(key, n);
if (n >= 1) {
n -= 1;
cells = step(cells);
}
}
return cells;
}class Solution {
public int[] prisonAfterNDays(int[] cells, int n) {
Map<String, Integer> seen = new HashMap<>();
while (n > 0) {
String key = Arrays.toString(cells);
if (seen.containsKey(key)) n %= seen.get(key) - n;
seen.put(key, n);
if (n >= 1) {
n--;
int[] next = new int[8];
for (int i = 1; i < 7; i++)
next[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
cells = next;
}
}
return cells;
}
}vector<int> prisonAfterNDays(vector<int>& cells, int n) {
unordered_map<string, int> seen;
while (n > 0) {
string key(cells.begin(), cells.end());
if (seen.count(key)) n %= seen[key] - n;
seen[key] = n;
if (n >= 1) {
n--;
vector<int> next(8, 0);
for (int i = 1; i < 7; i++)
next[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
cells = next;
}
}
return cells;
}Explanation
Each day every cell updates at once: an inner cell becomes 1 if its two neighbors match (both occupied or both vacant), else 0; the two end cells have only one neighbor so they always become 0. The naive idea is to apply this n times, but n can be huge.
The saving observation is that there are only 8 cells, so at most 2^8 = 256 possible states. A sequence with finitely many states must eventually repeat — it becomes periodic. So instead of simulating millions of days, we detect the cycle and skip ahead.
We store each state we have seen in a map seen together with how many days were left at the time. If we ever see a state again, the gap between the two day-counts is the cycle length, and we collapse the remaining days with n %= seen[key] - n so we only simulate the leftover.
Otherwise, while days remain, we apply one step and continue. The step function rebuilds the row using the neighbor-match rule, forcing both ends to 0.
Example: cells = [0,1,0,1,1,0,0,1], n = 7. After day 1 it becomes [0,1,1,0,0,0,0,0], and applying the rule seven times yields [0,0,1,1,0,0,0,0].