Mfcttrf

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


def is_dead(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:
 if is_dead(state):
 return False
 if state in seen:
 return True
 seen.append(state)
 state = get_new_state(state)


num_cases = int(sys.stdin.readline().strip())
for i in range(num_cases):
 cur_state = []
 case = sys.stdin.readline().strip()
 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?

You are representing each state of the universe as a list of bits. However, CPUs are experts at handling sequences of bits — that's what an integer is!

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.

Using a set instead of list would immediately improve the performance. However, I recommend to avoid huge collections whatsoever and investigate a Tortoise and Hare approach.