День 6 — захватывающий вызов; это сложно, поэтому решайте осторожно, легко попасть в ловушку грубой силы и долгой работы.

Если вы не знакомы с Пришествием кода, я настоятельно рекомендую решить его самостоятельно, прежде чем рассматривать эти решения.

Понять проблему

Нам нужно понять закономерность размножения рыбы-фонаря; вот и все. Каждая рыба-фонарь может воспроизвести новую рыбу-фонарь за 7 дней. И эти новые дети могут начать размножаться через 9 дней.

Итак, с данным примером, то есть 3 4 3 1 2. В настоящее время у нас есть пять Lanternfish вместе с оставшимися днями разведения.

Initial state: 3,4,3,1,2
After  1 day : 2,3,2,0,1
After  2 days: 1,2,1,6,0,8
After  3 days: 0,1,0,5,6,7,8
After  4 days: 6,0,6,4,5,6,7,8,8
After  5 days: 5,6,5,3,4,5,6,7,7,8

У нас есть десять Lanternfish с новыми пятерками в конце 5-го дня.

Примечание. В приведенном выше примере семь дней переводится от 0 до 6 (всего семь дней), а девять дней — от 0 до 8 (всего девять дней).

Часть 1: Подход 1

Это будет выглядеть прямо и прямолинейно; нам нужно уменьшить счетчик, сбросить его до шести и добавить новый Lanternfish с 8.

for i in range(80):
    temp = []
    babies = 0
    for cur_cntr in fishes:
        new_cntr = cur_cntr - 1
        if new_cntr < 0:
            new_cntr = 6
            babies += 1
        temp.append(new_cntr)
    fishes = temp + [8] * babies
print(f'Total lanternfish after 80 days: {len(next_fishes)}')

И мы закончили с первой частью.

Часть 2: Подход 2

Теперь запустите приведенный выше код на 256 дней и прокомментируйте его здесь после завершения. :)

Попробовав, вы поймете, что прирост Lanternfish огромен с каждым новым днем. Вышеупомянутая задача может потребовать суперкомпьютер для ее выполнения, или с помощью некоторого метода мемоизации мы можем улучшить ее, но все равно это займет много времени.

Пришло время переосмыслить приведенную выше постановку проблемы, и я повторяю здесь:

Каждая рыба-фонарь может воспроизвести новую рыбу-фонарь за 7 дней. И эти новые дети могут начать размножаться через 9 дней.

Нам нужен циклический массив или список, в котором мы можем вывести количество заводчиков на сегодняшний день и отодвинуть их на семь, в случае взрослых особей, и на девять, в случае новых детенышей.

days = [0] * 9
# Update the current numbers
for fish in fishes:
    days[fish] += 1
for i in range(256):
    # To make it cyclic: 0, 1, 2, 3, 4, 5, 6, 7, 8    
    today = i % len(days)
    # Add new babies
    days[(today + 7) % len(days)] += days[today]
print(f'Total lanternfish after 256 days: {sum(days)}')

Примечание. Обязательно используйте введенные данные для получения ответа.

Спасибо!