Исследователи недавно обнаружили интересную пчелиную колонию, которая живет в бесконечном поле сот:
Каждая клетка может содержать пчелу или нет. На самом деле, жизнь этих существ выглядит немного ... хаотично. Можно посчитать, что колония всегда начинается со следующей схемы:
(Биография Эммануэля Буте из Wikimedia Commons . Таким образом, изображение с сотами и пчелами публикуется под CC-By-SA . Ворчит )
После этого жизненные циклы пчелы делятся на так называемые поколения. Каждое поколение старых пчел умирает, а новые вылупляются, и это в первую очередь зависит от соседей их клетки:
- Если у пчелы меньше двух соседей, она умирает из-за одиночества.
- Если у пчелы более трех соседей, она умирает из-за переполненности.
- Если в соседней камере есть две, три или четыре живые пчелы, то в следующем поколении появляется новая пчела.
Умирающие пчелы не умирают до конца поколения, поэтому они все еще влияют на окружающие клетки, которые могут вывести пчел в следующем поколении.
Теперь, когда мы знаем, как работает такая колония, мы можем моделировать ее через любое количество поколений.
вход
Ввод - это одно число N , заданное на стандартном вводе, оканчивающееся переводом строки. 0 ≤ N ≤ 150. Это количество поколений для симуляции.
Выход
Вывод представляет собой одно число на стандартном выводе и, возможно, за ним следует разрыв строки, который представляет количество живых пчел после N поколений.
Дополнительный вывод по стандартной ошибке игнорируется.
Образцы входов
0
5
42
100
Пример выходов
6
44
1029
5296
Выигрышное условие
Самый короткий код выигрывает, как это принято в гольфе. В случае ничьей победит более раннее решение.
Контрольные примеры
Есть два сценария тестирования, содержащие идентичные тестовые случаи:
Вызов в обоих случаях: <test script> <my program> [arguments]
например, ./test ruby beehive.rb
или ./test.ps1 ./beehive.exe
.
Я знаю, что есть только 22 теста вместо 151 (в основном потому, что решения часто бывают довольно медленными). Пожалуйста, воздержитесь от встраивания точных тестовых случаев вместо решения задачи. Эти сценарии удобны для вас, чтобы проверить, вызывает ли изменение правильное поведение программы; Нельзя сказать, что вы можете адаптировать свой код для конкретных тестовых случаев.
Еще одна заметка
Эта задача была частью соревнования по гольфу, проводимого в моем университете в течение 2011-W24. Баллы и языки наших конкурсантов были следующими:
- 336 - С
- 363 - С
- 387 - С
- 389 - Хаскелл
- 455 - С
Наше собственное решение было
- 230 - Рубин
Ответы:
Рубин,
181163153146 символовЭта реализация следует стандартному подходу с использованием массива
h
(размеры200
х200
сплющены), где каждый элемент либо0
(нет пчелы), либо1
(пчела включена). Массив[0,-200,201,202,2,3]
описывает начальные позиции пчел (относительно любой начальной клетки).Ввод и вывод, как указано выше, проходит все определенные тестовые наборы.
Правка 1: теперь вернулось решение для переноса вместо версии «дополнительное пространство» (которая была короче в промежуточной версии, но теперь на несколько символов длиннее).
Редактировать 2: переменная
b
полностью удалена .Редактировать 3: предупреждение: это редактирование сделало программу ужасно медленной. Таким образом, я уменьшил размеры до 200, что по-прежнему достаточно для 150 итераций. Вместо индексации массива по переменной мы постоянно вращаем массив вперед. Не очень хороший дизайн, но сейчас мы значительно ниже 150.
источник
Python, 152 символа
Это решение отслеживает местоположения пчел с помощью набора комплексных чисел. Это довольно медленно, потому что внутренний цикл является квадратичным по количеству пчел. Я проверил до 50, и это работает.
источник
P={0,2,3,1j,1+1j,1-1j}
а затем использовать{p}<P
для проверки членства (сохраняет 1 символ)Питон,
171169158 символовЯ моделирую мир как массив 300 * 300 = 900000 1D (
h
на самом деле он больше, но конец не используется), где пчела равна 1, а пустая равна 0. Размер 300 - это хорошо, потому что в большинстве случаев рост будет 2 в каждом измерении для каждого поколения, и не более 150 поколений.Вот слегка раскрученная и прокомментированная версия:
источник