Untaian perampok ada di sini .
Tantangan polisi: Merancang bahasa pemrograman yang tampaknya tidak dapat digunakan untuk pemrograman, tetapi mengakui perhitungan (atau setidaknya penyelesaian tugas) melalui beberapa mekanisme yang tidak jelas.
Anda harus merancang bahasa pemrograman sederhana yang membaca kode dari file input dan kemudian melakukan ... sesuatu. Anda harus menyiapkan program solusi yang menemukan angka terbesar ke-3 dalam input saat dijalankan dalam juru bahasa Anda. Anda harus membuatnya sesulit mungkin bagi perampok untuk menemukan program solusi. Perhatikan bahwa perampok dapat memposting solusi apa pun yang menyelesaikan tugas, bukan hanya yang Anda pikirkan.
Ini adalah kontes popularitas. Tujuan polisi adalah untuk mendapatkan suara sebanyak mungkin sambil bertahan 8 hari setelah memposting penerjemah tanpa retak. Untuk tujuan ini, praktik-praktik berikut harus membantu:
- Menjelaskan semantik bahasa Anda dengan akurat
- Menulis kode yang dapat dibaca
Taktik berikut sangat tidak dianjurkan:
- Menggunakan enkripsi, hash, atau metode kriptografi lainnya. Jika Anda melihat bahasa yang menggunakan enkripsi RSA, atau menolak untuk menjalankan program kecuali hash SHA-3-nya sama dengan 0x1936206392306, jangan ragu untuk melakukan downvote.
Tantangan perampok: Tulis sebuah program yang menemukan bilangan bulat terbesar ketiga dalam input saat dijalankan dalam penerjemah polisi.
Yang ini relatif mudah. Untuk memecahkan jawaban polisi, Anda harus membuat program yang menyelesaikan tugas saat dijalankan dalam penerjemahnya. Ketika Anda memecahkan sebuah jawaban, kirim komentar yang mengatakan "Retak" pada jawaban polisi yang terhubung ke posting Anda. Siapa pun yang paling banyak meretas polisi akan memenangkan utas perampok.
Aturan I / O
- Penerjemah harus mengambil nama file pada baris perintah untuk program, dan menggunakan input dan output standar saat menjalankannya.
- Masukan akan diberikan secara unary dan hanya terdiri dari karakter
0
dan1
(48 dan 49 di ASCII). Angka N dikodekan sebagai N1s
diikuti oleh a0
. Ada tambahan0
sebelum akhir file. Contoh: Untuk urutan (3, 3, 1, 14), inputnya adalah11101110101111111111111100
. - Input dijamin memiliki setidaknya 3 angka. Semua angka adalah bilangan bulat positif.
- Output akan dinilai berdasarkan jumlah yang
1
dicetak sebelum program dihentikan. Karakter lain diabaikan.
Dalam contoh berikut, baris pertama adalah input dalam format desimal; yang kedua adalah input program aktual; yang ketiga adalah output sampel.
1, 1, 3
101011100
1
15, 18, 7, 2, 15, 12, 3, 1, 7, 17, 2, 13, 6, 8, 17, 7, 15, 11, 17, 2
111111111111111011111111111111111101111111011011111111111111101111111111110111010111111101111111111111111101101111111111111011111101111111101111111111111111101111111011111111111111101111111111101111111111111111101100
111111,ir23j11111111111u
247, 367, 863, 773, 808, 614, 2
<omitted>
<contains 773 1's>
Aturan membosankan untuk jawaban polisi:
- Untuk mencegah keamanan melalui ketidakjelasan, penerjemah harus ditulis dalam bahasa di atas 100 indeks TIOBE ini dan memiliki kompiler / penerjemah yang tersedia secara bebas.
- Penerjemah tidak boleh menafsirkan bahasa yang diterbitkan sebelum tantangan ini.
- Penerjemah harus sesuai dengan posting Anda dan tidak di-host secara eksternal.
- Penerjemah harus deterministik
- Penerjemah harus portabel dan mengikuti standar bahasanya sendiri; jangan gunakan perilaku atau bug yang tidak terdefinisi
- Jika program solusi terlalu panjang untuk cocok dengan jawaban, Anda harus memposting program yang menghasilkannya.
- Program solusi harus hanya terdiri dari ASCII yang dapat dicetak dan baris baru.
- Anda harus menjalankan program solusi Anda dalam waktu kurang dari 1 jam di komputer Anda sendiri untuk masing-masing input contoh di atas.
- Program harus bekerja untuk bilangan bulat apa pun yang kurang dari 10 6 , dan sejumlah bilangan bulat kurang dari 10 6 (tidak harus dalam waktu kurang dari satu jam), asalkan total panjang input kurang dari 10 9 .
- Agar aman, seorang polisi harus mengedit program solusi menjadi jawaban setelah 8 hari berlalu.
Mencetak gol
Polisi yang menjadi aman dengan skor tertinggi, dan skor positif, memenangkan pertanyaan ini.
Jawaban:
Changeling (aman)
ShapeScript
ShapeScript adalah bahasa pemrograman yang muncul secara alami. Shape shifter (atau Perubahan , karena mereka lebih suka disebut) dapat berubah menjadi seperangkat instruksi yang memungkinkan mereka untuk memproses data.
ShapeScript adalah bahasa berbasis tumpukan dengan sintaksis yang relatif sederhana. Tidak mengherankan, sebagian besar kesepakatan bawaannya dengan mengubah bentuk string. Ditafsirkan, karakter demi karakter, sebagai berikut:
'
dan"
mulai string literal.Sampai kutipan yang cocok ditemukan dalam kode sumber, semua karakter di antara kutipan yang cocok ini dikumpulkan dalam sebuah string, yang kemudian didorong pada tumpukan.
0
untuk9
mendorong bilangan bulat 0 hingga 9 pada tumpukan. Perhatikan bahwa10
mendorong dua bilangan bulat.!
muncul string dari tumpukan, dan mencoba untuk mengevaluasinya sebagai ShapeScript.?
muncul bilangan bulat dari tumpukan, dan mendorong salinan item tumpukan pada indeks itu.Indeks 0 sesuai dengan item tumpukan paling atas (LIFO) dan indeks -1 ke paling bawah.
_
muncul iterable dari stack, dan mendorong panjangnya.@
muncul dua item dari tumpukan, dan mendorongnya dalam urutan terbalik.$
muncul dua string dari tumpukan, dan pisahkan yang terbawah pada kejadian yang paling atas. Daftar yang dihasilkan didorong sebagai imbalan.&
muncul string (paling atas) dan iterable dari stack, dan bergabung iterable, menggunakan string sebagai pemisah. String yang dihasilkan didorong sebagai balasan.Jika ShapeScript digunakan di planet kita, karena ular adalah Changelings kerabat terdekat di Bumi, semua karakter lain c pop dua item x dan y (paling atas) dari stack, dan berusaha untuk mengevaluasi kode Python
x c y
.Misalnya, urutan karakter
23+
akan mengevaluasi2+3
, sedangkan urutan karakter"one"3*
akan mengevaluasi'one'*3
, dan urutan karakter1''A
akan mengevaluasi1A''
.Dalam kasus terakhir, karena hasilnya adalah Python tidak valid, Changeling akan mengeluh bahwa bentuknya saat ini adalah unpurposed (kesalahan sintaks), karena itu tidak benar ShapeScript.
Sebelum mengeksekusi kode, interpreter akan menempatkan seluruh input pengguna dalam bentuk string pada stack. Setelah mengeksekusi kode sumber, juru bahasa akan mencetak semua item pada tumpukan. Jika ada bagian di antara gagal, Changeling akan mengeluh bahwa bentuknya saat ini tidak memadai (kesalahan runtime).
Bentuk bergeser
Dalam keadaan alami mereka, Perubahan tidak mengambil bentuk dari ShapeScript. Namun, beberapa dari mereka dapat berubah menjadi satu kode sumber potensial (yang belum tentu berguna atau bahkan secara sintaksis valid).
Semua Perubahan yang memenuhi syarat memiliki bentuk alami berikut:
Semua baris harus memiliki jumlah karakter yang sama.
Semua baris harus terdiri dari karakter ASCII yang dapat dicetak, diikuti oleh satu linefeed.
Jumlah garis harus sesuai dengan jumlah karakter yang dapat dicetak per baris.
Misalnya, urutan byte
ab\ncd\n
adalah Changeling yang memenuhi syarat.Dalam upayanya untuk beralih ke ShapeScript, Changeling mengalami transformasi berikut:
Awalnya, tidak ada kode sumber.
Untuk setiap baris berikut terjadi:
Akumulator Changeling diatur ke nol.
Untuk setiap karakter c dari baris (termasuk trafeed linefeed), titik kode c adalah XOR dengan akumulator dibagi 2, dan karakter Unicode yang sesuai dengan titik kode yang dihasilkan ditambahkan ke kode sumber.
Setelah itu, perbedaan antara titik kode c dan titik kode spasi (32) ditambahkan ke akumulator.
Jika ada bagian di atas gagal, Changeling akan mengeluh bahwa bentuknya saat ini tidak menyenangkan.
Setelah semua baris diproses, transformasi Changeling menjadi ShapeScript (mudah-mudahan valid) selesai, dan kode yang dihasilkan dieksekusi.
Solusi (ShapeScript)
ShapeScript sebenarnya ternyata cukup bermanfaat; bahkan dapat melakukan pengujian primality ( bukti ) dan karena itu memenuhi definisi bahasa pemrograman kami.
Saya telah menerbitkan ulang ShapeScript di GitHub , dengan sintaks yang sedikit dimodifikasi dan I / O yang lebih baik.
Kode melakukan hal berikut:
Solusi (Changeling)
Seperti semua program Changeling, kode ini memiliki linefeed tambahan.
ShapeScript akan segera melakukan kesalahan pada karakter apa pun yang tidak dimengerti, tetapi kita dapat mendorong string sewenang-wenang sebagai pengisi dan pop mereka nanti. Hal ini memungkinkan kita untuk menempatkan hanya sejumlah kecil kode pada setiap baris (di awal, di mana akumulator kecil), diikuti oleh pembukaan
"
. Jika kita memulai baris berikutnya dengan"#
, kita menutup dan memunculkan string tanpa memengaruhi kode sebenarnya.Selain itu, kita harus mengatasi tiga hambatan kecil:
String panjang dalam kode ShapeScript adalah token tunggal, dan kami tidak akan dapat memasangnya pada satu baris.
Kami akan mendorong string ini dalam potongan (
'@'
,'1?'
, dll), yang akan kita gabungkan nanti.Titik kode
_
agak tinggi, dan mendorong'_'
akan bermasalah.Namun, kami dapat mendorong
'_@'
dengan mudah, diikuti oleh yang lain'@'
untuk membatalkan swap.Kode ShapeScript Changeling kami akan menghasilkan terlihat seperti ini 1 :
Saya menemukan kode Changeling dengan menjalankan kode ShapeScript di atas melalui konverter ini . 2
Penerjemah (Python 3)
1 Setiap baris diisi dengan sampah acak dengan jumlah baris, dan umpan baris tidak benar-benar ada.
2 Angka-angka di bagian bawah menunjukkan titik kode terendah dan tertinggi dalam kode Changeling, yang harus tetap antara 32 dan 126.
sumber
0"#002?'+'&'0'$'0?2?-@2?>*+00'&!++'1'*'0'+@1?$0?''&@_2-2?*@+@"3*!@#
. Saya sudah menyerah menemukan Changeling untuk itu, meskipun. Bahkan diselingi dengan pernyataan yang kebanyakan tidak berguna, saya belum bisa mendapatkan lebih dari 20 byte.Acak (ditulis dalam C ++), Retak! oleh Martin
Sunting Martin memecahkannya. Untuk melihat solusinya, klik tautannya. Solusi saya juga telah ditambahkan.
Edit perintah Tetap
print-d
untuk dapat menangani register dan tumpukan. Karena ini adalah perintah debug yang tidak diizinkan dalam suatu solusi, ini seharusnya tidak memengaruhi siapa pun yang menggunakan penerjemah versi sebelumnya.Saya masih baru dalam hal ini, jadi jika ada yang salah dengan jawaban atau penerjemah saya, beri tahu saya. Silakan minta klarifikasi jika ada sesuatu yang tidak jelas.
Saya tidak membayangkan bahwa ini akan terlalu sulit, tetapi mudah-mudahan ini akan memberikan semacam tantangan. Apa yang membuat shuffle cukup tidak dapat digunakan adalah bahwa ia hanya akan mencetak ketika segala sesuatunya ada di tempatnya.
-> Dasar-dasar:
Ada 24 tumpukan, kami menyebutnya
stack1, ... stack24
. Tumpukan ini hidup dalam daftar. Pada awal setiap program, tumpukan ini memiliki nol dorongan dan mereka mulai di tempat yang tepat, yaitu tumpukan i pada posisi engan dalam daftar (Perhatikan bahwa kami akan mengindeks mulai dari 1, tidak seperti C ++). Selama program berlangsung, urutan tumpukan dalam daftar akan bergeser. Ini penting karena alasan yang akan dijelaskan ketika saya membahas perintah.Ada 5 register yang tersedia untuk digunakan. Mereka diberi nama
Alberto
,Gertrude
,Hans
,Leopold
,ShabbySam
. Masing-masing diatur ke nol pada awal program.Jadi, pada permulaan program apa pun, ada 24 tumpukan, masing-masing memiliki nomor yang cocok dengan indeksnya dalam daftar tumpukan. Setiap tumpukan memiliki tepat satu nol di atas. Masing-masing dari lima register diinisialisasi ke nol.
-> Perintah dan Sintaks :
Ada 13 perintah (perintah debugging +1) yang tersedia di Acak. Mereka adalah sebagai berikut
cinpush
perintah ini tidak membutuhkan argumen. Itu menunggu input baris perintah dengan cara yang dijelaskan dalam pertanyaan (input lain akan mengarah pada hasil yang tidak ditentukan / tidak ditentukan). Kemudian membagi string input menjadi bilangan bulat, misalnya101011100
->1,1,3
. Untuk setiap input yang diterima, ia melakukan hal berikut: (1) memungkinkan daftar tumpukan berdasarkan nilai. Biarkan nilai integer yang dimaksud disebut a . Jika a kurang dari 10 itu permutasi u . Jika a adalah antara 9 dan 30 (tidak termasuk) ia melakukan permutasi d . Kalau tidak, itu permutasi r . (2) Ini kemudian mendorong ake tumpukan yang pertama dalam daftar. Perhatikan bahwa saya tidak bermaksudstack1
(walaupun mungkin itu yangstack1
pertama dalam daftar). Permutasi didefinisikan di bawah ini. Karenacinpush
satu-satunya cara untuk mendapatkan input pengguna , itu harus muncul dalam solusi apa pun.mov value register
Themov
perintah pada dasarnya adalah tugas variabel. Itu ditugaskanvalue
untukregister
.value
dapat mengambil beberapa bentuk: bisa berupa (1) bilangan bulat, misalnya47
(2) nama register yang berbeda, misalnyaHans
(3) indeks tumpukan diikuti dengan 's', misalnya4s
. Perhatikan bahwa ini adalah indeks dalam daftar, bukan jumlah tumpukan. Dengan demikian, jumlahnya tidak boleh melebihi 24.Beberapa
mov
contoh:movfs index register
Ini adalah singkatan dari 'move from stack'. Ini mirip denganmov
perintah. Itu ada sehingga Anda dapat mengakses tumpukan yang diindeks oleh register. Misalnya, jika sebelumnya Anda menetapkan Hans sama dengan 4 (mov 4 Hans
) Maka Anda dapat menggunakanmovfs Hans Gertrude
untuk mengatur Gertrude sama dengan bagian atas tumpukan 4. Jenis perilaku ini tidak dapat diakses hanya dengan menggunakanmov
.inc register
meningkatkan nilai register sebesar 1.dec register
mengurangi nilai register sebesar 1.compg value value register
Ini berarti 'bandingkan lebih besar'. Ini mengatur register sama dengan yang lebih besar dari dua nilai.value
bisa berupa bilangan bulat, register, atau indeks tumpukan diikuti oleh 's', seperti di atas.compl value value register
'bandingkan lebih rendah' sama seperti di atas, kecuali mengambil nilai lebih kecil.gte value1 value2 register
Cek jikavalue1 >= value2
kemudian masukkan nilai Boolean (seperti 1 atau 0)register
.POP!! index
muncul di bagian atas tumpukan diindeks olehindex
dalam daftar tumpukan.jmp label
melompat tanpa syarat ke labellabel
. Ini adalah saat yang tepat untuk membicarakan label. Label adalah kata yang diikuti oleh ':'. Interpreter pra-parsing untuk label, sehingga Anda dapat melompat ke depan untuk label dan juga kembali.jz value label
melompat kelabel
jikavalue
nol.jnz value label
melompat kelabel
jikavalue
bukan nol.Contoh label dan lompat:
"shuffle" permutation
Ini adalah perintah shuffle. Ini memungkinkan Anda untuk mengubah daftar tumpukan. Ada tiga permutasi valid yang dapat digunakan sebagai argumen,l
,f
, danb
.print register
Ini memeriksa apakah semua tumpukan berada di posisi awalnya, yaitu tumpukan i berada pada indeks i dalam daftar tumpukan. Jika ini masalahnya, ia mencetak nilairegister
di unary. Kalau tidak, itu mencetak kesalahan buruk. Seperti yang Anda lihat, untuk menghasilkan apa pun, tumpukan harus berada di tempat yang benar.done!
ini memberitahu program untuk berhenti tanpa kesalahan. Jika program berakhir tanpadone!
, itu akan mencetak ke konsol nomor di atas setiap tumpukan diikuti oleh nomor tumpukan itu. Urutan tumpukan dicetak adalah urutan yang muncul dalam daftar tumpukan. Jika tumpukan kosong, itu akan dihilangkan. Perilaku ini untuk tujuan debugging dan mungkin tidak digunakan dalam solusi.print-d value
ini mencetak nilai dari stack, register, atau integer diberikan (untuk mengakses stack i , lulusis
sebagai argumen, seperti yang dijelaskan di atas). Ini adalah alat debugging dan bukan bagian dari bahasa, karena itu tidak diizinkan dalam solusi.-> Ini adalah kode juru bahasa
Semua penguraian terjadi di fungsi utama. Di sinilah Anda akan menemukannya parsing untuk perintah tertentu.
-> Permutasi Permutasi memungkinkan elemen-elemen dari daftar tumpukan dengan cara berikut:
Dimana artinya
(Ini juga muncul dalam kode juru bahasa. Jika ada perbedaan, juru bahasa benar.)
-> Contoh Sederhana
Dua program sederhana ini mencetak angka dari 24 menjadi 1 (tanpa tanda) tanpa spasi.
atau
Mereka adalah program yang sama.
Penjelasan dan Solusi:
Martin juga memiliki penjelasan yang bagus dalam jawabannya .
Seperti yang diketahui Martin, bahasa ini terinspirasi oleh kubus saku (alias kubus 2x2 Rubik). 24 tumpukan itu seperti 24 kotak individu pada kubus. Permutasi adalah gerakan dasar yang diizinkan: atas, bawah, kanan, kiri, depan, belakang.
Perjuangan utama di sini adalah ketika nilai didorong, hanya tiga gerakan yang digunakan: atas, bawah, dan kanan. Namun, Anda tidak memiliki akses ke gerakan ini saat "mengocok" tumpukan. Anda hanya memiliki tiga gerakan lainnya.
Ternyata, kedua set dari tiga gerakan sebenarnya menjangkau seluruh kelompok (yaitu generator), sehingga masalahnya dapat dipecahkan. Ini berarti bahwa Anda benar-benar dapat menyelesaikan kubus 2x2 Rubik hanya menggunakan 3 langkah.
Yang tersisa untuk dilakukan adalah mencari tahu cara membatalkan gerakan naik, turun, dan kanan menggunakan tiga lainnya. Untuk tujuan ini, saya menggunakan sistem aljabar komputer yang disebut GAP .
Setelah membatalkan permutasi, menemukan angka terbesar ketiga cukup sepele.
sumber
Brian & Chuck , Retak oleh cardboard_box
Saya telah tertarik untuk beberapa waktu sekarang oleh gagasan bahasa pemrograman di mana dua program berinteraksi satu sama lain (mungkin terinspirasi oleh ROCB ). Tantangan ini adalah insentif yang bagus untuk menangani konsep ini pada akhirnya sambil berusaha menjaga bahasa seminimal mungkin. Tujuan desainnya adalah untuk membuat bahasa Turing-lengkap sementara masing-masing bagian secara individual tidak Turing-lengkap. Selain itu, bahkan keduanya bersama-sama tidak boleh Turing-lengkap tanpa memanfaatkan manipulasi kode sumber. Saya pikir saya sudah berhasil dengan itu, tetapi saya belum membuktikan semua itu secara formal. Jadi tanpa basa-basi lagi saya hadir untuk Anda ...
Protagonis
Brian dan Chuck adalah dua program seperti Brainfuck. Hanya satu dari mereka yang dieksekusi pada waktu tertentu, dimulai dengan Brian. Tangkapannya adalah bahwa rekaman memori Brian juga merupakan kode sumber Chuck. Dan kaset memori Chuck juga merupakan kode sumber Brian. Selain itu, kepala kaset Brian juga merupakan penunjuk instruksi Chuck dan sebaliknya. Kaset semi-tak terbatas (yaitu tak terbatas ke kanan) dan dapat menyimpan bilangan bulat presisi arbitrer yang ditandatangani, diinisialisasi ke nol (kecuali ditentukan lain oleh kode sumber).
Karena kode sumber juga merupakan pita memori, perintah secara teknis ditentukan oleh nilai integer, tetapi sesuai dengan karakter yang masuk akal. Perintah berikut ada:
,
(44
): Baca byte dari STDIN ke dalam sel memori saat ini. Hanya Brian yang bisa melakukan ini. Perintah ini adalah no-op untuk Chuck..
(46
): Tulis sel memori saat ini, modulo 256, sebagai byte ke STDOUT. Hanya Chuck yang bisa melakukan ini. Perintah ini adalah no-op untuk Brian.+
(43
): Meningkatkan sel memori saat ini.-
(45
): Mengurangi sel memori saat ini.?
(63
): Jika sel memori saat ini nol, ini adalah larangan. Kalau tidak, serahkan kontrol ke program lain. Kaset kepala pada program yang menggunakan?
akan tetap di?
. Kepala tape program lain akan memindahkan satu sel ke kanan sebelum menjalankan perintah pertama (sehingga sel yang digunakan sebagai tes tidak dieksekusi sendiri).<
(60
): Pindahkan kepala kaset satu sel ke kiri. Ini adalah no-op jika kepala pita sudah di ujung kiri pita.>
(62
): Pindahkan kepala kaset satu sel ke kanan.{
(123
): Gerakkan kepala pita berulang kali ke kiri hingga sel saat ini nol atau ujung kiri pita tercapai.}
(125
): Gerakkan kepala kaset berulang kali ke kanan hingga sel saat ini nol.Program berakhir ketika pointer instruksi program aktif mencapai titik di mana tidak ada instruksi lagi di sebelah kanannya.
Kode Sumber
File sumber diproses sebagai berikut:
```
, file akan dipecah menjadi dua bagian di sekitar kemunculan pertama string itu. Semua spasi putih terkemuka dan tertinggal dilucuti dan bagian pertama digunakan sebagai kode sumber untuk Brian dan bagian kedua untuk Chuck._
di kedua program diganti dengan byte NULL.Sebagai contoh, file sumber berikut
Akan menghasilkan kaset awal berikut:
Penerjemah
Penerjemah ditulis dalam Ruby. Dibutuhkan dua flag baris perintah yang tidak boleh digunakan oleh solusi apa pun (karena mereka bukan bagian dari spesifikasi bahasa aktual):
-d
: Dengan bendera ini, Brian dan Chuck memahami dua perintah lagi.!
akan mencetak representasi string dari kedua kaset memori, program aktif yang terdaftar pertama (^
akan menandai kepala kaset saat ini).@
juga akan melakukan ini, tetapi kemudian segera menghentikan program. Karena saya malas, tak satu pun dari mereka yang berfungsi jika mereka adalah perintah terakhir dalam program, jadi jika Anda ingin menggunakannya di sana, ulangi atau tulis no-op setelahnya.-D
: Ini adalah mode debug verbal. Ini akan mencetak informasi debug yang sama seperti!
setelah setiap centang.@
juga berfungsi dalam mode ini.Ini kodenya:
Inilah solusi saya sendiri (tulisan tangan) untuk masalah ini:
Kode ini dapat dijalankan seperti apa adanya, karena semua anotasi menggunakan no-ops dan dilewati oleh
{
dan}
.Ide dasarnya adalah:
1
s, tambahkan elemen itu.Saat kita membaca
0
, lakukan pembersihan. Jika bilangan bulat yang dihasilkan lebih besar dari nol, kembali ke 1.Sekarang kita punya daftar nomor input di akhir rekaman Chuck dan kita tahu panjang daftar itu.
Kurangi 2 dari panjang daftar (jadi langkah-langkah berikut mengabaikan dua elemen terbesar), sebut ini
N
.Sementara
N > 0
, tambahkan total yang berjalan dan kemudian kurangi semua elemen daftar. Setiap kali elemen daftar mencapai nol, penurunanN
.Pada akhir ini, total yang berjalan akan berisi angka terbesar ketiga dalam input
M
,.Tulis
M
salinan.
hingga akhir kaset Chuck.1
kaset Brian dan jalankan yang dihasilkan.
di akhir.Setelah menyelesaikan ini saya menyadari bahwa saya bisa menyederhanakannya di beberapa tempat. Misalnya, alih-alih melacak penghitung itu dan menulisnya
.
ke kaset Chuck, saya bisa langsung mencetaknya1
, setiap kali sebelum saya mengurangi semua elemen daftar. Namun, membuat perubahan pada kode ini cukup menyebalkan, karena menyebarkan perubahan lain di semua tempat, jadi saya tidak repot-repot melakukan perubahan.Bit yang menarik adalah bagaimana melacak daftar dan cara mengulanginya. Anda tidak bisa hanya menyimpan angka berurutan di kaset Chuck, karena jika Anda ingin memeriksa kondisi pada salah satu elemen daftar, Anda berisiko mengeksekusi sisa daftar yang mungkin berisi kode yang valid. Anda juga tidak tahu berapa lama daftar itu, jadi Anda tidak bisa hanya menyimpan sedikit ruang di depan kode Chuck.
Masalah selanjutnya adalah kita perlu membiarkan daftar menurun
N
ketika kita sedang memprosesnya, dan kita harus kembali ke tempat yang sama seperti sebelumnya. Tapi{
dan}
akan melewati seluruh daftar.Jadi kita perlu menulis beberapa kode secara dinamis ke Chuck. Faktanya, setiap elemen daftar
i
memiliki bentuk:1
adalah penanda yang dapat kita atur ke nol untuk menunjukkan di mana kita tinggalkan memproses daftar. Tujuannya adalah untuk menangkap{
atau}
yang hanya akan melewati kode dani
. Kami juga menggunakan nilai ini untuk memeriksa apakah kami berada di akhir daftar selama pemrosesan, jadi sementara kami tidak, ini akan menjadi1
dan kondisional?
akan beralih kontrol ke Chuck.Code A
digunakan untuk menangani situasi itu dan memindahkan IP pada Brian yang sesuai.Sekarang ketika kita mengurangi
i
kita perlu memeriksa apakahi
sudah nol. Meskipun tidak,?
akan kembali beralih kontrol, begituCode B
juga untuk mengatasinya.sumber
HPR, ditulis dalam Python 3 ( Cracked oleh TheNumberOne )
HPR (namanya tidak berarti) adalah bahasa untuk memproses daftar bilangan bulat. Ini dirancang untuk menjadi minimalis , sangat terbatas , dan bebas dari batasan "buatan" . Memprogram dalam HPR itu menyakitkan, bukan karena Anda harus memecahkan teka-teki untuk mencegah penerjemah meneriaki Anda, tetapi karena sulit membuat program melakukan sesuatu yang bermanfaat. Saya tidak tahu apakah HPR mampu melakukan sesuatu yang jauh lebih menarik daripada menghitung elemen terbesar ketiga dalam daftar.
Spesifikasi bahasa
Program HPR dijalankan di lingkungan , yang merupakan kumpulan bilangan bulat non-negatif bebas-unordered dan daftar bilangan bulat non-negatif. Awalnya, lingkungan hanya berisi daftar input (penerjemah menguraikannya untuk Anda). Ada tiga perintah dan dua operator "aliran kontrol" yang mengubah lingkungan:
*
menghapus elemen pertama dari setiap daftar yang tidak kosong di lingkungan, dan menempatkannya di lingkungan. Daftar kosong tidak terpengaruh. Misalnya, itu berubah-
mengurangi semua angka di lingkungan, dan kemudian menghilangkan elemen negatif. Misalnya, itu berubah$
memutar setiap daftar di lingkungan satu langkah ke kiri. Misalnya, itu berubah!(A)(B)
, di manaA
danB
program, pada dasarnya adalah sebuahwhile
loop. Ia melakukan "aksi"A
sampai "tes"B
akan menghasilkan lingkungan kosong. Ini dapat menghasilkan loop tak terbatas.#(A)(B)
, di manaA
danB
program, berlakuA
danB
untuk lingkungan saat ini dan mengambil perbedaan hasil simetris.Perintah dijalankan dari kiri ke kanan. Pada akhirnya, ukuran lingkungan dicetak secara unary.
Penerjemah
Penerjemah ini memiliki fitur perintah debug
?
, yang mencetak lingkungan tanpa mengubahnya. Seharusnya tidak muncul dalam solusi apa pun untuk tugas tersebut. Setiap karakter kecuali*-$!#()?
diabaikan, sehingga Anda dapat menulis komentar langsung ke dalam kode. Akhirnya, interpreter mengenali idiom!(A)(#(A)())
sebagai "performA
sampai hasilnya tidak lagi berubah", dan optimalkan untuk kecepatan ekstra (saya membutuhkannya untuk mendapatkan solusi saya untuk menyelesaikan kurang dari satu jam pada test case terakhir).Solusi saya
Solusi referensi saya adalah 484 byte, jadi cukup pendek dibandingkan dengan program 3271-byte TheNumberOne. Ini kemungkinan besar karena sistem makro TheNumberOne yang canggih dan mengagumkan yang dikembangkan untuk pemrograman dalam HPR. Gagasan utama dalam kedua program kami serupa:
Namun, sejauh yang saya tahu, detail implementasi yang tepat sangat berbeda. Inilah solusi saya:
Dan inilah program Python yang berkomentar yang menghasilkannya (tidak ada yang mewah di sini, hanya manipulasi string dasar untuk menghilangkan semua pengulangan):
sumber
TKDYNS (Untuk Membunuh Naga, Kamu Membutuhkan Pedang) - Retak oleh Martin Büttner
EDIT: Saya telah menambahkan solusi dan penjelasan saya di bawah posting utama.
Latar Belakang
Dalam bahasa ini, Anda mengendalikan seorang pejuang pemberani yang telah ditugaskan untuk membunuh naga yang mengerikan. Naga itu hidup di labirin bawah tanah, penuh bahaya dan bahaya, dan sampai sekarang, tidak ada yang bisa memetakannya dan bertahan hidup. Ini berarti Anda harus menavigasi jalan ke naga dalam kegelapan pekat, dengan apa-apa selain intuisi dan keberanian untuk membimbing Anda.
...
Ya tidak cukup. Anda telah membawa persediaan antek sekali pakai yang hampir tanpa batas, dan mereka bersedia untuk mendahului Anda untuk menemukan rute yang aman. Sayangnya, semuanya setebal dua papan pendek, dan hanya akan melakukan persis apa yang Anda perintahkan. Terserah Anda untuk menemukan metode cerdas untuk memastikan bahwa antek Anda menemukan jalan yang benar.
Lebih detail
Sarang naga berbentuk kotak 10x10. Di antara titik-titik yang berdekatan di grid, ada jalan sempit; di antara yang lain, ada jurang yang dalam dan kematian yang pasti. Contoh tata letak untuk kisi 4x4 mungkin sebagai berikut:
Anda tahu bahwa selalu ada cara untuk mendapatkan dari satu titik ke titik lain, tetapi tidak lebih dari yang telah diungkapkan kepada Anda.
Untuk berhasil mengalahkan naga, pertama-tama Anda perlu mengumpulkan beberapa item yang Anda dapat gabungkan bersama untuk membuat pisau pembunuh naga ajaib. Mudahnya, semua potongan untuk senjata ini telah tersebar di sekitar sarang naga. Anda hanya perlu mengumpulkannya.
Memelintir adalah bahwa setiap bagian dari senjata telah terperangkap dalam tubuh. Setiap kali dikumpulkan, tata letak trotoar berubah. Jalur yang sebelumnya aman sekarang bisa mengarah pada kematian, dan sebaliknya.
Perintah
Hanya ada 5 perintah yang valid.
<
- Ambil langkah ke kiri>
- Ambil langkah ke kanan^
- Ambil langkah ke atasv
- Ambil langkah ke bawahc
- Kumpulkan barang-barang yang berada di posisi Anda saat ini. Jika ada item, tata letak sarang berubah. Dengan posisi yang dinomori dalam baris di atas, ambil modulo posisi Anda 10. Ada 10 tata letak yang dikodekan secara keras ke dalam juru bahasa, dan tata letak berubah menjadi yang sesuai. Misalnya, jika Anda berada di posisi 13, maka tata letak berubah menjadilayouts[3]
Layout yang muncul di interpeter telah dikodekan ke integer dengan cara berikut:
Tata letak kosong dikodekan ke nol.
Untuk setiap tepi dalam tata letak, biarkan
x
yang lebih kecil dari dua posisi yang digabungkan.Jika langkahnya horizontal, tambahkan
2^(2*x)
ke pengkodean (itu kekuatan, bukan XOR)Jika langkahnya vertikal, tambahkan
2^(2*x + 1)
ke pengkodean.Alur eksekusi
Interpreter dijalankan dengan nama file sumber sebagai argumen baris perintah.
Ketika penerjemah dijalankan, itu akan meminta pengguna untuk memberikan pencarian. Input ini harus dalam bentuk yang dijelaskan dalam pertanyaan, dan menentukan lokasi di sarang komponen senjata. Secara khusus, setiap integer input diambil modulo 100, dan ditempatkan di lokasi yang sesuai di sarang.
Setiap program sumber terdiri dari beberapa baris, setiap baris terdiri dari beberapa urutan 5 karakter yang valid di atas. Garis-garis ini mewakili kaki tangan Anda. Anda, sang pejuang, melacak urutan tindakan yang diketahui aman. Awalnya, Anda tidak tahu apa-apa tentang sarang, jadi urutan ini kosong. Mengambil setiap antek secara bergantian, berikut ini dilakukan, mulai dari posisi 0:
Minion diinstruksikan untuk melakukan semua tindakan yang diketahui aman, diikuti oleh tindakan dalam baris kode sendiri.
Jika antek mati pada titik mana pun, Anda diberi tahu tentang hal ini, dan sarang akan kembali ke konfigurasi awalnya. Semua item diganti, dan jalan setapak kembali ke posisi awal mereka.
Sebaliknya, jika antek itu bertahan, maka Anda tetap menguapnya - itu hanya antek. Seperti sebelumnya, ini memicu pengaturan ulang sarang ke keadaan awal, tetapi kali ini, Anda menambahkan tindakan dari baris kode antek ke urutan tindakan yang diketahui aman.
Setelah semua antek habis, Anda, prajurit, melakukan semua tindakan yang diketahui aman, sekali lagi mulai dari posisi 0. Ada dua hasil yang mungkin:
Anda mengumpulkan semua bagian senjata - dalam hal ini, Anda berhasil membunuh naga itu, dan pesan kemenangan yang menarik adalah output. Pesan kemenangan ini akan berisi, di antara karakter lain
n
, di manan
angka tertinggi ketiga diberikan sebagai input.Anda gagal mengumpulkan beberapa bagian senjata - dalam kasus ini, naga hidup terus, dan Anda gagal dalam pencarian Anda.
Kode juru bahasa (Python 2)
Semoga sukses, prajurit gagah berani.
Solusi dan penjelasan saya
Berikut ini adalah skrip Python yang menghasilkan kode sumber untuk menyelesaikan masalah. Yang menarik, kode sumber terakhir Martin sekitar 5 kali lebih kecil dari kode yang dihasilkan oleh skrip saya. Di sisi lain, skrip saya untuk menghasilkan kode adalah sekitar 15 kali lebih kecil daripada program Mathematica Martin ...
Struktur dasar
Ini menghasilkan 990 baris kode sumber, yang datang dalam kelompok 10. 10 baris pertama semuanya berisi instruksi yang mencoba untuk memindahkan antek dari posisi
0
ke posisi1
, dan kemudian mengumpulkan item - satu set untuk setiap tata letak yang mungkin. 10 baris berikutnya semuanya berisi instruksi yang mencoba untuk memindahkan antek dari posisi1
ke posisi2
, dan kemudian mengumpulkan item. Dan seterusnya ... Jalur ini dihitung denganpath
fungsi dalam skrip - hanya melakukan pencarian kedalaman-pertama yang sederhana.Jika kita dapat memastikan bahwa, di setiap kelompok 10, tepatnya satu antek berhasil, maka kita akan menyelesaikan masalah.
Masalah dengan pendekatan
Ini mungkin tidak selalu menjadi kasus yang tepat satu antek dari kelompok 10 berhasil - misalnya, antek dirancang untuk mendapatkan dari posisi
0
ke posisi1
mungkin sengaja berhasil bergerak dari posisi1
ke posisi2
(karena kesamaan dalam layout), dan bahwa salah perhitungan akan menyebar melalui, berpotensi menyebabkan kegagalan.Bagaimana memperbaikinya
Perbaikan yang saya gunakan adalah sebagai berikut:
Untuk setiap antek yang berusaha bergerak dari posisi
n
ke posisin+1
, pertama-tama buat dia berjalan dari posisin
ke posisi0
(sudut kiri atas) dan kembali lagi, kemudian dari posisin
ke posisi99
(sudut kanan bawah) dan kembali lagi. Instruksi ini hanya dapat dilakukan dengan aman dari posisin
- posisi awal lainnya dan antek akan berjalan menjauh.Oleh karena itu, instruksi tambahan ini mencegah antek agar tidak sengaja pergi ke suatu tempat yang tidak seharusnya, dan ini memastikan bahwa satu antek dari masing-masing kelompok 10 berhasil. Perhatikan bahwa belum tentu antek yang Anda harapkan - mungkin antek yang percaya bahwa dia ada di tata letak 0 berhasil, bahkan ketika kita benar-benar di tata letak 7 - tetapi dalam kasus apa pun, fakta bahwa kita memiliki sekarang perubahan posisi berarti bahwa semua antek lainnya dalam grup akan mati. Langkah-langkah tambahan ini dihitung oleh
assert_at
fungsi, dansafe_path
fungsi mengembalikan jalur yang merupakan gabungan dari langkah-langkah tambahan ini dengan jalur biasa.sumber
Firetype, Cracked oleh Martin Büttner
Campuran yang sangat aneh dari BF dan CJam. Dan siapa yang tahu apa lagi! Cukup yakin ini akan menjadi mudah, tapi itu tetap menyenangkan. FYI, namanya mengacu pada Vermillion Fire dari Final Fantasy Type-0 .
CATATAN : Maafkan saya atas ambiguitas dalam uraian ini. Saya bukan penulis terbaik ...: O
Martin memecahkan ini dengan sangat cepat! Ini adalah program asli saya untuk menyelesaikan masalah:
Sintaksis
Skrip Firetype pada dasarnya adalah daftar baris. Karakter pertama dari setiap baris adalah perintah untuk dijalankan. Baris kosong pada dasarnya adalah NOP.
Semantik
Anda memiliki array bilangan bulat dan pointer (pikirkan BF). Anda dapat memindahkan elemen ke kiri dan ke kanan atau "mendorong" ke dalam array.
Mendorong
Saat Anda "mendorong" suatu elemen dan Anda berada di ujung array, elemen tambahan akan ditambahkan ke bagian akhir. Jika Anda tidak pada akhirnya, elemen berikutnya akan diganti. Apapun, pointer akan selalu bertambah.
Perintah
_
Dorong nol ke array.
+
Tambahkan elemen pada pointer saat ini.
-
Mengurangi elemen di pointer saat ini.
*
Gandakan elemen pada pointer saat ini.
/
Membagi dua elemen pada pointer saat ini.
%
Ambil elemen pada pointer saat ini dan lompat ke depan banyak garis, dan gerakkan pointer ke kiri. Jika nilainya negatif, sebaliknya melompat mundur.
=
Ambil elemen pada pointer saat ini dan lompat ke garis itu + 1. Misalnya, jika elemen saat ini
0
, ini akan melompat ke garis1
. Ini juga memindahkan pointer ke kiri.,
Baca karakter dari input standar dan dorong nilai ASCII-nya.
^
Ambil elemen pada pointer saat ini, menafsirkannya sebagai nilai ASCII untuk karakter, dan mengubahnya menjadi integer. Misalnya, jika nilai saat ini adalah
49
(nilai ASCII1
), elemen pada pointer saat ini akan ditetapkan ke integer1
..
Tulis nomor saat ini ke layar.
!
Ambil elemen pada pointer saat ini dan ulangi baris berikutnya yang berkali-kali. Juga menggerakkan pointer ke kiri.
<
Pindahkan penunjuk ke kiri. Jika Anda sudah di awal, kesalahan dilemparkan.
>
Pindahkan penunjuk ke kanan. Jika Anda sudah di bagian akhir, kesalahan terjadi.
~
Jika elemen saat ini bukan nol, gantilah dengan
0
; jika tidak, ganti dengan1
.|
Kuadratkan elemen saat ini.
@
Setel elemen saat ini ke panjang array.
`
Gandakan elemen saat ini.
\
Urutkan elemen pada dan sebelum pointer.
#
Meniadakan elemen saat ini.
Penerjemah
Juga tersedia di Github .
sumber
self.ptr-1
akses, Anda mungkin harus memeriksaself.ptr>0
tidak>=0
. (Ini seharusnya tidak membatalkan program yang valid tetapi mungkin membuat beberapa program membuat pekerjaan tidak sengaja yang seharusnya.)=
set nilaiarray() - 1
, dokumentasi mengatakan+1
?Acc !! (aman)
Itu Baack ...
... dan
mudah-mudahanpasti lebih banyak jalan keluarnya.Saya sudah membaca Acc! spek. Bagaimana Acc !! berbeda?
Di Acc !! , variabel loop keluar dari ruang lingkup ketika loop keluar. Anda hanya bisa menggunakannya di dalam loop. Di luar, Anda akan mendapatkan kesalahan "nama tidak didefinisikan". Selain perubahan ini, bahasa-bahasa itu identik.
Pernyataan
Perintah diurai baris demi baris. Ada tiga jenis perintah:
Count <var> while <cond>
Menghitung
<var>
dari 0 selama<cond>
bukan nol, setara dengan C ++for(int <var>=0; <cond>; <var>++)
. Penghitung lingkaran dapat berupa huruf kecil tunggal. Kondisi dapat berupa ekspresi apa pun, tidak harus melibatkan variabel loop. Loop berhenti ketika nilai kondisi menjadi 0.Loop membutuhkan kurung kurawal gaya K&R (khususnya, varian Stroustrup ):
Seperti disebutkan di atas, variabel loop hanya tersedia di dalam loop mereka ; mencoba merujuk mereka setelah itu menyebabkan kesalahan.
Write <charcode>
Output karakter tunggal dengan nilai ASCII / Unicode yang diberikan ke stdout. Kode sandi dapat berupa ekspresi apa pun.
Ekspresi apa pun yang berdiri sendiri dievaluasi dan ditugaskan kembali ke akumulator (yang dapat diakses sebagai
_
). Jadi, misalnya,3
adalah pernyataan yang menetapkan akumulator ke 3;_ + 1
menambah akumulator; dan_ * N
membaca karakter dan mengalikan akumulator dengan kode sandi-nya.Catatan: akumulator adalah satu-satunya variabel yang dapat ditugaskan secara langsung; variabel loop dan
N
dapat digunakan dalam perhitungan tetapi tidak dimodifikasi.Akumulator awalnya 0.
Ekspresi
Ekspresi dapat menyertakan bilangan bulat integer, variabel loop (
a-z
),_
untuk akumulator, dan nilai khususN
, yang membaca karakter dan mengevaluasi karakternya setiap kali digunakan. Catatan: ini berarti Anda hanya mendapatkan satu kesempatan untuk membaca setiap karakter; lain kali Anda gunakanN
, Anda akan membaca yang berikutnya.Operator adalah:
+
, tambahan-
, pengurangan; negasi unary*
, penggandaan/
, pembagian bilangan bulat%
, modulo^
, eksponensialKurung dapat digunakan untuk menegakkan prioritas operasi. Karakter lain dalam ekspresi adalah kesalahan sintaksis.
Spasi dan komentar
Ruang putih dan baris kosong terkemuka dan tertinggal diabaikan. Spasi putih dalam header loop harus persis seperti yang ditunjukkan, dengan satu ruang antara header loop dan kurung kurawal terbuka juga. Ekspresi di dalam spasi putih adalah opsional.
#
memulai komentar satu baris.Input output
Acc !! mengharapkan satu baris karakter sebagai input. Setiap karakter input dapat diambil secara berurutan dan karakternya diproses menggunakan
N
. Mencoba membaca melewati karakter terakhir dari baris menyebabkan kesalahan. Sebuah karakter dapat di-output dengan memberikan kode-nya keWrite
pernyataan.Penerjemah
Penerjemah (ditulis dengan Python 3) menerjemahkan Acc !! kode ke Python dan
exec
s itu.Larutan
Kejatuhan Acc asli ! adalah variabel loop yang terus dapat diakses di luar loop mereka. Ini memungkinkan penyimpanan salinan akumulator, yang membuat solusinya terlalu mudah.
Di sini, tanpa lubang loop ini (maaf), kami hanya memiliki akumulator untuk menyimpan barang. Namun, untuk menyelesaikan tugas, kita perlu menyimpan empat nilai besar yang sewenang-wenang. 1 Solusinya: interleave bit mereka dan simpan nomor kombinasi yang dihasilkan di akumulator. Misalnya, nilai akumulator 6437 akan menyimpan data berikut (menggunakan bit urutan terendah sebagai flag bit tunggal):
Kita dapat mengakses bit nomor apa pun dengan membagi akumulator dengan kekuatan yang sesuai dari 2, mod 2. Ini juga memungkinkan untuk mengatur atau membalik bit individu.
Pada tingkat makro, algoritme melingkupi angka-angka unary dalam input. Bunyinya nilai ke angka 0, kemudian melakukan algoritma bubble sort untuk menempatkannya di posisi yang tepat dibandingkan dengan tiga angka lainnya. Akhirnya, ia membuang nilai yang tersisa di angka 0, karena itu adalah yang terkecil dari empat sekarang dan tidak pernah bisa menjadi terbesar ketiga. Ketika loop selesai, angka 1 adalah yang terbesar ketiga, jadi kami membuang yang lain dan mengeluarkannya.
Bagian tersulit (dan alasan saya memiliki variabel global loop dalam inkarnasi pertama) adalah membandingkan dua angka untuk mengetahui apakah akan menukar mereka. Untuk membandingkan dua bit, kita bisa mengubah tabel kebenaran menjadi ekspresi matematika; terobosan saya untuk Acc !! sedang menemukan algoritma perbandingan yang berjalan dari bit orde rendah ke orde tinggi, karena tanpa variabel global tidak ada cara untuk mengulang bit angka dari kiri ke kanan. Bit akumulator terendah menyimpan bendera yang memberi sinyal apakah akan menukar dua angka yang sedang dipertimbangkan.
Saya curiga bahwa Acc !! adalah Turing-complete, tapi saya tidak yakin saya ingin repot membuktikannya.
Inilah solusi saya dengan komentar:
1 Menurut spesifikasi pertanyaan, hanya nilai hingga 1 juta yang perlu didukung. Saya senang tidak ada yang memanfaatkan itu untuk solusi yang lebih mudah - walaupun saya tidak sepenuhnya yakin bagaimana Anda akan melakukan perbandingan.
sumber
Picofuck (aman)
Picofuck mirip dengan Smallfuck . Ini beroperasi pada pita biner yang tidak terikat di sebelah kanan, terikat di sebelah kiri. Ini memiliki perintah berikut:
>
gerakkan pointer ke kanan<
gerakkan pointer ke kiri. Jika penunjuk jatuh dari kaset, program berakhir.*
balikkan bit pada pointer(
jika bit pada pointer0
, lompat ke yang berikutnya)
)
tidak melakukan apa pun - tanda kurung di Picofuck adalahif
blok, bukanwhile
loop..
tulis untuk stdout bit pada pointer sebagai ascii0
atau1
.,
dibaca dari stdin sampai kita menghadapi0
atau1
, dan menyimpan ini dalam bit pada pointer.Kode Picofuck membungkus - setelah akhir program tercapai, ia berlanjut dari awal.
Selain itu, Picofuck melarang kurung bersarang. Tanda kurung yang muncul dalam program Picofuck harus bergantian antara
(
dan)
, dimulai dengan(
dan diakhiri dengan)
.Penerjemah
Ditulis dengan Python 2.7
pemakaian:
python picofuck.py <source_file>
Larutan
Program python 2.7 berikut menghasilkan solusi saya yang dapat ditemukan di sini
Saya dapat mengedit posting ini nanti dengan penjelasan yang lebih menyeluruh tentang cara kerjanya, tetapi ternyata Picofuck adalah Turing-complete.
sumber
PQRS - Aman! / Solusi Disediakan
Dasar-dasar
Semua instruksi yang tersirat memiliki empat operan alamat memori:
Di mana
v
ukuran memori dalam kuartet.Pᵢ
,Qᵢ
,Rᵢ
,Sᵢ
Yang bilangan bulat dalam ukuran asli mesin anda menandatangani (misalnya 16, 32 atau 64 bit) yang akan kita sebut sebagai kata-kata.Untuk setiap kuartet
i
, operasi tersirat, dengan[]
menunjukkan tipuan, adalah:Perhatikan bahwa Subleq adalah subset dari PQRS .
Subleq telah terbukti lengkap, jadi PQRS juga harus lengkap!
Struktur Program
PQRS mendefinisikan header awal sebagai berikut:
H₀ H₁ H₂ H₃
selalu merupakan instruksi pertamaP₀ Q₀ R₀ S₀
.H₀
untukH₃
perlu didefinisikan pada saat beban.PQRS memiliki I / O yang belum sempurna, tetapi cukup untuk tantangan.
H₄ H₅
: pada awal program, ia membaca maksimumH₅
ASCII karakter dari input standar dan menyimpan sebagai kata pada indeksH₄
dan seterusnya.H₄
danH₅
perlu didefinisikan pada waktu buka. Setelah membaca,H₅
akan diatur ke jumlah karakter yang dibaca (dan kata-kata disimpan).H₆ H₇
: pada saat terminasi program, mulai dari indeksH₆
, ia mencetak semua byte yang terdiri dariH₇
kata - kata ke output standar sebagai karakter ASCII.H₆
danH₇
perlu didefinisikan sebelum program berakhir. Null byte'\0'
dalam output akan dilewati.Penghentian
Pengakhiran dicapai dengan menetapkan
Sᵢ
batasi < 0
ataui ≥ v
.Trik
Kuartet
Pᵢ Qᵢ Rᵢ Sᵢ
tidak perlu disejajarkan atau berurutan, percabangan diizinkan pada interval sub-kuartet.PQRS memiliki tipuan sehingga, tidak seperti Subleq, ada cukup fleksibilitas untuk menerapkan subrutin.
Kode dapat dimodifikasi sendiri!
Penerjemah
Penerjemah ditulis dalam C:
Untuk menggunakan, simpan di atas sebagai pqrs.c lalu kompilasi:
Program sampel
Input gema hingga 40 karakter, didahului oleh 'PQRS-'.
Untuk menjalankan, simpan di atas sebagai
echo.pqrs
, lalu:Menjalankan test case:
Semua test case berjalan sangat cepat, mis. <500 ms.
Tantangan
PQRS dapat dianggap stabil, sehingga tantangannya dimulai 2015-10-31 13:00 dan berakhir pada 2015-11-08 13:00, kali dalam UTC.
Semoga berhasil!
Larutan
Bahasa ini sangat mirip dengan yang digunakan dalam "Baby" - mesin digital elektronik program tersimpan pertama di dunia. Pada halaman itu ada program untuk menemukan faktor integer tertinggi dalam memori (CRT!) Kurang dari 32 kata!
Saya menemukan menulis solusi agar sesuai dengan spesifikasi tidak kompatibel dengan OS dan mesin yang saya gunakan (turunan Ubuntu Linux pada perangkat keras yang sedikit lebih tua). Itu hanya meminta lebih banyak memori daripada yang tersedia, dan dumping inti. Pada OS dengan manajemen memori virtual canggih atau mesin dengan setidaknya 8 GB memori, Anda mungkin dapat menjalankan solusi sesuai spesifikasi. Saya telah memberikan kedua solusi.
Sangat sulit untuk kode dalam PQRS secara langsung, seperti menulis bahasa mesin, bahkan mungkin mikrokode. Alih-alih lebih mudah untuk menulis dalam semacam bahasa majelis kemudian "kompilasi". Di bawah ini adalah bahasa rakitan beranotasi untuk solusi yang dioptimalkan untuk menjalankan kasus uji:
Apa yang dilakukannya adalah mengurai input, mengubah unary ke binary, kemudian menyortir angka-angka dengan nilai-nilai dalam urutan menurun, kemudian akhirnya menghasilkan nilai terbesar ketiga dengan mengubah biner kembali ke unary.
Perhatikan bahwa
INC
(kenaikan) negatif danDEC
(penurunan) positif! Di mana ia menggunakanL#
atauL#+1
sebagaiP-
atauQ-OP
s, apa yang terjadi adalah memperbarui pointer: incrementing, decrementing, swapping, dll. Assembler dikompilasi dengan tangan ke PQRS dengan mengganti label dengan offset. Di bawah ini adalah solusi optimal PQRS :Kode di atas dapat disimpan
challenge-optimized.pqrs
untuk menjalankan kasus uji.Untuk kelengkapan, berikut adalah sumber per spesifikasi:
Dan solusi:
Untuk menjalankan di atas, Anda akan perlu untuk komentar
#define OPTIMIZED
dan menambahkan#define PER_SPECS
dalampqrs.c
dan mengkompilasi ulang.Ini adalah tantangan besar - sangat menikmati latihan mental! Membawa saya kembali ke hari-hari assembler 6502 lama saya ...
Jika saya menerapkan PQRS sebagai bahasa pemrograman "nyata", saya mungkin akan menambahkan mode tambahan untuk akses tidak langsung langsung dan ganda di samping akses tidak langsung, serta posisi relatif dan posisi absolut, keduanya dengan opsi akses tidak langsung untuk percabangan!
sumber
Seng, Retak! oleh @Zgarb
Juga tersedia di GitHub .
Anda membutuhkan Dart 1.12 dan Pub. Jalankan saja
pub get
untuk mengunduh satu-satunya dependensi, parsing library.Ini untuk berharap ini berlangsung lebih dari 30 menit! :HAI
Bahasa
Seng berorientasi pada operator yang mendefinisikan ulang. Anda dapat mendefinisikan ulang semua operator dalam bahasa dengan mudah!
Struktur program Zinc yang khas terlihat seperti:
Hanya ada dua tipe data: integer dan set. Tidak ada yang namanya himpunan literal, dan himpunan kosong tidak diizinkan.
Ekspresi
Berikut ini adalah ekspresi valid di Zinc:
Literal
Seng mendukung semua literal bilangan bulat normal, seperti
1
dan-2
.Variabel
Seng memiliki variabel (seperti kebanyakan bahasa). Untuk referensi mereka, cukup gunakan namanya. Sekali lagi seperti kebanyakan bahasa!
Namun, ada variabel khusus yang disebut
S
berperilaku seperti PythQ
. Saat pertama kali menggunakannya, itu akan dibaca dalam satu baris dari input standar dan menafsirkannya sebagai satu set angka. Misalnya, jalur input1234231
akan berubah menjadi set{1, 2, 3, 4, 3, 2, 1}
.CATATAN PENTING!!! Dalam beberapa kasus, literal di ujung override operator diuraikan secara salah, jadi Anda harus mengelilinginya dengan tanda kurung.
Operasi biner
Operasi biner berikut ini didukung:
+
:1+1
.-
:1-1
.*
:2*2
./
:4/2
.=
:3=3
.Selain itu, operasi unary berikut juga didukung:
#
:#x
.Diutamakan selalu asosiatif benar. Anda dapat menggunakan tanda kurung untuk mengganti ini.
Hanya persamaan dan panjang yang bekerja pada set. Saat Anda mencoba mendapatkan panjang bilangan bulat, Anda akan mendapatkan jumlah digit dalam representasi stringnya.
Tetapkan pemahaman
Untuk memanipulasi set, Zinc telah menetapkan pemahaman. Mereka terlihat seperti ini:
Klausa adalah klausa kapan atau semacam.
A ketika klausa terlihat seperti
^<expression>
. Ekspresi yang mengikuti tanda sisipan harus menghasilkan bilangan bulat. Menggunakan klausa when hanya akan mengambil elemen dalam set yangexpression
tidak nol. Di dalam ekspresi, variabel_
akan diatur ke indeks saat ini di set. Ini kira-kira setara dengan Python ini:Sebuah klausul semacam , yang terlihat seperti
$<expression>
, macam set turun oleh nilai<expression>
. Itu sama dengan Python ini:Berikut adalah beberapa contoh pemahaman:
Ambil hanya elemen himpunan
s
yang sama dengan 5:Urutkan set
s
berdasarkan nilainya jika elemen-elemennya kuadrat:Mengganti
Override operator memungkinkan Anda mendefinisikan ulang operator. Mereka terlihat seperti ini:
atau:
Dalam kasus pertama, Anda dapat mendefinisikan operator untuk menyamai operator lain. Sebagai contoh, saya dapat mendefinisikan
+
untuk benar-benar mengurangi melalui:Ketika Anda melakukan ini, Anda dapat mendefinisikan kembali operator untuk menjadi operator ajaib . Ada dua operator ajaib:
join
mengambil satu set dan integer dan bergabung dengan isi set. Misalnya, bergabung{1, 2, 3}
dengan4
akan menghasilkan bilangan bulat14243
.cut
juga mengambil set dan integer dan akan mempartisi set pada setiap kemunculan integer. Menggunakancut
di{1, 3, 9, 4, 3, 2}
dan3
akan membuat{{1}, {9, 4}, {2}}
... TAPI setiap single-elemen set diratakan, sehingga hasilnya akan benar-benar{1, {9, 4}, 2}
.Berikut ini contoh yang mengubah arti
+
operatorjoin
:Untuk kasus yang terakhir, Anda dapat mendefinisikan ulang operator ke ekspresi yang diberikan. Sebagai contoh, ini mendefinisikan operasi plus untuk menambahkan nilai dan kemudian menambahkan 1:
Tapi apa
+:
? Anda dapat menambahkan titik dua:
ke operator untuk selalu menggunakan versi bawaan. Contoh ini menggunakan builtin+
via+:
untuk menambahkan angka bersama, lalu menambahkan 1 (ingat, semuanya benar-asosiatif).Mengganti operator panjang terlihat seperti:
Perhatikan bahwa hampir semua operasi builtin (kecuali persamaan) akan menggunakan operator panjang ini untuk menentukan panjang set. Jika Anda mendefinisikannya sebagai:
setiap bagian dari Zinc yang bekerja pada set kecuali
=
hanya akan beroperasi pada elemen pertama dari set itu diberikan.Beberapa penimpaan
Anda dapat mengganti beberapa operator dengan memisahkannya dengan koma:
Pencetakan
Anda tidak dapat langsung mencetak apa pun di Zinc. Hasil dari ekspresi berikut
in
akan dicetak. Nilai-nilai dari himpunan akan digabungkan dengan ke pemisah. Misalnya, ambil ini:Jika
expr
sudah diatur{1, 3, {2, 4}}
,1324
akan dicetak ke layar setelah program selesai.Menyatukan semuanya
Berikut adalah program Zinc sederhana yang tampaknya menambah
2+2
tetapi menyebabkan hasilnya 5:Penerjemah
Ini masuk
bin/zinc.dart
:Dan ini masuk
pubspec.yaml
:Solusi yang dimaksudkan
sumber
join
satu set campuran suka{1,{3,2}}
, apakah akan ada kesalahan? Saya tidak dapat menginstal Dart sekarang, jadi saya tidak dapat memeriksa diri saya sendiri.dart bin/zinc.dart test.znc
saya mendapatkan kesalahan sintaks:'file:///D:/Development/languages/zinc/bin/zinc.dart': error: line 323 pos 41: unexpected token '?'
...var input = stdin.readLineSync() ?? '';
-2+#:S
ketika diberikanS
, yang memotong dua nol trailing. Itulah yang saya harapkan akan diselesaikan. Dan^
tidak seharusnya membalik set ... itu bug ...Sup Kompas ( retak oleh cardboard_box )
Penerjemah: C ++
Kompas Soup adalah jenis seperti mesin Turing dengan pita 2 dimensi yang tak terbatas. Tangkapan utama adalah bahwa memori instruksi dan memori data berada dalam ruang yang sama, dan output dari program adalah seluruh isi ruang itu.
Bagaimana itu bekerja
Program adalah blok teks 2 dimensi. Ruang program dimulai dengan seluruh kode sumber ditempatkan dengan karakter pertama di (0,0). Sisa ruang program tidak terbatas dan diinisialisasi dengan karakter nol (ASCII 0).
Ada dua petunjuk yang dapat bergerak di sekitar ruang program:
!
karakter atau di (0,0) jika itu tidak ada.x
,X
,y
, danY
. Dimulai di lokasi@
karakter atau di (0,0) jika itu tidak ada.Memasukkan
Isi stdin dicetak ke dalam ruang program mulai dari lokasi
>
karakter, atau pada (0,0) jika itu tidak ada.Keluaran
Program berakhir ketika pointer eksekusi berjalan di luar batas. Outputnya adalah seluruh isi ruang program pada waktu itu. Itu dikirim ke stdout dan 'result.txt'.
Instruksi
n
- mengarahkan kembali pointer eksekusi Utara (negatif y)e
- mengalihkan pointer eksekusi Timur (positif x)s
- mengalihkan pointer eksekusi Selatan (positif y)w
- mengalihkan pointer eksekusi Barat (negatif x)y
- Memindahkan penunjuk data Utara (negatif y)X
- Memindahkan penunjuk data Timur (positif x)Y
- Memindahkan penunjuk data Selatan (positif y)x
- Memindahkan penunjuk data Barat (negatif x)p
- menulis karakter selanjutnya yang ditemukan oleh pointer eksekusi pada pointer data. Karakter itu tidak dieksekusi sebagai instruksi.j
- memeriksa karakter berikutnya yang dihadapi oleh pointer eksekusi terhadap karakter di bawah pointer data. Karakter itu tidak dieksekusi sebagai instruksi. Jika mereka sama, pointer eksekusi melompati karakter berikutnya.c
- menulis karakter nol pada penunjuk data.*
- breakpoint - hanya menyebabkan penerjemah putus.Semua karakter lain diabaikan oleh pointer eksekusi.
Penerjemah
Interpreter mengambil file sumber sebagai argumen dan input pada stdin. Ini memiliki debugger steppable, yang dapat Anda gunakan dengan instruksi breakpoint dalam kode (
*
). Ketika rusak, pointer eksekusi ditampilkan sebagai ASCII 178 (blok berbayang lebih gelap) dan pointer data ditampilkan sebagai ASCII 177 (blok berbayang lebih terang).Contohnya
Halo Dunia
Kucing
Parity: menerima serangkaian karakter yang diakhiri dengan nol ('0'). Output
yes
pada baris pertama dari output jika jumlah 1s dalam input ganjil, jika tidak output|
.Kiat
Anda harus menggunakan editor teks yang baik dan memanfaatkan fungsi tombol 'Sisipkan' dengan bijaksana, dan menggunakan 'Seret-Alt' untuk menambah atau menghapus teks pada beberapa baris sekaligus.
Larutan
Ini solusinya. Ini tidak sebagus cardboard_box karena saya harus membuat kode sumber hapus sendiri. Saya juga berharap dapat menemukan cara untuk menghapus semua kode dan hanya meninggalkan jawabannya, tetapi saya tidak bisa.
Pendekatan saya adalah untuk membagi urutan yang berbeda dari
1
s ke baris yang berbeda, kemudian mengurutkan mereka dengan memiliki1
semua "jatuh" sampai mereka mencapai yang lain1
, dan akhirnya menghapus semuanya kecuali baris ketiga setelah input.#A#
reads1
s dan menyalinnya ke baris terakhir dari split sampai0
dibaca.#B#
memeriksa sebentar0
dan pergi ke utara ke#D#
sana. Jika tidak,#C#
mulailah garis pemisah baru dengan menempatkan|
setelah yang terakhir, dan kembali ke#A#
.#F#
adalah kode gravitasi. Ia berjalan ke baris terakhir terakhir1
dan menggerakkannya hingga menyentuh1
atau-
. Jika tidak bisa, itu menandai baris selesai dengan meletakkan+
sebelumnya.#G#
menghapus semua pemisahan yang tidak diperlukan, dan#H#
menghapus stdin dan semua kode di antara tanda kurung.Kode:
sumber
c
di awal yang seharusnya tidak ada di sana. Aku telah memperbaikinya. Juga menambahkan solusi saya untuk masalah ini.Acc! , Cracc'd oleh ppperry
Bahasa ini memiliki satu struktur pengulangan, matematika integer dasar, karakter I / O, dan akumulator (dengan demikian namanya). Hanya satu akumulator. Demikian namanya.
Pernyataan
Perintah diurai baris demi baris. Ada tiga jenis perintah:
Count <var> while <cond>
Menghitung
<var>
dari 0 selama<cond>
bukan nol, setara dengan C-stylefor(<var>=0; <cond>; <var>++)
. Penghitung lingkaran dapat berupa huruf kecil tunggal. Kondisi dapat berupa ekspresi apa pun, tidak harus melibatkan variabel loop. Loop berhenti ketika nilai kondisi menjadi 0.Loop membutuhkan kurung kurawal gaya K&R (khususnya, varian Stroustrup ):
Write <charcode>
Output karakter tunggal dengan nilai ASCII / Unicode yang diberikan ke stdout. Kode sandi dapat berupa ekspresi apa pun.
Ekspresi apa pun yang berdiri sendiri dievaluasi dan ditugaskan kembali ke akumulator (yang dapat diakses sebagai
_
). Jadi, misalnya,3
adalah pernyataan yang menetapkan akumulator ke 3;_ + 1
menambah akumulator; dan_ * N
membaca karakter dan mengalikan akumulator dengan kode sandi-nya.Catatan: akumulator adalah satu-satunya variabel yang dapat ditugaskan secara langsung; variabel loop dan
N
dapat digunakan dalam perhitungan tetapi tidak dimodifikasi.Akumulator awalnya 0.
Ekspresi
Ekspresi dapat menyertakan bilangan bulat integer, variabel loop (
a-z
),_
untuk akumulator, dan nilai khususN
, yang membaca karakter dan mengevaluasi karakternya setiap kali digunakan. Catatan: ini berarti Anda hanya mendapatkan satu kesempatan untuk membaca setiap karakter; lain kali Anda gunakanN
, Anda akan membaca yang berikutnya.Operator adalah:
+
, tambahan-
, pengurangan; negasi unary*
, penggandaan/
, pembagian bilangan bulat%
, modulo^
, eksponensialKurung dapat digunakan untuk menegakkan prioritas operasi. Karakter lain dalam ekspresi adalah kesalahan sintaksis.
Spasi dan komentar
Ruang putih dan baris kosong terkemuka dan tertinggal diabaikan. Spasi putih dalam header loop harus persis seperti yang ditunjukkan, dengan satu ruang antara header loop dan kurung kurawal terbuka juga. Ekspresi di dalam spasi putih adalah opsional.
#
memulai komentar satu baris.Input output
Acc! mengharapkan satu baris karakter sebagai input. Setiap karakter input dapat diambil secara berurutan dan karakternya diproses menggunakan
N
. Mencoba membaca melewati karakter terakhir dari baris menyebabkan kesalahan. Sebuah karakter dapat di-output dengan memberikan kode-nya keWrite
pernyataan.Penerjemah
Penerjemah (ditulis dalam Python 3) menerjemahkan Acc! kode ke Python dan
exec
s itu.sumber
GoToTape (Aman)
(Sebelumnya dikenal sebagai Simp-plex.)
Bahasa ini sederhana. Kontrol aliran utama adalah goto, bentuk kontrol yang paling alami dan berguna.
Spesifikasi bahasa
Data disimpan pada kaset dan dalam akumulator. Ini berfungsi sepenuhnya dengan integrasi yang tidak ditandatangani. Setiap karakter adalah perintah. Berikut ini adalah semua perintah:
a
-z
adalah pernyataan kebagian, pergi keA
-Z
, masing-masing.:
: setel akumulator ke nilai ASCII menjadi char dari input.~
: output char untuk nilai ASCII di akumulator.&
: kurangi satu dari akumulator jika 1 atau lebih, tambahkan satu.|
: tambahkan satu ke akumulator.<
: setel pointer data ke 0.+
: menambah sel data pada penunjuk data; pindahkan penunjuk +1.-
: kurangi satu dari sel data di penunjuk data jika positif; pindahkan penunjuk +1.[...]
: jalankan kode n kali di mana n adalah angka pada rekaman di penunjuk data (tidak dapat disarangkan)./
: lewati instruksi berikutnya jika akumulatornya 0.Penerjemah (C ++)
Selamat bersenang-senang!
Larutan
A:+&&&&&&&&&&/gbG&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&/a<aB<[|]C[&]-[|]/c<[|]D[&]-[|]/d<[|]+E[&]|||||||||||||||||||||||||||||||||||||||||||||||||~X&/x-[|]/e
sumber
calloc
alih-alihnew char
, menulis loop gaya-C sementara, menggunakan manajemen memori gaya-C, membuat kami mengkompilasi ulang file C ++ setiap kali kami mengubah kode, dan menggunakan 20 jika bukan sebagai gantiswitch
? Saya tidak mengeluh, tetapi mata saya berdarah sekarang ...: Ostr.c_str()
untuk mendapatkanchar*
.Ini adalah ide yang buruk karena hampir semua bahasa esoteris terlihat tidak dapat dibaca (lihat Jelly).
Tapi begini:
Pylongolf2 beta6
Mendorong ke Stack
Mendorong ke tumpukan bertindak berbeda dari bahasa lain.
Kode
78
mendorong7
dan8
masuk ke tumpukan, namun di Pylongolf itu mendorong78
.Dalam Pylongolf2 ini bisa diubah dengan
Ü
.Perintah
String Concatenation dan Menghapus Pola Regex dari String
Simbol + menyatukan string.
Anda dapat menggunakan simbol - untuk menghapus karakter mengikuti pola regex dari string:
Kode ini mengambil input dan menghapus semua karakter non-abjad dengan menghapus semua pola yang cocok
[^a-zA-Z]
.Item yang dipilih harus berupa regex dan yang sebelumnya harus berupa string untuk diedit.
Jika Pernyataan
Untuk melakukan pernyataan if, beri tanda
=
untuk membandingkan item yang dipilih dan yang sesudahnya.Ini menempatkan a
true
atau afalse
di tempatnya.Perintah
?
memeriksa boolean ini.Jika itu
true
maka itu tidak melakukan apa-apa dan penerjemah berjalan.Jika itu
false
maka penerjemah melompat ke¿
karakter terdekat .Diambil dari halaman Github.
Penerjemah untuk Pylongolf2 (Jawa):
sumber
Rainbow (Catatan: Penerjemah segera hadir)
Saya tahu tantangan ini berakhir.
Pelangi adalah campuran ... banyak hal.
Rainbow adalah bahasa berbasis tumpukan 2D dengan dua tumpukan (Seperti Brain-Flak) dan 8 arah (
N NE E SE S SW W NW
). Ada 8 perintah:1
,+
,*
,"
Melakukan persis apa yang mereka lakukan di 1+.!
matikan tumpukan aktif.>
putar IP searah jarum jam.,
masukan karakter dan tekan..
pop dan output karakter.Namun, karakter dalam kode sumber tidak segera dieksekusi. Sebaliknya,
[The Character in the source code]^[Top Of Stack]
dimasukkan ke dalam hal dugaan Collatz, dan jumlah langkah yang diperlukan untuk mencapai 1 dikonversi menjadi karakter oleh tabel ASCII. Karakter ini kemudian dieksekusi.Di awal program, kode sumber (kecuali untuk karakter terakhir) didorong ke stack.
Ketika IP mencapai tepi kode sumber, itu berakhir.
Wahyu
n dan m adalah dua register. Ketika
>
instruksi dieksekusi, m bertambah. Kiamat hanya dipicu jika m melebihi n. Ketika Kiamat terjadi, itu:m awalnya nol, dan n awalnya karakter terakhir dari kode sumber.
Enkripsi
Setelah menjalankan eksekusi apa pun, kode sumber dienkripsi. ASCII karakter 1 bertambah satu, karakter 2 dikurangi satu, karakter ketiga ditambah dua, karakter keempat dikurangi dua, dll.
sumber