35
\$\begingroup\$

You have a stack of pancakes on a plate with a glob of syrup on top so thick it can't run down the sides. You won't be happy to eat until both faces of each pancake have at least touched the syrup, but right now only one face of the top pancake has.

You know that the syrup will never soak through even one pancake, but it can be transferred indefinitely via face-to-face contact between two pancakes. Once a face of a pancake has touched syrup it is considered coated in syrup forever, and will make any non-syrup coated face that touches it syrup coated as well. It is possible to transfer syrup to and from the top side of the plate as well.

You proceed to coat every pancake face with syrup by inserting a spatula below one or more pancakes and flipping them all over, exactly as is done in pancake sorting. (Unfortunately this spatula is syrup-resistant, and does not help to distribute the syrup by touching pancake faces.) Sadly you lose track of which pancake faces have touched syrup but you do remember the flips you have made.

Given your past flips can you determine if your pancakes are all coated with syrup yet?

Challenge

Write a program that takes in a positive integer N for the number of pancakes, and a list of positive integers (all <= N) for the flips you have made so far. Each number in the list represents the number of pancakes that were flipped. Output a truthy value if the pancakes are done being coated and a falsy value if not. (truthy/falsy definition)

The input should come from stdin or the command line and the output should go to stdout (or closest alternatives). It's fine if your input needs a little extra formatting: e.g. [1, 1, 2, 2] instead of 1 1 2 2 for the list.

Examples

Assume N = 2, so we have a stack of two pancakes on a plate, starting with the syrup on top.

If the list is 1 1 2 2, this means we...

  • flip the top pancake - coating the upper face of the bottom pancake
  • flip the top again - coating the original bottom face of the top pancake
  • flip both - coating the plate
  • flip both again - coating the original bottom face of the bottom pancake

Since all four faces are coated the output would be something like True or 1.

If the list is 1 2 2 1, this means we...

  • flip the top pancake - coating the upper face of the bottom pancake
  • flip both - coating nothing
  • flip both again - coating nothing
  • flip the top again - coating the original bottom face of the top pancake

Since the face touching the plate is still syrup-free the output would be something like False or 0.

Notes

  • The flip list may be arbitrarily large and can be empty, in which case the output is falsy.
  • The plate acts as a syrup-carrier but it doesn't matter if it gets coated or not. (In fact any flip solution will coat the plate because the pancake face it touches must be coated, but regardless.)
  • The plate cannot be flipped.
  • You can assume these pancakes are unit disks with no sides to speak of, only two opposite faces.

Scoring

This is code-golf. The shortest solution in bytes wins.

\$\endgroup\$
  • 4
    \$\begingroup\$ This is a very, very nice challenge. ;) \$\endgroup\$ – Soham Chowdhury Sep 27 '14 at 9:13
  • \$\begingroup\$ is a function that gets a list and returns a boolean is okay? \$\endgroup\$ – proud haskeller Sep 27 '14 at 10:43
  • 9
    \$\begingroup\$ There should be a bonus if anyone can implement it in this language. \$\endgroup\$ – grc Sep 27 '14 at 12:25
  • 3
    \$\begingroup\$ @grc There is now a bounty for just that! \$\endgroup\$ – Calvin's Hobbies Oct 1 '14 at 4:00
  • 2
    \$\begingroup\$ Heres my solution in Pancake Stack: Put syrup on the pancakes! ;) \$\endgroup\$ – rodolphito Oct 7 '14 at 7:20
9
\$\begingroup\$

CJam, 32 30 29 bytes

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

Try it online.

Test cases

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

How it works

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)                                              ";
\$\endgroup\$
  • 17
    \$\begingroup\$ CJam? More like CRup. \$\endgroup\$ – Ingo Bürk Sep 29 '14 at 5:41
12
\$\begingroup\$

Haskell, 92 90 86 84 114 110 99 98

the requirement of a full program is so annoying. I wonder why would anyone require this.

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

this solution works by representing the pile of pancakes by a list of the sides, when adjacent pancakes share the same side. every side is a number, and a side is coated if it has a zero value.

run as:

*Main> main
[2,1,1,2,2]
True
\$\endgroup\$
  • 1
    \$\begingroup\$ +1 for not using Python 2 ;) \$\endgroup\$ – Calvin's Hobbies Sep 27 '14 at 10:23
  • \$\begingroup\$ @Calvin'sHobbies lol \$\endgroup\$ – proud haskeller Sep 27 '14 at 10:23
  • \$\begingroup\$ I'm afraid a full program is required... \$\endgroup\$ – John Dvorak Sep 27 '14 at 10:40
  • 1
    \$\begingroup\$ @JanDvorak I didn't see that... I just asked if a function is okay in the comments of the question. if it isn't, i'll change it \$\endgroup\$ – proud haskeller Sep 27 '14 at 10:44
  • \$\begingroup\$ @proudhaskeller now you have been told explicitly by OP... I expect a change soon. \$\endgroup\$ – John Dvorak Sep 27 '14 at 10:52
10
\$\begingroup\$

Python, 92 bytes

I think this works:

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)

It uses a list of pancake faces (plate included) to remember which are coated with syrup. Pancakes are flipped by reversing part of the list, but any syrup is first transferred between the top face and the newly revealed face.

Usage:

$ python pancakes.py
2
1, 1, 2, 2
True
\$\endgroup\$
  • \$\begingroup\$ That is a really, really clever way to reverse. +1 \$\endgroup\$ – Soham Chowdhury Sep 27 '14 at 9:32
  • \$\begingroup\$ It looks like you're excluding the plate from the "is everything syrupy" check. Do you need to? When all pancake faces are coated, the plate will be touching a syrupy pancake face, so the plate will be syrupy too. \$\endgroup\$ – user2357112 supports Monica Sep 28 '14 at 1:52
  • \$\begingroup\$ @user2357112 Yes, you're right. Thanks! \$\endgroup\$ – grc Sep 28 '14 at 2:11
8
\$\begingroup\$

Python 2: 75

A simplification of grc's and feersum's solution.

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

Storing the syrup state of 2*n+1 pancake edges is redundant because touching edges are always the same. This instead remembers the state of each of n+1 pancake junctions. That way, syrup transfer is automatically accounted for.

The only update needed is to preserve the syrup at the x junction when a flip cuts it. This is done by or-ing the post-flip syrup at 0 into x.

Taking input twice doesn't affect the character count.

s=[1]+[0]*input()
for x in input():s[:x+1]=s[x::-1];s[x]|=s[0]
print all(s)
\$\endgroup\$
5
\$\begingroup\$

Python 2, 93 bytes

At first I was going to post my answer, but then grc had already posted a very similar one a minute before. So I tried to come up with some improvements. The only one I could find is to use a lexicographic list comparison instead of all().

Edit: Fixed a mistake introduced by unsuccessfully trying different input methods which doesn't change character count.

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

Sample input/output:

2, [1, 1, 2]

 

False
\$\endgroup\$
3
\$\begingroup\$

APL, 77

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

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]))
\$\endgroup\$
2
\$\begingroup\$

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

Probably not completely golfed yet, but it works without manipulating a list of coated sides. Instead, it works its way backwards to figure out whether a given side of a given pancake has ever come in contact with anything that was the top side at the beginning. foldr effectively traverses the list of flips backwards, therefore there is no reverse.

So here is the algorithm: We map over all relevant sides ([0..m]) and make a list of sides that our side inherits syrup from at each step, starting from the back: initially the list is just [i], but with a flip of n pancakes, each entry becomes [n-i] if i<n, [n,0] if i==n, and [i] if i>n. The side in question has been coated if and only if the resulting list after all flips contains a 0 (any (<1)). all does the rest, and main converts all this into a runnable program.

The program takes its input from stdin in the form of [n_pancakes, flip1, flip2, flip3, ...], terminated by a newline.

\$\endgroup\$
  • \$\begingroup\$ interesting approach. \$\endgroup\$ – proud haskeller Oct 4 '14 at 9:53
  • \$\begingroup\$ how about instead of using functions to code the inherits list to use lists, i.e. n%i|i>n=[i]|i<n=[n-i]|0<1=[n,0] and instead of foldr($)[].map(n%) have (=<<).(%), that will map all inherits and join them. \$\endgroup\$ – proud haskeller Oct 4 '14 at 10:02
  • \$\begingroup\$ you made me realize I can start with a stack of [0..] and represent a coated pancake as 0 instead of making nonzero pancakes coated. thanks! \$\endgroup\$ – proud haskeller Oct 4 '14 at 10:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.