957. Prison Cells After N Days

Problem Link

Description

---

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.

You are given an integer array cells where cells[i] == 1 if the ith cell is occupied and cells[i] == 0 if the ith cell is vacant, and you are given an integer n.

Return the state of the prison after n days (i.e., 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]

 

Constraints:

• cells.length == 8
• cells[i] is either 0 or 1.
• 1 <= n <= 109

Solution

---

Python3

class Solution:
    def prisonAfterNDays(self, cells: List[int], days: int) -> List[int]:
        
        def g(cells):
            masks = 0
            
            for cell, occupied in enumerate(cells):
                if occupied:
                    masks |= (1 << cell)
            
            return masks
        
        def transform(cells):
            new_cells = [0] * 8
            
            for i in range(1, 7):
                if cells[i - 1] == cells[i + 1]:
                    new_cells[i] = 1
            
            return new_cells
        
        original = cells[:]
        seen = set()
        cycle = 0
        hasCycle = False
        
        for _ in range(days):
            next_cells = transform(cells)
            masks = g(next_cells)
            
            if masks in seen:
                hasCycle = True
                break
            else:
                seen.add(masks)
                cycle += 1
            
            cells = next_cells
        
        if hasCycle:
            count = days % cycle
            
            for _ in range(count):
                cells = transform(cells)
            
        return cells

Java

class Solution {
    public int[] prisonAfterNDays(int[] cells, int N) {
		if(cells==null || cells.length==0 || N<=0) return cells;
        boolean hasCycle = false;
        int cycle = 0;
        HashSet<String> set = new HashSet<>(); 
        for(int i=0;i<N;i++){
            int[] next = nextDay(cells);
            String key = Arrays.toString(next);
            if(!set.contains(key)){ //store cell state
                set.add(key);
                cycle++;
            }
            else{ //hit a cycle
                hasCycle = true;
                break;
            }
            cells = next;
        }
        if(hasCycle){
            N%=cycle;
            for(int i=0;i<N;i++){
                cells = nextDay(cells);
            }   
        }
        return cells;
    }
    
    private int[] nextDay(int[] cells){
        int[] tmp = new int[cells.length];
        for(int i=1;i<cells.length-1;i++){
            tmp[i]=cells[i-1]==cells[i+1]?1:0;
        }
        return tmp;
    }
}