Zadanie

Na wejściu distajemy listę liczb, która zmienia się przy każdym naszym mrugnięciu, wedle ściśle określonych zasad.

• 0 zamienia się w 1
• liczby o parzystej liczbie cyfr dzielą się na dwa (1234 -> [12, 34])
• pozostałe liczby są mnożone razy 2024 Nasza lista rośnie z każdym mrugnięciem oto przykładowa progresja:

125 17
253000 1 7
253 0 2024 14168
512072 1 20 24 28676032
512 72 2024 2 0 2 4 2867 6032
...

Musimy policzyć jak długa będzie nasza lista po 25 mrugnięciach.

Rozwiązanie

Pierwszą część spróbuję rozwiązać brute forcem, czyli wygeneruję po prostu wszystkie kolejne listy zadania na podstawie poprzednich list. Podejrzewam że część druga będzie związana z wygenerowaniem rozwiązania dla dużo większej liczby mrugnięć a ilość elementów będzie rosła bardzo szybko. Ale staram się niczego nie zakładać w programowaniu i rozwiązać najpierw aktualne problemy, by później dopiero je optymalizować.

def expand(arr):
    new = []
    for num in arr:
        snum = str(num)
        if num == 0:
            new.append(1)
        elif len(snum) % 2 == 0:
            half = len(snum) // 2
            l = int(snum[:half])
            r = int(snum[half:])
            new.append(l)
            new.append(r)
        else:
            new.append(num * 2024)
    return new

Pózniej wystarczy uruchomić tą funkcję 25 razy i policzyć długość końcowej listy:

def part1(starting):
    cur = starting
    for _ in range(25):
        cur = expand(cur)
    return len(cur)

# Zczytanie wejścia
data = list(map(int, input().split()))
print(part1(data))

Dostajemy poprawny wynik w 0.098 sekundy, co jest akceptowalnym jak na pythona wynikiem.

Część 2

Tak jak przewidziałem, druga część jest praktycznie identyczna do pierwszej, jedyna rzecz która się zmienia to ilość mrugnięć (iteracji), wzrasta ona do 75, spodziewałem się jeszcze wyższej wartośći, sprawdźmy czy nasz brute-force poradzi jeśli zmienimy wartość z 25 na 75.

def part1(starting):
    cur = starting
    for i in range(75):
        print(i)  # Dodaję printa żeby móc zobaczyć progres
        cur = expand(cur)
    return len(cur)

Jak można zauważyć pierwsze 30 iteracji wykonuje się bardzo szybko, ale później progres drastycznie zwalnia, musimy wymyśleć coś sprytniejszego.

Optymalizacja

To co musimy zrobić to znaleźć miejsca w programie, w których duplikujemy pracę. Zauważmy że wszystkie liczby są od siebie niezależne, więc mając input: [0 0 0], nie musimy 3 razy symulować ewolucji liczby 0. Każda z nich stworzy taką samą ilość liczb po 75 iteracjach więc wystarczy nam obliczyć tylko jedno z nich i pomnożyć wynik razy 3.

Ta sama obserwacja dotyczy wszystkich liczb na niższych poziomach naszego drzewka (liczby które pojawiają się po kilku mrugnięciach). Wiemy że 1 wygeneruje tyle samo co każde inne 1 na tym samym poziomie, niezależnie od tego z jakiej liczby zostało wygenerowane.

Rozwiązaine uzyskamy implementując funkcję rekurencyjną z cachowaniem poprzednich wyników

from functools import cache


@cache
def solve(number, iters=75):
    if iters == 0:
        return 1

    if number == 0:
        return solve(1, iters - 1)

    snum = str(number)
    if len(snum) % 2 == 0:
        half = len(snum) // 2
        l = int(snum[:half])
        r = int(snum[half:])
        return solve(l, iters - 1) + solve(r, iters - 1)

    return solve(number * 2024, iters - 1)


if __name__ == "__main__":
    data = list(map(int, input().split()))
    print(sum([solve(x, 25) for x in data]))
    print(sum([solve(x) for x in data]))

Rozwiązanie to jest bardzo wydajne, obie części wykonują się w 0.084 sekundy.

Podsumowanie

Od jakiegoś czasu staram się unikać przedwczesnej optymalizacji kodu, nigdy nie wiemy, jak zmienią się wymagania w przyszłości, w tym przypadku odgadłem poprawnie że druga część będzie wymagała całkowitej zmiany kodu, jednak wolałem nie zapędzać się za bardzo, gdyż mogłoby się okazać że część druga jest zupełnie inna i wtedy zmarnowałbym czas optymalizująć część pierwszą.