Das Szenario
Nach einem langen Arbeitstag im Büro und dem Durchstöbern von stackexchange.com gehe ich endlich um 16:58 Uhr aus der Tür, schon müde vom Tag. Da ich noch Praktikant bin, bin ich momentan mit dem Fahrrad unterwegs. Ich gehe zu meinem vertrauenswürdigen Peugeot Reynolds 501 , aber bevor ich davonsegeln kann, muss ich ihn entsperren. Das Schloss ist ein vierstelliges Standardkombinationsschloss (0-9) über den Rahmen und das Vorderrad. Während ich versuche, wach zu bleiben, ziehe ich meine Hand nach oben, um in die Kombination einzutreten.
Die Herausforderung
Weil meine Finger so müde sind, möchte ich das Schloss mit den wenigsten Bewegungen auf die richtige Kombination drehen. Eine Bewegung ist definiert als eine Drehung um eine Position (36 Grad), zum Beispiel gibt es eine Bewegung von 5737
bis 5738
. Ich bin jedoch in der Lage, bis zu drei aufeinanderfolgende Ringe gleichzeitig zu erfassen und sie als einen zu drehen , was nur als eine einzige Bewegung zählt. Zum Beispiel gibt es auch nur eine Bewegung von 5737
nach 6837
oder nach 5626
. Das Bewegen von 5737
nach 6838
ist nicht eine Bewegung, da sich die Ziffern 1, 2 und 4 in die gleiche Richtung bewegt haben, sondern unabhängig von Ziffer 3.
Daher kann ich für eine bestimmte Kombination auf dem Fahrradschloss (eine beliebige 4-stellige Ganzzahl) sehen, wie viele Bewegungen ich am wenigsten ausführen kann, um es zu entsperren, und ja, ich kann mich jederzeit in beide Richtungen drehen. Damit meine ich, dass ich einige Ziffern in die eine und andere Ziffern in die andere Richtung drehen kann: Nicht alle meine Bewegungen werden bei jedem Entsperren im oder gegen den Uhrzeigersinn ausgeführt.
Da ich faul bin, ist mein Freischaltcode 0000.
Dies ist Codegolf Ich kann nicht viel Code schreiben, so dass das kürzeste Programm in Anzahl von Bytes gewinnt.
Die Eingabe erfolgt von stdin, und Ihr Code sollte die Kombinationen ausgeben, die ich bei jedem Schritt nach jeder Bewegung sehen kann, einschließlich der 0000 am Ende. Jede der ausgegebenen Kombinationen sollte durch ein Leerzeichen / Zeilenumbruch / Komma / Punkt / Et-Zeichen getrennt werden.
Beispiele
Input: 1210
0100
0000
Input: 9871
9870
0980
0090
0000
Input: 5555
4445&3335&2225&1115&0005&0006&0007&0008&0009&0000
Input: 1234
0124 0013 0002 0001 0000
Ich habe versucht, dies auf http://bicycles.stackexchange.com zu posten , aber es hat ihnen nicht gefallen ...
Haftungsausschluss: Erstes Golfen, also alles was kaputt ist / fehlende Informationen lass es mich wissen! Außerdem habe ich alle Beispiele von Hand gemacht, sodass es Lösungen geben kann, die weniger Bewegungen erfordern!
BEARBEITEN: Für Antworten mit mehreren Lösungspfaden und gleicher Anzahl von Bewegungen (praktisch alle) gibt es keine bevorzugte Lösung.
Antworten:
Matlab,
412327 BytesGolfen (Danke an @AndrasDeak fürs Golfen
s
!):Dieser Code verwendet eine dynamische Programmierung, um den kürzesten "Pfad" von der angegebenen Nummer zu finden
0000
und nur die möglichen Schritte zu verwenden. Die Herausforderung ist im Grunde genommen ein Problem mit dem kürzesten Weg (alternativ könnten Sie die Schritte vielleicht als eine kommutative Gruppe betrachten.), Aber die Schwierigkeit bestand darin, eine effiziente Implementierung zu finden. Die Grundstruktur besteht aus zwei 10000-Elemente-Arrays, eines zum Speichern der Anzahl der Schritte, um zu diesem Index zu gelangen, das andere zum Speichern eines Zeigers auf den vorherigen 'Knoten' in unserem Diagramm. Es berechnet gleichzeitig die 'Pfade' zu allen anderen möglichen Zahlen.Beispiele:
Vollständiger Code (einschließlich einiger Kommentare):
quelle
6444
gibt Ihr Code 6444 7554 8664 9774 0884 0994 0004 0003 0002 0001 0000, während ich die Antwort als 6444 6333 6222 6111 6000 7000 8000 9000 0000 finde. Meine Antwort ist 8 Schritte, Ihre ist 10. Ich kann die nicht sehen Ausgabe, und es scheint, dort in der Golf- und in der ungolfed Version zu sein. Dies ist in Ihrer letzten Bearbeitung behoben.s
der letzten Reihe sollte sein[0,1,1,1]
. Dann erhalten Sie auch eine 8-Stufen-Lösung! Es tut mir leid für die Unannehmlichkeiten =)Batch - 288 Bytes
Selbst wenn Sie sagten, dass sie aufeinanderfolgend sein müssen (die Ringe), gehe ich logischerweise (gemäß dem Beispiel) davon aus, dass ich die mittlere von1234
bis überspringen kann0224
.Dies ist meine Batch-Lösung: 236 Bytes.Edit: korrigierte Lösung
Die neue Lösung (gemäß den zugrunde liegenden Kommentaren behoben) ist 288 Byte schwer.
quelle
1234
,0224
ist keine einzige Bewegung. Die Idee ist, dass ich mit nur zwei Fingern bis zu drei aufeinanderfolgende Ringe mit einem Griff greifen kann.Haskell - 310 Bytes
Dies funktioniert, indem wiederholt eine neue Liste von Kombinationen erstellt wird, indem jede mögliche Runde auf jede bereits erreichte Kombination angewendet wird, bis eine von ihnen die richtige Kombination ist. Duplikate werden bei jeder Iteration aus der Liste entfernt, damit die Speichernutzung nicht exponentiell zunimmt.
Als Brute-Force-Lösung ist dies sehr ineffizient und kann mehrere Minuten dauern.
Ich habe nicht viel Erfahrung mit Haskell, also könnte man wahrscheinlich etwas besser machen.
quelle