LeetCode: Prison Cells After N Days

Question

Stack, I can't quite wrap my head around this oddity. I'm evaluating the positions within the array, each time. How is it that by initializing the array each time I receive different results... I would appreciate if someone can explain this.

In While Loop: Correct

0,1,0,1,1,0,0,1
0,1,1,0,0,0,0,0
0,0,0,0,1,1,1,0
0,1,1,0,0,1,0,0
0,0,0,0,0,1,0,0
0,1,1,1,0,1,0,0
0,0,1,0,1,1,0,0
0,0,1,1,0,0,0,0

Outside While Loop (Initialized Once): Incorrect

0,1,0,1,1,0,0,1
0,1,1,0,0,0,0,0
0,0,1,0,1,0,1,0
0,0,1,1,0,0,1,0
0,0,0,1,0,0,1,0
0,1,1,0,1,1,0,0
0,0,1,1,1,0,1,0
0,0,0,0,1,1,0,0

Question Details

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: Expected Output

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]

Method

    static public int[] PrisonAfterNDays(int[] cells, int N) 
    {
        int counter = 0;
        //Doesn't work if it's here
        //int[] temp = new int[8];
        while(counter < N)
        {
            Console.WriteLine(String.Join(",",cells));

            //Works if it's here ?!?!?!
            int[] temp = new int[8];
            for(int j = 1; j < 8-1; j++)
            {
                if(cells[j-1] == cells[j+1])
                {
                    temp[j] = 1;
                }
                else
                {
                    temp[j] = 0;
                }

            }

            cells = temp;
            counter++;
        }

        return cells;
    }

@Michael It seems to be some kind of learning platform. Thankfully it's not a variant of brainf#!@ or lolcode :) As for why it's in the title... no idea. — ProgrammingLlama, Apr 08 '19 at 01:22

ProgrammingLlama · Accepted Answer · 2019-04-08T01:24:44.617

Remember that even though int is a value type, arrays are reference types, so int[] is a reference type. (See What is the difference between a reference type and value type in c#?)

When you execute cells = temp;, you point cells and temp at the exact same array! You can test this with the following code:

int[] a = new int[2];
int[] b = a;

b[0] = 85;
b[1] = 3;

Console.WriteLine(a[0]); // prints 85
Console.WriteLine(a[1]); // prints 3

So this means that on the second iteration of the outer loop, the following code changes both cells[j] and temp[j]:

temp[j] = 1;

Which, clearly, means you will get strange results.

For this reason, I'd argue that you should define temp within the loop.

Yes, that was it. By re-creating within the inner loop the memory location was different. This meant as I made changes to the variable in question the makeup of the "previous" iteration wasn't altered. Thank you — FirebladeDan, Apr 08 '19 at 02:05

score 0 · Answer 2 · answered Jul 27 '22 at 06:34

class Solution:
    def prisonAfterNDays(self, states: List[int], n: int) -> List[int]:
        # Since we have 6 cells moving cells (two wil remain unchaged at anytime) 
        # the cycle will restart after 14 iteration
        # 1- The number of days if smaller than 14 -> you brute force O(13)
        # 2- The number is bigger than 14
        #                       - You do a first round of 14 iteration
        #                       - Than you do a second round of n%14 iteration
        #                       ===> O(27)
        if n < 14:
            # iif n
            for _ in range(n):
                states = self.getNewStates(states)
        else:
            for _ in range(14):
                states = self.getNewStates(states)
            
            for _ in range(n%14):
                states = self.getNewStates(states)
                
        return states
    
    def getNewStates(self, states: List[int]) -> List[int]:
        newStates = ["0"] * len(states)
        for i in range(1, len(states)):
            if i != 0 and i != len(states) - 1 and states[i-1] == states[i+1]:
                newStates[i] = "1"
        return newStates

LeetCode: Prison Cells After N Days

2 Answers2