Melapisi Setiap Pancake

35

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 2untuk 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 Trueatau 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 Falseatau 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.

Hobi Calvin
sumber
4
Ini adalah tantangan yang sangat, sangat menyenangkan. ;)
Soham Chowdhury
apakah fungsi yang mendapat daftar dan mengembalikan boolean tidak apa-apa?
haskeller bangga
9
Harus ada bonus jika ada yang bisa menerapkannya dalam bahasa ini .
grc
3
@ grc Sekarang ada hadiah untuk itu!
Hobi Calvin
2
Inilah solusi saya di Pancake Stack Put syrup on the pancakes!
:;

Jawaban:

9

CJam, 32 30 29 byte

q~2@#2b\{)/(W%)1$0=|@]s:~}/:&

Cobalah online.

Uji kasus

$ cjam pancakes.cjam <<< '2 [1 1 2 2]'; echo
1
$ cjam pancakes.cjam <<< '2 [1 2 2 1]'; echo
0

Bagaimana itu bekerja

q~                            " N, L := eval(input())                                     ";
  2@#2b                       " P := base(2 ** N, 2)                                      ";
       \{                }/   " for F in L:                                               ";
         )/                   "   P := split(P, F + 1)                                    ";
           (W%)               "   T, U, V := P[1:], reverse(P[0])[:-1], reverse(P[-1])[0] ";
               1$0=|          "   V |= U[0]                                               ";
                    @]s:~     "   P := map(eval, str([U, V, T]))                          ";
                           :& " print and(P)                                              ";
Dennis
sumber
17
CJam? Lebih mirip CRup.
Ingo Bürk
12

Haskell, 92 90 86 84 114 110 99 98

persyaratan program lengkap sangat menjengkelkan. Saya bertanya-tanya mengapa ada orang yang memerlukan ini.

m(n:s)=all(<1)$foldl(\r@(p:s)n->reverse(take n s)++(p*r!!n):drop n s)[0..n]s
main=readLn>>=print.m

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:

*Main> main
[2,1,1,2,2]
True
haskeller bangga
sumber
1
+1 karena tidak menggunakan Python 2;)
Calvin Hobbies
@ Calvin'sHobbies lol
haskeller bangga
Saya khawatir program lengkap diperlukan ...
John Dvorak
1
@ JanDvorak Saya tidak melihat itu ... Saya hanya bertanya apakah suatu fungsi baik-baik saja di komentar pertanyaan. jika tidak, saya akan mengubahnya
haskeller bangga
@proudhaskeller sekarang Anda telah diberitahu secara eksplisit oleh OP ... Saya mengharapkan perubahan segera.
John Dvorak
10

Python, 92 byte

Saya pikir ini bekerja:

s=[1]+[0,0]*input()
for f in input():x=f*2;s[0]=s[x]=s[0]|s[x];s[:x]=s[x-1::-1]
print all(s)

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:

$ python pancakes.py
2
1, 1, 2, 2
True
grc
sumber
Itu adalah cara yang sangat, sangat cerdas untuk membalikkan. +1
Soham Chowdhury
Sepertinya Anda mengecualikan pelat dari cek "is everything syrupy". Apakah kamu perlu? Ketika semua wajah panekuk dilapisi, piring akan menyentuh wajah panekuk sirop, sehingga piring juga akan menjadi sirup.
user2357112 mendukung Monica
@ user2357112 Ya, Anda benar. Terima kasih!
grc
8

Python 2: 75

Penyederhanaan solusi grc dan feersum.

n,b=input()
s=[1]+[0]*n
for x in b:s[:x+1]=s[x::-1];s[x]|=s[0]
print all(s)

Menyimpan keadaan sirup pada 2*n+1tepi pancake adalah berlebihan karena menyentuh ujung selalu sama. Ini sebagai gantinya mengingat keadaan setiap n+1persimpangan pancake. Dengan begitu, transfer sirup secara otomatis diperhitungkan.

Satu-satunya pembaruan yang diperlukan adalah mempertahankan sirup di xpersimpangan saat flip memotongnya. Hal ini dilakukan oleh atau-ing sirup pasca-flip di 0dalam x.

Mengambil input dua kali tidak mempengaruhi jumlah karakter.

s=[1]+[0]*input()
for x in input():s[:x+1]=s[x::-1];s[x]|=s[0]
print all(s)
Tidak
sumber
5

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.

n,F=input()
L=[1]+2*n*[0]
for f in F:f*=2;L[0]=L[f]=L[0]|L[f];L[:f]=L[~-f::-1]
print[1]*2*n<L

Input / output sampel:

2, [1, 1, 2]

 

False
feersum
sumber
3

APL, 77

∧/⊃{x[1]+←⍺⌷x←⍵⋄(⌽⍺↑x),⍺↓x}/(⌽1+⎕),⊂1,⎕⍴0
TwiNight
sumber
2

Python 2, 107

d=[1]+[0,0]*input()
for i in input():n=2*i;d[:n]=reversed(d[:n]);d[n]=d[n-1]=d[n]|d[n-1]
print(all(d[:-1]))
Soham Chowdhury
sumber
2

Haskell, 129 125

t(m:l)=all(any(<1).(\i->foldr(\n->foldr($)[].map(n%))[i]l))[0..m]
n%i|i>n=(i:)|i<n=(n-i:)|1>0=(n:).(0:)
main=readLn>>=print.t

Mungkin 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. foldrsecara efektif melintasi daftar membalik ke belakang, oleh karena itu tidak ada reverse.

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 flip npancake, setiap entri menjadi [n-i]jika i<n, [n,0]jika i==n, dan [i]jika i>n. Sisi yang dimaksud telah dilapisi jika dan hanya jika daftar yang dihasilkan setelah semua flips berisi 0(any (<1) ). allmelakukan sisanya, dan mainmengubah semua ini menjadi program runnable.

Program ini mengambil input dari stdindalam bentuk [n_pancakes, flip1, flip2, flip3, ...], diakhiri oleh baris baru.

TheSpanishInquisition
sumber
pendekatan yang menarik.
haskeller bangga
bagaimana kalau alih-alih menggunakan fungsi untuk kode daftar warisan untuk menggunakan daftar, yaitu n%i|i>n=[i]|i<n=[n-i]|0<1=[n,0]dan bukannya foldr($)[].map(n%)memiliki (=<<).(%), yang akan memetakan semua warisan dan bergabung dengan mereka.
haskeller bangga
Anda membuat saya sadar bahwa saya bisa mulai dengan tumpukan [0..]dan mewakili pancake dilapisi sebagai 0 bukannya membuat pancake bukan nol dilapisi. Terima kasih!
haskeller bangga