¿Puedes doblar un hexomino en un cubo?

24

Uno de los juguetes favoritos de mis hijos es un set como este . En realidad, es uno de mis juguetes favoritos: he estado jugando con él y me ha estado dando algunas ideas de desafío de PPCG. Aquí hay uno:

Escriba un programa o función que tome un dibujo lineal ASCII como entrada y decida si se pliega o no en un cubo.

Entrada

La entrada consistirá en exactamente un hexomino construido a partir de cuadrados como este:

+-+
| |
+-+

Por ejemplo, una entrada válida heximino es:

+-+
| |
+-+-+-+-+
| | | | |
+-+-+-+-+
  | |
  +-+

Salida

  • Un valor verdadero si el hexomino se puede plegar en un cubo, o
  • Un valor falso de lo contrario.

Para ahorrarnos un poco de trabajo, wikipedia tiene buenos gráficos de:

  • Los 35 hexominoes:

  • Los 11 hexominós que se pliegan en cubos:

Notas

  • Los hexominoes de entrada pueden tener cualquier rotación o reflexión, no solo los que se muestran en las imágenes de arriba
  • Los hexominós de entrada pueden tener espacios iniciales, pero se alinearán correctamente con respecto a ellos mismos
  • Los hexominós de entrada pueden tener espacio final al final de las líneas y líneas nuevas al final de la entrada
code-golf ascii-art kolmogorov-complexity geometry Trauma digital
fuente
1
¿Puedes explicar por qué hay una etiqueta de procesamiento de imágenes aquí? Ni la pregunta ni la respuesta tendrán que hacer ningún tipo de procesamiento de imágenes para resolver el desafío.
Optimizador
Aclaración sobre el espacio inicial / final: ¿se permiten espacios iniciales / finales innecesarios en cada fila y nuevas líneas innecesarias en la entrada? ¿Debería poder administrar una entrada de más de 1000 caracteres?
edc65
@ edc65 sí, debe esperar el espacio en blanco innecesario que describe. Tamaño de entrada 1000 caracteres máx parece razonable - Voy a editar en que
Digital Trauma
Hmm Me pregunto cuántos cubos hexominoes se pueden exprimir, yuxtaponer, en una página impresa.
luser droog

Respuestas:

7

PMA / Caracoles , 130

.!(z\ |o{c..!(z\ }3){w=(..!(z\ )|b..!(z\ )o{..!(z\ }2|c{..!(z\ }1,2w..!(z\ )|w{..!(z\ }1,2c..!(z\ }4o..!(z\ )(..!(z\ )|n..!(z\ )`2

o más "legible",

?
.!(z\  | o{c..!(z\ }3  )
{w =( ..!(z\ ) | b ..!(z\ ) o {..!(z\ }2  | c {..!(z\ }1,2w..!(z\ ) | w {..!(z\ }1,2c..!(z\  }4
o  ..!(z\ ) ( ..!(z\ ) | n ..!(z\ ) `2

Inusualmente, surgió un problema que puede ser manejado por la cantidad limitada de características implementadas hasta ahora. El !(z\ )patrón determina que la posición actual está en el espacio en el medio de un cuadrado usando una afirmación negativa de que hay un espacio en alguna dirección "octilineal". La idea general es verificar un patrón que coloque un cuadrado en cada una de las 5 ubicaciones necesarias en relación con el cuadrado en el que comienza la coincidencia. Además, debe verificar que no esté en un bloque de cuadrados de 2x2. Antes de que el programa funcionara, tuve que corregir un error con el análisis de paréntesis.

Si el hexomino no mapea un cubo, 0se imprime. Si lo hace, se imprime un número entero positivo (número de coincidencias).

He adaptado este generador poliominó para crear todos los posibles casos de prueba:

n=input()
r=range
T=lambda P:set(p-min(p.real for p in P)-min(p.imag for p in P)*1j for p in P)
A=[]
for i in r(1<<18):
 P=[k%3+k/3*1j for k in r(18)if i>>k&1]
 C=set(P[:1])
 for x in P:[any(p+1j**k in C for k in r(4))and C.add(p)for p in P]
 P=T(P)
 if not(C^P or P in A or len(P)-n):
  #for y in r(4):print''.join(' *'[y+x*1j in P] for x in r(6))
  o = [ [' ']*13 for _ in r(9)]
  for y in r(4):
   for x in r(6):
    if y+x*1j in P: X=2*x;Y=2*y; o[Y][X]=o[Y+2][X]=o[Y][X+2]=o[Y+2][X+2]='+'; o[Y][X+1]=o[Y+2][X+1]='-';o[Y+1][X+2]=o[Y+1][X]='|'
  print '\n'.join(map(''.join,o))
  A+=[T([p*1j**k for p in P])for k in r(4)]
Feersum
fuente
jajajajajajaja más "legible"
Optimizer
5

Ruby, 173148145143 bytes

h=->b,c{[c.count(c.max),c.count(c.min),3].max*2<b.max-b.min}
->s{x=[];y=[];i=j=0
s.bytes{|e|e==43&&x<<i|y<<j;i=e<32?0*j+=1:i+1}
h[x,y]||h[y,x]}

Último cambio: /2en el lado derecho de <reemplazado por *2en el lado izquierdo. Permite la eliminación de un conjunto de()

Explicación

El código consta de dos partes: una función principal sin nombre que realiza el análisis y una función auxiliar sin nombre asignada a la variable hque realiza la comprobación.

La función principal escanea bytewise a través de la cadena, agregando las coordenadas x e y i,jde todos los +símbolos encontrados en x[]y y[]. Luego llama hdos veces. La primera vez que asume que el hexomino es horizontal ( x[]contiene los largos y y[]los anchos) y la segunda vez que asume que es vertical.

La función htoma las coordenadas longitudinales en la matriz y bluego las coordenadas a lo ancho en la matriz c. Calcula la longitud (en cuadrados) por la expresión (b.max.b.min)/2. Si esto es menor o igual a 3, el hexomino debe evaluarse en la otra dirección para que hregrese false.

La inspección de los hexominos mostrará que si la longitud es 4, esos hexominos que se doblarán en un cubo no tienen más de 2 cuadrados (3 +símbolos) en la primera y última fila . La mayoría de los cuadrados se concentran en la fila central, que se convertirá en el ecuador del cubo. Esta condición resulta necesaria y suficiente para un hexomino de longitud 4 que se pliega en un cubo.

Solo hay un hexomino de longitud 5 que se doblará en un cubo. Tiene 3 cuadrados (4 +símbolos) en su primera y última fila. Todos los demás hexominos de longitud 5 tienen 5 o más +símbolos en la primera o última fila.

Solo hay un hexomino de longitud 6. Tiene 7 +símbolos en cada fila.

Al juntar todo esto, es suficiente verificar que la longitud del hexomino sea mayor que 3, y que la cantidad de +símbolos en la primera y última fila (la que sea mayor) sea menor que la longitud.

Sin golf en el programa de prueba

#checking function as explained in text
h=->b,c{[c.count(c.max),c.count(c.min),3].max<(b.max-b.min)/2}

#main function for parsing
f=->s{
  x=[]                 #separate assignments required, 
  y=[]                 #otherwise we get 2 pointers to the same array
  i=j=0                #start coordinates 0,0
  s.bytes{|e|          #scan string bytewise
    e==43&&x<<i|y<<j     #if byte is a + symbol (ascii 43) add the coordinates to arrays x and y
    i=e<32?0*j+=1:i+1    #if byte is before ascii 32 assume newline, increment j and zero i. Otherwise increment i
  }
  h[x,y]||h[y,x]       #call h twice, with x and y in each possible order
}



#VALID INPUTS
puts f["
+-+
| |
+-+-+-+-+
| | | | |
+-+-+-+-+
| |
+-+"]

puts f["
+-+
| |
+-+-+-+-+
| | | | |
+-+-+-+-+
  | |
  +-+"]

puts f["
+-+
| |
+-+-+-+-+
| | | | |
+-+-+-+-+
    | |
    +-+"]
puts f["
+-+
| |
+-+-+-+
| | | |
+-+-+-+-+
    | | |
    +-+-+"]

puts f["
+-+
| |
+-+-+-+-+
| | | | |
+-+-+-+-+
      | |
      +-+"]

puts f["
    +-+
    | |
+-+-+-+-+
| | | | |
+-+-+-+-+
    | |
    +-+"]
puts f["
    +-+
    | |
+-+-+-+
| | | |
+-+-+-+-+
    | | |
    +-+-+"]


puts f["
  +-+
  | |
+-+-+-+-+
| | | | |
+-+-+-+-+
    | |
    +-+"]
puts f["
  +-+
  | |
+-+-+-+
| | | |
+-+-+-+-+
    | | |
    +-+-+"]  
puts f["
+-+-+
| | |
+-+-+-+
  | | |
  +-+-+-+
    | | |
    +-+-+"]

puts f["
  +-+-+-+
  | | | |
  +-+-+-+-+-+
      | | | |
      +-+-+-+
"]


#INVALID INPUTS

puts f["
  +-+-+-+
  | | | |
  +-+-+-+
  | | | |
  +-+-+-+
"]


puts f["
  +-+-+-+-+-+-+
  | | | | | | |
  +-+-+-+-+-+-+

"]


puts f["
  +-+-+
  | | |
  +-+-+
  | |
  +-+
  | |
  +-+
  | |
  +-+
  | |
  +-+
"]

puts f["
  +-+-+-+-+-+
  | | | | | |
  +-+-+-+-+-+
    | |
    +-+
"]

puts f["
      +-+
      | |
  +-+-+-+-+-+
  | | | | | |
  +-+-+-+-+-+
"]

puts f["
  +-+-+-+-+
  | | | | |
  +-+-+-+-+-+
        | | |
        +-+-+"]

puts f["
  +-+-+-+-+
  | | | | |
  +-+-+-+-+
      | | |
      +-+-+
"] 


puts f["
  +-+-+-+-+
  | | | | |
  +-+-+-+-+
  | | | |
  +-+ +-+
"]

puts f["
 +-+   +-+
 | |   | |
 +-+-+-+-+
 | | | | |
 +-+-+-+-+
"]

puts f["
   +-+-+
   | | |
 +-+-+-+-+
 | | | | |
 +-+-+-+-+
"]

puts f["
  +-+
  | |
  +-+
  | |
  +-+-+-+-+
  | | | | |
  +-+-+-+-+
"]

puts f["
  +-+
  | |
  +-+-+-+
  | | | |
  +-+-+-+
  | |
  +-+
  | |
  +-+
"]

puts f["
  +-+
  | |
+-+-+-+
| | | |
+-+-+-+
| |
+-+
| |
+-+"]

puts f["
  +-+-+
  | | |
  +-+-+
  | |
  +-+-+
  | | |
  +-+-+
    | |
    +-+
"]

puts f["
  +-+-+-+
  | | | |
  +-+-+-+-+
    | | | |
    +-+-+-+
"]

puts f["
  +-+-+-+
  | | | |
  +-+-+-+
      | |
      +-+-+
      | | |
      +-+-+
"]


puts f["
  +-+-+-+
  | | | |
  +-+-+-+-+
      | | |
      +-+-+
        | |
        +-+
"]
Level River St
fuente
pentonimo → hexonimo en tu texto?
Paŭlo Ebermann
3

JavaScript (ES6), 443 431

Editar corrección de errores, problema durante el análisis de entrada, eliminar columnas en blanco 

F=t=>(a=b=c=d=e=f=g=h=0,M=Math.min,
t=t.split('\n').filter(r=>r.trim()>''),
t=t.map(r=>r.slice(M(...t.map(r=>r.search(/\S/))))),
t.map((r,i)=>i&1&&[...r].map((_,j)=>j&1&&r[j-1]==r[j+1]&t[i-1][j]==t[i+1][j]&r[j-1]=='|'
&&(y=i>>1,x=j>>1,z=y*5,w=x*5,a|=1<<(z+x),e|=1<<(w+y),b|=1<<(4+z-x),f|=1<<(4+w-y),c|=1<<(20-z+x),g|=1<<(20-w+y),d|=1<<(24-z-x),h|=1<<(24-w-y)
))),~[1505,2530,3024,4578,252,6552,2529,4577,2499,4547,7056].indexOf(M(a,b,c,d,e,f,g,h)))

Eso es muy largo, e incluso más, ya que analizar la entrada es una gran parte de la tarea.

Lo que hago es verificar si la entrada dada es uno de los 11 hexominós plegables.

Cada hexomino plegable se puede asignar a un mapa de bits de 5x5 (hasta 8 diferentes, con simmetría y rotaciones). Tomado los mapas de bits como un número de 25 bits, he encontrado los valores mínimos para los 11 hexominós anotados, usando el siguiente código (con un formato de entrada muy simple)

h=[ // Foldable hexominoes
'o\noooo\no', ' o\noooo\n o', // pink
'o\noooo\n   o', ' o\noooo\n  o', 'ooo\n  ooo', 'oo\n oo\n  oo', //blue
'o\noooo\n o', 'o\noooo\n  o', 'oo\n ooo\n o', 'oo\n ooo\n  o', 'o\nooo\n  oo' // gray
]
n=[]
h.forEach(t=>(
  a=[],
  t.split('\n')
    .map((r,y)=>[...r]
      .map((s,x)=>s>' '&&(
         a[0]|=1<<(y*5+x),a[1]|=1<<(x*5+y),  
         a[2]|=1<<(y*5+4-x),a[3]|=1<<(x*5+4-y),  
         a[4]|=1<<(20-y*5+x),a[5]|=1<<(20-x*5+y),  
         a[6]|=1<<(24-y*5-x),a[7]|=1<<(24-x*5-y))
     )
  ),
n.push(Math.min(...a))
))

Eso da [1505,2530,3024,4578,252,6552,2529,4577,2499,4547,7056]

Entonces, dada la cadena de entrada, tengo que hacer lo mismo para encontrar el mapa de bits mínimo, luego devolver verdadero si este número está presente en mi lista de precalc.

// Not so golfed 

F=t=>(  
  a=b=c=d=e=f=g=h=0,M=Math.min,
  t=t.split('\n').filter(r=>r.trim()>''), // remove blank lines
  t=t.map(r=>r.slice(M(...t.map(r=>r.search(/\S/))))), // remove blank colums to the left
  t.map((r,i)=>i&1&&[...r] // only odd rows
   .map((_,j)=>j&1&& // only odd columns
      r[j-1]==r[j+1]&t[i-1][j]==t[i+1][j]&r[j-1]=='|' // found a cell
         &&(y=i>>1,x=j>>1,z=y*5,w=x*5, // find bitmaps for 8 rotations/simmetries
            a|=1<<(z+x),e|=1<<(w+y),  
            b|=1<<(4+z-x),f|=1<<(4+w-y),  
            c|=1<<(20-z+x),g|=1<<(20-w+y),  
            d|=1<<(24-z-x),h|=1<<(24-w-y)  
    ))),
   ~[1505,2530,3024,4578,252,6552,2529,4577,2499,4547,7056].indexOf(Math.min(a,b,c,d,e,f,g,h)) // look for min
)

Ejecute el fragmento para probar en Firefox

Mostrar fragmento de código

edc65
fuente
Perdóname si me falta algo, pero ¿no podrías ,\nt=tdesde el final de la segunda línea / el comienzo de la tercera línea?
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ revisando seis meses después, el código de análisis podría hacerse 10 ... 15 bytes más corto. Tal como está, necesito la asignación a t en la línea 2 y nuevamente en la línea 3 porque en la línea 3 se usa para encontrar el número de caracteres en blanco para cortar en el lado izquierdo.
edc65