Angenommen, wir definieren ein einfaches Programm, das ein Array L natürlicher Zahlen mit einer gewissen Länge N verwendet und Folgendes tut:
i=0 #start at the first element in the source array
P=[] #make an empty array
while L[i]!=0: #and while the value at the current position is not 0
P.append(L[i]) #add the value at the current position to the end of the output array
i=(i+L[i])%N #move that many spaces forward in the source array, wrapping if needed
return P #return the output array
Jedes dieser Programme wird entweder für immer ausgeführt oder schließlich beendet, wodurch eine Liste positiver Ganzzahlen erstellt wird. Ihre Aufgabe ist es, bei einer Liste P mit positiven ganzen Zahlen eine kürzeste Liste L mit natürlichen Zahlen zu erstellen, die endet und P erzeugt, wenn sie in das vorherige Programm eingesteckt wird.
Eine solche Liste existiert immer, da man P[i]-1
nach jeder P[i]
in der Liste nur Nullen hinzufügen kann , dann eine letzte 0, und die ursprüngliche Liste erstellt wird. Zum Beispiel [5,5]
ist eine Lösung gegeben [5,0,0,0,0,5,0,0,0,0,0]
. Ist [5,0,5]
jedoch viel kürzer, so ist die automatische Lösung für Ihr Programm nicht gültig.
[5,6]->[5,6,0,0]
[5,7]->[5,0,0,0,0,7,0,0]
[5,6,7]->[5,6,0,7]
[5,6,8]->[5,0,8,0,0,6,0,0,0]
[1,2,3,4]->[1,2,0,3,0,0,4,0]
[1,2,1,2]->[1,2,0,1,2,0,0]
[1,3,5,7]->[1,3,0,0,5,0,0,0,0,7]
[1,3,5,4]->[1,3,4,0,5,0,0]
Die Eingabe ist eine Liste positiver Ganzzahlen (in einem von Ihnen angegebenen Format), und die Ausgabe sollte im selben Format erfolgen. Listen- und Ganzzahlgröße können bis zu 2 ^ 16 betragen. Dies ist Code Golf, also gewinnt das kürzeste Programm in Bytes!
Antworten:
Python 3,
109 102 100 9593 BytesEine rekursive Lösung. Nennen wir es wie
f([1,2,3,4])
. Beobachten Sie, wie alle Testfälle bestanden werden.Wir beginnen mit
k=1
(Länge der Ausgabe) undi=0
(Position in der Ausgabe) und erstellen eine ListeP
mitk
Nullen. Dann iterieren wir entlang der Elementex
vonL
und aktualisierenP[i]
aufP[i]or x
(P[i]
behält also seinen Wert, wenn er nicht Null ist) undi
auf(i+P[i])%k
. Danach überprüfen wir, ob der Endwert vonP[i]
Null ist, erhöhen ihn,k
wenn dies nicht der Fall ist, und kehren zurückP
.Wenn der Algorithmus zu irgendeinem Zeitpunkt
P[i]
bereits ungleich Null ist, tritt er in eine Schleife ein, die einige der Werte ungleich Null umgehtP
, und endet bei einem Wert ungleich Null. dann rekursieren wir.quelle