Dies wurde durch ein mathematisches Problem inspiriert, das ich irgendwo im Internet gesehen habe, aber ich erinnere mich nicht, wo (UPDATE: Das ursprüngliche Problem wurde auf den unterditierten mathematischen Rätseln mit einem Beweis gefunden, sofern es möglich ist, siehe auch diesen Math SE-Beitrag ), gefragt ein Beweis, ob das folgende Verfahren für ein beliebiges ganzzahliges Paar möglich ist (soweit ich mich erinnere, war es für ein bestimmtes Paar möglich):
Wenn ein Paar von ganzen Zahlen j und k gegeben ist, verdoppeln Sie eine von ihnen und addieren Sie eine zu der anderen, was zu einem Paar neuer ganzer Zahlen führt, dh (j, k) -> (j + 1, k * 2) oder (j * 2, k + 1). Wiederholen Sie diesen Vorgang dann mit diesen ganzen Zahlen, mit dem Ziel, dass das ganze Zahlenpaar gleich ist.
Diese angegebenen Beispiele sind nicht unbedingt optimal, zeigen jedoch, wie dieser Prozess für alle positiven, negativen oder Nullen von ganzen Zahlen durchgeführt werden kann:
(2, 5) -> (3, 10) -> (6, 11) -> (12, 12)
(5, 6) -> (6, 12) -> (7, 24) -> (14, 25) -> (28, 26) -> (56, 27) -> (112, 28) -> (113, 56) -> (226, 57) -> (227, 114) -> (228, 228)
(0, 2) -> (1, 4) -> (2, 5) -> (3, 10) -> (6, 11) -> (12, 12)
(-4, 0) -> (-3, 0) -> (-2, 0) -> (-1, 0) -> (0, 0)
(3, -1) -> (6, 0) -> (12, 1) -> (13, 2) -> (14, 4) -> (15, 8) -> (16, 16)
(-4, -3) -> (-8, -2) -> (-16, -1) -> (-32, 0) -> (-31, 0) -> ... -> (0, 0)
Herausforderung
Erstellen Sie ein Programm mit zwei Ganzzahlen, und geben Sie die Liste der Schritte aus, die erforderlich sind, um diese Ganzzahlen durch wiederholtes Inkrementieren und Verdoppeln der beiden Zahlen gleich zu machen
Spezifikationen
- Die Lösung muss nicht optimal sein, sondern muss für jedes beliebige Paar in einer endlichen Anzahl von Schritten gelöst werden
Die Eingabe muss aus zwei ganzen Zahlen bestehen
Die Ausgabe kann jede sinnvolle Ausgabe sein, die die resultierenden ganzen Zahlen jedes Schritts eindeutig kennzeichnet, zum Beispiel:
- eine Zeichenfolge mit zwei unterschiedlichen Trennzeichen (ein beliebiges Symbol, ein Leerzeichen usw.), eines für jede Ganzzahl in einem Paar und eines für jedes Paar
- zB Eingabe j, k: 2, 5 -> Ausgabe: 3,10; 6,11; 12,12
- eine Liste von Listen mit ganzen Zahlen
- zB Eingabe j, k: 2, 5 -> Ausgabe: [[3, 10], [6, 11], [12, 12]]
- eine Zeichenfolge mit zwei unterschiedlichen Trennzeichen (ein beliebiges Symbol, ein Leerzeichen usw.), eines für jede Ganzzahl in einem Paar und eines für jedes Paar
Wenn es sich bei der Eingabe um ein Paar gleicher Zahlen handelt, können Sie alles ausgeben, solange es mit anderen nichttrivialen Antworten übereinstimmt
- zum Beispiel
- Wenn Eingang [2, 5] Ausgang [[3, 10], [6, 11], [12, 12]] hat, der das Eingangspaar nicht enthält, sollte Eingang [4, 4] nichts ausgeben.
- Wenn Eingang [2, 5] Ausgang [[2, 5], [3, 10], [6, 11], [12, 12]] hat, der das Eingangspaar enthält, sollte Eingang [4, 4] Ausgabe [[4, 4]].
- zum Beispiel
Es gelten Standard-E / A-Methoden, und Standard-Regelungslücken sind verboten
Dies ist Codegolf, also gewinnt die kürzeste Antwort in Bytes
quelle
[(12,12),(6,11),(3,10),(2,5)]
zur Eingabe(2,5)
?Antworten:
JavaScript (ES6),
1119083 ByteProbieren Sie es online!
Kommentiert
quelle
Haskell,
7069 BytesProbieren Sie es online!
Ein einfaches BFS. Verfolgt die Schritte in einer Liste von Paaren.
quelle
Python 3 ,
907472 Bytes-2 Bytes dank Dennis .
Probieren Sie es online!
Übernimmt die Eingabe als Singleton-Liste .
Ungolfed
quelle
Pyth, 41 Bytes
Probieren Sie es hier aus
Erläuterung
Dies ist eine ziemlich unkomplizierte Breitensuche. Halten Sie eine Reihe möglicher Sequenzen (
J
), und bis wir ein passendes Paar erhalten, nehmen Sie die nächste Sequenz, halten Sie sich an alle möglichen Züge und stellen Sie sie an das Ende der Reihe.Der Kürze halber definieren wir eine Funktion
y
(unter Verwendung des Lambda-AusdrucksL
), um eine der Bewegungen auszuführen, und wenden sie sowohl vorwärts als auch rückwärts an.quelle
Gelee , 20 Bytes
Probieren Sie es online!
quelle
[[2,5]]
)05AB1E ,
252220 BytesNimmt eine doppelt verschachtelte Liste als Eingabe und gibt eine gezackte Liste mit jedem Schritt in einer Verschachtelungstiefe aus.
Probieren Sie es online!
Erläuterung
quelle
Netzhaut , 72 Bytes
Probieren Sie es online! Nur zwei Testfälle aufgrund der Einschränkungen der unären Arithmetik. Erläuterung:
In Unary konvertieren.
Während die Eingabe kein Paar identischer Zahlen enthält ...
... finde das letzte Paar in jeder Zeile ...
... und die Zeile in zwei Zeilen umwandeln, wobei eine mit der ersten Nummer inkrementiert und die zweite mit der doppelten und die andere mit der ersten Nummer inkrementiert und die zweite mit der doppelten Nummer inkrementiert wird.
Halten Sie die Linie mit dem passenden Paar.
Zurück in Dezimalzahl konvertieren.
89Vorzeichenlose 88-Byte-Dezimal-Arithmetikversion (funktioniert auch mit 0):Probieren Sie es online!
quelle
MATL , 24 Bytes
Die Laufzeit ist zufällig, aber mit Wahrscheinlichkeit 1 endlich.
Der Code ist sehr ineffizient. Bei Eingaben, die mehr als 4 oder 5 Schritte erfordern, besteht eine hohe Wahrscheinlichkeit, dass der Online-Interpreter ein Zeitlimit überschreitet.
Probieren Sie es online!
Erläuterung
quelle
Stax ,
2926 BytesFühren Sie es aus und debuggen Sie es
Es ist eine breite erste Suche. Es scheint ziemlich schnell.
Es wird ein doppelt in ein Array eingeschlossenes Paar von ganzen Zahlen benötigt. Die Ausgabe ist eine durch Leerzeichen getrennte Liste von Werten. Jeweils zwei Werte stehen für ein Paar auf dem Weg zur Lösung.
quelle
Haskell , 95 Bytes
Probieren Sie es online! Ausgänge in umgekehrter Reihenfolge, zB
h(2,5)
Erträge[(12,12),(6,11),(3,10),(2,5)]
.quelle
Rot , 142 Bytes
Nimmt die Eingabe als doppelt verschachtelten Block des Ganzzahlpaares im Red -Format
(2, 5)
->2x5
Gibt das Ergebnis beispielsweise als Liste mit roten Paaren zurück
2x5 3x10 6x11 12x12
. Beinhaltet das erste Paar.Probieren Sie es online!
Strikte Eingabe:
Die Eingabe besteht beispielsweise aus zwei Zahlen
2 5
Rot , 214 Bytes
Probieren Sie es online!
Erläuterung:
quelle