5
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Carcigenicate Jun 25 at 21:00
6
\$\begingroup\$

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 ^.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.