Recubriendo cada panqueque

35

Tienes una pila de panqueques en un plato con una gota de jarabe en la parte superior tan gruesa que no puede correr por los lados. No estará contento de comer hasta que las dos caras de cada panqueque hayan tocado al menos el jarabe, pero en este momento solo una cara del panqueque superior tiene.

Usted sabe que el jarabe nunca empapará ni siquiera un panqueque, pero puede transferirse indefinidamente a través del contacto cara a cara entre dos panqueques. Una vez que la cara de un panqueque ha tocado jarabe, se considera recubierto con jarabe para siempre, y hará que cualquier cara sin jarabe que lo toque también esté cubierta de jarabe. También es posible transferir el jarabe hacia y desde el lado superior de la placa.

Procedes a cubrir cada cara de panqueque con jarabe insertando una espátula debajo de uno o más panqueques y volteándolos por completo, exactamente como se hace en la clasificación de panqueques . (Desafortunadamente, esta espátula es resistente al jarabe y no ayuda a distribuir el jarabe al tocar las caras de los panqueques). Lamentablemente, pierde la noción de qué caras de panqueques han tocado el jarabe, pero recuerda las volteretas que hizo.

Teniendo en cuenta sus cambios anteriores, ¿puede determinar si sus panqueques ya están cubiertos con jarabe?

Reto

Escriba un programa que tome un entero positivo N para la cantidad de panqueques, y una lista de enteros positivos (todos <= N) para los saltos que ha realizado hasta ahora. Cada número en la lista representa el número de panqueques que se voltearon. Emite un valor verdadero si los panqueques se están recubriendo y un valor falso si no. ( definición de verdad / falsedad )

La entrada debe provenir de stdin o la línea de comando y la salida debe ir a stdout (o las alternativas más cercanas). Está bien si su entrada necesita un poco de formato adicional: por ejemplo, en [1, 1, 2, 2]lugar de 1 1 2 2para la lista.

Ejemplos

Suponga N = 2, entonces tenemos una pila de dos panqueques en un plato, comenzando con el jarabe en la parte superior.

Si la lista es 1 1 2 2, esto significa que nosotros ...

  • voltear el panqueque superior - cubriendo la cara superior del panqueque inferior
  • voltee la parte superior nuevamente - cubriendo la cara inferior original del panqueque superior
  • voltear ambos - cubriendo la placa
  • voltee ambos de nuevo, cubriendo la cara inferior original del panqueque inferior

Dado que las cuatro caras están recubiertas, la salida sería algo así como Trueo 1.

Si la lista es 1 2 2 1, esto significa que nosotros ...

  • voltear el panqueque superior - cubriendo la cara superior del panqueque inferior
  • voltear los dos, sin recubrir nada
  • voltear ambos de nuevo, sin recubrir nada
  • voltee la parte superior nuevamente - cubriendo la cara inferior original del panqueque superior

Dado que la cara que toca la placa aún no contiene jarabe, la salida sería algo así como Falseo 0.

Notas

  • La lista desplegable puede ser arbitrariamente grande y puede estar vacía, en cuyo caso la salida es falsa.
  • La placa actúa como un jarabe-portadora, pero no importa si se queda recubierta o no. (De hecho, cualquier solución flip voluntad recubrir la placa porque la cara pancake que toca debe recubrirse, pero independientemente.)
  • La placa no puede ser volteado.
  • Se puede asumir estos panqueques son disco unidad sin partes para hablar de, sólo dos caras opuestas.

Tanteo

Este es el código de golf. La solución más corta en bytes victorias.

Pasatiempos de Calvin
fuente
44
Este es un desafío muy, muy agradable. ;)
Soham Chowdhury
es una función que obtiene una lista y devuelve un valor booleano ¿está bien?
orgulloso Haskeller
99
Debería haber una bonificación si alguien puede implementarlo en este idioma .
grc
3
@grc ¡Ahora hay una recompensa por eso!
Aficiones de Calvin
2
Aquí está mi solución en Pancake Stack Put syrup on the pancakes!
:;

Respuestas:

9

Cjam, 32 30 29 bytes

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

Pruébalo en línea.

Casos de prueba

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

Cómo funciona

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
fuente
17
Cjam? Más como crup.
Ingo Bürk
12

Haskell, 92 90 86 84 114 110 99 98

El requisito de un programa completo es muy molesto. Me pregunto por qué alguien requeriría esto.

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

Esta solución funciona representando la pila de panqueques por una lista de los lados, cuando los panqueques adyacentes comparten el mismo lado. cada lado es un número y un lado está cubierto si tiene un valor cero.

correr como:

*Main> main
[2,1,1,2,2]
True
orgulloso Haskeller
fuente
1
+1 por no usar Python 2;)
Calvin's Hobbies
@ Calvin'sHobbies lol
orgulloso haskeller
Me temo que se requiere un programa completo ...
John Dvorak
1
@ JanDvorak No lo vi ... Solo pregunté si una función está bien en los comentarios de la pregunta. si no es así, lo cambiaré
orgulloso Haskeller
@proudhaskeller ahora OP te ha dicho explícitamente ... Espero un cambio pronto.
John Dvorak
10

Python, 92 bytes

Creo que esto funciona:

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)

Utiliza una lista de caras de panqueque (placa incluida) para recordar cuáles están recubiertas con jarabe. Los panqueques se invierten invirtiendo parte de la lista, pero cualquier jarabe se transfiere primero entre la cara superior y la cara recién revelada.

Uso:

$ python pancakes.py
2
1, 1, 2, 2
True
grc
fuente
Esa es una forma muy, muy inteligente de revertir. +1
Soham Chowdhury
Parece que está excluyendo la placa del control "todo está almibarado". Necesitas Cuando todas las caras de panqueque estén cubiertas, el plato tocará una cara de panqueque almibarada, por lo que el plato también estará almibarado.
user2357112 es compatible con Monica el
@ user2357112 Sí, tienes razón. ¡Gracias!
grc
8

Pitón 2: 75

Una simplificación de la solución de grc y 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)

Almacenar el estado de jarabe de los 2*n+1bordes de los panqueques es redundante porque tocar los bordes es siempre el mismo. Esto en cambio recuerda el estado de cada uno den+1 uniones panqueques. De esa manera, la transferencia de jarabe se contabiliza automáticamente.

La única actualización necesaria es preservar el jarabe en la xunión cuando un volteo lo corta. Esto se hace colocando el jarabe post-flip 0en x.

Tomar la entrada dos veces no afecta el recuento de caracteres.

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

Python 2, 93 bytes

Al principio iba a publicar mi respuesta, pero luego grc ya había publicado una muy similar un minuto antes. Así que traté de encontrar algunas mejoras. Lo único que pude encontrar es usar una comparación de lista lexicográfica en lugar de all().

Editar: se corrigió un error introducido al intentar sin éxito diferentes métodos de entrada que no cambia el recuento de caracteres.

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

Entrada / salida de muestra:

2, [1, 1, 2]

 

False
Feersum
fuente
3

APL, 77

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

Pitón 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
fuente
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

Probablemente todavía no esté completamente golfizado, pero funciona sin manipular una lista de lados recubiertos. En cambio, funciona hacia atrás para descubrir si un lado determinado de un panqueque alguna vez ha entrado en contacto con algo que era el lado superior al principio. foldrefectivamente atraviesa la lista de volteos hacia atrás, por lo tanto no hay reverse.

Así que aquí está el algoritmo: mapeamos todos los lados relevantes ( [0..m]) y hacemos una lista de los lados de los que nuestro lado hereda el jarabe en cada paso, comenzando desde la parte posterior: inicialmente la lista es justa [i], pero con un giro de npanqueques, cada entrada se convierte en [n-i]if i<n, [n,0]if i==ny [i]if i>n. El lado en cuestión se ha cubierto si y solo si la lista resultante después de todos los cambios contiene un 0( any (<1)). allhace el resto ymain convierte todo esto en un programa ejecutable.

El programa toma su entrada stdinen forma de [n_pancakes, flip1, flip2, flip3, ...], terminada por una nueva línea.

La Inquisición Española
fuente
Enfoque interesante.
orgulloso Haskeller
¿qué tal en lugar de usar funciones para codificar la lista de herencias para usar listas, es decir, n%i|i>n=[i]|i<n=[n-i]|0<1=[n,0]y en lugar de foldr($)[].map(n%)tener (=<<).(%), que asignará todas las herencias y las unirá.
orgulloso Haskeller
me hiciste darme cuenta de que puedo comenzar con una pila de [0..]y representar un panqueque recubierto como 0 en lugar de hacer panqueques recubiertos con cero. ¡Gracias!
orgulloso Haskeller