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
L
mewakili pasak kiri, C
mewakili pasak tengah dan R
mewakili 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.
Jawaban:
Sekam , 5 byte
Cobalah online!
Masing-masing
n
dalam output mewakili disk yang bergerakn
ke pasak yang tersedia berikutnya (membungkus secara siklis).Penjelasan
sumber
Python, 76 karakter
Misalnya, untuk N = 3 mengembalikan:
sumber
Perl - 54 karakter
Jalankan dengan
perl -M5.010
dan masukkan jumlah disk pada stdin.Format output:
Satu baris per gerakan, digit pertama dari pasak, digit kedua adalah pasak (mulai dari 0)
Contoh:
sumber
$x=--$_&-$_,say(($_-$x)%3,($_+$x)%3)for 2..1<<<>
GolfScript (
31 2524 karakter)Dengan terima kasih kepada Ilmari Karonen karena menunjukkan bahwa
tr
permutasi 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: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
sumber
])~{.{3^3%}%2,@{2\-}%++}*
Perl, 75
79karakterBenar-benar mencuri format output Keith Randall:
Meminta
-M5.010
untuksay
.(Saya pikir ini dapat ditingkatkan jika Anda dapat menemukan cara untuk menggunakan nilai pengembalian fungsi alih-alih hanya menekannya.)
sumber
say
" rekomendasi]SML, 63
fungsi panggilan
f(n,s,t)
dengan:sumber
Bash (64 karakter)
Posting yang ini meskipun lebih dari dua kali panjang dari GolfScript karena saya suka menggunakan kembali
t
sebagaiecho $s
.sumber
Scala,
928887 karakterFormat output
Katakan jumlah disk = 3 lalu,
sumber
C,
989287 karakterMenerapkan algoritma paling sepele.
Output adalah dalam bentuk di
ab ab ab
mana 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
sumber
h(x,printf(...))
hanyalah cara untuk memanggilprintf
sebelumh
dipanggil. Yang terakhirn++
dibuat setelah batinh
kembali. Ini digunakan untuk membatalkan inisialn--
.;
akan sama di sini.,
sering bermanfaat (misalnyaif(x)a,b;
menggantikanif(x){a;b;}
), tetapi tidak memiliki keuntungan di sini.Jelly , 5 byte
Cobalah online!
0
pindahkan disk terkecil satu ruang ke kanan (membungkus kembali ke awal jika perlu)1
pindahkan disk terkecil kedua ke satu-satunya kolom hukum lainnya2
memindahkan disk terkecil ketiga ke satu-satunya kolom hukum lainnyadll.
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):
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 ; itu
ọb
. 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,
€
danR
, 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 (karena2*
menghasilkan satu terlalu banyak elments), sehingga dengan itu-link2*
danọ2
menjadi2*Ṗọ2
memberi kita solusi 5-byte untuk masalah ini.sumber
Awk, 72 karakter
Format output sama dengan format Keith Randall .
sumber
Skrip Bash,
10096 karakterFormat output sama dengan format Keith Randall .
Sunting : Disimpan 4 karakter oleh komentar peter .
sumber
$@
J, 23 byte
solusi angka biner
Solusi ini menggunakan metode penghitungan biner yang dijelaskan dalam video ini .
Artinya, saya menghasilkan digit biner dari
1
atas2^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
berarti "pindahkan pasak terkecil ke kanan, putar kembali ke pasak pertama jika perlu"n
, untuk semua yang lainn
, berarti "pindahkan diskn
ke pasak yang sah" (akan selalu ada satu)Cobalah online!
solusi rekursif
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:
Cobalah online!
sumber
APL (Dyalog Classic) , 19 byte
Cobalah online!
output adalah matriks 2-kolom ints di {0,1,2} - dari pasak, ke pasak
sumber
K (ngn / k) , 23 byte
Cobalah online!
sumber
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.
Cobalah online!
sumber
JavaScript (ES6), 45b
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.)sumber