Sekwencje odwołujące się do siebie jak Kolakoski

19

Oto jak zdefiniowano sekwencję Kolakoskiego (OEIS A000002 ):

Sekwencja Kolakoski jest sekwencją, która zawiera 1i 2, a nth elementem tej sekwencji jest długość nth grupy równych elementów (przebiegów) w samej sekwencji. Pierwsze 20 elementów sekwencji i odpowiednie długości to:

1 2 2 1 1 2 1 2 2 1 2 2 1 1 2 1 1 2 2 1
- --- --- - - --- - --- --- - --- --- -
1  2   2  1 1  2  1  2   2  1  2   2  1

Zasadniczo długości grup równych elementów sekwencji Kolakoski to sama sekwencja Kolakoski.

Jak dotąd, tak dobrze, ale dlatego powinniśmy się ograniczać do 1i 2? Nie zamierzamy! Biorąc pod uwagę dwa dane wejściowe, tablicę dodatnich liczb całkowitych Ai liczbę całkowitą N, zwracają pierwsze Nwyrażenia sekwencji podobnej do Kolakoskiego, zdefiniowane przez cykliczne przechodzenie A. Aby lepiej to zrozumieć, oto sprawdzony przykład z długością nowo dodanych grup w nawiasach:

A = [2, 3, 1]
N = 25

2: [[2], 2 ]
3: [ 2 ,[2], 3 , 3 ]
1: [ 2 , 2 ,[3], 3 , 1 , 1 , 1 ]
2: [ 2 , 2 , 3 ,[3], 1 , 1 , 1 , 2 , 2 , 2 ]
3: [ 2 , 2 , 3 , 3 ,[1], 1 , 1 , 2 , 2 , 2 , 3 ]
1: [ 2 , 2 , 3 , 3 , 1 ,[1], 1 , 2 , 2 , 2 , 3 , 1 ]
2: [ 2 , 2 , 3 , 3 , 1 , 1 ,[1], 2 , 2 , 2 , 3 , 1 , 2 ]
3: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 ,[2], 2 , 2 , 3 , 1 , 2 , 3 , 3 ]
1: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 ,[2], 2 , 3 , 1 , 2 , 3 , 3 , 1 , 1 ]
2: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 ,[2], 3 , 1 , 2 , 3 , 3 , 1 , 1 , 2 , 2 ]
3: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 , 2 ,[3], 1 , 2 , 3 , 3 , 1 , 1 , 2 , 2 , 3 , 3 , 3 ]
1: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 , 2 , 3 ,[1], 2 , 3 , 3 , 1 , 1 , 2 , 2 , 3 , 3 , 3 , 1 ]
2: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 1 ,[2], 3 , 3 , 1 , 1 , 2 , 2 , 3 , 3 , 3 , 1 , 2 , 2 ]
C: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 1 , 2 , 3 , 3 , 1 , 1 , 2 , 2 , 3 , 3 , 3 , 1 , 2 , 2 ]

Oto kolejny sprawdzony przykład z wiodącym 1:

A = [1, 2, 3]
N = 10

1: [[1]]
2: [ 1 ,[2], 2 ]
3: [ 1 , 2 ,[2], 3 , 3 ]
1: [ 1 , 2 , 2 ,[3], 3 , 1 , 1 , 1 ]
2: [ 1 , 2 , 2 , 3 ,[3], 1 , 1 , 1 , 2 , 2 , 2 ]
C: [ 1 , 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 ]

Jak widać powyżej, wynik końcowy został przycięty do N = 10elementów. Elementem ntym powinna być długość grupy nrównych elementów, nawet jeśli sam element należy do grupy, do której się odnosi. Podobnie jak w powyższym przypadku, pierwsza 1odnosi się do pierwszej takiej grupy, która jest właśnie taka 1, a pierwsza 2odnosi się do drugiej takiej grupy, która zaczyna się od niej.

Zasady

  • Możesz założyć, że Anigdy nie będzie mieć dwóch lub więcej równych elementów. Amogą zawierać całkowitą więcej niż jeden raz, a pierwsze i ostatnie elementy nie są takie same, i Azawiera co najmniej 2 elementy (np [1, 2, 2, 3], [2, 4, 3, 1, 2]i [3]nie będzie podane). Jest tak, ponieważ gdyby istniały kolejne równe elementy, końcowy wynik byłby nieprawidłowym prefiksem dla takiej sekwencji.
  • Możesz założyć, że Azawiera tylko dodatnie liczby całkowite (ponieważ taka sekwencja byłaby w przeciwnym razie nieokreślona).
  • Możesz założyć, że Njest nieujemną liczbą całkowitą ( N >= 0).
  • Nie możesz zwrócić więcej warunków niż zażądano.
  • Korzystanie ze standardowych luk jest surowo zabronione.
  • Możesz użyć dowolnej rozsądnej metody We / Wy .
  • Twoja odpowiedź nie musi działać poza naturalnymi ograniczeniami języka, ale teoretycznie algorytm powinien działać dla dowolnie dużych danych wejściowych i liczb całkowitych .
  • To jest , więc wygrywa najkrótsza odpowiedź.

Przypadki testowe

[5, 1, 2], 0 -> []
[2, 3, 1], 25 -> [2, 2, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 2, 2, 3, 3, 3, 1, 2, 2]
[1, 2, 3], 10 -> [1, 2, 2, 3, 3, 1, 1, 1, 2, 2]
[1, 2], 20 -> [1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1]
[1, 3], 20 -> [1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 1, 3, 3, 3, 1, 1, 1, 3]
[2, 3], 50 -> [2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3]
[7, 4], 99 -> [7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 7, 7, 7, 7, 4, 4, 4, 4, 7, 7, 7, 7, 4, 4, 4, 4, 7, 7, 7, 7, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7, 7, 4]
[1, 2, 3], 5 -> [1, 2, 2, 3, 3]
[2, 1, 3, 1], 2 -> [2, 2]
[1, 3, 5], 2 -> [1, 3]
[2, 3, 2, 4], 10 -> [2, 2, 3, 3, 2, 2, 2, 4, 4, 4]
Erik the Outgolfer
źródło
piaskownica (
ponad
Związane z.
Martin Ender
@MartinEnder myślał, że już to powiązałem
Erik the Outgolfer

Odpowiedzi:

9

Łuska , 8 bajtów

Ṡωȯ↑⁰`Ṙ¢

Najpierw bierze długość, potem listę. Wypróbuj online!

Wyjaśnienie

Ṡωȯ↑⁰`Ṙ¢  Inputs: n=9 and x=[2,1,3]
Ṡωȯ       Apply the following function to x until a fixed point is reached:
           Argument is a list, say y=[2,2,1,3,3,3]
       ¢   Cycle x: [2,1,3,2,1,3..
     `Ṙ    Replicate to lengths in y: [2,2,1,1,3,2,2,2,1,1,1,3,3,3]
   ↑⁰      Take first n elements: [2,2,1,1,3,2,2,2,1]
          Final result is [2,2,1,1,3,2,1,1,1], print implicitly.
Zgarb
źródło
8

Pyth, 14 bajtów

u<s*V]M*QlGGvz

Wypróbuj online: pakiet demonstracyjny lub testowy

Wyjaśnienie:

u                 start with G = input array
       *QlG       repeat input array
     ]M           put every element into its own list
   *V      G      repeat every list vectorized by the counts in G
  s               flatten
 <          vz    take the first (second input line) numbers
                  and assign them to G until you reach fixed point
Jakube
źródło
Ciekawa alternatywa:u&VSvzs*V]M*Ql
Jakube,
1
To miłe podejście.
Erik the Outgolfer,
5

Java 8, 151 + 19 119 115 bajtów

a->n->{int c=0,l[]=new int[n],i=0,j;for(;i<n;i++)for(j=0;j<(c==i?a[i]:l[i])&c<n;j++)l[c++]=a[i%a.length];return l;}

Wypróbuj online!

Roberto Graham
źródło
1
Można zmniejszyć cztery bajty, pozbywając się z dwóch nawiasie, zmienia &&się &i usuwania przecinek: a->n->{int c=0,l[]=new int[n],i=0,j;for(;i<n;i++)for(j=0;j<(c==i?a[i]:l[i])&c<n;j++)l[c++]=a[i%a.length];return l;}( 115 bajtów )
Kevin Cruijssen
Zaproponuj (c==i?a:l)[i]zamiastc==i?a[i]:l[i]
ceilingcat
5

R , 120 114 108 bajtów

-6 bajtów dzięki plannapusowi

function(A,N){i=inverse.rle
w=length
a=rle(A)
while(w(a$l)<N){a[[1]]=i(a)
a[[2]]=rep(A,l=w(a$l))}
i(a)[0:N]}

Wypróbuj online!

Funkcja anonimowa; kolejno odwraca RLE zastępując długości a[[1]]z odwróconym RLE, a wartości a[[2]]z Areplikacji o długości równej liczbie a$l.

Giuseppe
źródło
@plannapus ah, racja! Próbowałem tego i zawiesiłem R, ponieważ przydział utworzy się, a$la a$vjeśli nie będą istnieć, ale nie wpłyną na wywołanie inverse.rle, powodując nieskończoną pętlę. Myślę, że mogę używać tylko a$lw whilestanie i repstanie.
Giuseppe,
5

Haskell , 68 bajtów

Ogromne podziękowania dla Laikoni i flawr za ich pomoc w debugowaniu i grze w golfa w odpowiedzi na czacie PPCG Haskell, Of Monads and Men . Zapraszamy do gry w golfa! Wypróbuj online!

(.f).take
f a@(z:_)=(z<$[1..z])++do i<-[1..];cycle a!!i<$[1..f a!!i]

Pierwszy wiersz jest funkcją anonimową. Druga linia to nieskończone rozumienie listy, które tworzy naszą sekwencję podobną do Kolakoskiego.

Wyjaśnienie

Po pierwsze, określamy zjako szef az a@(z:_). Następnie inicjujemy sekwencję za pomocą (z<$[1..z]).

Następnie z 1r do i<-[1..], to dołączenie następuje na sekwencji: cycle a!!i<$[1..f a!!i], który jest i-ty członkiem a(cyklicznie bez końca) dołączony f a!!irazy.

Wreszcie, anonimowa funkcja bierze po prostu pierwsze nwarunki naszej sekwencji podobnej do Kolaskoskiego.

Sherlock9
źródło
1

Python 2 , 123 bajty

x,y=input()
k=x[0]
t,j=[],0
if k==1:t,j=[k]+x[1]*[x[1]],2
while len(t)<y:t+=(j and t[j]or k)*[x[j%len(x)]];j+=1
print t[:y]

Wypróbuj online!

Officialaimm
źródło