LeetCode 957 - Prison Cells After N Days

https://leetcode.com/problems/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:

• If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
• 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.)

Example 1:

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]

Example 2:

Input: cells = [1,0,0,1,0,0,1,0], N = 1000000000
Output: [0,0,1,1,1,1,1,0]

Note:

1. cells.length == 8
2. cells[i] is in {0, 1}
3. 1 <= N <= 10^9

X.
https://blog.csdn.net/GQxxxxxl/article/details/85040103

观察可知第一位和最后一位数字一定会变成0，故只有中间六位数字，2**6=64，即最多有64种状态，一定会形成一种循环。取余求循环位置即可。

一个很显然的观察是，两侧的格子在1天后都会变成空并且保持这个状态，所以实际上可以只考虑6个格子的状态。所以状态数量最多只有1+2^6种。不过当成2^8种来做也没什么问题。

显然用线性算法在N=1e9的时候必然会超时。不过，观察到状态必然会重复之后，可以通过找到循环来解决问题。如果第i天的状态与第start天相同，那么循环节的长度为i - start，可以令N = (N - i) % (i - start)，然后找到对应的天数的状态。

我比赛的时候没有写N--，而是i = 0 to N-1，显然前一种比较利于取模，后一种比较麻烦。所以我在给N取模这一点上错了两次。

另一个观察是[1]，因为格子的数量是偶数，所以对于每一种状态，都可以找到一种合法的之前的状态，所以初始状态后一步就可以进入循环；而且循环节长度必然是1、7或14，所以可以在一步之后就按照14为循环节进行操作。

https://leetcode.com/problems/prison-cells-after-n-days/discuss/205684/JavaPython-Find-the-Loop-Mod-14

We record all seen states.
Be careful,
we need transform array to string as the key,
otherwise it use the reference.

Java:

    public int[] prisonAfterNDays(int[] cells, int N) {
        Map<String, Integer> seen = new HashMap<>();
        while (N > 0) {
            int[] cells2 = new int[8];
            seen.put(Arrays.toString(cells), N--);
            for (int i = 1; i < 7; ++i)
                cells2[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
            cells = cells2;
            if (seen.containsKey(Arrays.toString(cells))) {
                N %= seen.get(Arrays.toString(cells)) - N;
            }
        }
        return cells;
    }

https://blog.csdn.net/u013383813/article/details/85040454
就算 是 T(N) 也会超时。
所以 方法是 减少 相应的 计算 总量，即 N 转化为 n。
考虑到 是一种规则变化，所以可以试试 看是否 是循环变化 ，即 存在 相应的 最小周期。

由于 起始数组 ，nums[0] 和nums[7] 可能不为零，必不会成为 循环的一环，所以从 nums1（nums迭代一次）开始迭代，寻找相应的最小周期，然后 将N 简化为 n。

  public int[] prisonAfterNDays(int[] cells, int N) {

    int[] ocells = new int[cells.length];

    int[] fcells = new int[cells.length];

    for (int i = 1; i <= 6; i++) {

      ocells[i] = 1 - cells[i - 1] ^ cells[i + 1];

      fcells[i] = ocells[i];

    }

    int[] ccells = new int[cells.length];

    int cnt = 1;

    while (true) {

      for (int i = 1; i <= 6; i++)

        ccells[i] = 1 - fcells[i - 1] ^ fcells[i + 1];

      for (int i = 1; i <= 6; i++)

        fcells[i] = ccells[i];

      boolean isSame = true;

      for (int i = 1; i <= 6; i++) {

        if (ccells[i] != ocells[i]) {

          isSame = false;

          break;

        }

      }

      if (isSame)

        break;

      cnt++;

    }

    int n = (N - 1) % cnt;

    while (n-- > 0) {

      for (int i = 1; i <= 6; i++)

        ccells[i] = 1 - fcells[i - 1] ^ fcells[i + 1];

      for (int i = 1; i <= 6; i++)

        fcells[i] = ccells[i];

    }

    return fcells;

  }

https://zxi.mytechroad.com/blog/uncategorized/leetcode-957-prison-cells-after-n-days/
Time complexity: O(2^8)
Space complexity: O(2^8)

I tried to find the pattern of the loop.
Well, the length of loop can be 1, 7, or 14.

So once we enter the loop, every 14 steps must be the same state.

The length of cells is even,
so for any state, we can find a previous state.
So all states are in a loop.

It means that, after a single step from the initial state, we enter the loop.

Java

    public int[] prisonAfterNDays(int[] cells, int N) {
        for (N = (N - 1) % 14 + 1; N > 0; --N) {
            int[] cells2 = new int[8];
            for (int i = 1; i < 7; ++i)
                cells2[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
            cells = cells2;
        }
        return cells;
    }

https://leetcode.com/problems/prison-cells-after-n-days/discuss/205700/Find-the-pattern
https://blog.csdn.net/fuxuemingzhu/article/details/85032587
写了一个多小时的题目，后来才发现周期是14.

发现周期的过程就是尝试了一下，不同的数组的循环周期是多少。试了几个之后发现是14，那就是14了。

如果知道是14之后那就好办了，先把N mod 14，然后注意了！如果mod完之后等于0，应该把N设置为14！！最后我是有时间提交通过的，但是这个地方没有想明白，所以比赛结束之后才通过的。

底下的转移方程就很简单了，直接转移。因为最多操作14次，所以很容易就过了。
https://blog.csdn.net/qq_17550379/article/details/85250138这是一个经典的细胞自动机问题，可以查看Leetcode 289：生命游戏（最详细的解法！！！）

https://leetcode.com/articles/prison-cells-after-n-days/

We simulate each day of the prison.

Because there are at most 256 possible states for the prison, eventually the states repeat into a cycle rather quickly. We can keep track of when the states repeat to find the period t of this cycle, and skip days in multiples of t.

Algorithm

Let's do a naive simulation, iterating one day at a time. For each day, we will decrement N, the number of days remaining, and transform the state of the prison forward (state -> nextDay(state)).

If we reach a state we have seen before, we know how many days ago it occurred, say t. Then, because of this cycle, we can do N %= t. This ensures that our algorithm only needs $O(2**{\text{cells.length}})$ steps.

• Time Complexity: $O(2^N)$, where $N$ is the number of cells in the prison.
• Space Complexity: $O(2^N * N)$.

  public int[] prisonAfterNDays(int[] cells, int N) {

    Map<Integer, Integer> seen = new HashMap();

    // state = integer representing state of prison

    int state = 0;

    for (int i = 0; i < 8; ++i) {

      if (cells[i] > 0)

        state ^= 1 << i;

    }

    // While days remaining, simulate a day

    while (N > 0) {

      // If this is a cycle, fast forward by

      // seen.get(state) - N, the period of the cycle.

      if (seen.containsKey(state)) {

        N %= seen.get(state) - N;

      }

      seen.put(state, N);

      if (N >= 1) {

        N--;

        state = nextDay(state);

      }

    }

    // Convert the state back to the required answer.

    int[] ans = new int[8];

    for (int i = 0; i < 8; ++i) {

      if (((state >> i) & 1) > 0) {

        ans[i] = 1;

      }

    }

    return ans;

  }

  public int nextDay(int state) {

    int ans = 0;

    // We only loop from 1 to 6 because 0 and 7 are impossible,

    // as those cells only have one neighbor.

    for (int i = 1; i <= 6; ++i) {

      if (((state >> (i - 1)) & 1) == ((state >> (i + 1)) & 1)) {

        ans ^= 1 << i;

      }

    }

    return ans;

  }

X. https://leetcode.com/problems/prison-cells-after-n-days/discuss/205684/JavaPython-Find-the-Loop-or-Mod-14

    public int[] prisonAfterNDays(int[] cells, int N) {
        while (N > 0) {
            N--;
            int[] cells2 = new int[8];
            for (int i = 1; i < 7; ++i)
                cells2[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
            cells = cells2;
        }
        return cells;
    }

This is right solution, but it will get TLE when N is big.
Note that cells.length = 8, and cells[0] and cells[7] will become 0.
In fact, cells have only 2 ^ 6 = 64 different states.
And there will be a loop.