Jika Anda tidak tahu apa itu Menara Hanoi , saya akan jelaskan secara singkat: Ada tiga batang dan beberapa cakram yang masing-masing memiliki ukuran berbeda. Pada awalnya semua disc ada di menara pertama, dalam urutan: Urut terbesar ada di bawah, yang terkecil di atas. Tujuannya adalah untuk membawa semua cakram ke batang ketiga. Kedengarannya mudah? Inilah masalahnya: Anda tidak dapat menempatkan disk di atas disk yang lebih kecil dari disk lain; Anda hanya dapat memegang satu disk di tangan Anda pada satu waktu untuk memindahkannya ke batang lain dan Anda hanya dapat menempatkan disk pada batang, bukan di atas meja, Anda bajingan licik.
solusi contoh ascii:
A B C
| | |
_|_ | |
__|__ | |
A B C
| | |
| | |
__|__ _|_ |
A B C
| | |
| | |
| _|_ __|__
A B C
| | |
| | _|_
| | __|__
Tantangan
Ada tiga batang yang disebut A, B dan C. (Anda juga dapat memanggilnya 1,2 dan 3 dengan hormat jika itu membantu) Pada awalnya semua cakram ada pada batang A (1).
Tantangan Anda adalah memverifikasi solusi untuk menara hanoi. Anda harus memastikan bahwa:
- Pada akhirnya semua n disc berada di rod C (3).
- Untuk setiap disk yang diberikan pada kondisi tertentu tidak ada disk yang lebih kecil di bawahnya.
- Tidak ada kesalahan yang jelas seperti mencoba mengambil disk dari batang kosong atau memindahkan disk ke batang yang tidak ada.
(solusinya tidak harus optimal.)
Memasukkan
Program Anda akan menerima dua input:
- Jumlah cakram n (bilangan bulat)
Bergerak yang diambil, yang akan terdiri dari satu set tupel dari: (menara untuk mengambil disk paling atas dari saat ini), (menara untuk membawa disk ini ke) di mana masing-masing tupel mengacu pada suatu gerakan. Anda dapat memilih bagaimana mereka diwakili. Misalnya sesuatu seperti cara berikut untuk mewakili solusi untuk n = 2 yang telah saya gambar di ascii di atas. (Saya akan menggunakan yang pertama dalam test case, karena mudah di mata):
"A-> B; A-> C; B-> C"
[("A", "B"), ("A", "C"), ("B", "C")]
[(1,2), (1,3), (2,3)]
"ABACBC"
[1,2,1,3,2,3]
Keluaran
Sebenarnya, jika kondisi itu dapat ditemukan di bawah "tantangan" terus.
Falsy, jika tidak.
Kasus uji:
Benar:
n=1, "A->C"
n=1, "A->B ; B->C"
n=2, "A->B ; A->C ; B->C"
n=2, "A->C ; C->B ; A->C ; B->C"
n=2, "A->C ; A->B ; C->B ; B->A ; B->C ; A->C"
n=3, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"
n=4, "A->B ; A->C ; B->C ; A->B ; C->A ; C->B ; A->B ; A->C ; B->C ; B->A ; C->A ; B->C ; A->B ; A->C ; B->C"
Salah:
Yang ketiga disarankan oleh @MartinEnder, 7th oleh @Joffan
n=1, "A->B"
n=1, "C->A"
n=2, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"
n=2, "A->B ; A->C ; C->B"
n=2, "A->C ; A->B ; C->B ; B->A"
n=2, "A->C ; A->C"
n=3, "A->B ; A->D; A->C ; D->C ; A->C"
n=3, "A->C ; A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"
n=3, "A->C ; A->B ; C->B ; A->B ; B->C ; B->A ; B->C ; A->C"
n=3, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; C->B"
n=4, "A->B ; A->C ; B->C ; A->B ; C->A ; C->B ; A->B ; A->C ; B->C ; B->A ; C->A ; B->C ; A->B ; A->C"
n=4, "A->B ; A->B ; A->B ; A->C ; B->C ; B->C ; B->C"
Ini adalah kode-golf , solusi terpendek yang menang. Aturan dan celah standar berlaku. Tidak termasuk baterai.
A=1
,B=2
,C=3
, dll)?A->A
?moving discs to nonexistant rods.
jadi tentu saja ya, iniD
Jawaban:
Retina ,
8480 Bytes-5 byte berkat Martin Ender
Cobalah online! (ditambah 5 byte untuk tes baris demi baris)
Kode mensimulasikan permainan penuh.
ACABCBACBABCAC~~~
.~~~
berarti tiga cakram.ACABCBACBABCAC ~~~ ~~ ~ABC
.Pada awalnya batang A memiliki semua 3 cakram, dan batang B dan C kosong.
Di luar contoh, setelah langkah pertama, teks akan terlihat seperti:
~CABCBACBABCAC ~~~ ~~ABC
.ABCBACBABCAC ~~~ ~~AB ~C
.sumber
Retina ,
167165157150123 byteIni benar-benar tampak seperti tantangan yang harus diselesaikan dengan satu regex ... (meskipun tajuknya berbunyi "Retina", ini hanyalah vanilla .NET regex, yang cocok dengan input yang valid).
Format input adalah daftar instruksi formulir
AB
, diikuti olehn
unary menggunakan digit1
. Tidak ada pemisah. Output1
untuk valid dan0
tidak valid.Cobalah online! (Dua karakter pertama memungkinkan suite tes yang dipisahkan dengan linefeed.)
Solusi alternatif, jumlah byte yang sama:
Ini mungkin dapat dipersingkat dengan menggunakan
1
,11
dan111
bukannyaA
,B
danC
tapi saya harus memeriksanya nanti. Mungkin juga lebih pendek untuk membagi program menjadi beberapa tahap, tetapi di mana tantangannya? ;)Penjelasan
Solusi ini banyak menggunakan kelompok penyeimbang .NET. Untuk penjelasan lengkap, lihat posting saya di Stack Overflow , tetapi intinya adalah bahwa menangkap grup di .NET adalah tumpukan, di mana setiap tangkapan baru mendorong substring lain dan di mana juga dimungkinkan untuk muncul dari tumpukan seperti itu lagi. Ini memungkinkan Anda menghitung berbagai jumlah dalam sebuah string. Dalam hal ini memungkinkan kita mengimplementasikan tiga batang secara langsung sebagai tiga kelompok pengambilan yang berbeda di mana setiap disk diwakili oleh suatu tangkapan.
Untuk memindahkan disk di sela-sela batang, kami menggunakan quirk
(?<A-B>...)
sintaksis yang aneh . Biasanya, ini muncul menangkap dari tumpukanB
dan mendorong ke tumpukanA
tali antara penangkapan muncul dan awal kelompok ini. Jadi(?<A>a).(?<B-A>c)
dicocokkanabc
akan dibiarkanA
kosong danB
denganb
(sebagai lawan daric
). Namun, karena .NET variabel-panjang lookbehinds mungkin untuk menangkap(?<A>...)
dan(?<B-A>...)
tumpang tindih. Untuk alasan apa pun, jika itu masalahnya, persimpangan dari dua kelompok didorong keB
. Saya telah merinci perilaku ini di "bagian lanjutan" tentang menyeimbangkan grup dalam jawaban ini .Aktif ke regex. Batang
A
,B
danC
sesuai dengan kelompok3
,4
dan5
di regex. Mari kita mulai dengan menginisialisasi batangA
:Jadi mis. Jika input berakhir dengan
111
, maka grup 3 / batangA
sekarang akan memegang daftar tangkapan[111, 11, 1]
(yang atas berada di sebelah kanan).Bit kode selanjutnya memiliki struktur sebagai berikut:
Setiap iterasi dari loop ini memproses satu instruksi. Pergantian pertama menarik cakram dari batang yang diberikan (ke grup sementara), pergantian kedua menempatkan cakram itu ke batang yang diberikan lainnya. Kami akan segera melihat bagaimana ini bekerja dan bagaimana kami memastikan bahwa langkah tersebut valid.
Pertama, mengambil disk dari batang sumber:
Ini menggunakan perilaku persimpangan-kelompok yang aneh yang telah saya jelaskan di atas. Perhatikan grup itu
3
,4
dan5
akan selalu menahan substring1
s pada akhir string yang panjangnya sesuai dengan ukuran disk. Kami sekarang menggunakan(?<1-N>.+)
pop disc atas dari stackN
dan mendorong persimpangan substring ini dengan pertandingan.+
ke stack1
. Karena.+
selalu harus mencakup seluruh tangkapan yang munculN
, kita tahu bahwa ini hanya memindahkan tangkapan.Selanjutnya, kami menempatkan disk ini dari tumpukan
1
ke tumpukan yang sesuai dengan batang kedua:Perhatikan bahwa kita tidak perlu membersihkan tumpukan
1
, kita bisa meninggalkan disk di sana, karena kita akan meletakkan yang baru di atas sebelum menggunakan tumpukan lagi. Itu berarti kita dapat menghindari(?<A-B>...)
sintaks dan cukup menyalin string(\1)
. Untuk memastikan bahwa langkah tersebut valid, kami menggunakan lookahead negatif(?!\N)
. Ini memastikan bahwa, dari posisi di mana kami ingin mencocokkan disk saat ini, tidak mungkin untuk mencocokkan disk yang sudah ada di tumpukanN
. Ini hanya dapat terjadi jika a)\N
tidak akan pernah cocok karena tumpukan benar-benar kosong atau b)the disc on top of stack
Nis larger than the one we're trying to match with
\ 1`.Akhirnya, yang tersisa adalah memastikan bahwa a) kami telah mencocokkan semua instruksi dan b) batang
A
danB
kosong, sehingga semua disc telah dipindahkanC
.Kami cukup memeriksa tidak ada yang cocok
\3
atau tidak\4
(yang hanya merupakan kasus jika keduanya kosong, karena setiap disc yang sebenarnya akan cocok) dan bahwa kami kemudian dapat mencocokkan1
sehingga kami belum menghilangkan instruksi apa pun.sumber
Java "hanya"
311 272 263 261 260 259256 byteMenyimpan
39byte yang tak terhitung jumlahnya karena @Frozn memperhatikan fitur debug yang lebih lama serta beberapa trik golf yang pintar.Versi golf
ungolfed dengan penjelasan dan tumpukan cetak cantik di setiap langkah
Versi ungolfed memiliki fitur di mana ia akan mencetak seperti apa tumpukan di setiap langkah seperti ...
sumber
System.out.println(Arrays.toString(s))
harus dilakukan&&
dengan&
.Python 2,
186167158135127115110102 byteMengambil input pada STDIN dalam format berikut:
Artinya, sebuah tuple Python dari jumlah cakram dan daftar tupel Python
(from_rod,to_rod)
. Seperti dalam Python, tanda kurung di sekitarnya adalah opsional. Batang nol diindeks.Sebagai contoh, test case ini:
akan diberikan sebagai:
Jika solusinya valid, tidak menghasilkan apa-apa dan keluar dengan kode keluar 0. Jika tidak valid, melempar pengecualian dan keluar dengan kode keluar dari 1. Melemparkan sebuah
IndexError
jika pindah ke batang yang tidak ada atau mencoba melepaskan disk dari batang yang tidak memiliki cakram di atasnya,ZeroDivisionError
jika cakram ditempatkan di atas cakram yang lebih kecil, atauNameError
jika ada cakram yang tersisa di batang pertama atau kedua di ujungnya.Disimpan 13 byte berkat @KarlKastor!
Disimpan 8 byte berkat @xnor!
sumber
Python 2.7,
173158138130127123 byte:Mengambil input melalui stdin dalam format di
(<Number of Discs>,<Moves>)
mana<Moves>
diberikan sebagai larik berisi tupel yang sesuai dengan setiap gerakan, yang masing-masing berisi sepasang bilangan bulat yang dipisahkan koma. Misalnya, test case:diberikan dalam pos akan diberikan sebagai:
ke program saya. Outputs
IndexError
jika kondisi ke-3 tidak terpenuhi,NameError
kondisi ke-2 tidak terpenuhi, danFalse
jika kondisi ke-1 tidak terpenuhi. Jika tidak, outputTrue
.sumber
Y
tidak pernah didefinisikan dalam kode Anda (saya pikir itu harus J) danU[J]+=[Y,[U[K].pop()]][U[J]<[1]or U[K]<U[J]]
lebih pendek oleh 3 karakter yangstmt1 if cond else stmt2
Y
variabel seperti itu adalah untuk menaikkanNameError
setiap kali kondisi ke-2 tidak terpenuhi. Jika saya harus mengubahY
keJ
, makaNameError
tidak akan dibangkitkan. Untuk alasan ini, saya juga tidak dapat melakukannyaU[J]+=[Y,[U[K].pop()]][U[J]<[1]or U[K]<U[J]]
karena ini akan meningkatkanNameError
waktu , bukan hanya ketika kondisi ke-2 tidak terpenuhi.VBA,
234217213196 byteFormat input untuk bergerak adalah string dengan angka genap (012). Doa ada dalam spreadsheet, = H ([jumlah disk], [pindahkan string])
Array A memegang posisi batang berbagai disk. Sebuah langkah hanya memperbarui kemunculan pertama dari nomor batang "Dari" ke nomor batang "Ke". Jika Anda menjumpai "ke" disk batang pertama, atau tidak ada "dari" disk batang, itu adalah langkah yang tidak valid. "Nilai batang" total A disimpan dalam L, yang harus berakhir pada 2N. Kesalahan diakumulasikan sebagai penghitungan negatif di E.
Secara umum dengan solusi lain, "memindahkan" disk dari menara ke menara yang sama tidak dilarang. Saya bisa melarangnya selama 6 byte lagi.
Hasil
Hasil fungsi di kolom pertama (n = 3 kasus terakhir adalah tambahan saya menggunakan batang tambahan).
sumber
php, 141 byte
Script baris perintah, mengambil input sebagai tinggi kemudian serangkaian indeks array (0 diindeks) misalnya 1 0 2 atau 2 0 1 0 2 1 2 untuk 1 atau 2 kasus uji terpendek ketinggian.
Gema 1 pada kasus yang benar dan tidak ada yang salah.
Memberi 2 pemberitahuan dan 1 peringatan sehingga perlu dijalankan di lingkungan yang membungkamnya.
sumber
JavaScript (ES6), 108
Format input: berfungsi dengan 2 argumen
Output: mengembalikan 1 jika ok, 0 jika tidak valid, kecuali jika tidak ada batang
Kurang bermain golf dan menjelaskan
Catatan Tes : baris pertama dari fungsi Tes diperlukan untuk mengonversi format input yang diberikan dalam pertanyaan menjadi input yang diharapkan oleh fungsi saya
sumber