Моделирование расширения колоний светлячков

Условие

Чтобы смоделировать процесс, мы используем числовую последовательность, которая представляет цикл размножения светлячков-лантерфишей, и отслеживаем размер их популяции за заданное количество дней. Каждый светлячок несет счетчик, который показывает, через сколько дней он породит нового рыба. Когда счетчик достигает нуля, рыба сбрасывает его на 6 и создает нового индивида, чей счетчик начинается с 8. Входные данные состоят из списка целых чисел, каждое из которых соответствует счетчику одного светлячка-лантерфиши. Например, начальное состояние [3, 4, 3, 1, 2] обозначает пять светлячков с указанными счетчиками.

Задача — запустить эту симуляцию и сообщить, сколько светлячков-лантерфишей существует после заданного количества дней: 80 дней для базовой версии и 256 дней для расширенной версии.

Иллюстрация роста популяции:

• Начальное состояние: 3,4,3,1,2
• После 1 дня: 2,3,2,0,1
• После 2 дней: 1,2,1,6,0,8
• После 3 дней: 0,1,0,5,6,7,8

Ответ

Считайте количество особей для каждого таймера 0–8, а не храните каждую рыбу. Для [3,4,3,1,2] получится 5934 через 80 дней и 26984457539 через 256 дней.

function population(initial, days) {
  const counts = Array(9).fill(0n);
  for (const timer of initial) counts[timer]++;
  for (let day = 0; day < days; day++) {
    const born = counts[0];
    for (let timer = 0; timer < 8; timer++) counts[timer] = counts[timer + 1];
    counts[6] += born;
    counts[8] = born;
  }
  return counts.reduce((sum, value) => sum + value, 0n);
}

Предполагаются целые таймеры 0–8 и неотрицательное целое число дней. Родители с нулевым таймером переходят в группу 6, новорождённые — в 8. BigInt сохраняет точность больших популяций. Требуются O(days + n) операций и девять счётчиков.