Poprzez problemy z zadaniem 21 ten post wrzucam z opóźnieniem, ale zadanie z dnia 22 na szczęście było dużo prostsze niż poprzednie. Najtrudniejszym aspektem było zrozumienie treści zadania poprzez czytanie ze zrozumieniem.

Część 1

W pierwszej części zadania mamy wygenerować ciąg liczb pseudolosowych zgodnie z podanym w treści algorytmem. Każda linijka zawiera sekretną liczbę początkową od jednego sprzedawcy, dla każdej z tych liczb mamy zasymulować transformacje 2000 razy i zwrócić sumę otrzymanych liczb.

Rozwiązanie

import sys

res = 0
for line in sys.stdin.readlines():
    num = int(line)
    for _ in range(2000):
        num = num ^ (num << 6)
        num %= 16777216

        num = num ^ (num >> 5)
        num %= 16777216

        num = num ^ (num << 11)
        num %= 16777216

    res += num
print(res)

Jest to trywialna implementacja, bez żadnych sztuczek i optymalizacji, działa wystarczająco szybko.

Część 2

W drugiej części zadania sytuacja się nieco zmienia, okazuje się że każda liczba w ciągu, który generują sprzedawcy służy do oblicznia ceny kryjówki w danym momencie czasu, cena otrzymywana jest biorąc tylko ostatnią cyfrę sekretnej liczby w danym momencie.

Mamy poinstruować małpę kiedy ma kupować, jest ona w stanie tylko rozpoznać ciągi zmian w cenach. Czyli możemy powiedzieć małpie żeby kupowała za każdym razem jak zobaczy ona taką sekwencję zmian: -1 0 3 6 (cena zmalała o 1 potem nie zmieniła się i wzrosła dwa razy), wtedy małpa kupi przy ostatni wzroście o 6, dobrze jakbyśmy jednak wybrali taką sekwencję co pozwoli nam kupować kiedy ceny są najniższe. Dodatkowo małpa może kupić tylko jedną kryjówkę od każdego sprzedawcy.

Rozwiązanie

Poniżej wklejam kod rozwiązujący obie części:

import sys
from collections import defaultdict

part1 = 0
quaternions_profit_sum = defaultdict(int)

for line in sys.stdin.readlines():
    num = int(line)
    sequence = [num % 10] # generacja sekwencji cen
    for _ in range(2000):
        num = num ^ (num << 6)
        num %= 16777216

        num = num ^ (num >> 5)
        num %= 16777216

        num = num ^ (num << 11)
        num %= 16777216

        sequence.append(num % 10)
    part1 += num

    # obliczenie różnic pomiędzy cenami w każdym momencie czasu
    diffs = []
    for i in range(len(sequence) - 1):
        diffs.append(sequence[i + 1] - sequence[i])
    sequence.pop(0)

    # zmapowanie ile zarobimy na każdej sekwencji zmian cen
    profits = defaultdict(int)
    for i in range(3, len(diffs)):
        quaternion = tuple(diffs[i - 3 : i + 1])
        profit = sequence[i]

        # rozważamy tylko pierwsze wystąpienie sekwencji
        if quaternion not in profits:
            profits[quaternion] = profit

    # dodajemy zyski dla każdej sekwencji
    for quaternion, profit in profits.items():
        quaternions_profit_sum[quaternion] += profit

print("Part 1: ", part1)
print("Part 2: ", max(quaternions_profit_sum.values()))