Ada 40 cara jalur Hamiltonian terarah dapat diatur pada kisi 3 × 3:
Grafik ini ( terima kasih Sp3000! ) Hanya menampilkan 20 jalur yang tidak diarahkan. Lintasi setiap garis berwarna di kedua arah untuk 40 jalur yang diarahkan.
Tantangan
Hanya menggunakan ASCII yang dapat dicetak , tulis kisi-kisi karakter 3 × 3, seperti:
ABC
DEF
GHI
Ketika masing-masing dari 40 jalur diarahkan dibaca dari kisi ini sebagai 40 baris tunggal, program 9-karakter, tujuannya adalah agar setiap program menghasilkan bilangan bulat unik dari 1 hingga 40. Melakukan ini untuk semua 40 jalur tampaknya sulit dan tidak mungkin, jadi Anda hanya perlu membuatnya bekerja untuk jalur sebanyak mungkin.
Kiriman yang program jalur 40-nya menampilkan angka paling berbeda dari 1 hingga 40 akan menjadi pemenang. Tiebreaker pergi ke pengiriman sebelumnya.
Program jalur yang kesalahan atau tidak menghasilkan bilangan bulat dari 1 hingga 40 atau menghasilkan bilangan bulat yang sudah dicakup program jalur lain tidak dihitung. Secara khusus:
- Program yang kesalahan saat mengkompilasi, menjalankan, atau keluar tidak dihitung. Peringatan tidak apa-apa.
- Program yang tidak menghasilkan bilangan bulat dari 1 hingga 40 atau menghasilkan sesuatu yang sedikit cacat seperti
-35
atau35 36
tidak dihitung. - Program yang membutuhkan input pengguna untuk menghasilkan output tidak dihitung.
- Program yang tidak pernah berakhir tidak dihitung.
- Mulai sekarang , program yang tidak deterministik tidak dihitung.
- Jika tidak, program-program yang valid yang menghasilkan bilangan bulat dari 1 hingga 40 yang tidak pernah dihitung oleh program lain yang valid. (Program pertama adalah dihitung.)
- Hanya program yang menampilkan representasi bilangan bulat dari 1 hingga 40 (inklusif) yang dihitung terhadap total Anda. Jumlahnya diperkirakan berada di biasa
1
,2
, ...,39
,40
Format, kecuali yang tidak norma untuk bahasa Anda. (Baris baru yang tertinggal di output baik-baik saja.) - Angka mana yang dihasilkan oleh program Anda dan urutannya tidak penting. Hanya jumlah bilangan bulat yang berbeda dari program yang valid yang penting.
Semua program jalur harus dijalankan dalam bahasa yang sama. Namun, "program" mungkin sebenarnya adalah fungsi (tanpa argumen yang diperlukan) atau perintah REPL , serta program lengkap, yang mencetak atau mengembalikan target integer mereka. Anda dapat mencampur dan mencocokkan antara fungsi, perintah REPL, dan program lengkap.
9 karakter ASCII Anda yang dapat dicetak tidak perlu berbeda.
Contoh
Jika kisi 3 × 3 Anda adalah
ABC
DEF
GHI
dan 40 program dan output Anda terlihat seperti ini
ABCFEDGHI -> 26
ABCFIHEDG -> 90
ABCFIHGDE -> 2
ABEDGHIFC -> syntax error
ADEBCFIHG -> prints 40 but then errors
ADGHEBCFI -> 6
ADGHIFCBE -> 6
ADGHIFEBC -> 6
CBADEFIHG -> runtime error
CBADGHEFI -> 3
CBADGHIFE -> 4
CFEBADGHI -> -32
CFIHEBADG -> 38.0
CFIHGDABE -> "36"
EDABCFIHG -> 33
EFCBADGHI -> no output
EHGDABCFI -> compilation error
EHIFCBADG -> 8
GDABCFEHI -> 22
GHEDABCFI -> 41
IHGDEFCBA -> 0
GDEHIFCBA -> '9'
EDGHIFCBA -> +10
CFIHGDEBA -> 11
GHIFCBEDA -> error
IFCBEHGDA -> error
EBCFIHGDA -> prints 23 but then loops infinitely
CBEFIHGDA -> randomly prints either 24 or 44
GHIFEDABC -> error
IFEHGDABC -> 30
EFIHGDABC -> 39
IHGDABEFC -> 7
GDABEHIFC -> 29
EBADGHIFC -> -1
GHIFCBADE -> 26
IHGDABCFE -> 1
IFCBADGHE -> error
GDABCFIHE -> no output
IHEFCBADG -> no output
IFCBADEHG -> "quack"
skor Anda akan menjadi 14, karena ada 14 bilangan bulat yang berbeda dari 1 hingga 40 output yang valid, yaitu 26 2 6 3 4 33 8 22 11 30 39 7 29 1
.
sumber
123654789
Jawaban:
PARI / GP - 24
PARI / GP mengabaikan spasi antar digit, sehingga
1 8 2
, misalnya diperlakukan sebagai182
. Hal yang sama dapat bekerja untuk perl dengan mengganti spasi dengan garis bawah. Saya belum kehabisan seluruh ruang pencarian, jadi mungkin ada kandidat yang lebih baik.Suatu program dapat diumpankan ke gp as
gp -q -f program.gp
, atau secara interaktif di repl.Keluaran
Semua kecuali 4 nilai berada dalam rentang yang diperlukan, dengan 12 entri rangkap.
Memperbarui
Saya sudah selesai mengunyah, ada enam 23 berbeda, dan hanya satu 24 (seperti yang dibaca oleh baris):
Program yang saya gunakan untuk menguraikan adalah di bawah ini. PARI / GP memiliki kemampuan pemrosesan string yang terbatas, jadi berurusanlah terutama dengan array char (alias
Vecsmall
). Operator diuji adalah+
,-
,*
,\
(lantai div),%
,;
(ekspresi pemisah, pada dasarnya membuang segala sesuatu sebelum itu), dan(ruang, seperti dijelaskan di atas). Operator eksponen
^
juga dapat ditambahkan, tetapi menjadi terlalu lambat untuk menguji secara mendalam.sumber
Deadfish , 18
Ini sebenarnya bahasa pertama yang saya coba sebelum saya mempertimbangkan operator infiks. Saya mempostingnya sekarang untuk kegembiraan belaka dari gagasan bahwa Deadfish dapat berguna untuk sesuatu.
Bagi mereka yang tidak tahu Deadfish,
i
adalah increment,s
adalah square dano
output, dengan akumulator mulai dari 0 (ada juga instruksi ke-4d
untuk decrement yang tidak digunakan di sini). Fakta bahwa kami tidak memiliki pencetakan otomatis dan perlu digunakano
adalah kelemahan utama, tetapi yang mengejutkan Deadfish tidak terlalu banyak melakukan hal ini, semua hal dipertimbangkan. Ternyata penempatan optimal dari operator output di tengah.sumber
Python REPL dan banyak lagi,
2223Pengamatan kunci: Jika Anda mewarnai kisi-kisi seperti kotak-kotak, jalur akan berganti warna kisi saat berjalan dan dimulai dan berakhir pada warna yang sama.
Masih dengan kekerasan memaksa untuk lebih baik.Mencoba dengan+*%
(dan bahkan**
untuk bahasa di mana^
eksponensial) sayangnya tidak menghasilkan sesuatu yang lebih baik. Saya juga mencoba melempar operator bitwise dan hanya^
(xor) yang agak membantu, tetapi pencarian terlalu lama sehingga saya menyerah.sumber
6+7*5%6%4
,6+7*4%6%5
dan6+8*4%6%5
(kiri ke kanan, atas ke bawah), dan tidak ada yang lain.+
dan-
di sudut-sudut / pusat? Karena mereka adalah operator unary dan juga biner, itu harus tetap menghasilkan semua ekspresi yang valid. Tidak mungkin itu akan menghasilkan solusi yang lebih baik, tetapi setidaknya itu memperluas ruang pencarian. Hmm, sebenarnya, itu mungkin masalah karena Anda bisa berakhir dengan urutan operator.J, 15
Ini hanya menghasilkan angka yang valid, tetapi banyak yang merupakan duplikat. Nilai uniknya adalah
17 11 16 28 31 23 13 10 21 33 18 24 22 29 27
. Anda pasti dapat melakukan yang lebih baik dengan mengganti operator dan bilangan bulat yang terlibat.sumber
Yes
.> <>, 36 *
Jika Anda cukup beruntung!
Karena tantangan tidak memerlukan kode untuk menjadi deterministik, kita hanya perlu membuktikan bahwa adalah mungkin (bahkan jika tidak mungkin) untuk mengembalikan 36 angka dan kita selesai.Kurasa bagus saat itu berlangsung.(Bagi mereka yang tidak terbiasa dengan> <>, intro yang hebat dapat ditemukan di sini )
Saya memutuskan untuk menggunakan instruksi "x" di> <>, yang mengubah arah petunjuk petunjuk ke atas, bawah, kiri atau kanan secara acak. Karena kode kita hanya akan menjadi satu baris, itu berarti bahwa kita hanya dapat melihat kasing-kasing ketika ia bergerak ke kanan atau ke kiri, karena jika penunjuknya naik atau turun, itu hanya akan mengenai instruksi "x" lagi.
Instruksi "n" mengeluarkan nomor di bagian atas tumpukan dan mencetaknya. Namun jika tumpukan kosong dan tidak ada yang muncul, kesalahan muncul.
Instruksi "l" hanya mendorong panjang tumpukan ke tumpukan (dan beruntung bagi kita itu tidak mengirim kesalahan jika tumpukan kosong), jadi misalnya jika tumpukan kosong dan "l" akan dipanggil, itu akan mendorong 0 ke tumpukan. Jika sekarang kita akan memanggil lagi "l", maka karena stack memiliki satu elemen (0), itu akan mendorong 1 ke atas stack dan sekarang itu berarti bahwa akan ada dua hal di stack dan itu berarti bahwa jika kita memanggil "l" lagi, kita akan mendorong 2 ke stack dll. Jadi kita bisa menggunakan "l" untuk mendorong nomor sewenang-wenang ke stack melalui metode yang ditunjukkan sebelumnya.
";" instruksi mengakhiri program.
Gagasan dengan menggunakan "x" adalah bahwa, misalnya jika hanya ada satu "x" dalam kode (di mana A, B, C, D adalah beberapa instruksi):
Program akan menjalankan A lalu B lalu C, dan setelah mencapai "x" kita akan memiliki dua kemungkinan: kode terus berjalan ke kanan dan tekan ";" dan keluar atau ke kiri dan mengeksekusi C lalu B lalu A lalu D dan hanya kemudian keluar. Jadi jika kode kita mengandung satu "x", program mendapatkan dua aliran program yang memungkinkan dari mana kita dapat memilih program yang paling cocok.
Saya ada dua atau lebih "x" maka kita mendapatkan jumlah tak terbatas dari kemungkinan aliran program.
Kode kita memiliki lima "x", lebih lanjut masing-masing dari mereka berada dalam "sel awal" dari jalur Hamilton, yang berarti setiap program tunggal akan dimulai dengan "x", dan setiap program akan memiliki struktur:
Di mana A, B, C, D milik {; , n, l, l} Ini berarti hanya ada 12 program unik. Lebih jauh lagi karena kita selalu memulai dengan "x", kita dapat melihat kasus ketika program berjalan ke kiri, sehingga program simetris juga dapat dianggap sama. Hingga simetri hanya ada 6 program yang berbeda. Hanya 4 dari mereka muncul dalam program yang dihasilkan sebagai jalur hamiltonian:
Mari kita lihat program pertama "xnxlxlx; x" jika kita langsung ke langkah pertama kita menekan perintah cetak yang akan menimbulkan kesalahan karena kita tidak memiliki apa-apa di stack. Jika kita ke kiri, kita tekan perintah program akhir. Jadi kami tidak dapat menampilkan nomor apa pun dari program ini.
Program kedua, "xlxnxlx; x", jauh lebih penuh harapan, karena setelah mulai dari awal, nol diletakkan di tumpukan, jika kita pergi ke kiri di "x" berikutnya, tumpukan kita naik satu, kemudian berjalan dengan benar lagi kami memiliki 2 yang kemudian dapat kami cetak dan teruskan untuk mengakhiri program. Kita dapat mengamati bahwa kita benar-benar dapat mencetak angka genap , karena pada bagian "xlx" di awal kita dapat mencapai sejumlah ukuran acak dengan pergi ke kanan lalu ke kiri lalu ke kanan lagi beberapa kali.
Serupa dengan itu dapat dilihat bahwa program ketiga xnxlx; xlx dapat menampilkan angka ganjil , dengan pergi ke kiri di awal dan kemudian mengulangi rutin "xlx" hanya kali ini ke kiri lalu ke kanan lalu ke kiri.
Dan program keempat pada dasarnya sama dengan program kedua dan dapat menampilkan angka genap .
Jadi untuk program yang diperlukan kami memiliki:
Itu adalah 4 program yang tidak dapat menghasilkan angka, 20 yang dapat menghasilkan angka genap, 16 yang dapat menghasilkan angka ganjil. Karena ada persis 20 angka genap dan setidaknya 16 angka ganjil dalam kisaran 1 hingga 40, maka dengan probabilitas tertentu terdapat kemungkinan bahwa akan ada 36 angka berbeda dalam kisaran 1 hingga 40 yang dihasilkan oleh blok kode ini.
sumber
GolfScript, 8
Saat ini solusi skor tertinggi. : P Baiksaat itu berlangsung.Program
sumber
0)1#2#3(4
pada 15. Simetri yang indah juga.CJam, 14
Di bawah program kerja:
Nilai yang dihasilkan adalah: [1, 3, 4, 11, 13, 14, 20, 21, 22, 23, 24, 30, 31, 33]
sumber
dc (20)
32 output, 20 di antaranya berbeda (ditandai dengan a
$
)2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 14, 15, 16, 20, 22, 24, 25, 32, 34, 40
sumber