Время жизни червя

28

условия

Червь является любым списком неотрицательных целых чисел, а его правый (т.е. последний ) элемент называется головой . Если голова не равна 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.)

Рез
источник
Я смущен вашим кодом. Вы сказали, что head - самый правый элемент, но в своем примере с Python вы рассматриваете head как элемент, w[0]который является * самым левым элементом этого списка?
@LegoStormtroopr Если вы можете рассматривать список как имеющий левый и правый. Если вы просто рассмотрите первое и последнее, вы можете сопоставить крайнее правое с первым или последним при чтении исходной строки - что не является частью вопроса. Но входы функций также не были строго определены.
Боб
@LegoStormtroopr - Хороший улов; Я исправил код, добавив строку для обратного ввода червя, чья голова действительно должна быть справа (т.е. последний элемент в списке w). Для эффективности программа работает с обратным червем.
Res
Получение правильного ответа для 2 1может быть слишком много , чтобы спросить , в разумный срок, но полезный тест , что последовательность должна начинаться (2 1), 2 0 2 0, 2 0 (2), 2 0 (1 1 1 1), ...
Питер Тейлор
1
@ThePlasmaRailgun - Перефразируя Харви Фридмана, числа, полученные из функций на уровне ε_0 в быстрорастущей иерархии (например, время жизни червя), совершенно НЕОБРАТИМОНЫ по сравнению с TREE (3) .
Res

Ответы:

15

GolfScript ( 56 54 символов)

{-1%0\{\)\.0={.0+.({<}+??\((\+.@<2$*\+}{(;}if.}do;}:L;

Онлайн демо

Я думаю, что ключевым трюком здесь, вероятно, является сохранение червя в обратном порядке. Это означает, что довольно просто найти длину активного сегмента: .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,

age, 1^n 0 xs -> age+1, (0 1^{n-1})^{age+1} 0 xs
              == age+1, 0 (1^{n-1} 0)^{age+1} xs
              -> age+2, (1^{n-1} 0)^{age+1} xs
              -> f_{1^{n-1}}^{age+1}(age+2), xs

так 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функция Аккермана – Петера.

age, 2 0 xs -> age+1, 1^{age+1} 0 xs
            -> f_{1^{age+1}}(age+1)

Этого достаточно, чтобы разобраться 1 2( 2 1в обозначении вопроса):

1, 1 2 -> 2, 0 2 0 2
       -> 3, 2 0 2
       -> f_{1^4}(4), 2
       -> f_{1^{f_{1^4}(4)+1}}(f_{1^4}(4)+1) - 1, []

Таким образом, учитывая данные 2 1мы ожидаем выхода ~ A(A(5,4), A(5,4)).

1, 3 -> 2, 2 2
     -> 3, 1 2 1 2 1 2
     -> 4, 0 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 2
     -> f_{21212}^4(5) - 1

age, 2 1 2 1 2 -> age+1, (1 1 2 1 2)^{age+1}
               -> age+2, 0 1 2 1 2 (1 1 2 1 2)^age
               -> age+3, 1 2 1 2 (1 1 2 1 2)^age

и я действительно могу начать понимать, почему эта функция растет так безумно.

Питер Тейлор
источник
Очень круто. Я думаю, что эта программа также даст выигрышный ответ на самую короткую завершающую программу, выходной размер которой превышает число Грэма . (Текущий победитель - 63 байта кода на Haskell.) Например, при 55 байтах что-то вроде (так как я склонен к синтаксическим ошибкам) 9{-1%0\{\)\.0={.0+.({<}+??\((\+.@<2$*\+}{(;}if.}do;}:L~вычисляет время жизни червя [9], которое намного превышает число Грэма - и может быть Гольф дальше.
Res
9

GolfScript, 69 62 символа

{0:?~%{(.{[(]{:^0=2$0+0=<}{\(@\+}/}{,:^}if;^?):?)*\+.}do;?}:C;

Функция Cожидает червя в стеке и заменяет его результатом.

Примеры:

> [1 1]
19

> [2]
51

> [1 1 0]
51
Говард
источник
Фантастика! Конечно, вы можете изменить это немного, чтобы также дать определенного победителя в вопросе «Самый большой номер для печати» .
Res
Я не видел, чтобы вы что-то там опубликовали , поэтому я продолжил и опубликовал модификацию этого кода как то, что, как я считаю, пока что является победным ответом - предполагая, что *и ^не используются в качестве арифметических операторов умножения и возвести в степень. Конечно, если вы хотите представить свой собственный (несомненно превосходящий) ответ, я с удовольствием удалю свой.
Res
7

Рубин - 131 символ

Я знаю, что это не может конкурировать с решениями GolfScript, описанными выше, и я вполне уверен, что это может уменьшить количество очков или больше символов, но, честно говоря, я счастлив, что смог решить проблему без присмотра. Отличная головоломка!

f=->w{t=0;w.reverse!;until w==[];t+=1;if w[0]<1;w.shift;else;h=w.take_while{|x|x>=w[0]};h[0]-=1;w.shift h.size;w=h*t+h+w;end;end;t}

Мое решение для игры в гольф, из которого вытекает вышесказанное:

def life_time(worm)
  step = 0
  worm.reverse!
  until worm.empty?
    step += 1
    if worm.first == 0
      worm.shift
    else
      head = worm.take_while{ |x| x >= worm.first }
      head[0] -= 1
      worm.shift(head.size)
      worm = head * (step + 1) + worm
    end
  end
  step
end
О.И.
источник
Общий совет: многие проблемы с гольфом работают с неотрицательными целыми числами, и в этом случае if foo==0их можно урезать if foo<1. Это может сэкономить вам один символ здесь.
Питер Тейлор
Между прочим, я нахожу это захватывающим, что это работает без секунды reverse.
Питер Тейлор
Ах, это не так. Это работает только в тестовых случаях, потому что они имеют только палиндромные активные сегменты.
Питер Тейлор
Спасибо за совет по гольфу, @PeterTaylor. Кроме того, хороший улов на недостающем втором реверсе. Я добавил это. Попробую переписать это другим способом, не используя реверс позже. Я почти уверен, что смогу свести elseпредложение в одну строку, а затем поменять местами if..else..endдля троичного выражения. Думаю, я мог бы также использовать лямбду, чтобы сохранить несколько символов.
OI
6

Скриптинг (43 символа)

글坼가⑴감套擘終長①加⒈丟倘⓶增⓶가采⓶擘❷小終⓷丟❶長貶❷가掊貶插①增復合감不가終終

Это ожидает ввода как разделенный пробелами список. Это выводит правильный ответ для 1 1и 2, но для 2 1или3 это занимает слишком много времени, поэтому я перестал ждать его завершения.

С комментарием:

글坼 | split at spaces
가⑴ | iteration count = 0

감套 | while:
  擘終長①加⒈丟 | remove zeros from end and add to iteration count
  倘 | if the list is not empty:
    ⓶增⓶ | increment iteration count
    가采⓶擘❷小終⓷丟 | separate out active segment
    ❶長貶❷가掊貶插 | compute reduced active segment
    ①增復合 | repeat reduced active segment and concat
    감 | continue while loop
  不 | else
    가 | stop while loop
  終 | end if
終 | end while
Timwi
источник
2
Ссылка на интерпретатор была бы удобной ... Кроме того, 86 байтов, используя UTF-16?
Питер Тейлор
@PeterTaylor: Спасибо, добавил в статью ссылку на переводчика. И да, 43 символа BMP преобразуются в 86 байтов в UTF-16.
Тимви
5

к (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)} ).

Некоторые примеры:

  worm 1 1 0
51
  worm 2
51
  worm 1 1
19

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

в частности, worm 2 1и worm 3просто отток (и, вероятно, будет выбрасывать 'wsfull(из памяти), если я позволю им продолжать идти).

Аарон Дэвис
источник
Я пытался запустить вашу программу с помощью этого онлайн-переводчика , но он не показывает никаких результатов. (Отправка текстового файла с расширением .k должна вызывать интерпретатор K.) Знаете ли вы, что можно сделать, чтобы отправить вывод на стандартный вывод?
Res
Похоже, что это работает kona, клон с открытым исходным кодом k3. Мой код написан на k4 и вряд ли будет совместим с k3. Вы можете получить ограниченную по времени бесплатную копию q / k4 по адресу kx.com/software-download.php ; как только вы это сделаете, запустите REPL, введите ` to switch from q` в kи вставьте мой код. Кроме того, вы можете сохранить мой код в файле с .kрасширением и загрузить его в интерпретатор.
Аарон Дэвис
2

APL (Dyalog Unicode) , 52 байта SBCS

Сохранено 7 байтов благодаря @ngn и @ Adám.

0{⍬≡⍵:⍺⋄n←⍺+10=⊃⍵:n1↓⍵⋄n∇∊(⊂1n/-∘1@1¨)@1⊆∘⍵⍳⍨⌊\⍵}⌽

Попробуйте онлайн!

Объяснение:

0{...}⌽     A monadic function train. We define a recursive function with two
            arguments: zero (our counter), and the reverse of our input
⍬≡⍵:⍺       Our base case - if our input is an empty list, return our counter
n←⍺+1       Define 'n' as our counter plus 1
0=⊃⍵:n1↓⍵  If the first element of the input is zero, recurse with the tail
            of our input and n
\⍵         Minimum-expand: creates a new list from our input where each element
            is the incremental minimum     
⍳⍨          Applies above to both sides of the index-of function. Index-of returns
            the index of the first occurence of each element in the left-side list.
            At this point, a (reversed) input list of [3 4 5 2 3 4] would result
            in [1 1 1 4 4 4]
⊆∘⍵         Partition, composed with our input. Partition creates sublists of the
            right input whenever the integer list in the left input increases.
            This means we now have a list of sub-lists, with the first element
            being the worm's active segment.
(...)@1    ⍝ Take the active segment and apply the following function train...
-∘1@1¨     ⍝ Subtract 1 from the first element of the active segment
1n/        ⍝ Replicate the resultant list above n+1 times
⊂          ⍝ Enclose the above, so as to keep the original shape of our sub-array
∊          ⍝ Enlist everything above together - this recursively concatenates our
           ⍝ new active segment with the remainder of the list
n∇         ⍝ Recurse with the above and n
voidhawk
источник
Я полагал, что у APL было бы действительно чистое решение для этого, разве это не язык на основе массива?
ThePlasmaRailgun
1

Скала, 198

type A=List[Int]
def T(w:A)={def s(i:Int,l:A):Stream[A]=l match{case f::r=>l#::s(i+1,if(f<1)r
else{val(h,t)=l.span(_>=l(0));List.fill(i)(h(0)-1::h.tail).flatten++t})
case _=>Stream()};s(2,w).length}

Использование:

scala> T(List(2))
res0: Int = 51
ValarDohaeris
источник
1

К, 95

{i::0;#{~x~,0}{((x@!b),,[;r]/[i+:1;r:{@[x;-1+#x;-1+]}@_(b:0^1+*|&h>x)_x];-1_x)@0=h:*|x:(),x}\x}

,

k)worm:{i::0;#{~x~,0}{((x@!b),,[;r]/[i+:1;r:{@[x;-1+#x;-1+]}@_(b:0^1+*|&h>x)_x];-1_x)@0=h:*|x:(),x}\x}
k)worm 2
51
k)worm 1 1
19
q)worm 1 1 0 0 0 0
635
tmartin
источник
1

C (gcc) , 396 байтов

#define K malloc(8)
typedef*n;E(n e,n o){n s=K,t=s;for(*s=*o;o=o[1];*t=*o)t=t[1]=K;t[1]=e;e=s;}main(c,f,l,j,a)n*f;{n w=K,x=w;for(;l=--c;x=x[1]=K)*x=atoi(f[c]);for(;w&&++l;)if(*w){n v=K,z=v,u=w,t=K;for(a=*v=*w;(u=u[1])&&*u>=*w;*z=*u)z=z[1]=K;for(x=v[1],v=K,*v=a-1,1[u=v]=x;u;u=u[1])w=w[1];for(j=~l;j++;)u=t=E(t,v);for(;(u=u[1])&&(x=u[1])&&x[1];);u[1]=0;w=w?E(w,t):t;}else w=w[1];printf("%d",--l);}

Попробуйте онлайн!

Я знаю, что ОЧЕНЬ опоздал на вечеринку, но я решил попробовать свои силы в C, что потребовало реализации связанного списка. Это не совсем игра в гольф, кроме изменения всех идентификаторов на отдельные символы, но это работает!

В целом, я очень счастлив, учитывая, что это третья программа на C / C ++, которую я когда-либо писал.

ThePlasmaRailgun
источник
Вам действительно нужен связанный список? Почему бы просто не выделить массивы? Так как это кодовый гольф, вам даже не нужно беспокоиться об их освобождении, когда вы закончите. Вы могли бы даже быть в состоянии найти способ их хранения в стеке вызовов (не уверен).
dfeuer
Кроме того, вам не нужна основная функция. Просто напишите функцию, которая принимает червя в качестве аргумента и возвращает его срок службы. Червь может быть массивом и его длиной, или, возможно, массивом, заканчивающимся отрицательным числом.
dfeuer
1

Haskell , 84 байта

(0!).reverse
n!(x:y)|x<1=(n+1)!y|(a,b)<-span(>=x)y=(n+1)!(([-1..n]*>x-1:a)++b)
n!_=n

Попробуйте онлайн!

Спасибо @xnor за два байта.

Я чувствую, что должен быть хороший способ выделить общий прирост, но я еще не нашел короткого.

dfeuer
источник
1
Два маленьких гольфа : проверьте второй случай пустого списка и сдвиньтесь nвниз на 1.
xnor
Я также думаю, что должен быть способ не писать (n+1)!дважды, но моя попытка только связана.
xnor