Die Idee hier ist, ein sich fast wiederholendes Muster zu erzeugen . Das heißt, die zu konstruierende Sequenz ändert sich im letzten Moment, um eine Wiederholung einer Teilsequenz zu vermeiden. Folgen vom Typ AA und ABA sind zu vermeiden (wobei B nicht länger als A ist).

Beispiele:

Ich werde zunächst alle kleinen Beispiele auflisten, um meine Beschreibung klarer zu machen. Beginnen wir mit 0.

Gültig: 0

Ungültig: 00 (AA-Muster)
Gültig: 01

Ungültig: 010 (ABA-Muster)
Ungültig: 011 (AA-Muster)
Gültig: 012

Gültig: 0120
Ungültig: 0121 (ABA-Muster)
Ungültig: 0122 (AA-Muster)

Ungültig: 01200 (AA-Muster)
Ungültig: 01201 (ABA-Muster; 01-2-01)
Ungültig: 01202 (ABA-Muster)
Gültig: 01203

Jetzt glaube ich fest daran, dass a 4niemals benötigt wird, obwohl ich keinen Beweis habe, weil ich leicht Sequenzen mit Hunderten von Zeichen gefunden habe, die nur verwendet werden 0123. (Es hängt wahrscheinlich eng damit zusammen, wie nur drei Zeichen benötigt werden, um unendliche Zeichenfolgen zu haben, die keine AA-Muster haben. Es gibt eine Wikipedia-Seite dazu.)

Input-Output

Die Eingabe ist eine einzelne positive Ganzzahl ungleich Null n. Sie können das annehmen n <= 1000.

Die Ausgabe ist eine nZeichenfolge ohne Teilsequenzen, die mit einem der verbotenen Muster (AA oder ABA) übereinstimmen.

Beispiel für Ein- und Ausgänge

>>> 1
0

>>> 2
01

>>> 3
012

>>> 4
0120

>>> 5
01203

>>> 50
01203102130123103201302103120132102301203102132012

Regeln

• Nur die Zeichen 0123sind erlaubt.
• B ist nicht länger als A. Dies dient dazu, die Situation zu vermeiden, in der 012345gefolgt werden muss, 6weil 0123451dies : 1-2345-1. Mit anderen Worten, die Sequenz wäre trivial und uninteressant.
• nkann durch jedes gewünschte Verfahren eingegeben werden, außer durch Hardcodierung.
• Die Ausgabe kann entweder eine Liste oder eine Zeichenfolge sein, je nachdem, was einfacher ist.
• Keine rohe Gewalt ; Die Laufzeit sollte in der Größenordnung von Minuten liegen, höchstens eine Stunde auf einer sehr langsamen Maschine, z n=1000. (Dies soll Lösungen disqualifizieren, die nur alle nPermutationen von Länge durchlaufen {0,1,2,3}, so dass Tricks und ähnliche Tricks nicht erlaubt sind.)
• Standardschlupflöcher sind wie üblich nicht zulässig.
• Die Bewertung erfolgt in Bytes. Dies ist Code-Golf , also gewinnt der kürzeste Eintrag (wahrscheinlich - siehe Bonus).
• Bonus: Wählen Sie bei jedem Schritt die niedrigste zulässige Ziffer. Wenn 1und 3für die nächste Ziffer in der Sequenz eine Auswahl möglich ist, wählen Sie1 . Subtrahieren Sie 5 Bytes von Ihrer Punktzahl. Beachten Sie jedoch den folgenden Hinweis.

Hinweis!

Sackgassen sind möglich. Ihr Programm oder Ihre Funktion muss diese vermeiden. Hier ist ein Beispiel:

Stumpf: 0120310213012310320130210312013210230120310213201230210312013023103201230213203102301203210231201302103123013203102130120321023013203123021032012310213012012
Stumpf: 0120310213012310320130210312013210230120310213201230210312013023103201230213203102301203210231201302103123013203102130120321023013203123021032012330212012
Stumpf: 01203102130123103201302103120132102301203102132012302103120130231032012302132031023012032102312013021031230132031021301203210230132031230210320123103303203
Stumpf: 012031021301231032013021031201321023012031021320123021031201302310320123021320310230120321023120130210312301320310213012032102301320312302103201233021203103

Jede dieser Sequenzen kann nicht weiter erweitert werden (ohne Verwendung von a 4). Beachten Sie aber auch, dass es einen entscheidenden Unterschied zwischen den ersten beiden und den zweiten beiden gibt. Ich werde die gemeinsame anfängliche Teilsequenz durch eine ersetzen X, um dies klarer zu machen.

Stumpf: X2130120
Stumpf: X2130123
Stumpf: X320
Stumpf: X321301203102130

Die letzten beiden Ziffern von Xsind 10, daher sind und die einzig mögliche Auswahl für die nächste Ziffer 2und 3. Die Auswahl 2führt zu einer Situation, in der die Sequenz beendet werden muss . Der Greedy - Algorithmus wird nicht hier arbeiten. (Jedenfalls nicht ohne Rückverfolgung.)

Netzhaut , 86 Bytes - 5 = 81

$
_
(r`^(?<-2>.)+_((.)+)\b$
$1!
\b$
0
3#
#
0#
1
1#
2
2#
3
)r`\1(?<-2>.)*((.)+)$
$0#
!
<empty>

Wobei <empty>eine leere nachfolgende Linie steht. Sie können den obigen Code aus einer einzelnen Datei mit dem -sFlag ausführen .

Die Eingabe sollte unär erfolgen , z 111111. Ich habe es noch nicht auf Ausgabe in der Größenordnung von Tausenden getestet - zwei der regulären Ausdrücke werden nach einer Weile möglicherweise etwas langsam -, aber es kann problemlos ein paar Hundert in wenigen Sekunden verarbeiten.

Erläuterung

Dies ist eine einfache Backtracking-Lösung.

1. Fügen Sie a hinzu 0.
2. Während die aktuelle Sequenz ungültig ist, entfernen Sie alle nachfolgenden 3s und erhöhen Sie die letzte Nicht- 3.
3. Wiederholen, bis eine gültige Sequenz mit der gewünschten Länge vorliegt.

Dieses Backtracking wird durch eine Schleife von Regex-Ersetzungen implementiert, die abgebrochen wird, sobald die Zeichenfolge durch eine Iteration unverändert bleibt.

$
_

Dies hängt ein _an die Eingabe an, mit der die unäre Eingabe von der Sequenz getrennt wird, die wir erstellen.

(r`^(?<-2>.)+_((.)+)\b$
$1!

Dies ist die erste Ersetzung in der Schleife (angezeigt durch die führende (). Die Regex stimmt überein, wenn a) am Ende der Zeichenfolge ein Wortzeichen (dh eine Ziffer) steht (was bedeutet, dass die Zeichenfolge gültig ist - wir werden unten sehen, dass ungültige Sequenzen mit einem nachgestellten Zeichen gekennzeichnet sind #) und b) mindestens vorhanden ist so viele Zeichen in der Sequenz wie in der Eingabe (dies wird mithilfe von Ausgleichsgruppen überprüft ). In diesem Fall entfernen wir die Eingabe und fügen a hinzu !. Dies !dient dazu, dass alle regulären Ausdrücke in der Schleife fehlschlagen, sodass sie beendet werden.

\b$
0

Wenn am Ende ein Wortzeichen steht (dh die Sequenz ist gültig und die Schleife wurde im vorherigen Schritt nicht beendet), fügen Sie a hinzu 0.

3#
#

Wenn (stattdessen) die Sequenz als ungültig markiert wurde und mit endet 3, entfernen wir diese 3(lassen die Sequenz jedoch als ungültig, da für das aktuelle Präfix keine Fortsetzung möglich ist ... daher muss auch das nächste Zeichen zurückverfolgt werden).

0#
1
1#
2
2#
3

Wenn die Sequenz als ungültig markiert ist und eine andere Ziffer als 3am Ende steht, erhöhen wir die Ziffer und entfernen die Markierung.

)r`\1(?<-2>.)*((.)+)$
$0#

Die letzte Ersetzung in der Schleife (wie durch angezeigt )). Es wird geprüft, ob die Zeichenfolge endet ABA(wobei sie Bnicht länger als, Aaber möglicherweise leer ist). Die relativen Längen von Aund Bwerden erneut unter Verwendung von Ausgleichsgruppen überprüft, und die Wiederholung von Awird mit einer einfachen Rückreferenz überprüft.

Wenn dieser reguläre Ausdruck übereinstimmt, markieren wir die Sequenz durch Anhängen als ungültig #.

!
<empty>

Sobald die Schleife beendet ist, müssen wir nur noch die entfernen !und dann die gewünschte Ausgabe erhalten.

Python 2, 175 - 5 = 170 Bytes

n=input();s='';u=j=-1
while n>len(s):
 while u>2:u=int(s[0]);s=s[1:]
 u+=1;t=`u`+s;m=c=0
 while t[c:]*0**m:c+=1;i=t[c:].find(t[:c]);m=j<i<=c
 if c>=len(t):s=t;u=j
print s[::j]

Dies ist der gierige Algorithmus mit Backtracking. Ich wünschte, es wäre kürzer. Ich hoffe es ist richtig (siehe unten).

Die Zeichenfolge wird ziffernweise erstellt. Bei einer dbereits gefundenen Ziffernfolge wird versucht, a 0als (d+1)erste Ziffer anzuhängen . Wenn das nicht funktioniert, versucht es a 1, dann a 2, dann a 3. Wenn keines davon funktioniert, kehrt es zur ddritten Ziffer zurück und erhöht sie (wenn kleiner als 3) oder entfernt sie (wenn gleich 3, in diesem Fall erhöht es die vorherige usw.).

Die Gültigkeitsprüfung ist die Zeile mit .find. Falls sich jemand entscheidet, meinen Code zu lesen, sollte ich sagen, dass dieses Programm die Zeichenfolge tatsächlich rückwärts speichert, was bedeutet, dass es Ziffern nach vorne hinzufügt . Bei der Prüfung wird also nach Stellen gesucht, an denen die ersten c Ziffern später in der Zeichenfolge erneut angezeigt werden (irgendwo nach den ersten cZiffern), und wenn es solche Stellen gibt, ob die dazwischen liegende Länge höchstens ist c.

(Natürlich wird die Zeichenfolge vor dem Drucken umgekehrt.)

Es könnte auch leicht schneller sein; Ich hatte ursprünglich verschiedene Schleifen aus Effizienzgründen frühzeitig verlassen, aber das kostete wertvolle Bytes. Im Bereich von n=1000ist es jedoch immer noch in Ordnung .

Wie auch immer, das Programm scheint eine Präferenz für die kleineren Ziffern aufzuweisen, aber es ist keine sehr starke Präferenz. Wenn n=2000ich es zum Beispiel mit laufen ließ, erhielt ich eine Zeichenfolge mit 523Nullen, 502Einsen, 497Zweien und 478Dreien, die mit endete 30210312013021. Wenn also jemand anderes an einem gierigen Algorithmus arbeitet, kann er dieses Ergebnis möglicherweise bestätigen. Oder mit habe n=1000ich [263, 251, 248, 238]für die Zählungen nach Ziffern.

Abschließend möchte ich erwähnen, dass diese Zählungen auf Symmetrie hindeuten, fast (wenn auch nicht genau), als hätten wir mit einer gleichmäßigen Verteilung begonnen und dann einige der 3's in 0' s und einige der 2's in 1' umgewandelt. s. Aber das könnte natürlich nur Zufall sein. Ich habe keine Ahnung!

Haskell, 115 (120 Bytes - 5 Bonus)

x?_|or[t x==t(drop i x)|i<-[1..length x],t<-[take$div(i+1)2]]=[]
x?0=[x]
x?n=(?(n-1)).(:x)=<<"0123"
f=reverse.head.([]?)

Laufen Sie online bei Ideone

Beispiellauf:

*Main> f 40
"0120310213012310320130210312013210230120"