Anda memiliki setumpuk panekuk di piring dengan segumpal sirup di atasnya begitu tebal sehingga tidak bisa mengecil. Anda tidak akan senang makan sampai kedua wajah masing-masing pancake setidaknya menyentuh sirup, tetapi saat ini hanya satu wajah dari pancake atas.
Anda tahu bahwa sirup tidak akan pernah meresap melalui satu pancake, tetapi dapat ditransfer tanpa batas waktu melalui kontak langsung antara dua pancake. Setelah sebuah wajah dari pancake menyentuh sirup, itu dianggap dilapisi dengan sirup selamanya, dan akan membuat wajah tanpa sirup apa pun yang menyentuh sirup itu dilapisi juga. Dimungkinkan untuk mentransfer sirup ke dan dari sisi atas piring juga.
Anda melanjutkan untuk melapisi setiap wajah pancake dengan sirup dengan memasukkan spatula di bawah satu atau lebih pancake dan membalik semuanya, persis seperti yang dilakukan dalam penyortiran pancake . (Sayangnya spatula ini tahan terhadap sirup, dan tidak membantu mendistribusikan sirup dengan menyentuh wajah panekuk.) Sayangnya Anda kehilangan jejak wajah panekuk yang menyentuh sirup tetapi Anda ingat flip yang Anda buat.
Mengingat flips masa lalu Anda, dapatkah Anda menentukan apakah pancake Anda sudah dilapisi dengan sirup?
Tantangan
Tulis program yang menggunakan bilangan bulat positif N untuk jumlah pancake, dan daftar bilangan bulat positif (semua <= N) untuk flip yang Anda buat sejauh ini. Setiap nomor dalam daftar mewakili jumlah pancake yang dibalik. Keluarkan nilai kebenaran jika pancake selesai dilapisi dan nilai palsu jika tidak. ( definisi benar / salah )
Input harus berasal dari stdin atau baris perintah dan output harus pergi ke stdout (atau alternatif terdekat). Tidak apa-apa jika input Anda memerlukan sedikit format tambahan: mis. [1, 1, 2, 2]
Alih-alih 1 1 2 2
untuk daftar.
Contohnya
Asumsikan N = 2, jadi kami memiliki setumpuk dua pancake di piring, dimulai dengan sirup di atasnya.
Jika daftar ini 1 1 2 2
, ini berarti kita ...
- flip pancake atas - melapisi wajah atas pancake bawah
- balik bagian atas lagi - melapisi wajah bawah asli pancake atas
- balik keduanya - melapisi piring
- balikkan keduanya lagi - melapisi wajah bagian bawah asli pancake bawah
Karena keempat wajah dilapisi, hasilnya akan seperti True
atau 1
.
Jika daftar ini 1 2 2 1
, ini berarti kita ...
- flip pancake atas - melapisi wajah atas pancake bawah
- flip keduanya - tidak ada lapisan
- balikkan keduanya lagi - tidak melapisi apa pun
- balik bagian atas lagi - melapisi wajah bawah asli pancake atas
Karena wajah yang menyentuh pelat masih bebas sirup, hasilnya akan seperti False
atau 0
.
Catatan
- Daftar flip mungkin besar sewenang-wenang dan dapat kosong, dalam hal ini hasilnya palsu.
- Piring bertindak sebagai pembawa-sirup tetapi tidak masalah jika dilapisi atau tidak. (Sebenarnya setiap solusi balik akan melapisi pelat karena wajah panekuk yang disentuhnya harus dilapisi, tetapi apa pun itu.)
- Piring tidak bisa dibalik.
- Anda dapat mengasumsikan pancake ini adalah disk unit tanpa sisi untuk dibicarakan, hanya dua wajah yang berlawanan.
Mencetak gol
Ini adalah kode-golf. Solusi terpendek dalam byte menang.
Put syrup on the pancakes!
Jawaban:
CJam,
323029 byteCobalah online.
Uji kasus
Bagaimana itu bekerja
sumber
Haskell,
929086841141109998persyaratan program lengkap sangat menjengkelkan. Saya bertanya-tanya mengapa ada orang yang memerlukan ini.
solusi ini bekerja dengan mewakili tumpukan pancake dengan daftar sisi, ketika pancake yang berdekatan berbagi sisi yang sama. setiap sisi adalah angka, dan sisi dilapisi jika memiliki nilai nol.
jalankan sebagai:
sumber
Python, 92 byte
Saya pikir ini bekerja:
Ini menggunakan daftar wajah panekuk (termasuk piring) untuk mengingat yang dilapisi dengan sirup. Pancake dibalik dengan membalik bagian daftar, tetapi sirup apa pun pertama kali ditransfer antara wajah bagian atas dan wajah yang baru terungkap.
Pemakaian:
sumber
Python 2: 75
Penyederhanaan solusi grc dan feersum.
Menyimpan keadaan sirup pada
2*n+1
tepi pancake adalah berlebihan karena menyentuh ujung selalu sama. Ini sebagai gantinya mengingat keadaan setiapn+1
persimpangan pancake. Dengan begitu, transfer sirup secara otomatis diperhitungkan.Satu-satunya pembaruan yang diperlukan adalah mempertahankan sirup di
x
persimpangan saat flip memotongnya. Hal ini dilakukan oleh atau-ing sirup pasca-flip di0
dalamx
.Mengambil input dua kali tidak mempengaruhi jumlah karakter.
sumber
Python 2, 93 byte
Awalnya saya akan memposting jawaban saya, tetapi kemudian grc sudah memposting yang sangat mirip satu menit sebelumnya. Jadi saya mencoba membuat beberapa perbaikan. Satu-satunya yang bisa saya temukan adalah menggunakan perbandingan daftar leksikografis alih-alih
all()
.Sunting: Memperbaiki kesalahan yang diperkenalkan oleh gagal mencoba metode input berbeda yang tidak mengubah jumlah karakter.
Input / output sampel:
sumber
APL, 77
sumber
Python 2, 107
sumber
Haskell,
129125Mungkin belum sepenuhnya golf, tetapi ia bekerja tanpa memanipulasi daftar sisi yang dilapisi. Alih-alih, ia bekerja mundur untuk mencari tahu apakah sisi tertentu dari pancake yang diberikan pernah bersentuhan dengan apa pun yang merupakan sisi atas pada awalnya.
foldr
secara efektif melintasi daftar membalik ke belakang, oleh karena itu tidak adareverse
.Jadi inilah algoritanya: Kami memetakan semua sisi yang relevan (
[0..m]
) dan membuat daftar sisi-sisi yang mewarisi sirup dari setiap langkah kami, mulai dari belakang: awalnya daftarnya adil[i]
, tetapi dengan flipn
pancake, setiap entri menjadi[n-i]
jikai<n
,[n,0]
jikai==n
, dan[i]
jikai>n
. Sisi yang dimaksud telah dilapisi jika dan hanya jika daftar yang dihasilkan setelah semua flips berisi0
(any (<1)
).all
melakukan sisanya, danmain
mengubah semua ini menjadi program runnable.Program ini mengambil input dari
stdin
dalam bentuk[n_pancakes, flip1, flip2, flip3, ...]
, diakhiri oleh baris baru.sumber
n%i|i>n=[i]|i<n=[n-i]|0<1=[n,0]
dan bukannyafoldr($)[].map(n%)
memiliki(=<<).(%)
, yang akan memetakan semua warisan dan bergabung dengan mereka.[0..]
dan mewakili pancake dilapisi sebagai 0 bukannya membuat pancake bukan nol dilapisi. Terima kasih!