Aby dowiedzieć się, czym jest wieża w Hanoi, skorzystaj z Google lub zajrzyj na stronę Wikipedii .

Twój kod powinien być w stanie zrobić 2 rzeczy, a są to:

• Zaakceptuj dane wprowadzone przez użytkownika, które określają liczbę dysków w punkcie początkowym wieży Hanoi
• Twórz dane wyjściowe w wybrany przez siebie sposób (o ile jest to logiczne), aby pokazać rozwiązanie łamigłówki typu tower.

Przykład logicznego wyjścia może wyglądać następująco (przy użyciu startu na 4 dyski):

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

Lreprezentuje lewy kołek, Creprezentuje środkowy kołek i Rreprezentuje prawy kołek, a liczby oznaczają, jak daleko przesunąć dysk na tym kołku i w jakim kierunku. Liczby dodatnie oznaczają liczbę kołków przesuwających się w kierunku skrajnie prawego kołka (ponieważ dyski zaczynają się od skrajnego lewego kołka).

Te zasady Tower of Hanoi są proste:

• Jednocześnie można przenosić tylko jeden dysk.
• Każdy ruch polega na wzięciu górnego dysku z jednego z kołków i zsunięciu go na inny kołek, na inne dyski, które mogą już znajdować się na tym kołku.
• Żaden dysk nie może być umieszczony na mniejszym dysku.

Dyski zaczynają się od skrajnie lewego kołka, największego na dole, oczywiście najmniejszego na górze.

Łuska , 5 bajtów

↑≠⁰İr

Wypróbuj online!
Każde nwyjście reprezentuje przenoszenie dysku nna następny dostępny kołek (cykliczne owijanie).

Wyjaśnienie

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

Python, 76 znaków

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)

Na przykład dla N = 3 zwraca:

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

Perl - 54 znaki

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

Uruchom perl -M5.010i wprowadź liczbę dysków na standardowym wejściu.

Format wyjściowy:

Jedna linia na ruch, pierwsza cyfra to peg, druga cyfra to peg (od 0)

Przykład:

02 -- move from peg 0 to peg 2
01
21
02
10
12
02

GolfScript ( 31 25 24 znaków)

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

Z podziękowaniami dla Ilmari Karonen za wskazanie, że moje oryginalne trs / permutacje można skrócić o 6 znaków. Rozkładając je jako produkt dwóch permutacji, udało mi się uratować jeszcze jedną.

Zauważ, że biorąc pod uwagę 3%wzrost długości o jeden znak:

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

Niektóre osoby mają naprawdę skomplikowane formaty wyjściowe. To powoduje, że kołek został przeniesiony z (ponumerowane 0, 1, 2) i kołek został przeniesiony do. Specyfikacja nie mówi, do którego kołka się przenieść, więc przechodzi do kołka 1.

Na przykład

$ golfscript hanoi.gs <<<"3"
01021201202101

Perl, 75 79 znaków

Całkowite kradzież formatu wyjściowego Keitha Randalla:

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

Wywołaj -M5.010za pomocą dla say.

(Myślę, że można to poprawić, jeśli można znaleźć sposób wykorzystania wartości zwracanej przez funkcję zamiast po prostu ją tłumić.)

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);

funkcja połączenia f(n,s,t)z:

• n liczba dysków
• punkt początkowy
• t punkt bramkowy

Bash (64 znaki)

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

Publikowanie tego, mimo że jest ponad dwa razy dłuższe niż w GolfScript, ponieważ lubię to, taby służyć jako echo $s.

Scala, 92 88 87 znaków

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)

Format wyjściowy

Powiedz liczbę dysków = 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

C, 98 92 87 znaków

Implementuje najbardziej trywialny algorytm.
Dane wyjściowe mają postać, w ab ab abktórej każda para oznacza „przenieś górną płytę z kołka a na kołek b”.
EDYCJA : Ruchy są teraz zakodowane w postaci szesnastkowej - 0x12 oznacza przejście z kołka 1 do kołka 2. Zapisano niektóre znaki.
EDYCJA : Czyta liczbę ze standardowego wejścia zamiast parametru. Krótszy
Przykład:
% 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);}

Galaretka , 5 bajtów

2*Ṗọ2

Wypróbuj online!

0przenieś najmniejszy dysk o jedno miejsce w prawo (w razie potrzeby wracając do początku)
1przenieś drugi najmniejszy dysk do jedynej legalnej kolumny
2przenieś trzeci najmniejszy dysk do jedynej legalnej kolumny
itp.

Algorytm

Rekurencyjnie widzimy rozwiązanie problemu Towers of Hanoi; przenieść stos wielkości n z A do B , przenoszenie stosu wielkości n -1 od A do C , to dysk o rozmiarze n z A do B , a następnie przemieszczać stos wielkości n -1 od B do C . Spowoduje to utworzenie wzoru o następującej formie (w formacie wyjściowym używanym przez ten program):

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

Możemy zauważyć, że ta sekwencja to A007814 w OEIS. Inną możliwą definicją sekwencji jest „ k- ty (oparty na 1) elementem sekwencji jest liczba zer na końcu liczby k, gdy jest zapisana binarnie”. I właśnie to oblicza program.

Wyjaśnienie

Najpierw obliczamy liczbę ruchów w rozwiązaniu, 2 ⁿ -1. Okazuje się, że najkrótsze jest obliczenie jednego dodatkowego ruchu i odrzucenie go później, więc jest to 2*np. 2 do siły czegoś. (Jedyne dane, które do tej pory przyjęliśmy, to argument wiersza poleceń, więc domyślnie jest używany)

Następnie używamy wbudowanego Jelly do obliczania liczby zer na końcu liczby w bazie b ; To . Ponieważ obliczamy binarnie, tak jest . Wszystko, co musimy zrobić, to zastosować to wbudowane do liczb od 1 do 2 ⁿ -1 włącznie.ọbọ2

Istnieją dwa proste sposoby iteracyjne nad zakresu liczb w galarecie, €a R, a moje wcześniejsze próby tego problemu stosować jedną z nich. Jednak w tym przypadku możliwe jest nieco krótsze: Ṗpodanie liczby jako wartości wejściowej pozwoli ci wykonać iterację, która zatrzymuje jeden element na krótko (ogólnie rzecz biorąc, Ṗjest wbudowanym narzędziem do przetwarzania wszystkich elementów oprócz jednego). To jest dokładnie to, co chcemy w tym przypadku (bo 2*generuje zbyt wielu elments), więc używając go do linku 2*i ọ2do 2*Ṗọ2daje nam rozwiązanie 5-bajtowy problemu.

Awk, 72 znaki

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)

Format wyjściowy jest taki sam jak w przypadku Keitha Randalla .

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

Skrypt Bash, 100 96 znaków

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

Format wyjściowy jest taki sam jak w przypadku Keitha Randalla .

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

Edit : Saved 4 znaków przez peter komentarzu „s.

J, 23 bajty

rozwiązanie liczb binarnych

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

To rozwiązanie wykorzystuje metodę zliczania binarnego opisaną w tym filmie .

Oznacza to, że generuję cyfry binarne od 1do 2^n, a następnie biorę przyrostki o długości 2 i porównuję każdy bit z odpowiednim bitem z poprzedniej liczby i sprawdzam, czy są one nierówne. Liczba nierównych bitów stanowi wynik tego ruchu.

Dane wyjściowe, np. Dla 3 dysków, gdzie najmniejszy dysk jest oznaczony jako 1:

1 2 1 3 1 2 1

1 oznacza „przenieś najmniejszy dysk o jeden kołek w prawo, w razie potrzeby zapętlając z powrotem do pierwszego kołka”

n, dla wszystkich innych n, oznacza „przenieś dysk ndo legalnego kołka” (zawsze będzie dokładnie jeden)

Wypróbuj online!

rozwiązanie rekurencyjne

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

Taki sam wynik jak w powyższym rozwiązaniu, ale logika tutaj sprawia, że ​​problem rekurencyjny jest wyraźniejszy.

Wizualizacja go jako drzewa podkreśla również ten punkt:

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

Wypróbuj online!

APL (Dyalog Classic) , 19 bajtów

3|(-⍪0 1⍪2∘-)⍣⎕,⍨⍪⍬

Wypróbuj online!

wyjście to macierz 2-kolumnowa liczb całkowitych w {0,1,2} - od kołka do kołka

K (ngn / k) , 23 bajty

{3!x{-x,(,0 2),1+x}/()}

Wypróbuj online!

R , 73 bajty

Umieszczenie R na mapie. Zainspirowany [odpowiedzią Keitha Randalla] [1] z uproszczonym wprowadzaniem, drukuj tylko koniec i uruchom peg, aby zapisać 2 bajty. Również kołki 0-indeksowane.

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)}}

Wypróbuj online!

JavaScript (ES6), 45b

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

np. wywołanie h(4, 'A', 'B', 'C')(przenieś 4 dyski z kołka A na kołek C za pomocą kołka pomocniczego B)

zwraca 'ABACBCABCACBABACBCBACABCABACBC'(przenieś płytę z kołka A na kołek B, przenieś płytę ze kołka A na kołek C, przenieś płytę ze kołka B na kołek C itp.)