Look-and-Say-Sequenz: Ausgabe mit römischen Ziffern

20

Herausforderungsbeschreibung

Wir hatten einige Probleme mit der Look-and-Say-Sequenz . Schnelle Erinnerung:

  • Die Folge beginnt mit 1,
  • Nachfolgende Terme dieser Sequenz werden erzeugt, indem jede Gruppe sich wiederholender Ziffern im vorhergehenden Term aufgezählt wird.

Die ersten Begriffe sind also:

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"

Jetzt machen wir dasselbe, aber verwenden stattdessen römische Ziffern . Wir beginnen mit Iund folgen den gleichen Regeln (wir die Ziffer Zählung Regel Zeichen gelten statt, so lesen wir , IVXwie one one, one five, one tenanstelle von one four, one tenoder eine andere Art und Weise):

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")

Bei einer positiven Ganzzahl Nentweder:

  • Geben Sie die ersten NZiffern dieser Sequenz aus (jedes sinnvolle Trennzeichen ist in Ordnung)["I", "II", "III", ...]
  • Gibt den NTerm dieser Sequenz aus (er kann 0-indiziert sein).

Denken Sie daran, Ihren Code so kurz wie möglich zu halten, da dies eine Herausforderung ist!

EDIT: Ich glaube, dass es immer einen Standard / bevorzugten Weg gibt, Ganzzahlen als römische Ziffern auszudrücken (wie 95-> XCVstatt VC). Ein paar römische Umrechner, die ich online gefunden habe, bestätigen meine Meinung. Verwenden Sie im Zweifelsfall einen Online-Konverter , da die Auflistung aller möglichen Randfälle und spezifischen Regeln für das Schreiben von römischen Ziffern nicht der Punkt dieser Herausforderung ist.

EDIT2: @PeterTaylor und @GregMartin darauf hingewiesen , dass nur Zahlen kleiner oder gleich 5in der Reihenfolge angezeigt, so dass Sie zu kümmern sich nicht um die Mehrdeutigkeit von römischen Ziffern (Zahlen 1- 8sind I, II, III, IV, V, VI, VII, und VIII)

shooqie
quelle
Es gibt keinen eindeutigen römischen Zahlenausdruck für jede Ganzzahl. Welche Zahlen müssen möglicherweise ausgedrückt werden, und welche Ausdrücke dieser Zahlen sind gültig?
Peter Taylor
Was meinen Sie mit "es gibt keinen eindeutigen römischen Zahlenausdruck für jede ganze Zahl"? Gefällt dir 4/ IV/ IIII? Oder 95/ XCV/ VC? Es gibt möglicherweise nicht immer eine eindeutige Möglichkeit, eine Ganzzahl auszudrücken, aber ich bin mir ziemlich sicher, dass es immer eine bevorzugte (Standard-) gibt - korrigieren Sie mich, wenn ich falsch liege.
Shooqie
1
Wie weit müssen wir mit unseren römischen Ziffern gehen?
Maltysen
Ja, diese beiden Fälle. Im zweiten Fall denke ich, dass es eine Frage der Meinung ist, die vorzuziehen ist.
Peter Taylor
9
@shooqie Wenn diese Details nicht geklärt wären, wie würden Sie die Antworten vergleichen? Wenn bestimmte Randfälle der Interpretation überlassen bleiben, werden die tatsächlichen Ergebnisse bedeutungslos, da sie einen größeren Unterschied machen können als alle Golf-Tricks, die Ihnen einfallen könnten.
Martin Ender

Antworten:

17

Perl, 49 Bytes

Beinhaltet +1 für -p

Mit dem 0-basierten Index für STDIN ausführen, z

ecce.pl <<< 14

ecce.pl:

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

Magische Formeln sind so magisch.

Normalerweise würde ich verwenden ($_=//)x$', um die Schleifensteuerung um ein Byte kürzer zu machen, aber die Bewertung auf dieser Seite ergibt ein Handicap von 2, so dass es 1 Byte länger endet. Auf älteren Perls können Sie das Leerzeichen vorher ablegen for. Einige Versionen von Perl erzwingen das Hinzufügen eines Finales ;, um die Transliteration zu schließen. Aber was oben angegeben ist, ist der Code, der auf meinem System funktioniert.

Erläuterung

Rückwärts von der Lösung zum Code arbeiten:

Die String-Transformationen, die wir brauchen:

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

V     -> IV
VV    -> IIV

Jede Ersetzung endet mit dem wiederholten Zeichen. Ich werde eine Sequenz der gleichen Zeichen mit Regex erhalten /(.)\1*/, dies kann also durch Anhängen erfolgen $1. Der Teil vor dem ->ist in$& . Damit brauche ich noch:

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

V     -> I
VV    -> II

Schreiben Sie Ials 1undV als 9:

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

9     -> 1
99    -> 11

Durch Teilen des Teils vor -> durch die wiederholte Ziffer erhält man:

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

1     -> 1
11    -> 11

Das wiederholte Original Vist also keine Ausnahme mehr. Deshalb möchte ich einen Ausdruck, der dies ermöglicht:

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

Und dies kann mit einem einfachen Modulo 182 geschehen:

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

(das stimmt sogar IIIIII, VIobwohl es hier nicht benötigt wird)

Jetzt müssen Sie nur noch die Arbeitsvariable 1für den Index 0 initialisieren , diese Transformation in einer Schleife wiederholen und am Ende 1durch Iund 9durch ersetzenV

1, 9Und 182ist die einzige Parameter - Kombination , für die diese einfache Formel funktioniert.

Tonne Hospel
quelle
2
Das ist Genie! :)
Lynn
10

Mathematica, 113 90 83 Bytes

Vielen Dank an Martin Ender für Vorschläge, die die Länge um über 25% reduziert haben!

Vorführen der übergeordneten Befehle in Mathematica.

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

Eine reine Funktion, die ein Argument N verwendet und das N-te Element dieser (0-indizierten) Sequenz als Liste von Zeichen ausgibt. Ein bisschen ausbreiten:

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

Die äußere Nestiteriert die mittlere Vierzeilenfunktion, beginnend am {"I"}N-fachen. Zeile 4 teilt die Zeichenliste der eingegebenen römischen Zahl in Läufe gleicher Zeichen auf und zählt jeden Lauf mitTally und setzt die Anzahl vor die Zeichen, die sie zählen. Zeile 3 rendert die Zählungen als römische Ziffern und teilt diese römischen Ziffern in Listen von Zeichen auf. Der FlattenBefehl reduziert die gesamte Liste der Listen auf eine eindimensionale Liste.

Hier ist die erste Version:

Nest[
  "" <> Flatten[{RomanNumeral@#[[1]], #[[2]]} & /@
    (Reverse@#[[1]] & /@ 
      Tally /@
        Split@Characters@#)] &,
  "I", #] &
Greg Martin
quelle
3
Grrr Mathematica;)
Beta Decay
Wenn Sie @@@anstelle von verwenden /@, können Sie #und #2anstelle von #[[1]]und verwenden #[[2]]. Außerdem sind Zeichenlisten akzeptable Zeichenfolgentypen, sodass Sie mit diesen arbeiten und die Verwendung vermeiden können Characters@.
Martin Ender
@MartinEnder Aha, ich wusste, dass es eine @@@ähnliche Verknüpfung gegeben haben muss! In Bezug auf Listen von Zeichen, die zulässige Zeichenfolgentypen sind (was meiner Meinung nach den Code verkürzen würde): Gibt es auf dieser Website einen Beitrag, auf den Sie mich verweisen können, der die Community-Standards beschreibt?
Greg Martin
1
Noch ein paar Einsparungen: CharactersThreads, die Sie automatisch verwenden können @, Reverse@#&sind natürlich dasselbe wie Plain Reverse. In diesem Fall benötigen Sie diese Klammern auch nicht. Und Präfixnotation (im Fall von Flatten) speichert nichts, wenn Sie Klammern hinzufügen müssen, damit es funktioniert. Alles zusammen:Nest[Flatten[Characters@{RomanNumeral@#,#2}&@@@Reverse@@@Tally/@Split@#]&,{"I"},#]&
Martin Ender
8

CJam ( 33 - 30 Byte)

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

Online-Demo

Der Schlüssel zur Korrektheit der Implementierung ist der folgende Satz:

Bei der ersten Generation ist Ikeine Lauflänge größer als fünf

Lemma: Wenn die erste Generation ist I, enthält keine Zeichenfolge jemals VVV. Beweis ist durch Widerspruch. Angenommen, es gibt einen ersten Index, nfür den die ndritte Generation enthält VVV. Wenn das so VVVausfällt, (a)V VVdann ist die Umstellung von der Vorgängergeneration schlecht: es hätte sein sollen (a+5)V. So muss es sein VV V(d), und die Vorgängergeneration enthielt VVVVVWiderspruch gegen die Wahl vonn .

Angenommen, es gibt einen ersten Index, mfür den die mdritte Generation enthält ...IIIIII.... Beachten Sie, dass es keine anderen Ziffern als Iund Vin der Zeichenfolge geben kann, da keine frühere Generation einen Lauf von neun ISekunden oder neun VSekunden hatte. Allenfalls vier der Is kommen aus einem Laufe von Is in der vorherige Zeichenfolge, so dass der entsprechende Abschnitt der vorherigen Zeichenfolge muss ...IIIVV...geben ... IIII IIV .... Da die VVin-Generation m-1nicht von VVVVV(siehe Lemma) stammt, Vmuss die zweite eine Lauflänge von Ziffern sein I, also m-1haben wir in der Generation ...IIIVVI.... Und da wollen wir die Initialen Is geben IIIIund nicht IVIoderVIwird entweder der Anfang der Zeichenkette oder ein vorangestellt V.

Wenn wir (...V)?IIIVVI...in der Generation haben m-1, was haben wir in der Generation m-2? Wir haben das VVvon gen schon beobachtet . m-1muss analysiert werden als (a)V V(I).

Angenommen, wir nehmen a=2: (...V)?I IIV VI...Eigentlich muss es sein ...VI IIV VI..., obwohl diese Führung Vein Teil von sein könnte IV; also in der vorigen generation haben wir entweder (...V)? IIII VV IIIII...oder (...V)? IIIII VV IIIII. In VVIIIIIbeiden VFällen treten Probleme auf : Die zweite muss eine Lauflänge sein, ...VI IIII...erfordert dann jedoch ein nachfolgendes (Lauflänge, Ziffer) Paar mit derselben Ziffer.

So muss es sein a=1: (...V)?II IV VI.... Da die Erzeugung mder erste mit einem Lauf von sechs ist Is, sein , dass muss (...V)? II IV VI..., so dass die Erzeugung m-2ist (...V)? I V IIIII.... ...VIVIIIII...ist unmöglich: Wir interpretieren jedoch die Sekunde, in der Vwir zwei aufeinanderfolgende (Lauflängen-, Ziffern-) Paare mit derselben Ziffer haben.

Daher m-2muss die Generierung ^IVIIIII...als ^IV IIII I(V)...oder analysiert werden ^IV III II(V).... Diese geben jeweils Erzeugung m-3als ^V III V ...oder ^V II VV....

Wenn wir uns jedoch den Anfang der Zeichenfolgen ansehen, der mit der ersten beginnt V, erhalten wir einen Zyklus:

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

und so beginnt keine Generation jemals mit entweder VIIIVoder VIIVV. Wir müssen daraus schließen, dass es keine solche gibt m.

Präparation

"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
Peter Taylor
quelle
6

Python 3, 195 Bytes

Die römischen Ziffern sind mit einer Menge Bytes belegt, so dass dort wahrscheinlich etwas Golf gespielt werden muss.

Vielen Dank an @ El'endiaStarman, @ Sherlock9 und @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 es!

Beta-Zerfall
quelle
Sie können eckige Klammern weglassen:for v,i in(5,"V"),(4,"IV"),(1,"I")
Shooqie
@shooqie Ich hatte keine Ahnung, dass Sie das tun könnten: D
Beta Decay
for v,i in(5,"V"),(4,"IV"),(1,"I"):a,x=divmod(x,v);r+=i*aSpeichert ein Byte.
Sherlock9
@ βετѧΛєҫαγ: Außerdem scheinen Sie i(wie in for i in range(...)) nicht zu verwenden. Ich habe versucht, mich damit zu beschäftigen, execaber dies, das 1in der 'sub'-Methode ausgeblendet wurde, scheint den Code durcheinander zu bringen. Ich konnte keine Problemumgehung finden.
Shooqie
@shooqie ich es verkürzt ein wenig durch loszuwerdenrange
Beta Decay
4

R 110 107 Bytes

as.romankombiniert mit rlemacht dies einfach. Scoping-Missbrauch und eingebautes Katzenverhalten <<-sparen ein paar Bytes.

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

N wird von der Konsole eingezogen. Gibt die ersten 2 bis N Terme der Sequenz aus (von denen ich glaube, dass sie innerhalb der Spezifikation liegen ...)

 [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"
Vlo
quelle
1

JavaScript (ES6), 107

Rekursive Funktion, die den N-ten Term basierend auf 0 zurückgibt

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

Prüfung

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>

edc65
quelle
1

Perl 6 , 62 Bytes

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

Anonyme Funktion, die einen nullbasierten Index akzeptiert.

Nutzt die Tatsache, dass römische Zahlen über 5 nicht benötigt werden, da nur folgende Gruppen von sich wiederholenden Ziffern vorkommen können:

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

V     -> IV
VV    -> IIV

( online ausprobieren )

smls
quelle