Turm des Hanoi-Lösers

10

Um zu erfahren, was der Turm von Hanoi ist, googeln Sie ihn oder schauen Sie auf der Wikipedia- Seite nach.

Ihr Code sollte in der Lage sein, zwei Dinge zu tun, und diese sind die folgenden:

  • Akzeptieren Sie Benutzereingaben, die die Anzahl der Discs am Startpunkt des Hanoi-Turms angeben
  • Erstellen Sie eine Ausgabe auf eine Weise Ihrer Wahl (sofern dies irgendwie logisch ist), um die Lösung für das Turmrätsel zu zeigen.

Ein Beispiel für eine logische Ausgabe wäre das Folgende (unter Verwendung eines 4-Disc-Starts):

L1L2C1L1R-2R-1L1L2C1C-1R-2C1L1L2C1

Lstellt den linken Stift dar, Cstellt den mittleren Stift dar und Rstellt den rechten Stift dar. Die Zahlen geben an, wie weit und in welche Richtung die Scheibe auf diesem Stift bewegt werden soll. Positive Zahlen geben die Anzahl der Stifte an, die sich in Richtung des am weitesten rechts liegenden Stifts bewegen (da die Festplatten am am weitesten links liegenden Stift beginnen).

Die Regeln zum Turm von Hanoi sind einfach:

  • Es kann jeweils nur eine Festplatte verschoben werden.
  • Jede Bewegung besteht darin, die obere Scheibe von einem der Stifte zu nehmen und auf einen anderen Stift zu schieben, über die anderen Scheiben, die möglicherweise bereits auf diesem Stift vorhanden sind.
  • Es darf keine Festplatte auf eine kleinere Festplatte gelegt werden.

Die Scheiben beginnen am linken Stift, am größten unten, am kleinsten oben.

Carter Pape
quelle
Müssen wir beliebig große Türme lösen, oder gibt es eine Grenze, die wir annehmen können, wie 10, 100, 1k, 1M-Discs?
Benutzer unbekannt
@userunknown Wenn ich Sie wäre, würde ich mir nicht allzu viele Sorgen um außergewöhnlich große Zahlen machen, aber ich werde sagen, dass die höchste Anzahl von Festplatten, die Ihr Programm verarbeiten kann, nur durch die Speicherkapazität des Computers oder dessen Aufrufstapellimit begrenzt werden sollte ( Ich denke, das Gleiche ist ein ziemlich allgemeiner Begriff. Lassen Sie sich jedoch beim Einreichen Ihres Codes nicht von willkürlich hohen Zahlen erschrecken. Wenn Ihre Lösung kreativ ist, aber nur so viele Festplatten verarbeiten kann, würde ich Ihnen trotzdem Anerkennung zollen.
Carter Pape
Nun, meine Idee war ein ziemlich ineffizienter Lösungsalgorithmus, und wenn die Grenze darin besteht, ob das Programm damit umgehen kann, wäre es in Ordnung. Aber ich habe mir die Lösungen bisher angesehen und festgestellt, dass ich in einer ganz anderen Liga spielen würde.
Benutzer unbekannt

Antworten:

2

Schale , 5 Bytes

↑≠⁰İr

Probieren Sie es online aus!
Jedes nin der Ausgabe repräsentiert das Verschieben der Festplatte nzum nächsten verfügbaren Stift (zyklisches Umwickeln).

Erläuterung

   İr   The ruler sequence [0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, ...]
↑       Take while...
 ≠⁰     ... not equal to the input.

quelle
7

Python, 76 Zeichen

def S(n,a,b):
 if n:S(n-1,a,6-a-b);print n,a,b;S(n-1,6-a-b,b)
S(input(),1,3)

Für N = 3 wird beispielsweise Folgendes zurückgegeben:

1 1 3  (move disk 1 from peg 1 to peg 3)
2 1 2  (move disk 2 from peg 1 to peg 2)
1 3 2  (move disk 1 from peg 3 to peg 2)
3 1 3  ...
1 2 1
2 2 3
1 1 3
Keith Randall
quelle
Ich weiß, dass ich etwas spät dran
bin,
6

Perl - 54 Zeichen

for(2..1<<<>){$_--;$x=$_&-$_;say(($_-$x)%3,($_+$x)%3)}

Führen Sie mit aus perl -M5.010und geben Sie die Anzahl der Discs auf stdin ein.

Ausgabeformat:

Eine Zeile pro Zug, die erste Ziffer ist vom Stift, die zweite Ziffer ist vom Stift (ab 0)

Beispiel:

02 -- move from peg 0 to peg 2
01
21
02
10
12
02
Geoff Reedy
quelle
Speichern Sie 5 Zeichen, indem Sie die Klammern entfernen. $x=--$_&-$_,say(($_-$x)%3,($_+$x)%3)for 2..1<<<>
Marinus
5

GolfScript ( 31 25 24 Zeichen)

])~{{~3%}%.{)3%}%2,@++}*

Vielen Dank an Ilmari Karonen für den Hinweis, dass meine ursprünglichen trS / Permutationen um 6 Zeichen verkürzt werden könnten. Indem ich sie als Produkt von zwei Permutationen zerlegte, gelang es mir, eine weitere zu speichern.

Beachten Sie, dass das Ausklammern die 3%Länge um ein Zeichen erhöht:

])~{{~}%.{)}%2,@++}*{3%}%

Einige Leute haben wirklich komplizierte Ausgabeformate. Dies gibt den Stift aus, der von (nummeriert 0, 1, 2) bewegt wurde, und den Stift, zu dem bewegt wurde. Die Spezifikation gibt nicht an, zu welchem ​​Stift bewegt werden soll, daher bewegt sie sich zu Stift 1.

Z.B

$ golfscript hanoi.gs <<<"3"
01021201202101
Peter Taylor
quelle
Zweifellos ist die gleiche Logik in sed noch kürzer, aber meine sed-Fähigkeiten sind dem nicht gewachsen.
Peter Taylor
1
Sie können es in 25 Zeichen tun:])~{.{3^3%}%2,@{2\-}%++}*
Ilmari Karonen
3

Perl, 75 79 Zeichen

Keith Randalls Ausgabeformat total stehlen:

sub h{my($n,$p,$q)=@_;h($n,$p^$q^h($n,$p,$p^$q),$q*say"@_")if$n--}h pop,1,3

Rufen Sie mit -M5.010für die say.

(Ich denke, dies kann verbessert werden, wenn Sie einen Weg finden, den Rückgabewert der Funktion zu nutzen, anstatt ihn nur zu unterdrücken.)

Brot-Box
quelle
[Aktie "nur verwenden say" Empfehlung]
JB
Okay - aber müsste ich nicht die Kosten für die Aktivierung von 5.10-Funktionen in meine Zeichenanzahl einbeziehen?
Brotkasten
1
Sie würden - aber es ist kostenlos. Notieren Sie sich einfach, wie Sie Ihr Programm aufrufen, damit Personen, die die Perl-Aufrufspezifikationen nicht fließend beherrschen, es trotzdem ausprobieren können.
JB
Danke für den Link; Ich habe früher nach so etwas gesucht.
Brotkasten
3

SML, 63

fun f(0,_,_)=[]|f(n,s,t)=f(n-1,s,6-s-t)@[n,s,t]@f(n-1,6-s-t,t);

Aufruffunktion f(n,s,t)mit:

  • n Anzahl der Festplatten
  • s Ausgangspunkt
  • t Zielpunkt
irgendwann
quelle
2

Bash (64 Zeichen)

t(){ tr 2$1 $12 <<<$s;};for((i=$1;i--;))do s=`t 1`01`t 0`;done;t

Posting dieses, obwohl es mehr als doppelt so lang ist wie das GolfScript, weil ich die Wiederverwendung von tals mag echo $s.

Peter Taylor
quelle
2

Scala, 92 88 87 Zeichen

def?(n:Int,a:Int,b:Int){if(n>0){?(n-1,a,a^b)
print(n,a,b);?(n-1,a^b,b)}};?(readInt,1,3)

Ausgabeformat

Sagen Sie dann die Anzahl der Festplatten = 3,

(1,1,3)(2,1,2)(1,3,2)(3,1,3)(1,2,1)(2,2,3)(1,1,3) (disk number,from peg, to peg)
                                                   \---------------------------/       
                                                            Move 1              ... Move n
Prinz John Wesley
quelle
Gute Verwendung von xor.
Peter Taylor
2

C 98 92 87 Zeichen

Implementiert den trivialsten Algorithmus.
Die Ausgabe erfolgt in der Form, ab ab abin der jedes Paar "die obere Scheibe von Stift a nach Stift b bewegen" bedeutet.
BEARBEITEN : Bewegungen werden jetzt hexadezimal codiert - 0x12 bedeutet, dass von Stift 1 zu Stift 2 gewechselt wird. Einige Zeichen wurden gespeichert.
BEARBEITEN : Liest die Nummer von stdin und nicht von Parametern. Kürzer.
Beispiel:
% echo 3 | ./hanoi
13 12 32 13 21 23 13

n;
h(d){n--&&h(d^d%16*16,printf("%02x ",d,h(d^d/16))),n++;}
main(){scanf("%d",&n);h(19);}
ugoren
quelle
Kann jemand die Syntax des Funktionskörpers h () erklären - insbesondere die beiden offensichtlichen Argumente in seinem rekursiven Aufruf (d ^ d% 16 * 16 und printf (...)) und die letzte Operation, die anscheinend am Ende hängt. Nach meinem Wissen weist diese Funktion zwei Syntaxfehler auf, aber ich weiß bereits, dass sie (nach Einbeziehung von stdio) erstellt und korrekt ausgeführt wird.
Griffin
1
Es ist möglich, mehr Parameter zu übergeben, als die Funktion wünscht. Ihre Werte gehen nirgendwo hin. h(x,printf(...))ist einfach eine Möglichkeit anzurufen, printfbevor haufgerufen wird. Der letzte n++wird nach der inneren hRückkehr gemacht. Es wird verwendet, um die Initiale rückgängig zu machen n--.
Ugoren
Danke, das macht Sinn (der Zweck von n ++ war offensichtlich). Warum gibt es kein Semikolon vor n ++ anstelle eines Kommas oder macht es einen Unterschied?
Griffin
@Griffin, eigentlich ;wäre das hier gleich. ,ist oft nützlich (zB if(x)a,b;ersetzt if(x){a;b;}), hat hier aber keinen Vorteil.
Ugoren
2

Gelee , 5 Bytes

2*Ṗọ2

Probieren Sie es online aus!

0Verschieben Sie die kleinste Festplatte um ein Leerzeichen nach rechts (ggf. zurück zum Start).
1Verschieben Sie die zweitkleinste Festplatte in die einzige andere zulässige Spalte.
2Verschieben Sie die drittkleinste Festplatte in die einzige andere zulässige Spalte
usw.

Algorithmus

Wir können die Lösung des Towers of Hanoi-Problems rekursiv sehen; einen Stapel von Größe zu bewegen n von A zu B , zu bewegen , um einen Stapel von Größe n -1 von A bis C , so ist die Scheibe der Größe n von A nach B , dann zu bewegen , um einen Stapel von Größe n -1 von B zu C . Dies erzeugt ein Muster der folgenden Form (in dem von diesem Programm verwendeten Ausgabeformat):

0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2 …

Wir können beobachten, dass diese Sequenz A007814 auf dem OEIS ist. Eine andere mögliche Definition der Sequenz ist "das k- te (1-basierte) Element der Sequenz ist die Anzahl der Nullen am Ende der Zahl k, wenn sie binär geschrieben ist". Und genau das berechnet das Programm hier.

Erläuterung

Zuerst berechnen wir die Anzahl der Züge in der Lösung, 2 n -1. Es stellt sich als am kürzesten heraus, tatsächlich einen zusätzlichen Zug zu berechnen und ihn später zu verwerfen. Dies ist 2*also 2 nach der Kraft von etwas. (Die einzige Eingabe, die wir bisher vorgenommen haben, ist das Befehlszeilenargument, das standardmäßig verwendet wird.)

Als nächstes verwenden wir Jellys Builtin, um die Anzahl der Nullen am Ende einer Zahl in Basis b zu berechnen . das ist . Da wir binär rechnen, ist es . Alles was wir tun müssen, ist dieses eingebaute auf die Zahlen von 1 bis einschließlich 2 n -1 anzuwenden .bọ2

Es gibt zwei einfache Möglichkeiten , um Iterierte über einen Bereich von Zahlen in Jelly, und R, und meine früheren Versuche, dieses Problem verwendet eine davon. In diesem Fall ist es jedoch möglich, etwas kürzer zu werden: Wenn Sie eine Zahl als Eingabe eingeben , können Sie eine Iteration ausführen, bei der ein Element kurz gehalten wird (im Allgemeinen wird ein Element verwendet, mit dem alle Elemente bis auf ein Element verarbeitet werden). Das ist genau das, was wir in diesem Fall wollen (weil 2*man zu viele elments erzeugt), so dass es zu Link mit 2*und ọ2in 2*Ṗọ2gibt uns eine 5-Byte - Lösung für das Problem.


quelle
1

Awk, 72 Zeichen

function t(n,a,b){if(n){t(n-1,a,a^b);print n,a,b;t(n-1,a^b,b)}}t($0,1,3)

Das Ausgabeformat ist das gleiche wie das von Keith Randall .

awk -f tower.awk <<< "3"    
1 1 1
2 1 1
1 1 1
3 1 3
1 1 1
2 1 3
1 1 3
Prinz John Wesley
quelle
1

Bash-Skript, 100 96 Zeichen

t(){ [[ $1<1 ]] && return
t $(($1-1)) $2 $(($2^$3))
echo $@
t $(($1-1)) $(($2^$3)) $3
}
t $1 1 3

Das Ausgabeformat ist das gleiche wie das von Keith Randall .

1 1 3
2 1 2
1 3 2
3 1 3
1 2 1
2 2 3
1 1 3

Bearbeiten : 4 Zeichen durch Peters Kommentar gespeichert .

Prinz John Wesley
quelle
1
Sie können die Leerzeichen hinzufügen und ein paar Zeichen speichern, indem Sie Echo$@
Peter Taylor
@ PeterTaylor: Guter Punkt. lass es mich aktualisieren.
Prinz John Wesley
1

J, 23 Bytes

Lösung für Binärzahlen

2&(+/@:~:/\)@#:@i.@^~&2

Diese Lösung verwendet die in diesem Video beschriebene binäre Zählmethode .

Das heißt, ich generiere die Binärziffern von 1bis zu 2^n, nehme dann Infixe der Länge 2 und vergleiche jedes Bit mit dem entsprechenden Bit der vorherigen Zahl und überprüfe, ob sie ungleich sind. Die Anzahl der ungleichen Bits ist die Ausgabe für diese Bewegung.

Ausgabe, z. B. für 3 Festplatten, wobei die kleinste Festplatte mit 1 gekennzeichnet ist:

1 2 1 3 1 2 1

1 bedeutet "Bewegen Sie die kleinste Scheibe um einen Stift nach rechts und kehren Sie bei Bedarf zum ersten Stift zurück"

nbedeutet für alle anderen n"Festplatte nauf einen legalen Stift verschieben" (es wird immer genau einen geben)

Probieren Sie es online aus!

rekursive Lösung

((],[,])$:@<:)`]@.(1=])

Gleiche Ausgabe wie die obige Lösung, aber die Logik hier macht die rekursive Natur des Problems klarer.

Die Visualisierung als Baum unterstreicht auch diesen Punkt:

              4
             / \
            /   \
           /     \
          /       \
         /         \
        /           \
       /             \
      3               3      
     / \             / \    
    /   \           /   \
   /     \         /     \ 
  2       2       2       2  
 / \     / \     / \     / \
1   1   1   1   1   1   1   1

Probieren Sie es online aus!

Jona
quelle
1
Die Zufälligkeit, Ihre Antwort über 5 Jahre nach der ursprünglichen Frage innerhalb derselben Stunde einzureichen, in der ich zurückgekehrt bin, um die Antworten auf diese Frage zu überprüfen, die ich vor über 5 Jahren eingereicht habe… wow. +1
Carter Pape
0

R , 73 Bytes

R auf die Karte setzen. Inspiriert von [Keith Randalls Antwort] [1] mit vereinfachter Eingabe, drucken Sie nur den End- und Startstift, um 2 Bytes zu sparen. Auch 0-indizierte Stifte.

f=function(n,s=0,e=2){if(n){f(n-1,s,3-s-e)
print(c(s,e))
f(n-1,3-s-e,e)}}

Probieren Sie es online aus!

JayCe
quelle
0

JavaScript (ES6), 45b

h=(n,f,a,t)=>n?h(--n,f,t,a)+f+t+h(n,a,f,t):''

zB anrufen h(4, 'A', 'B', 'C')(4 Discs mit dem Hilfsstift B von Stift A auf Stift C verschieben)

kehrt zurück 'ABACBCABCACBABACBCBACABCABACBC'(verschieben Sie eine Disc von Stift A zu Stift B, verschieben Sie eine Disc von Stift A zu Stift C, verschieben Sie eine Disc von Stift B zu Stift C usw.)

Targumon
quelle
1
Nett. Ich frage mich, ob die Parameter f, a, t Standardeinstellungen in der Funktionsdefinition enthalten sollten. Andernfalls könnten Einsendungen beliebige Daten in zusätzlichen Argumenten enthalten. Ich bin allerdings ein Neuling, daher sollte jemand mit mehr Erfahrung beraten.
John Rees