Opis wyzwania

Mieliśmy kilka wyzwań związanych z sekwencją Look-and-say . Szybkie przypomnienie:

• Sekwencja zaczyna się 1,
• Kolejne warunki tej sekwencji są generowane przez wyliczenie każdej grupy powtarzających się cyfr z poprzedniego terminu,

Tak więc pierwsze kilka warunków to:

1        "one"
11       "one one" (we look at the previous term)
21       "two ones"
1211     "one two, one one"
111221   "one one, one two, two ones"
312211   "three ones, two twos, one one"

Teraz zróbmy to samo, ale zamiast tego użyj cyfr rzymskich . Zaczynamy odI i przestrzegamy tych samych zasad (zamiast tego stosujemy zasadę liczenia cyfr do znaków, więc czytamy IVXjako one one, one five, one tenzamiast one four, one tenlub w inny sposób):

I           "one"
II          "one one"
III         "two ones" = "II" + "I"
IIII        "three ones" = "III" + "I"
IVI         "four ones" = "IV" + "I"
IIIVII      "one one, one five, one one"
IIIIIVIII   "three ones, one five, two ones" = ("III" + "I") + ("I" + "V") + ("II" + "I")

Biorąc pod uwagę dodatnią liczbę całkowitą N:

• Wypisz pierwsze Ncyfry tej sekwencji (jakikolwiek rozsądny separator również jest w porządku["I", "II", "III", ...]
• Wyjściowy Nelement tej sekwencji (może być indeksowany 0).

Pamiętaj, aby twój kod był jak najkrótszy, ponieważ jest to wyzwanie dla golfa !

EDYCJA: Uważam, że zawsze istnieje jeden standardowy / preferowany sposób wyrażania liczb całkowitych jako cyfr rzymskich (jak 95-> XCVzamiastVC ). Kilka konwerterów cyfr rzymskich, które znalazłem w Internecie, potwierdza moje zdanie. W razie wątpliwości skorzystaj z konwertera online , ponieważ wyszczególnienie wszystkich możliwych przypadków brzegowych i szczegółowych zasad pisania cyfr rzymskich nie jest celem tego wyzwania.

EDIT2: @PeterTaylor i @GregMartin wskazał, że tylko liczby mniejsze lub równe 5są wyświetlane w kolejności, więc nie trzeba się martwić o dwuznaczności cyframi rzymskimi (numery 1- 8są I, II, III, IV, V, VI, VII, i VIII)

Perl, 49 bajtów

Obejmuje +1 dla -p

Uruchom z indeksem 0 na STDIN, np

ecce.pl <<< 14

ecce.pl:

#!/usr/bin/perl -p
s,(.)\1*,$&/$1%182 .$1,eg for($_=/$/)x$`;y;19;IV

Magiczne formuły są takie magiczne.

Normalnie użyłbym, ($_=//)x$'aby kontrola pętli była o jeden bajt krótsza, ale ocena na tej stronie daje handicap 2, więc kończy się o 1 bajt dłużej. Na starszych perlach możesz wcześniej upuścić przestrzeń for. Niektóre wersje Perla zmuszają cię do dodania finału; aby zamknąć transliterację. Ale to, co podano powyżej, to kod, który działa w moim systemie.

Wyjaśnienie

Praca wstecz od rozwiązania do kodu:

Potrzebne nam transformacje ciągów:

I     -> II
II    -> III
III   -> IIII
IIII  -> IVI
IIIII -> VI

V     -> IV
VV    -> IIV

Każda zamiana kończy się powtarzającym się znakiem. Otrzymam sekwencję tych samych znaków za pomocą wyrażenia regularnego /(.)\1*/, więc można to zrobić przez dołączenie $1. Część przed ->jest w $&. Z tym nadal potrzebuję:

I     -> I
II    -> II
III   -> III
IIII  -> IV
IIIII -> V

V     -> I
VV    -> II

Napisz Ijako 1i Vjako 9:

1     -> 1
11    -> 11
111   -> 111
1111  -> 19
11111 -> 9

9     -> 1
99    -> 11

Dzieląc poprzednią część ->przez powtarzającą się cyfrę, staje się to:

1     -> 1
11    -> 11
111   -> 111
1111  -> 19
11111 -> 9

1     -> 1
11    -> 11

Więc teraz powtórzony oryginał Vnie jest już wyjątkiem. Chcę więc wyrażenie, które sprawi, że tak się stanie:

1     -> 1
11    -> 11
111   -> 111
1111  -> 19
11111 -> 9

Można to zrobić za pomocą prostego modułu 182:

1     % 182 = 1
11    % 182 = 11
111   % 182 = 111
1111  % 182 = 19
11111 % 182 = 9

(to jeszcze dostaje IIIIIIsię do VIprawa, choć nie jest potrzebne tutaj)

Pozostaje tylko zainicjowanie zmiennej roboczej 1dla indeksu 0, powtórzenie transformacji w pętli, a na końcu zastąpienie 1przez Ii 9przezV

1, 9I 182jest to jedyny parametr kombinacja dla których ten proste prace formule.

Mathematica, 113 90 83 bajtów

Podziękowania dla Martina Endera za sugestie, które zmniejszyły długość o ponad 25%!

Pochwalanie się poleceniami wysokiego poziomu w Mathematica.

Nest[Flatten[Characters@{RomanNumeral@#,#2}&@@@Reverse@@@Tally/@Split@#]&,{"I"},#]&

Czysta funkcja, przyjmująca argument N i wysyłająca N-ty element tej (0-indeksowanej) sekwencji, jako listę znaków. Rozłóż się trochę:

Nest[
  Flatten[
    Characters @ {RomanNumeral@#,#2}& @@@
      Reverse @@@ Tally /@ Split@ #
    ]& ,
  {"I"}, #]&

Zewnętrzne Nestiteruje środkową funkcję czteroliniową, zaczynając od {"I"}N razy. Wiersz 4 dzieli listę znaków wejściowej cyfry rzymskiej na serie podobnych znaków, zlicza każdą serię za pomocą Tallyi umieszcza liczby przed znakami, które liczą. Wiersz 3 renderuje liczby jako cyfry rzymskie, a następnie dzieli te cyfry rzymskie na listy znaków. TheFlattenPolecenie zmniejsza całej listy-of-listy do listy jednowymiarowa.

Oto początkowa wersja:

Nest[
  "" <> Flatten[{RomanNumeral@#[[1]], #[[2]]} & /@
    (Reverse@#[[1]] & /@ 
      Tally /@
        Split@Characters@#)] &,
  "I", #] &

CJam ( 33 30 bajtów)

"I"{e`{(4md1$^'I*\'V*@}%e_}ri*

Demo online

Kluczem do poprawności wdrożenia jest następujące twierdzenie:

Jeśli pierwsza generacja to I, żadna długość serii nie jest większa niż pięć

Lemat: jeśli jest to pierwsza generacja I, żaden ciąg nie zawiera VVV. Dowodem jest sprzeczność. Załóżmy, że istnieje pierwszy indeks, ndla którego nzawiera th generacja VVV. Jeśli to się VVVpsuje, (a)V VVto konwersja z poprzedniej generacji jest zła: tak powinno być (a+5)V. Tak musi być VV V(d), a poprzednie pokolenie zawierało VVVVV, co stoi w sprzeczności z wyboremn .

Załóżmy teraz, że istnieje pierwszy indeks, mdla którego mzawiera th generacja ...IIIIII.... Pamiętaj, że nie może być innych cyfr niżI i Vw ciągu, ponieważ żadna poprzednia generacja miała serię dziewięciu Is lub dziewięć Vsekund. Co najwyżej cztery Is pochodzą z serii Is poprzedniego łańcucha, więc odpowiednia sekcja poprzedniego łańcucha musi ...IIIVV...dawać ... IIII IIV .... Ponieważ VVgeneracja m-1nie pochodzi VVVVV(patrz lemat), druga Vmusi być ciągiem cyfr I, więc w generacji m-1mamy ...IIIVVI.... A ponieważ chcemy, aby początkowe Is dawałyIIII a nie IVIlubVI, jest poprzedzony albo początkiem ciągu, albo znakiem V.

Jeśli mamy (...V)?IIIVVI...z pokoleniem m-1, co mamy z pokoleniem m-2? Zauważyliśmy już, że VVgen. m-1należy przeanalizować jako (a)V V(I).

Załóżmy, że weźmiemy a=2: (...V)?I IIV VI...Właściwie to musi być ...VI IIV VI..., chociaż to prowadzenie Vmoże być częścią IV; tak w poprzedniej generacji mamy albo (...V)? IIII VV IIIII...albo (...V)? IIIII VV IIIII. Tak czy inaczej, mamy z tym problem VVIIIII: drugi Vmusi być ciągiem, ale następnie ...VI IIII...wymaga następnej pary (ciąg, cyfra) z tą samą cyfrą.

Więc to musi być a=1: (...V)?II IV VI.... Ponieważ pokolenie mjest pierwszym z sześciu run Is, który musi być (...V)? II IV VI...tak, że pokolenie m-2to (...V)? I V IIIII.... ...VIVIIIII...jest niemożliwe: jednak zdecydujemy się zinterpretować sekundę, w wyniku Vczego otrzymamy dwie kolejne pary (długość, cyfra) o tej samej cyfrze.

Dlatego generacja m-2musi być ^IVIIIII...parsowana jako ^IV IIII I(V)...lub ^IV III II(V).... Dają one odpowiednio generację m-3jako ^V III V ...lub ^V II VV....

Ale jeśli spojrzymy na początek ciągów zaczynających się od pierwszego, który zaczyna się od V, otrzymujemy cykl:

    VI IV I...
    IV III IV ...
    II IV IVI ...
    IIII IV II IV ...

i tak nie zawsze zaczyna się generacja albo VIIIValbo VIIVV. Musimy stwierdzić, że takich nie ma m.

Sekcja

"I"          e# Initial generation
{            e# Loop...
  e`         e#   Run-length encode
  {          e#   Foreach [run-length char] pair...
    (        e#     Extract the run-length r
    4md1$^   e#     Get the number of Vs and the number of Is
             e#     The number of Vs is r/4 ; the number of Is is (r%4)^(r/4)
    'I*\'V*@ e#     Repeat strings the appropriate number of times and reorder
  }%
  e_         e#  Flatten to a simple string
}ri*         e# ... n times, where n is taken from stdin

Python 3, 195 bajtów

Na cyfrach rzymskich marnowanych jest wiele bajtów, więc prawdopodobnie trzeba tam zagrać w golfa.

Dzięki @ El'endiaStarman, @ Sherlock9 i @Shooqie

import re
def f(x,r=""):
 for v,i in(5,"V"),(4,"IV"),(1,"I"):a,x=divmod(x,v);r+=i*a
 return r
s="I"
for i in[0]*int(input()):print(s);s=re.sub(r'(.)\1*',lambda m:f(len(m.group()))+m.group()[0],s)

Ideone to!

R, 110 107 bajtów

as.romanw połączeniu z rleułatwia to. Wykrywanie nadużyć i wbudowane zachowanie kota <<-oszczędza kilka bajtów.

x="I"
replicate(scan(),{r=rle(strsplit(x,"")[[1]])
x<<-paste(rbind(paste(as.roman(r$l)),r$v),collapse="")})

Pobiera N z konsoli. Wyprowadza pierwsze 2 do N warunki sekwencji (które moim zdaniem mieszczą się w specyfikacji ...)

 [1] "II"                                                                                                                                                                                                                                     
 [2] "III"                                                                                                                                                                                                                                    
 [3] "IIII"                                                                                                                                                                                                                                   
 [4] "IVI"                                                                                                                                                                                                                                    
 [5] "IIIVII"                                                                                                                                                                                                                                 
 [6] "IIIIIVIII"                                                                                                                                                                                                                              
 [7] "VIIVIIII"                                                                                                                                                                                                                               
 [8] "IVIIIIVIVI"                                                                                                                                                                                                                             
 [9] "IIIVIVIIVIIIVII"                                                                                                                                                                                                                        
[10] "IIIIIVIIIVIIIIVIIIIIVIII"                                                                                                                                                                                                               
[11] "VIIVIIIIIVIVIIVVIIVIIII"                                                                                                                                                                                                                
[12] "IVIIIIVVIIVIIIVIIIIIVIIIIVIVI"                                                                                                                                                                                                          
[13] "IIIVIVIIIVIIIIVIIIIIVVIIVIVIIVIIIVII"                                                                                                                                                                                                   
[14] "IIIIIVIIIVIIIIIVIVIIVVIIIVIIIIVIIIVIIIIVIIIIIVIII"                                                                                                                                                                                      
[15] "VIIVIIIIIVVIIVIIIVIIIIIVIIIIIVIVIIVIIIIIVIVIIVVIIVIIII"                                                                                                                                                                                 
[16] "IVIIIIVVIIIVIIIIVIIIIIVVIIVVIIVIIIVIIIIVVIIVIIIVIIIIIVIIIIVIVI"                                                                                                                                                                         
[17] "IIIVIVIIIVIIIIIVIVIIVVIIIVIIIIIVIIIIVIIIIIVIVIIIVIIIIVIIIIIVVIIVIVIIVIIIVII"                                                                                                                                                            
[18] "IIIIIVIIIVIIIIIVVIIVIIIVIIIIIVIIIIIVVIIVIVIIVVIIVIIIVIIIIIVIVIIVVIIIVIIIIVIIIVIIIIVIIIIIVIII"                                                                                                                                           
[19] "VIIVIIIIIVVIIIVIIIIVIIIIIVVIIVVIIIVIIIIVIIIVIIIIIVIIIIVIIIIIVVIIVIIIVIIIIIVIIIIIVIVIIVIIIIIVIVIIVVIIVIIII"                                                                                                                              
[20] "IVIIIIVVIIIVIIIIIVIVIIVVIIIVIIIIIVIIIIIVIVIIVIIIIIVVIIVIVIIVVIIIVIIIIVIIIIIVVIIVVIIVIIIVIIIIVVIIVIIIVIIIIIVIIIIVIVI"                                                                                                                    
[21] "IIIVIVIIIVIIIIIVVIIVIIIVIIIIIVIIIIIVVIIVVIIVIIIVIIIIVVIIIVIIIIVIIIVIIIIIVIIIIIVIVIIVVIIIVIIIIIVIIIIVIIIIIVIVIIIVIIIIVIIIIIVVIIVIVIIVIIIVII"                                                                                             
[22] "IIIIIVIIIVIIIIIVVIIIVIIIIVIIIIIVVIIVVIIIVIIIIIVIIIIVIIIIIVIVIIIVIIIIIVIVIIVIIIIIVVIIVVIIVIIIVIIIIIVIIIIIVVIIVIVIIVVIIVIIIVIIIIIVIVIIVVIIIVIIIIVIIIVIIIIVIIIIIVIII"                                                                      
[23] "VIIVIIIIIVVIIIVIIIIIVIVIIVVIIIVIIIIIVIIIIIVVIIVIVIIVVIIVIIIVIIIIIVVIIVIIIVIIIIVVIIIVIIIIIVIIIIVIIIIIVVIIVVIIIVIIIIVIIIVIIIIIVIIIIVIIIIIVVIIVIIIVIIIIIVIIIIIVIVIIVIIIIIVIVIIVVIIVIIII"                                                   
[24] "IVIIIIVVIIIVIIIIIVVIIVIIIVIIIIIVIIIIIVVIIVVIIIVIIIIVIIIVIIIIIVIIIIVIIIIIVVIIIVIIIIVIIIIIVIVIIIVIIIIIVVIIVIVIIVVIIIVIIIIIVIIIIIVIVIIVIIIIIVVIIVIVIIVVIIIVIIIIVIIIIIVVIIVVIIVIIIVIIIIVVIIVIIIVIIIIIVIIIIVIVI"                             
[25] "IIIVIVIIIVIIIIIVVIIIVIIIIVIIIIIVVIIVVIIIVIIIIIVIIIIIVIVIIVIIIIIVVIIVIVIIVVIIIVIIIIIVIVIIVVIIVIIIVIIIIIVVIIIVIIIIVIIIVIIIIIVIIIIIVVIIVVIIVIIIVIIIIVVIIIVIIIIVIIIVIIIIIVIIIIIVIVIIVVIIIVIIIIIVIIIIVIIIIIVIVIIIVIIIIVIIIIIVVIIVIVIIVIIIVII"

JavaScript (ES6), 107

Funkcja rekurencyjna zwracająca N-ty termin na podstawie 0

f=(n,r='I')=>n?f(n-1,r.match(/I+|V+/g).map(x=>((n=x.length)-4?'VIII'.slice(n<5,1+n%5):'IV')+x[0]).join``):r

Test

f=(n,r='I')=>n?f(n-1,r.match(/I+|V+/g).map(x=>((n=x.length)-4?'VIII'.slice(n<5,1+n%5):'IV')+x[0]).join``):r

function update() {
  O.textContent=f(I.value)
}

update()

<input id=I value=25 type=number oninput='update()'><pre id=O></pre>

Perl 6 , 62 bajtów

{("I",{S:g/(.)$0*/{<I II III IV V>[$/.chars-1]~$0}/}...*)[$_]}

Anonimowa funkcja akceptująca indeks zerowy.

Wykorzystuje fakt, że liczby rzymskie wyższe niż 5 nie są potrzebne, ponieważ jedynymi grupami powtarzających się cyfr, które mogą wystąpić, są:

I     -> II
II    -> III
III   -> IIII
IIII  -> IVI
IIIII -> VI

V     -> IV
VV    -> IIV

( spróbuj online )