In Conway's Game of Life, cells in a grid are used to simulate biological cells.
Each cell is considered to be either alive or dead.
At each step of the simulation
each cell's current status and number of living neighbors is used to determine the status
of the cell during the following step of the simulation.
In this one-dimensional version, there are N cells numbered 0 through N-1.
The number of cells does not change at any point in the simulation.
Each cell i is adjacent to cells i-1 and i+1.
Here, the indices are taken modulo N meaning cells 0 and N-1 are also adjacent to eachother.
At each step of the simulation, cells with exactly one living neighbor change their status
(alive cells become dead, dead cells become alive).
For example, if we represent dead cells with a '0' and living cells with a '1', consider
the state with 8 cells:
01100101
Cells 0 and 6 have two living neighbors.
Cells 1, 2, 3, and 4 have one living neighbor.
Cells 5 and 7 have no living neighbors.

Thus, at the next step of the simulation, the state would be:
00011101

Given some state of the game, your task is to determine the state immediately preceding it.
In some cases there may be more than one answer or no possible answer.

------ Input ------ 

Input will begin with an integer T<100, the number of test cases.
Each test case consists of a single line, with between 3 and 50 characters, inclusive.
Each character will be either '0' or '1'.
Each '0' represents a dead cell, and each '1' represents an alive cell.

------ Output ------ 

For each test case, output the state of the game that precedes the given state.
If there is no possible solution, print "No solution" (quotes for clarity only).
If there are multiple possible solutions, print "Multiple solutions" (quotes for clarity only).

----- Sample Input 1 ------ 
4
00011101
000
000001
11110
----- Sample Output 1 ------ 
01100101
Multiple solutions
No solution
10010

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Constructive algorithms

Mathematics

Ad-hoc


Solutions:
def check(s):
	p = ['00', '01', '10', '11']
	for val in s[1:-1]:
		for i in range(4):
			p[i] = p[i] + str(int(p[i][-2]) ^ int(p[i][-1]) ^ int(val))
	count = 0
	for x in p:
		if convert(x) == s:
			count += 1
			r = x
	if count == 1:
		return r
	elif count == 0:
		return 'No solution'
	else:
		return 'Multiple solutions'

def convert(s):
	s = s[-1] + s + s[0]
	n = len(s)
	result = ''
	for i in range(1, n - 1):
		if (s[i - 1] + s[i + 1]).count('1') == 1:
			result += '1' if s[i] == '0' else '0'
		else:
			result += s[i]
	return result
t = int(input())
for _ in range(t):
	s = input().rstrip()
	print(check(s))


t = int(input())
zero_list = ['000', '101', '110', '011']
one_list = ['100', '001', '010', '111']
for iter in range(t):
	cells = list(input())
	if cells[-1] == '0':
		possibles = zero_list[:]
	else:
		possibles = one_list[:]
	possibles.sort()
	for i in range(len(cells) - 2, -1, -1):
		for j in range(4):
			if cells[i] == '0':
				possibles[j] = zero_list[j][0] + possibles[j]
			else:
				possibles[j] = one_list[j][0] + possibles[j]
		possibles.sort()
	answers = []
	for poss in possibles:
		if poss[0:2] == poss[-2:]:
			answers.append(poss[1:-1])
	if len(answers) == 0:
		print('No solution')
	elif len(answers) > 1:
		print('Multiple solutions')
	else:
		print(answers[0])


import sys
import math

def main(arr):
	v = 0
	sol = []
	arr = list(map(int, arr))
	c = [(0, 0), (0, 1), (1, 0), (1, 1)]
	for e in c:
		(a, b) = e
		new_arr = [0] * len(arr)
		new_arr[0] = a
		new_arr[1] = b
		for i in range(1, len(arr) - 1):
			if new_arr[i] == arr[i]:
				new_arr[i + 1] = new_arr[i - 1]
			else:
				new_arr[i + 1] = new_arr[i - 1] ^ 1
		if new_arr[-1] == arr[-1]:
			if new_arr[-2] == new_arr[0]:
				if new_arr[0] == arr[0]:
					if new_arr[1] == new_arr[-1]:
						v += 1
						sol = new_arr
				elif new_arr[1] == new_arr[-1] ^ 1:
					v += 1
					sol = new_arr
		elif new_arr[-2] == new_arr[0] ^ 1:
			if new_arr[0] == arr[0]:
				if new_arr[1] == new_arr[-1]:
					v += 1
					sol = new_arr
			elif new_arr[1] == new_arr[-1] ^ 1:
				v += 1
				sol = new_arr
	if v == 1:
		sol = list(map(str, sol))
		print(''.join(sol))
	elif v > 1:
		print('Multiple solutions')
	else:
		print('No solution')
	return
for i in range(int(input())):
	s = input()
	main(s)