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:

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

Difficulty: interview

Starter code:

class Solution:
    def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:
        

Solutions:
class Solution:
    def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:
        cell = 0
        for c in cells:
            cell = (cell << 1) | c
        seendict = {}
        index = 0
        while True:
            # print([int(x) for x in '{0:08b}'.format(cell)])
            if cell in seendict:
                if (N - index) % (index - seendict[cell]) == 0:
                    return [int(x) for x in '{0:08b}'.format(cell)]
            seendict[cell] = index
            not_cell = (cell ^ 255) 
            cell = ((cell << 1) & (cell >> 1)) | ((not_cell << 1) & (not_cell >> 1))
            index += 1

class Solution:
    def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:

        seen = dict()
        is_fast_forwarded = False

        # step 1). convert the cells to bitmap
        state_bitmap = 0x0
        for cell in cells:
            state_bitmap <<= 1
            state_bitmap = (state_bitmap | cell)

        # step 2). run the simulation with hashmap
        while N > 0:
            if not is_fast_forwarded:
                if state_bitmap in seen:
                    # the length of the cycle is seen[state_key] - N 
                    N %= seen[state_bitmap] - N
                    is_fast_forwarded = True
                else:
                    seen[state_bitmap] = N
            # if there is still some steps remained,
            #   with or without the fast-forwarding.
            if N > 0:
                N -= 1
                state_bitmap = self.nextDay(state_bitmap)

        # step 3). convert the bitmap back to the state cells
        ret = []
        for i in range(len(cells)):
            ret.append(state_bitmap & 0x1)
            state_bitmap = state_bitmap >> 1

        return reversed(ret)


    def nextDay(self, state_bitmap: int):
        state_bitmap = ~ (state_bitmap << 1) ^ (state_bitmap >> 1)
        state_bitmap = state_bitmap & 0x7e  # set head and tail to zero
        return state_bitmap

class Solution:
    def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:
        def nextDay(cells):
            ans = [0] #start
            for i in range(1, len(cells) - 1):
                ans.append(int(cells[i - 1] == cells[i + 1]))
            ans.append(0)
            return ans
        
        seen = {}
        forwarded = False
        
        while N > 0: # when there is loop left
            if not forwarded: # if cycle hasn't been detected
                snapshot = tuple(cells)
                if snapshot in seen: # detected cycle
                    N %= seen[snapshot] - N # length of cycle
                    forwarded = True
                else:
                    seen[snapshot] = N
            if N > 0: # update snapshot to next day's
                N -= 1
                cells = nextDay(cells)
        return cells
        
    # Given K number of cells, there could be at most 2**K possible states. If the number of steps is larger than all possible states (N > 2 ** K), we are destined to repeat ourselves sooner or later.


class Solution:
    def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:
        
        
        def transform(cells): 
            nxtCells = [0]*len(cells)
            for i in range(1, len(cells)-1): 
                nxtCells[i] = 1 if cells[i-1] == cells[i+1] else 0
            return nxtCells
        
        day = 0 
        while N>0: 
            cells = transform(cells)
            day += 1
            N -= 1
            if day == 1: 
                origin = [i for i in cells]
            elif cells == origin: 
                # print(day, N, cells)
                N %= day-1
                # print(day, N, cells)
            
            # print(N, cells)
                
        
        return cells 

class Solution:
    def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:
        visited = {str(cells) : N}
        
        cycle = 0
        hascycle = False
        
        def get_next(cells) -> List[int]:
            '''return next cell'''
            tmp = [0] + [cells[i-1] ^ cells[i+1] ^ 1 for i in range(1,7)] + [0]
            return tmp
            
        
        while N > 0:
            visited[str(cells)] = N
            
            N -= 1
            cells = get_next(cells.copy())
            if str(cells) in visited:
                hascycle = True
                cycle = visited[str(cells)] - N 
                break
            
            
        if hascycle:
            N = N % cycle
            while N > 0:
                N -= 1
                cells = get_next(cells)
            
        return cells

class Solution:
    def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:
        
        
        if not cells:return cells
        #brute force can be optimized by finding number count aftwer which the pattern 
        #repeats. So take first day and change according to rules and update counter
        #when new updated cell matches the one u started with ,get the counter
        #this is number after which pattern repeats
        #now we can simply fast forward 
        
        day1=self.nextDay(cells)
        cells=day1.copy()
        count=0
        N-=1
        
        while N>0:
            each_day=self.nextDay(cells)
            count+=1
            N-=1
            
            if each_day==day1:
                N=N%count
            cells=each_day
        return cells
           
                
    def nextDay(self,cells):
        ret=[0]
        for i in range(1,len(cells)-1):
            ret.append(int(cells[i-1]==cells[i+1]))
        ret.append(0)
        return ret
         
            
            
        return cells
                        
            
           
    
            
#         dp=cells.copy()
#         for i in range(N):
#             for j in range(8):
#                 if j==0:
#                     if dp[j]==1:cells[j]=0
#                 elif j==7 :
#                     if dp[j]==1:cells[j]=0
#                 else:
#                     if dp[j-1]^dp[j+1]==0:
#                         cells[j]=1
#                     else:
#                         cells[j]=0
                        
                        
#             dp=cells.copy()
                
#         return cells


class Solution:
    def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:
        for i in range((N - 1) % 14 + 1):
            cells = [0] + [cells[i - 1] ^ cells[i + 1] ^ 1 for i in range(1, 7)] + [0]
        return cells

class Solution:
    def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:
        prison_size = len(cells)
        seen = {}
        seen[str(cells)] = 0
        history = [cells]
        
        
        for d in range(1,N+1):
            ans = [0] * prison_size
            for i in range(1,7):
                ans[i] = 1 if cells[i-1] == cells[i+1] else 0
            
            if str(ans) in seen:
                cycle_length = d - seen[str(ans)]
                return history[seen[str(ans)] + (N-d)%cycle_length]
            else:
                history.append(ans)
                seen[str(ans)] = d
            cells = ans
        
        
        return cells

class Solution:
    def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:
        def next(state):
            return tuple(1 if i>0 and i <len(state)-1 and state[i-1] == state[i+1] else 0 for i in range(len(state)))
        
        seen = {}
        state = tuple(cells)
        
        i = 0
        remaining = 0
        while i < N:
            if state in seen:
                cycle = i - seen[state]
                remaining = (N-i)%cycle
                break
            seen[state] = i 
            state = next(state)
            i+=1
            
        while remaining > 0:
            state = next(state)
            remaining -= 1
                
        return state 

class Solution:
    # 1,2,3,4,2,3,4,2,3,4,2  N = 11
    # groupSize
    # 0 1 2 3 4 5 6 7 8 9 0
    # x = 4 pos = 1
    def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:
        iterations = {}
        x = 0
        lastGroup = False
        while x < N:
            iteration = tuple(cells)
            if not lastGroup:
                if iteration in iterations:
                    print ('first',x, iteration)
                    lastGroup = True
                    pos = iterations[iteration]
                    #we found a cycle
                    groupSize = x-pos
                    print ('groupSize',groupSize )
                    groups = (N-pos)//groupSize
                    x = pos + groups*groupSize 
                    if x == N:
                        break
                    print (\"**\",x)
                else:
                    print(x, iteration)
                    iterations[iteration] = x
            #curr = cells.copy()
            prev = cells[0]
            if x ==0:
                cells[0]=0
            for i in range (1,len(cells)-1):
                if prev == cells[i+1]:
                    prev = cells[i]
                    cells[i] =1
                else:
                    prev = cells[i]
                    cells[i]=0
                    
            if x == 0:
                cells[-1]=0
            # increment x
            x+= 1
            #curr = cells.copy()
        return cells
                    
        

from queue import deque
from collections import defaultdict
class Solution:
    def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:
        
        def next_day(c)->List[int]:
            res=[0]*8
            for i in range(1,7):
                if c[i-1]==c[i+1]:res[i]=1
                else:res[i]=0
            return res
        
        def period(c)->int:
            if c[0]!=0 or c[-1]!=0: return 0
            temp=c
            for day in range(1,2**6+1):
                if day==2**6: return 0
                temp=next_day(temp)
                if temp==c:return day
        
                
        temp=cells
        
        for day in range(1,N+1):
            temp=next_day(temp)
            if period(temp):break
        
        N=(N-day)%period(temp)
        for day in range(1,N+1):
            temp=next_day(temp)
        
        
        
        return temp

# class Solution:
#     def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:
#         n = N
#         currCells = cells[:]
#         while n > 0:
#             for i in range(len(cells)):
#                 if i == 0 or i == len(cells)-1:
#                     currCells[i] = 0
#                 elif cells[i-1] == cells[i+1]:
#                     currCells[i] = 1
#                 else:
#                     currCells[i] = 0
#             cells = currCells[:]
#             n -= 1
#         return cells

class Solution:
    def prisonAfterNDays(self, cells, N):
        
        seen = {}
        while N:
            seen.setdefault(str(cells), N)
            print(seen)
            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