#Skip to menu

Day 10, Year 2015: Elves Look, Elves Say

First read the problem description.

Discussions about Conway’s video.

Memory allocation is the slowest part. We estimate the upper bound of the length of the nth sequence and preallocate two lists with the needed space and compute the new sequence populating each time the other list.

def look_and_say(current, new):
    prev_d = current[0]
    run_len = 0
    new_i = 0
    for d in current:
        if d != prev_d:
            new[new_i] = run_len
            new[new_i+1] = prev_d
            new_i += 2
            run_len = 0
            prev_d = d
            if d == 0:
                break

        run_len += 1

def estimate_length(times):
    λ = 1.30357726903429639125709911215255189073070250465940487575486139062855088785246155712681576686442522555
    return λ**times
times = 50
upper_bound = int(10 * estimate_length(times))

sequence = [0]*upper_bound
sequence[0:10] = [1,1,1,3,1,2,2,1,1,3]
tmp = [0]*upper_bound

for _ in range(times): 
    look_and_say(sequence, tmp)
    sequence, tmp = tmp, sequence

# remove trailing 0s
sequence = sequence[:sequence.index(0)]

len(sequence)
5103798

See what people say about this article.


Source code of the solution(s):