условия
Червь является любым списком неотрицательных целых чисел, а его правый (т.е. последний ) элемент называется головой . Если голова не равна 0, у червя есть активный сегмент, состоящий из самого длинного непрерывного блока элементов, который включает в себя голову и имеет все свои элементы, по крайней мере, такие же большие, как голова . Уменьшается активный сегмент является активным сегментом с головой уменьшается на 1. Например, червь 3 1 2 3 2
имеет активный сегмент 2 3 2
, и восстановленный активный сегмент 2 3 1
.
Правила эволюции
Червь развивается постепенно, следующим образом:
На шаге t (= 1, 2, 3, ...),
если заголовок равен 0: удалите заголовок,
иначе: замените активный сегмент на t + 1 составных копий сокращенного активного сегмента.
Факт : любой червь в конечном итоге превращается в пустой список , и количество шагов, которые нужно сделать, - это время жизни червя .
(Подробности можно найти в документе «Принцип червя » Л.Д. Беклемишева. Использование «list» для обозначения конечной последовательности и «head» для обозначения его последнего элемента взято из этой статьи - его не следует путать с общим использованием списков в качестве абстрактного типа данных , где заголовок обычно означает первый элемент.)
Примеры (активный сегмент в скобках)
Червяк: 0,1
step worm
0(1)
1 0 0 0
2 0 0
3 0
4 <- lifetime = 4
Червяк: 1,0
step worm
1 0
1 (1)
2 0 0 0
3 0 0
4 0
5 <- lifetime = 5
Червь: 1,1
step worm
(1 1)
1 1 0 1 0
2 1 0(1)
3 1 0 0 0 0 0
4 1 0 0 0 0
5 1 0 0 0
...
8 (1)
9 0 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0
...
18 0
19 <- lifetime = 19
Червь: 2
step worm
(2)
1 (1 1)
2 1 0 1 0 1 0
3 1 0 1 0(1)
4 1 0 1 0 0 0 0 0 0
5 1 0 1 0 0 0 0 0
6 1 0 1 0 0 0 0
...
10 1 0(1)
11 1 0 0 0 0 0 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0 0 0
...
24 (1)
25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
...
50 0
51 <- lifetime = 51
Червь: 2,1
(2 1)
1 2 0 2 0
2 2 0(2)
3 2 0(1 1 1 1)
4 2 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0
5 2 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0(1 1 1)
6 2 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0
7 2 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0(1 1)
8 2 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0{1 0}^9
...
?? <- lifetime = ??
Червь: 3
step worm
(3)
1 (2 2)
2 (2 1 2 1 2 1)
3 2 1 2 1 2 0 2 1 2 1 2 0 2 1 2 1 2 0 2 1 2 1 2 0
4 2 1 2 1 2 0 2 1 2 1 2 0 2 1 2 1 2 0 2 1 2 1(2)
5 2 1 2 1 2 0 2 1 2 1 2 0 2 1 2 1 2 0(2 1 2 1 1 1 1 1 1 1)
6 2 1 2 1 2 0 2 1 2 1 2 0 2 1 2 1 2 0{2 1 2 1 1 1 1 1 1 0}^7
7 2 1 2 1 2 0 2 1 2 1 2 0 2 1 2 1 2 0{2 1 2 1 1 1 1 1 1 0}^6 (2 1 2 1 1 1 1 1 1)
... ...
?? <- lifetime = ??
В сторону
Время жизни червя, как правило, огромно, о чем свидетельствуют следующие нижние границы в терминах стандартной быстрорастущей иерархии функций f α :
worm lower bound on lifetime
---------------- ------------------------------------------
11..10 (k 1s) f_k(2)
2 f_ω(2)
211..1 (k 1s) f_(ω+k)(2)
2121..212 (k 2s) f_(ωk)(2)
22..2 (k 2s) f_(ω^k)(2)
3 f_(ω^ω)(2)
...
n f_(ω^ω^..^ω)(2) (n-1 ωs) > f_(ε_0) (n-1)
Примечательно, что червь [3] уже имеет время жизни, которое намного превосходит число Грэхема G:
е ш ш (2) = F ш 2 (2) = F ω2 (2) = е ш + 2 (2) = е ш + 1 (е ш + 1 (2)) >> е ш + 1 (64) > Г.
Code Golf Challenge
Напишите кратчайшую возможную подпрограмму функции со следующим поведением:
Вход : любой червь.
Выход : время жизни червя.Размер кода измеряется в байтах.
Вот пример (Python, гольф до 167 байт):
from itertools import *
def T(w):
w=w[::-1]
t=0
while w:
t+=1
if w[0]:a=list(takewhile(lambda e:e>=w[0],w));a[0]-=1;w=a*(t+1)+w[len(a):]
else:w=w[1:]
return t
Примечание : если t (n) - время жизни червя [n], то скорость роста t (n) примерно равна скорости функции Гудштейна . Так что, если это может быть golfed ниже 100 байт, он вполне может дать выигрышную ответ на самое большое количество печати вопрос . (Для этого ответа скорость роста может быть значительно увеличена, если всегда начинать счетчик шагов с n - то же значение, что и у червя [n] - вместо запуска с 0.)
w[0]
который является * самым левым элементом этого списка?2 1
может быть слишком много , чтобы спросить , в разумный срок, но полезный тест , что последовательность должна начинаться(2 1)
,2 0 2 0
,2 0 (2)
,2 0 (1 1 1 1)
, ...Ответы:
GolfScript (
5654 символов)Онлайн демо
Я думаю, что ключевым трюком здесь, вероятно, является сохранение червя в обратном порядке. Это означает, что довольно просто найти длину активного сегмента:
.0+.({<}+??
(где0
добавляется в качестве защиты, чтобы мы нашли элемент меньше, чем голова).Кроме того, некоторый анализ продолжительности жизни червя. Я буду обозначать червя как
age, head tail
(то есть в обратном порядке от обозначения вопроса), используя показатели степени, чтобы указать повторение в голове и хвосте: например,2^3
есть2 2 2
.лемма : для любого активного сегмента
xs
существует функцияf_xs
, котораяage, xs 0 tail
преобразуется вf_xs(age), tail
.Доказательство: ни один активный сегмент не может содержать a
0
, поэтому возраст, к которому мы удаляем все, прежде чем хвост, не зависит от хвоста и, следовательно, зависит только от негоxs
.Лемма : для любого активного сегмента
xs
червьage, xs
умирает в возрастеf_xs(age) - 1
.Доказательство: по предыдущей лемме,
age, xs 0
превращается вf_xs(age), []
. Последний шаг - это удаление того0
, что ранее не затрагивалось, потому что оно никогда не может быть частью активного сегмента.С этими двумя леммами мы можем изучить некоторые простые активные сегменты.
Для
n > 0
,так
f_{1^n} = x -> f_{1^{n-1}}^{x+1}(x+2)
(с базовым вариантомf_{[]} = x -> x+1
, или, если вы предпочитаетеf_{1} = x -> 2x+3
). Мы видим, чтоf_{1^n}(x) ~ A(n+1, x)
гдеA
функция Аккермана – Петера.Этого достаточно, чтобы разобраться
1 2
(2 1
в обозначении вопроса):Таким образом, учитывая данные
2 1
мы ожидаем выхода ~A(A(5,4), A(5,4))
.и я действительно могу начать понимать, почему эта функция растет так безумно.
источник
9{-1%0\{\)\.0={.0+.({<}+??\((\+.@<2$*\+}{(;}if.}do;}:L~
вычисляет время жизни червя [9], которое намного превышает число Грэма - и может быть Гольф дальше.GolfScript,
6962 символаФункция
C
ожидает червя в стеке и заменяет его результатом.Примеры:
источник
*
и^
не используются в качестве арифметических операторов умножения и возвести в степень. Конечно, если вы хотите представить свой собственный (несомненно превосходящий) ответ, я с удовольствием удалю свой.Рубин - 131 символ
Я знаю, что это не может конкурировать с решениями GolfScript, описанными выше, и я вполне уверен, что это может уменьшить количество очков или больше символов, но, честно говоря, я счастлив, что смог решить проблему без присмотра. Отличная головоломка!
Мое решение для игры в гольф, из которого вытекает вышесказанное:
источник
if foo==0
их можно урезатьif foo<1
. Это может сэкономить вам один символ здесь.reverse
.else
предложение в одну строку, а затем поменять местамиif..else..end
для троичного выражения. Думаю, я мог бы также использовать лямбду, чтобы сохранить несколько символов.Скриптинг (43 символа)
Это ожидает ввода как разделенный пробелами список. Это выводит правильный ответ для
1 1
и2
, но для2 1
или3
это занимает слишком много времени, поэтому я перестал ждать его завершения.С комментарием:
источник
к (83)
worm:{-1+*({x,,(,/((x+:i)#,@[y@&w;(i:~~#y)#0;-1+]),y@&~w:&\~y<*y;1_y)@~*y}.)/(1;|,/x)}
это, вероятно, может быть использовано в дальнейшем, так как это просто реализует повторение довольно просто.
основная эволюционная функция
{x,,(,/((x+:i)#,@[y@&w;(i:~~#y)#0;-1+]),y@&~w:&\~y<*y;1_y)@~*y}
- 65 символов и использует некоторые приемы, чтобы не увеличивать возраст, когда червь умирает. Обертка вводит одно целое число в список, переворачивает ввод (короче, чтобы записать повторение в терминах червя, обратного из вашей нотации), запрашивает точку фиксации, выбирает возраст в качестве выходных данных и корректирует результат. для учета перерегулирования в последнем поколении.если я делаю принуждение и обращение вручную, оно падает до 80 (
{-1+*({x,,(,/((x+:i)#,@[y@&w;(i:~~#y)#0;-1+]),y@&~w:&\~y<*y;1_y)@~*y}.)/(1;x)}
).Некоторые примеры:
к сожалению, он, вероятно, не слишком широко используется для печати с наибольшим числом , кроме как в очень теоретическом смысле, поскольку он довольно медленный, ограничен 64-разрядными целыми числами и, вероятно, не особенно эффективен для использования памяти.
в частности,
worm 2 1
иworm 3
просто отток (и, вероятно, будет выбрасывать'wsfull
(из памяти), если я позволю им продолжать идти).источник
` to switch from
q` вk
и вставьте мой код. Кроме того, вы можете сохранить мой код в файле с.k
расширением и загрузить его в интерпретатор.APL (Dyalog Unicode) , 52 байта SBCS
Сохранено 7 байтов благодаря @ngn и @ Adám.
Попробуйте онлайн!
Объяснение:
источник
Скала, 198
Использование:
источник
К, 95
,
источник
C (gcc) , 396 байтов
Попробуйте онлайн!
Я знаю, что ОЧЕНЬ опоздал на вечеринку, но я решил попробовать свои силы в C, что потребовало реализации связанного списка. Это не совсем игра в гольф, кроме изменения всех идентификаторов на отдельные символы, но это работает!
В целом, я очень счастлив, учитывая, что это третья программа на C / C ++, которую я когда-либо писал.
источник
Haskell , 84 байта
Попробуйте онлайн!
Спасибо @xnor за два байта.
Я чувствую, что должен быть хороший способ выделить общий прирост, но я еще не нашел короткого.
источник
n
вниз на 1.(n+1)!
дважды, но моя попытка только связана.Perl 5
-pa
, 92 байтаПопробуйте онлайн!
источник
Stax , 31 байт
Запустите и отладьте его
источник