День 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)}')
Примечание. Обязательно используйте введенные данные для получения ответа.
Спасибо!