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?