Saya memiliki kotak musik yang dioperasikan engkol yang dapat memainkan serangkaian empat catatan. Ketika saya memutar engkol, itu memutar salah satu dari empat senar, tergantung pada posisi engkol dan arah putaran. Ketika engkol diputar ke utara, kotak (dengan senar bernomor 1 hingga 4) terlihat seperti ini:
1 | 2
|
O
4 3
Dari sana, saya bisa memutar engkol searah jarum jam untuk memetik senar # 2 dan mengarahkan engkol ke timur:
1 2
O---
4 3
Sebagai alternatif, saya juga bisa memutar engkol berlawanan arah jarum jam dari utara untuk memainkan string # 1 dan mengakhiri dengan engkol yang menunjuk ke barat:
1 2
---O
4 3
Maka, pada waktu tertentu, kotak itu dapat memainkan salah satu dari dua not: not berikutnya tersedia dalam arah searah jarum jam atau not berikutnya dalam arah berlawanan arah jarum jam.
Tantangan
Tantangan Anda adalah menulis program atau fungsi yang menerima string nilai not yang tidak kosong (yaitu, angka yang 1
dilewati 4
) dan menentukan apakah mungkin untuk memainkan urutan not pada kotak musik. Menghasilkan hasil yang benar atau salah untuk menunjukkan kemampuan memutar atau tidak dapat dimainkannya input.
Beberapa catatan:
Masukan tidak membuat asumsi tentang posisi awal awal. Input
214
(mulai ke timur dan bergerak sangat berlawanan arah jarum jam) dan234
(mulai ke utara dan bergerak dengan ketat searah jarum jam) dan keduanya valid.Engkol dapat bergerak bebas ke kedua arah setelah setiap nada. Serangkaian catatan yang sama dimungkinkan (misalnya,
33333
) dengan bergerak bolak-balik melintasi satu string. Serial1221441
ini dapat dimainkan dengan sempurna (mulai barat, bergerak searah jarum jam dua langkah, lalu berlawanan arah tiga langkah, lalu searah jarum jam dua langkah).
Sampel
Beberapa true
kasus:
1
1234
1221
3333
143332
22234
2234
22214
1221441
41233
Beberapa false
kasus:
13 (note 3 is never available after note 1)
1224 (after `122`, the crank must be north, so 4 is not playable)
121 (after `12` the crank is east; 1 is not playable)
12221 (as above, after `1222` the crank is east)
43221
sumber
Jawaban:
Pyth,
3027 byteInilah idenya:
Engkol selalu pada posisi setengah bilangan bulat
c
. Pada setiap langkah, kami merefleksikannya pada nota posisi integern
dengan menetapkanc = 2*n-c
. Jikan
valid,c
ubah dengan ± 1 mod 8. Jikan
tidak valid,c
ubah dengan ± 3 mod 8. Kami secara kumulatif mengurangi input untuk mengumpulkan semua nilaic
, dan kemudian melihat apakah semua catatan valid. Kami melakukan ini untuk setiap nilai awalc
, karena lebih pendek daripada memeriksa hanya yang berdekatan dengan catatan pertama.Diformat:
Suite uji .
sumber
CJam,
3431 byteApakah ini di ponsel saya, jadi saya harus memberikan penjelasan nanti.Output tidak kosong jika jujur.Cobalah online | Suite uji
Penjelasan
Kode baru sedikit mengubah tata letak:
Angka genap sesuai dengan posisi string dan angka ganjil sesuai dengan posisi engkol.
Inilah yang terjadi:
Tumpukan kemudian dicetak secara otomatis di bagian akhir. Setiap posisi akhir yang mungkin ada dalam output, misalnya untuk input
1
output31
, yang berarti engkol dapat berakhir menghadap ke kiri atau ke atas.Kalau saja CJam memiliki filter dengan parameter tambahan ...
Sunting: Sementara memutar kembali sementara saya meyakinkan diri sendiri bahwa 29-byte ini berfungsi:
sumber
Haskell,
93 8887 byteIni mengevaluasi ke fungsi anonim yang mengambil string dan mengembalikan boolean. Test suite di sini.
Penjelasan
Idenya adalah bahwa lambda di sebelah kanan peta nomor
a
ke[[a,a+1],[a+1,a]]
, dua kemungkinan "bergerak" yang mengambil engkol lebih jumlah itu, menurut diagram berikut:Dalam fungsi anonim utama, pertama-tama kita lakukan
mapM((...).read.pure)
, yang mengubah setiap karakter menjadi bilangan bulat, menerapkan lambda di atasnya, dan memilih salah satu dari dua gerakan, mengembalikan daftar semua urutan langkah yang dihasilkan. Kemudian, kami memeriksa apakah ada dari sekuens ini yang memiliki properti bahwa jumlah kedua dari setiap gerakan sama dengan jumlah pertama dari modulo 4 berikutnya, yang berarti bahwa itu adalah urutan yang memungkinkan secara fisik. Untuk melakukan ini, kitazip
masing-masing memindahkan urutan dengantail
, memeriksa kondisi untukall
pasangan, dan melihat apakahany
urutan mengevaluasiTrue
.sumber
Retina, 50 byte
Saya pikir ini berhasil?
Coba di sini.
sumber
Retina ,
127109 byteIni mencetak
0
atau1
, sesuai.Cobalah online! (Ini adalah versi yang sedikit dimodifikasi yang menandai semua kecocokan dalam input alih-alih mencetak
0
atau1
.)Saya mencoba membuat algoritma yang elegan, tetapi beberapa upaya pertama saya tidak dapat menghindari backtracking ... dan menerapkan backtracking itu mengganggu ... jadi saya menggunakan bahasa yang melakukan backtracking untuk saya di mana saya hanya perlu menyandikan solusi yang valid. Sayangnya, pengkodeannya cukup bertele-tele dan cukup berlebihan ... Saya yakin ini bisa dipersingkat.
Sementara saya mencoba mencari tahu sesuatu yang lebih rapi, jika ada yang ingin memilah cara kerjanya, ini adalah versi yang lebih mudah dibaca:
Dan ini adalah sebuah petunjuk:
sumber
MATL ,
5755 byteIni menggunakan rilis saat ini (10.2.1) , yang lebih awal dari tantangan ini.
EDIT (17 Januari, 2017): karena perubahan bahasa,
v
perlu diganti oleh&v
, dantL3$)
olehY)
(selain itu, beberapa perbaikan lain dapat dilakukan). Tautan berikut mencakup dua modifikasi tersebutCobalah online!
Penjelasan
Ini didasarkan pada dua alat favorit saya untuk golf kode: brute force dan convolution .
Kode mendefinisikan jalur diikuti oleh engkol dalam hal koordinat
0.5
,1.5
dll. Setiap angka memberitahu posisi engkol antara catatan. Kode pertama kali membangun larik lintasan dengan semua lintasan yang mungkin yang dimulai dengan nada pertama dari string input. Setiap jalur adalah kolom dalam array ini. Ini adalah komponen brute force .Dari larik lintasan ini, larik catatan diperoleh, di mana setiap kolom adalah urutan catatan yang dimainkan. Misalnya, pindah dari posisi
0.5
ke1.5
menghasilkan catatan1
. Ini terdiri dari mengambil rata-rata antara posisi dan kemudian menerapkan operasi modulo 4. Rata-rata berjalan di sepanjang setiap kolom dilakukan dengan konvolusi 2D .Akhirnya, program memeriksa apakah ada kolom array catatan yang bertepatan dengan input.
sumber
Pyth, 43
Test Suite
Ini mungkin sangat golfable, dan juga bukan algoritma yang optimal untuk golf (saya berharap menghitung semua jalur akan lebih pendek?) ... Lagi pula, jika Anda menemukan kesalahan dengan algoritma tolong beri tahu saya, saya pikir itu harus bekerja tetapi saya pernah salah sebelumnya!
Saya akan menjelaskan algoritma saya menggunakan contoh input
1221
. Program ini pertama memetakan angka melawan penerus mereka, seperti:[[1,2],[2,2],[2,1]]
. Kemudian mendapat perbedaan mereka mod4
(Pyth mendapat hasil yang cocok dengan tanda argumen yang tepat%
, jadi ini selalu positif):[3,0,1]
. Kemudian hasilnya dibagi pada0
dan telah2
dikurangi dari masing-masing:[[1],[-1]]
.Sekarang setelah setup selesai, kami membuat daftar
[-1,1,-1...]
dan negasinya[1,-1,...]
, sama panjangnya dengan array yang dihasilkan dari sebelumnya. Kemudian, untuk masing-masing daftar ini, lakukan pengurangan setwise antara elemen daftar dan daftar yang dihasilkan pada langkah sebelumnya. Kemudian, jika salah satu dari hasil hanya berisi daftar kosong, kami menampilkan true.sumber
1221221
dan1221441
?1221221
adalah palsu dan1221441
memberikan benar secara keseluruhan, tetapi jika saya mengerti Anda ingin hasilnya setelah langkah itu dalam algoritma? Jika itu adalah kasus memberikan: dari[3, 0, 1, 3, 0, 1]
ke[[3], [1, 3], [1]]
dan[3, 0, 1, 1, 0, 3]
ke[[3], [1, 1], [3]]
. Beri tahu saya jika Anda ingin sesuatu yang lain dijelaskan :)[[1], [-1, 1], [-1]]
dan[[1], [-1, -1], [1]]
dari sini, Anda dapat melihat bahwa yang pertama tidak memiliki daftar yang bergantian antara-1
dan1
sementara daftar lainnya, memberikan hasil akhir. Algoritma ini agak tumpul, tetapi pada dasarnya memetakan perubahan0
arah dan arah sebagai+/-1
, kemudian memeriksa bahwa tidak ada lompatan dibuat dan arah masuk akal.Matlab,
279180 byteSolusi yang cukup malas, tetapi yang terpendek yang bisa saya lakukan. Saya membuat matriks khusus: Ketika Anda mengkodekan keadaan pemetik dan string terakhir yang akan dipetik, ia mengembalikan vektor, yang mengkodekan posisi baru pemetik , dan apakah pemetik sebelumnya dimungkinkan sama sekali. Sekarang kita hanya mengulang semua catatan dari dua posisi awal yang memungkinkan dan melihat apakah salah satunya menghasilkan melodi yang dapat dimainkan. Mungkin bisa bermain golf lebih banyak.
Sumber diperluas dan dijelaskan:
sumber
ES6,
104100 byteSunting: Disimpan 4 byte berkat @DigitalTrauma.
Ini adalah penulisan ulang yang lengkap karena pendekatan saya sebelumnya cacat.
Saya mulai dengan mengurangi semua run digit menjadi 1 atau 2 tergantung pada apakah ada angka ganjil atau genap dalam menjalankan. Saya kemudian mencari semua kombinasi ilegal:
13|24|31|42
(sisi berlawanan)3[24]{2}1
sebagai3221
dan3441
ilegal4xx2
,1xx3
dan di2xx4
manax
salah satu dari digit yang hilang(.).\1
karena hal-hal seperti121
ilegal (111
telah dikurangi menjadi1
sebelumnya)Jika tidak ada pasangan ilegal atau "tiga kali lipat" maka seluruh string sah (bukti dengan induksi dibiarkan sebagai latihan karena sudah larut malam di sini).
Saya mencoba untuk menyederhanakan
3[24]{2}1|1[24]{2}3
menggunakan pernyataan lookahead negatif tetapi ternyata lebih lama seperti itu.sumber
f("1122") => true
@DigitalTraumaf("1221221")
menghasilkan jawaban yang salah, jadi saya harus memikirkan kembali.[24][24]
ke(2|4)\1
tapi aku tidak diuji secara memadai. Maaf soal itu.[24][24]
ke[24]{2}
?JavaScript (ES6), 80 byte
Penjelasan
i%4
adalah posisi engkol saat ini:Diindentasi dan Dikomentari
Uji
sumber
|
kerjanya dalam kasus ini?(x.map(...),v)
. Ia bekerja karena larik yangmap
dikembalikan ke0
dan0|v == v
.Lua ,
146 142 108 162 159 149 135 135 132 118113 byteMengembalikan benar atau salah diberi string angka antara 1 dan 4. (Tidak menangani data atau di luar angka jangkauan.
Cukup melacak apa gerakan terakhir itu dan memeriksa apakah gerakan ini adalah pembalikan dari gerakan terakhir (IE, 121 atau 12221) atau jika jarak bergerak lebih dari mungkin.
EDIT 1 :
Disimpan 6 byte. Saya lupa bahwa
if (int) then
mengembalikan true jika int bukan nol.Jadi:
perubahan ke:
Juga menghemat beberapa byte dengan restrukturisasi.
EDIT 2 :
Saya perlahan mencari tahu ini. Saya telah membaca dokumentasi di sini: http://www.lua.org/pil/ Dan salah satu halaman yang lebih berguna di sana untuk bermain golf adalah http://www.lua.org/pil/3.3.html
Secara khusus, ini sangat membantu:
Apa artinya ini bagi saya adalah bahwa saya dapat melanjutkan dan menghapus deklarasi saya untuk q ( yang awalnya ditetapkan ke 0 ) karena akan dianggap sebagai "salah" sampai ditetapkan. Jadi saya menyimpan beberapa byte lagi melalui ini.
Hal lain yang layak disebut, meskipun saya tidak menggunakannya, adalah jika Anda ingin menukar nilai dalam Lua, Anda bisa melakukannya
a,b=b,a
tanpa perlu variabel sementara.EDIT 3
Jadi, melalui beberapa rekonstruksi pintar serta fungsi baru, saya punya hitungan mundur 9 oleh lebih.
Mode Terbaik untuk Menerima Input
Jika Anda perlu membaca daftar angka dan melakukan operasi satu per satu, Anda dapat menggunakan:
Jika dibandingkan dengan alternatif Anda menggunakan string: sub, Anda dapat melihat nilai untuk golf (atau penggunaan umum):
Merestrukturisasi Fungsi atau String
Hal kedua, jika Anda memiliki banyak deklarasi pada satu baris dan salah satu nilainya adalah fungsi atau Anda memiliki kondisi di mana Anda membandingkan angka dengan hasil fungsi seperti ini:
dengan menata ulang sehingga tanda kurung penutup adalah karakter terakhir dalam kondisi atau deklarasi, Anda dapat memotong karakter seperti:
Mengembalikan Kondisi yang Menyamakan Benar atau Salah, bukan 'Benar' atau 'Salah'
Saya menemukan cara yang agak lucu untuk mengurangi jumlah byte saya lebih jauh. Jika Anda perlu mengembalikan benar atau salah, Anda dapat mengembalikan pernyataan yang sama dengan benar atau salah yang memiliki karakter kurang dari "benar" atau "salah" sendiri.
Misalnya, bandingkan:
Untuk:
sumber
121
seharusnya output salah.MATL, 49 byte (tidak bersaing 1 )
1. Jawabannya (ab) menggunakan pengindeksan yang lebih ketat dari versi MATL yang lebih baru, dan tidak akan berfungsi pada saat tantangan ini diposting.
Cobalah online! .
Saya melihat tantangan ini di Best of PPCG 2016 , dan berpikir bahwa ini bisa menggunakan operator favorit saya :
Atau,
diff
dalam MATLAB / Octave (saya akan dengan bebas menggunakan terminologi MATLAB / Octave dalam penjelasan saya, karena lebih mudah dibaca untuk manusia). Perintah ini menghitung perbedaan elemen-bijaksana dalam vektor atau, dalam hal ini, dalam array karakter.Untuk masalah ini, perbedaannya menunjukkan pola yang menarik. Catat itu
Untuk pola perbedaan (mengabaikan
1-4
transisi untuk saat ini), ini artinyaSaya menerapkan ini dengan, untuk setiap array, menemukan nol pertama. Saya memangkas nol, dan melipatgandakan semua elemen setelahnya
-1
. Untuk hasil akhirnya, ini berarti semua elemen harus memiliki tanda yang sama. Tentu saja, ada masalah kecil-3
penyamaan+1
, dan2
ditolak secara umum. Saya memecahkan ini dengan membawa set gabungan hasil dengan[1 -3]
, dan memeriksa apakah ini adalah ukuran 2 (yaitu, tidak ada elemen yang tidak diizinkan 'memasuki' set melalui serikat). Ulangi untuk[-1 3]
, dan periksa apakah salah satu (atau keduanya, dalam hal input 1-panjang) benar.sumber
M
, terakhir kali saya mencobanya, itu bekerja berbeda dari yang diharapkan jadi saya mengabaikannya untuk sementara waktu. Apakah benar mengatakan bahwa itu perlu3M
karena saya mendapatkan input bukan)
, bukan:
tetapiq
(melewatkanw
karena itu bukan fungsi normal )?w
dilewati karena itu bukan fungsi normal. Fungsi normal yang tidak mengambil input akan dilewati jugaPython (3.5)
160151150 byteSolusi rekursif
Tidak disatukan tanpa lambda
Saya memutar semua kotak, bukan engkol. Posisi engkol adalah antara karakter pertama dan kedua dari string c. Saya perlu menguji semua posisi awal engkol.
Trik digunakan untuk memutar string
Cara biasa untuk memutar string dalam python (
s[i:]+s[:i]
) perlu mengulangi baik indeks dan string. Dalam hal ini saya menduplikasi string dan memotong karakter pertama.Uji kasus
sumber
3"[i:]) for
.Python 2 , 65 byte
Cobalah online!
sumber
JavaScript (ES2015),
1109515 byte disimpan oleh Neil! Versi asli ungolfed:
Pengujian: https://jsbin.com/cuqicajuko/1/edit?js,console
sumber
(s,d)=>(h=s[0],t=s.slice(1),g=t[0],!g||(d?g==h?p(t,-d):g%4==(h-d)%4&&p(t,d):p(s,1)||p(s,-1)))
Kode mesin Turing, 395 byte
Cobalah online!
Ini pada dasarnya adalah pendekatan berbasis negara:
a
,b
,c
, Dand
adalah "ragu-ragu menyatakan" bahwa hanya terjadi pada awalN
,E
,S
, DanW
adalah "negara memutuskan", jelas berdiri untukN
orth,E
ast,S
elatan, danW
est.sumber
Thue, 203 byte
Saya tidak bisa memikirkan bagaimana cara bermain golf ini lebih jauh.
Jika urutan note dimungkinkan, akan menampilkan arah akhir, jika tidak maka output akan kosong.
sumber
Prolog (SWI) , 117 byte
Menentukan predikat
p
yang berhasil pada input yang dapat diputar (diberikan sebagai daftar bilangan bulat) dan gagal pada yang tidak dapat dimainkan. Cobalah online!Penjelasan
a
mendefinisikan hubungan kedekatan antara catatanN
dan posisi engkolP
. Kami mendefinisikan posisi p berada di antara catatan p dan p + 1 . Dengan demikian, suatu posisi berbatasan dengan noteN
iffN
(P=N
); atauN=1,P=4
); atau!
) dan posisinya sama denganN-1
(P is N-1
).m
mengambil daftar catatan dan mencoba menghasilkan daftar posisi yang akan memainkan catatan itu.A
adalah not yang baru saja diputar,B
apakah not akan segera dimainkan;X
adalah posisi engkol saat ini,Y
adalah posisi engkol berikutnya. Suatu langkah sah jika iffa(A,X)
);a(B,X)
);a(B,Y)
); danX\=Y
).Jika semua ini bertahan, kambuh. Jika kami berhasil masuk ke salah satu catatan (
m([_],_)
), urutan catatan dapat diputar.Untuk pertanyaan ini, kami hanya peduli apakah ada urutan pergerakan, jadi kami menetapkan
p
untuk memanggilm
dan membuang daftar posisi engkol yang dihasilkan.Lihat versi yang tidak dipisahkan dan verifikasi semua kasus uji di sini .
sumber