Coating Every Pancake

Question

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.

Answer 1

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)                                              ";

Answer 2

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

Answer 3

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

Answer 4

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)

Answer 5

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

Answer 6

APL, 77

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

Answer 7

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]))

Answer 8

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.