Menara pemecah hanoi

10

Untuk referensi tentang apa menara Hanoi itu, Google atau lihat di halaman Wikipedia .

Kode Anda harus dapat melakukan 2 hal, dan itu adalah sebagai berikut:

  • Terima input pengguna yang menentukan jumlah disk di titik awal menara Hanoi
  • Buat output dengan cara yang Anda pilih (asalkan logis) untuk menunjukkan solusi pada puzzle menara.

Contoh output logis adalah sebagai berikut (menggunakan awal 4 disk):

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

Lmewakili pasak kiri, Cmewakili pasak tengah dan Rmewakili pasak kanan dan angka adalah seberapa jauh untuk memindahkan disk pada pasak itu dan ke arah mana. Angka positif menunjukkan jumlah pasak yang bergerak menuju pasak paling kanan (karena cakram mulai pada pasak paling kiri).

The aturan untuk menara Hanoi sederhana:

  • Hanya satu disk yang dapat dipindahkan sekaligus.
  • Setiap gerakan terdiri dari mengambil disk atas dari salah satu pasak dan menggesernya ke pasak lain, di atas disk lain yang mungkin sudah ada pada pasak itu.
  • Disk tidak dapat ditempatkan di atas disk yang lebih kecil.

Disk mulai pada pasak paling kiri, terbesar di bawah, terkecil di atas, secara alami.

Pape Carter
sumber
Apakah kita perlu memecahkan menara besar yang sewenang-wenang, atau adakah batasan yang dapat kita asumsikan, seperti cakram 10, 100, 1k, 1M?
pengguna tidak diketahui
@ penggunaunknown jika saya jadi Anda, saya tidak akan terlalu khawatir tentang jumlah yang luar biasa besar, tetapi saya akan mengatakan bahwa jumlah disk tertinggi yang dapat ditangani oleh program Anda hanya akan dibatasi oleh kapasitas memori komputer atau batas tumpukan panggilannya ( jenis hal yang sama saya kira, karena memori adalah istilah yang cukup umum). Namun, jangan biarkan angka tinggi yang sewenang-wenang membuat Anda takut ketika mengirimkan kode Anda; jika solusi Anda kreatif tetapi hanya dapat menangani begitu banyak disk, saya akan tetap memberi Anda kredit.
Carter Pape
Nah, ide saya adalah algoritma pemecahan yang cukup tidak efisien, dan jika batasnya adalah, apakah program dapat menangani, itu akan baik-baik saja. Tetapi saya telah melihat solusi sejauh ini, dan menyadari, bahwa saya akan bermain di liga yang sama sekali berbeda.
pengguna tidak diketahui

Jawaban:

2

Sekam , 5 byte

↑≠⁰İr

Cobalah online!
Masing-masing ndalam output mewakili disk yang bergerak nke pasak yang tersedia berikutnya (membungkus secara siklis).

Penjelasan

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

sumber
7

Python, 76 karakter

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)

Misalnya, untuk N = 3 mengembalikan:

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
sumber
Saya tahu saya sedikit terlambat ke permainan tetapi ini mencukur 13 karakter: tio.run/##K6gsycjPM/r/…
JayCe
6

Perl - 54 karakter

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

Jalankan dengan perl -M5.010dan masukkan jumlah disk pada stdin.

Format output:

Satu baris per gerakan, digit pertama dari pasak, digit kedua adalah pasak (mulai dari 0)

Contoh:

02 -- move from peg 0 to peg 2
01
21
02
10
12
02
Geoff Reedy
sumber
Hemat 5 karakter dengan melepas kawat gigi. $x=--$_&-$_,say(($_-$x)%3,($_+$x)%3)for 2..1<<<>
marinus
5

GolfScript ( 31 25 24 karakter)

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

Dengan terima kasih kepada Ilmari Karonen karena menunjukkan bahwa trpermutasi asli saya dapat dipersingkat dengan 6 karakter. Dengan menguraikannya sebagai produk dari dua permutasi, saya berhasil menyelamatkan satu lagi.

Perhatikan bahwa memperhitungkan 3%penambahan panjang satu karakter:

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

Beberapa orang memiliki format keluaran yang sangat rumit. Ini menghasilkan pasak bergerak dari (nomor 0, 1, 2) dan pasak pindah ke. Spek tidak mengatakan ke mana pasak bergerak, jadi pasak bergerak 1

Misalnya

$ golfscript hanoi.gs <<<"3"
01021201202101
Peter Taylor
sumber
Tidak diragukan lagi logika yang sama dalam sed bahkan lebih pendek, tetapi kemampuan sed saya tidak sampai ke situ.
Peter Taylor
1
Anda dapat melakukannya dalam 25 karakter:])~{.{3^3%}%2,@{2\-}%++}*
Ilmari Karonen
3

Perl, 75 79 karakter

Benar-benar mencuri format output Keith Randall:

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

Meminta -M5.010untuk say.

(Saya pikir ini dapat ditingkatkan jika Anda dapat menemukan cara untuk menggunakan nilai pengembalian fungsi alih-alih hanya menekannya.)

kotak roti
sumber
[stok "gunakan saja say" rekomendasi]
JB
Oke - tetapi bukankah saya harus memasukkan biaya mengaktifkan 5,10 fitur terhadap jumlah char saya?
kotak roti
1
Anda akan - tetapi gratis. Catat saja cara menjalankan program Anda sehingga orang yang tidak fasih dalam doa khusus dapat mencobanya.
JB
Terima kasih untuk tautannya; Saya mencari hal semacam itu sebelumnya.
kotak roti
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);

fungsi panggilan f(n,s,t)dengan:

  • jumlah disk
  • titik awal
  • t titik tujuan
seseorang
sumber
2

Bash (64 karakter)

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

Posting yang ini meskipun lebih dari dua kali panjang dari GolfScript karena saya suka menggunakan kembali tsebagai echo $s.

Peter Taylor
sumber
2

Scala, 92 88 87 karakter

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 output

Katakan jumlah disk = 3 lalu,

(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
Pangeran John Wesley
sumber
Penggunaan xor yang bagus.
Peter Taylor
2

C, 98 92 87 karakter

Menerapkan algoritma paling sepele.
Output adalah dalam bentuk di ab ab abmana setiap pasangan berarti "pindahkan cakram atas dari pasak ke pasak b".
EDIT : Bergerak sekarang dikodekan dalam hex - 0x12 berarti bergerak dari pasak 1 ke pasak 2. Menyimpan beberapa karakter.
EDIT : Membaca angka dari stdin, bukan parameter. Singkat.
Contoh:
% 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
sumber
Dapatkah seseorang menjelaskan sintaks tubuh fungsi h () - khususnya dua argumen yang jelas dalam panggilan rekursif (d ^ d% 16 * 16 dan printf (...)), dan operasi terakhir tampaknya menggantung ujungnya. Berdasarkan pengetahuan saya, fungsi itu memiliki dua kesalahan sintaks, tapi saya sudah tahu itu membangun (setelah menyertakan stdio) dan mengeksekusi dengan benar.
Griffin
1
Dimungkinkan untuk melewatkan lebih banyak parameter daripada fungsi yang diinginkan. Nilai-nilai mereka tidak ke mana-mana. h(x,printf(...))hanyalah cara untuk memanggil printfsebelum hdipanggil. Yang terakhir n++dibuat setelah batin hkembali. Ini digunakan untuk membatalkan inisial n--.
ugoren
Terima kasih, itu masuk akal (tujuan n ++ terbukti). Mengapa tidak ada titik koma yang mendahului n ++ bukannya koma, atau apakah itu membuat perbedaan?
Griffin
@ Griffin, Sebenarnya ;akan sama di sini. ,sering bermanfaat (misalnya if(x)a,b;menggantikanif(x){a;b;} ), tetapi tidak memiliki keuntungan di sini.
ugoren
2

Jelly , 5 byte

2*Ṗọ2

Cobalah online!

0pindahkan disk terkecil satu ruang ke kanan (membungkus kembali ke awal jika perlu)
1pindahkan disk terkecil kedua ke satu-satunya kolom hukum lainnya
2memindahkan disk terkecil ketiga ke satu-satunya kolom hukum lainnya
dll.

Algoritma

Kita dapat melihat solusi dari masalah Menara Hanoi secara rekursif; untuk memindahkan tumpukan ukuran n dari A ke B , memindahkan tumpukan ukuran n -1 dari A ke C , kemudian disk dengan ukuran n dari A ke B , lalu memindahkan tumpukan ukuran n -1 dari B ke C . Ini menghasilkan pola bentuk berikut (dalam format output yang digunakan oleh program ini):

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

Kita dapat mengamati bahwa urutan ini adalah A007814 pada OEIS. Definisi lain yang mungkin dari urutan adalah "elemen ke- k (dari-1) dari urutan adalah jumlah nol di akhir angka k ketika ditulis dalam biner". Dan itulah yang sedang dihitung oleh program di sini.

Penjelasan

Pertama, kami menghitung jumlah gerakan dalam solusi, 2 n -1. Ternyata menjadi yang terpendek untuk benar-benar menghitung satu langkah ekstra dan membuangnya nanti, jadi ini 2*, yaitu 2 pangkat dari sesuatu. (Satu-satunya input yang kami ambil sejauh ini adalah argumen baris perintah, sehingga digunakan secara default.)

Selanjutnya, kami menggunakan Jelly builtin untuk menghitung jumlah nol di akhir angka dalam basis b ; itub . Seperti yang kita hitung dalam biner, itu ọ2. Yang perlu kita lakukan adalah menerapkan builtin ini ke angka dari 1 hingga 2 n -1 inklusif.

Ada dua cara sederhana untuk beralih pada kisaran angka di Jelly, dan R, dan upaya saya sebelumnya pada masalah ini menggunakan salah satunya. Namun, dalam hal ini, mungkin menjadi sedikit lebih pendek:, ketika diberi nomor sebagai input, akan memungkinkan Anda melakukan iterasi yang menghentikan satu elemen pendek (secara umum, adalah builtin yang digunakan untuk memproses semua kecuali satu elemen dari sesuatu). Itulah yang kita inginkan dalam hal ini (karena 2*menghasilkan satu terlalu banyak elments), sehingga dengan itu-link 2*dan ọ2menjadi 2*Ṗọ2memberi kita solusi 5-byte untuk masalah ini.


sumber
1

Awk, 72 karakter

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 output sama dengan format 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
Pangeran John Wesley
sumber
1

Skrip Bash, 100 96 karakter

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

Format output sama dengan format Keith Randall .

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

Sunting : Disimpan 4 karakter oleh komentar peter .

Pangeran John Wesley
sumber
1
Anda dapat menambahkan spasi dan menyimpan beberapa karakter dengan menggema$@
Peter Taylor
@PeterTaylor: Poin bagus. biarkan saya memperbaruinya.
Pangeran John Wesley
1

J, 23 byte

solusi angka biner

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

Solusi ini menggunakan metode penghitungan biner yang dijelaskan dalam video ini .

Artinya, saya menghasilkan digit biner dari 1atas 2^n, lalu mengambil infiks dengan panjang 2 dan membandingkan setiap bit dengan bit yang sesuai dari angka sebelumnya, dan memeriksa apakah mereka tidak sama. Jumlah bit yang tidak sama adalah output untuk langkah itu.

Output, misalnya, untuk 3 disk, di mana disk terkecil diberi label 1:

1 2 1 3 1 2 1

1 berarti "pindahkan pasak terkecil ke kanan, putar kembali ke pasak pertama jika perlu"

n, untuk semua yang lain n, berarti "pindahkan disk nke pasak yang sah" (akan selalu ada satu)

Cobalah online!

solusi rekursif

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

Output yang sama dengan solusi di atas, tetapi logika di sini membuat sifat rekursif masalah menjadi lebih jelas.

Memvisualisasikannya sebagai pohon juga menekankan hal ini:

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

Cobalah online!

Jonah
sumber
1
sifat kebetulan mengirimkan jawaban Anda lebih dari 5 tahun setelah pertanyaan asli diajukan dalam jam yang sama ketika saya kembali untuk meninjau jawaban atas pertanyaan ini yang saya kirimkan lebih dari 5 tahun yang lalu ... wow. +1
Carter Pape
0

APL (Dyalog Classic) , 19 byte

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

Cobalah online!

output adalah matriks 2-kolom ints di {0,1,2} - dari pasak, ke pasak

ngn
sumber
0

R , 73 byte

Menempatkan R di peta. Terinspirasi oleh [Jawaban Keith Randall] [1] dengan input yang disederhanakan, hanya cetak ujung dan mulai pasak untuk menghemat 2 byte. Juga pasak 0-diindeks.

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

Cobalah online!

JayCe
sumber
0

JavaScript (ES6), 45b

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

mis. memanggil h(4, 'A', 'B', 'C')(pindahkan 4 disk dari pasak A ke pasak C menggunakan pasak bantu B)

mengembalikan 'ABACBCABCACBABACBCBACABCABACBC'(memindahkan disk dari pasak A ke pasak B, memindahkan disk dari pasak A ke pasak C, memindahkan cakram dari pasak B ke pasak C, dll.)

targumon
sumber
1
Bagus. Saya bertanya-tanya apakah parameter f, a, t harus memiliki default yang disertakan dalam definisi fungsi? Kalau tidak, pengiriman dapat menyertakan data sewenang-wenang dalam argumen tambahan. Saya seorang pemula, jadi seseorang yang lebih berpengalaman harus memberi nasihat.
John Rees