Pescando redes de cubo

30

Los cubos pueden estar hechos de seis cuadrados como lados. Pero también puedes doblar tres rectángulos de 2x1 por la mitad y pegarlos para formar un cubo. Ahora, en este desafío, obtienes un conjunto de piezas que están hechas de cuadrados, y debes determinar si puedes elegir piezas para formar un cubo unitario. No todas las piezas tienen que usarse, puede que queden algunas.

Detalles

Las piezas se dan como una cadena de dos caracteres diferentes o una imagen en blanco y negro o cualquier formato de ráster 2D conveniente. A continuación, supongo que los píxeles que forman las piezas son negros y el fondo es blanco.

Se considera que dos píxeles que comparten un lado pertenecen a la misma pieza. Las piezas solo se pueden plegar a lo largo de las líneas de la cuadrícula que separan los píxeles, y no se pueden cortar. Cada lado del cubo tiene el tamaño de un píxel, y cada lado del cubo solo puede estar hecho de una sola capa.

El resultado debe ser verdadero o falso. valor .

Casos de prueba

A continuación, los espacios son símbolos de fondo y hash# representan las piezas.

(más por agregar)

Válido

##  
 ## 
  ##

 #  
####
 #  

# # # # # # #

# ##
## #

Inválido

###
###

#  #
####

### ## ####

Ejecute el siguiente fragmento para obtener más casos de prueba.

Mostrar fragmento de código

PD: Esta es una generalización de este desafío.

code-golf geometry falla
fuente
¿Por qué el fragmento de código JS solo imprime casos de prueba codificados adicionales? ¿Por qué no simplemente ponerlos en el post jaja?
Magic Octopus Urn
1
@carusocomputing Esa fue solo una medida para evitar que la publicación se abarrote.
falla
¿Habrá siempre seis píxeles encendidos?
Wheat Wizard
No, podría haber más o menos.
defecto
1
@Blue Ah, no, analizar la entrada de piezas es parte del desafío. Esta entrada lo simplificaría bastante, así que no permitiría eso. ¡Gracias por preguntar!
flawr

Respuestas:

7

C, 824803 bytes

#define Z return
#define Y char*b
#define N --n
i,j,n,w,h,A,B,C,D,E,F,G,H;char c[9999],*r,*d;x(b)Y;{if(b<c||*b<35)Z;++n;*b^=1;x(b-1);x(b+1);x(b-w);x(b+w);}m(b,p,y)Y,*p;{d=b;if(!y)for(y=-1,--p;1[++p]&31;)d+=w;for(i=0;*p&31?!(*p&16>>i)||b[i]&1:0;++i>4?p+=y,b+=w,i=0:0);Z!(*p&31)?x(d),n:0;}a(b)Y;{for(j=n=0;j<w*h;++j)if(m(c+j,b,1)||m(c+j,b,0))Z n;Z 0;}f(Y){bzero(c,9999);for(h=0,b=strcpy(c,b);r=b,b=strchr(b+1,10);h++,w=b-r);for(A=2,r=1+"@_`^C@|T@^R@XO@XX`|FB@|PP@|DD@PXN@XHX@XPX`PPXL@XHHX@XLDD@XPPX`PPPXH@PXHHH@PPPPP@";*r;r+=A+=r[-1]/96)while(a(r));A=B=C=D=E=F=G=H=0;while(a("PX")||a("XH")) (n-=3)?N?N?N?0:++H:++G:++F:++C;while(a("^")||a("PPPP"))(n-=4)?N?N?0:++H:++G:++E;while(a("P"))N?N?N?N?N?N?0:++H:++G:++F:++D:++B:++A;Z H||(G&&A)||(F&&B+B+A>1)||(E&&A>1)||D>1||C>1||((D||C)*3+B*2+A>5)*(A>1||B>2||A*B);}

Nota: Incluye una corrección de errores (la entrada anterior identificó falsamente un tromino y dos fichas de dominó como formando un cubo). En el código del controlador TIO, hay más casos de prueba y ahora hay un rastreador de pasa / falla; Los casos de prueba de hexomino se actualizaron con el valor esperado de aprobado / reprobado en la etiqueta.

Pruébalo en línea!

... y antes de explicar esto en detalle, vale la pena una descripción general de alto nivel.

Resumen Básico

Este algoritmo aplica un patrón de comparación para clasificar cada poliomino que encuentra con un patrón dado como su subconjunto. A medida que los polyominoes coinciden, están "sin marcar", excluyéndolos de la coincidencia de patrones nuevamente. La clasificación inicial dada por el comparador es simplemente un recuento del número de mosaicos en el poliomino.

El emparejador se aplica primero para eliminar todos los poliominós que no se pueden plegar en un cubo; Se descarta la clasificación de estos poliominos. La coincidencia tiene éxito si estos poliominós aparecen dentro de los de nivel superior; por lo tanto, solo nos importa el subconjunto más pequeño de "desplegable" para cada clase. Aquí, junto con las codificaciones acolchadas, se muestran todos esos poliominós (excepto sus reflejos verticales). La codificación utiliza los bits 4-0 de cada carácter para representar cuadrados en cada fila:

[^C```] [XHX``] [PPPXH] [XHHX`] [PXN``] [|PP``]
 ####.   ##...   #....   ##...   #....   ###..
 ...##   .#...   #....   .#...   ##...   #....
 .....   ##...   #....   .#...   .###.   #....
 .....   .....   ##...   ##...   .....   .....
 .....   .....   .#...   .....   .....   .....
[|FB``] [XPX``] [PPXL`] [XLDD`] [XPPX`] [|DD``]
 ###..   ##...   #....   ##...   ##...   ###..
 ..##.   #....   #....   .##..   #....   ..#..
 ...#.   ##...   ##...   ..#..   #....   ..#..
 .....   .....   .##..   ..#..   ##...   .....
 .....   .....   .....   .....   .....   .....
[|T```] [^R```] [PXHHH] [XO```] [_````] [PPPPP]
 ###..   ####.   #....   ##...   #####   #....
 #.#..   #..#.   ##...   .####   .....   #....
 .....   .....   .#...   .....   .....   #....
 .....   .....   .#...   .....   .....   #....
 .....   .....   .#...   .....   .....   #....

[XX```]
 ##...
 ##...
 .....
 .....
 .....

Una vez que se eliminan estos poliominós, clasificamos los poliominós restantes en categorías relevantes. Vale la pena señalar que en casi todos los casos, uno solo puede encontrar poliominoes que permanecen (aquellos plegables en cubos) y simplemente buscar sumas de seis. Hay dos excepciones:

  • Un tromino de esquina y un tromino de línea no pueden formar un cubo.
  • Una línea tetromino y un dominó no pueden formar un cubo.

Para poder acomodar esta restricción, formamos 8 categorías, desde AH: A para monominoes (fichas solitarias), B para dominó, C para trominoes de esquina, D para trominoes de línea, E para tetrominoes de línea, F para otros tetrominoes, G para pentominoes y H para hexominoes. Todo lo que no cae en una de estas categorías se ignora. Contar los poliominoes que caen en cada categoría es suficiente.

Al final, solo devolvemos la veracidad o falsedad basada en una ecuación gigante y estas tabulaciones.

Ungolfed con comentarios

i,j,n,w,h,A,B,C,D,E,F,G,H;char c[9999],*r,*d;
x(b)char*b;{      // recursively unmarks polyomino pointed to by b.
   if(b<c||*b<35)return;
   ++n; *b^=1;    // Tabulates tiles in n as it goes.
   x(b-1);x(b+1);x(b-w);x(b+w); // left/up/down/right
}
m(b,p,y)char*b,*p;{ // pattern match area b with pattern p, direction y.
                    //   y=1 scans down; y=0 scans up.
   d=b; // d tracks a tile in the currently matched pattern for unmarking.
        // Note that all patterns are oriented to where "top-left" is a tile.
   if(!y) // ...when scanning up, move p to the end, set y to -1 to count backward,
          //    and advance d to guarantee it points to a tile (now "bottom-left")
      for(y=-1,--p;1[++p]&31;)d+=w;
   // Match the pattern
   for(i=0;*p&31?!(*p&16>>i)||b[i]&1:0;++i>4?p+=y,b+=w,i=0:0);
   return !(*p&31)   // If it matches...
          ? x(d),n   // ...unmark/count total polyomino tiles and return the count
          : 0;
}
a(b)char*b;{ // Scan for an occurrence of the pattern b.
   for(j=n=0;j<w*h;++j)
      if(m(c+j,b,1)||m(c+j,b,0)) // (short circuit) try down then up
         return n;
   return 0;
}
// This is our function.  The parameter is a string containing the entire area,
// delimited by new lines.  The algorithm assumes that this is a rectangular area.
// '#' is used for tiles; ' ' spaces.
f(char*b) {
   bzero(c,9999); // Init categories, c buffer
   for(h=0,b=strcpy(c,b);r=b,b=strchr(b+1,10);h++,w=b-r); // Find width/height
   // Unmark all polyominoes that contain unfoldable subsets.  This was
   // compacted since the last version as follows.  A tracks
   // the current pattern's length; r[-1], usually terminator for the
   // previous pattern, encodes whether the length increases; and o/c
   // the patterns were sorted by length.
   for(A=2,r=1+"@_`^C@|T@^R@XO@XX`|FB@|PP@|DD@PXN@XHX@XPX`PPXL@XHHX@XLDD@XPPX`PPPXH@PXHHH@PPPPP@";*r;r+=A+=r[-1]/96)
      while(a(r));
   A=B=C=D=E=F=G=H=0;
   // Match corner trominoes now to ensure they go into C.
   while(a("PX")||a("XH"))
      (n-=3)
         ?   --n
             ?   --n
                 ?   --n
                    ?   0 // More than 6 tiles?  Ignore it.
                    : ++H // 6 tiles?  It's an H.
                 : ++G // 5 tiles?  It's a G.
             : ++F // 4 tiles?  It's an F.
        : ++C; // only 3 tiles?  It's a C.
   // Now match line tetrominoes to ensure they go into E.
   while(a("^")||a("PPPP"))
      (n-=4)
         ?   --n
             ?   --n
                 ?   0 // More than 6 tiles?  Ignore it.
                 : ++H // 6 tiles?  It's an H.
             : ++G // 5 tiles?  It's a G.
         : ++E; // only 4 tiles?  It's an E.
   // Find all remaining tetrominoes ("P" is a monomino pattern)
   while(a("P"))
      --n
         ?   --n
             ?   --n
                 ?   --n
                     ?   --n
                         ?   --n
                             ?   0 // More than 6 tiles?  Ignore it.
                             : ++H // 6 tiles?  It's an H.
                         : ++G // 5 tiles? It's a G.
                     : ++F // 4 tiles?  It's an F.
                : ++D // 3 tiles?  It's a D.
            : ++B // 2 tiles?  It's a B.
         : ++A; // only 1 tile? It's an A.
   // Figure out if we can form a cube:
   return H               // Yes if we have a foldable hexomino
      ||(G&&A)            // Yes if we have a foldable pentomino
                          // and a monomino
      ||(F&&B+B+A>1)      // Yes if we have a foldable non-line tetromino
                          // and 2 other tiles (dominoes count twice).
                          // Either one domino or two monominoes will do.
      ||(E&&A>1)          // Yes if we have a foldable line tetromino (E)
                          // and two monominoes (A).  Note we can't make a
                          // cube with a line tetromino and a domino (B).
      ||D>1               // Yes if we have two line trominoes
      ||C>1               // Yes if we have two corner trominoes
      ||((D||C)*3+B*2+A>5)
                          // Any combination of trominoes, dominoes, monominoes>6,
                          // where trominoes are used at most once
                          // (via logical or)...
         * (A>1||B>2||A*B)
                          // ...times this includer/excluder fudge factor
                          // that culls out the one non-working case;
                          // see table:
                          //
                          // Trominos Dominos Monomos Cube  A>1 B>2 A*B
                          //    1        0       3+    yes   Y   N   0
                          //    1        1       1+    yes   Y   N   1
                          //    1        2       0     no    N   N   0
                          //    0+       3       0+    yes   Y   Y   1
      ;
}
H Walters
fuente
Esto no funcionara. La pregunta dice que algunas piezas pueden ser inusitado
John Dvorak
@ JanDvorak ¡Gracias por señalar eso!
H Walters
A mí me parece extraño que lo deletree tromino en lugar de triomino , pero al parecer ambos son deletreos válidos.
mbomb007