Bit-based universe simulation

I am working with this problem (https://open.kattis.com/problems/whowantstoliveforever). As the problem states, my program has to determine if the universe lives or dies based on the input 0s and 1s.

To determine the next value of the i-th bit, look at the current value of the bits at positions i−1 and i+1 (if they exist; otherwise assume them to be 0). If you see exactly one 1, then the next value of the i-th bit is 1, otherwise it is 0. All the bits change at once, so the new values in the next state depend only on the values in the previous state. We consider the universe dead if it contains only zeros.

My code works but when submitting it to Kattis.com it says ""Time Limit Exceeded" > 3.00 s". Below is my code.

import sys

def get_bit(bits, i):
if 0 <= i < len(bits):
return int(bits[i])
else:
return 0

def get_new_state(old_state):
new_state = []
for index in range(len(old_state)):
if (get_bit(old_state, index-1) == 0 and get_bit(old_state, index+1) == 0) or (get_bit(old_state, index-1) == 1 and get_bit(old_state, index+1) == 1):
new_state.append(0)
elif(get_bit(old_state, index-1) == 0 and get_bit(old_state, index+1) == 1) or (get_bit(old_state, index-1) == 1 and get_bit(old_state, index+1) == 0):
new_state.append(1)
return new_state

if set(state).pop() == "1":
return False
elif set(state).pop() == 1:
return False
elif len(set(state)) == 1:
return True
else:
return False

def foresee_fate(state):
seen = []
while True:
return False
if state in seen:
return True
seen.append(state)
state = get_new_state(state)

for i in range(num_cases):
cur_state = []
for char in case:
cur_state.append(char)
print("LIVES" if foresee_fate(cur_state) else "DIES")



What are some ways to improve the performance of my code?

• Just a note, this is basically a very simple Cellular Automata. If you want to try other stuff like this, looking into Conway's Game of Life and a Forest Fire simulator. They're very cool learning projects. – Carcigenicate Jun 25 at 21:00

Given two bits, the way to find out whether exactly one of them is 1 is to use the ^ operator (XOR).
You should be able to solve this challenge using bit-shifting (<< and >> operators) and ^.
Testing for state repetition by if state in seen: is suboptimal. The number of states could grow exponentially with number of bits (and you are dealing with 200000 bits universe). Since seen is a list, the search time is linear, making the total time complexity quadratic with the size of the period.