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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Data structures

Mathematics

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:
			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
		state_bitmap = 0
		for cell in cells:
			state_bitmap <<= 1
			state_bitmap = state_bitmap | cell
		while N > 0:
			if not is_fast_forwarded:
				if state_bitmap in seen:
					N %= seen[state_bitmap] - N
					is_fast_forwarded = True
				else:
					seen[state_bitmap] = N
			if N > 0:
				N -= 1
				state_bitmap = self.nextDay(state_bitmap)
		ret = []
		for i in range(len(cells)):
			ret.append(state_bitmap & 1)
			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 & 126
		return state_bitmap


class Solution:

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

		def nextDay(cells):
			ans = [0]
			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:
			if not forwarded:
				snapshot = tuple(cells)
				if snapshot in seen:
					N %= seen[snapshot] - N
					forwarded = True
				else:
					seen[snapshot] = N
			if N > 0:
				N -= 1
				cells = nextDay(cells)
		return cells


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:
				N %= day - 1
		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]:
			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
		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


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


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, 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