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): = current prev_d = 0 run_len = 0 new_i for d in current: if d != prev_d: = run_len new[new_i] +1] = prev_d new[new_i+= 2 new_i = 0 run_len = d prev_d if d == 0: break += 1 run_len def estimate_length(times): = 1.30357726903429639125709911215255189073070250465940487575486139062855088785246155712681576686442522555 λ return λ**times
= 50 times = int(10 * estimate_length(times)) upper_bound = *upper_bound sequence 0:10] = [1,1,1,3,1,2,2,1,1,3] sequence[= *upper_bound tmp for _ in range(times): look_and_say(sequence, tmp)= tmp, sequence sequence, tmp # remove trailing 0s = sequence[:sequence.index(0)] sequence len(sequence)
Source code of the solution(s):