Les cubes peuvent être constitués de six carrés comme côtés. Mais vous pouvez également plier trois rectangles 2x1 en deux et les coller ensemble pour former un cube. Maintenant, dans ce défi, vous obtenez un ensemble de pièces qui sont chacune faites de carrés, et vous devez déterminer si vous pouvez choisir des pièces pour former un cube unitaire. Toutes les pièces ne doivent pas être utilisées, il peut en rester.

Détails

Les pièces sont données sous la forme d'une chaîne de deux caractères différents ou d'une image en noir et blanc ou tout format raster 2D pratique. Dans ce qui suit, je suppose que les pixels qui forment les pièces sont noirs et l'arrière-plan est en blanc.

Deux pixels qui partagent un côté sont considérés comme appartenant à la même pièce. Les pièces ne peuvent être pliées que le long du quadrillage qui sépare les pixels et ne peuvent pas être coupées. Chaque côté du cube a la taille d'un pixel et chaque côté du cube ne peut être constitué que d'une seule couche.

La sortie doit être une valeur true ou falsey .

Cas de test

Dans ce qui suit, les espaces sont le fond et les symboles de hachage #représentent les pièces.

(plus à ajouter)

Valide

##  
 ## 
  ##

 #  
####
 #  

# # # # # # #

# ##
## #

Invalide

###
###

#  #
####

### ## ####

Exécutez l'extrait de code suivant pour plus de cas de test.

document.getElementById("asdfasdf").style.display = "block";

<div id="asdfasdf" display="none">
<h3>Valid</h3>

    <pre><code>
    ##  
     ## 
      ##
    </code></pre>

    <hr>

    <pre><code>
     #  
    ####
     #  
    </code></pre>

    <hr>

    <pre><code>
    # # # # # # #
    </code></pre>

    <hr>

    <pre><code>
    # ##
    ## #
    </code></pre>

    <hr>

    <pre><code>
    #   #
    ###
      #
    </code></pre>

    <h3>Invalid</h3>

    <pre><code>
    ###
    ###
    </code></pre>

    <hr>

    <pre><code>
    #  #
    ####
    </code></pre>

    <hr>

    <pre><code>
    ### ## ####
    </code></pre>

    <hr>

    <pre><code>
    ##  ##  ##  ##  
    ##  ##  ##  ##  
      ##  ##  ##  ##
      ##  ##  ##  ##
    </code></pre>
  </div>

^{PS: Ceci est une généralisation de ce défi}

C, 824 803 octets

#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);}

Remarque: inclut un correctif de bogue (l'entrée précédente a identifié à tort un tromino et deux dominos comme formant un cube). Dans le code du pilote TIO, il y a plus de cas de test et il y a maintenant un tracker de réussite / échec; les cas de test hexomino ont été mis à jour avec la valeur de réussite / échec attendue dans l'étiquette.

Essayez-le en ligne!

... et avant d'expliquer cela en détail, cela vaut un aperçu de haut niveau.

Présentation de base

Cet algorithme applique un filtreur de motifs pour classer chaque polyomino qu'il trouve avec un motif donné comme sous-ensemble. Comme les polyominos sont appariés, ils sont "non marqués", les excluant de nouveau de l'appariement de motifs. La classification initiale donnée par le matcher est simplement un comptage du nombre de tuiles dans le polyomino.

Le matcher est appliqué en premier pour éliminer tous les polyominos qui ne peuvent pas être pliés sur un cube; la classification de ces polyominos est écartée. La correspondance réussit si ces polyominos apparaissent dans ceux de niveau supérieur; par conséquent, nous nous soucions uniquement du plus petit sous-ensemble de "dépliables" pour chaque classe. Ici, avec les encodages rembourrés sont tous ces polyominos (à l'exclusion de leurs réflexions verticales). Le codage utilise les bits 4-0 de chaque caractère pour représenter les carrés sur chaque ligne:

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

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

Une fois que ces polyominos sont éliminés, nous classons les polyominos restants en catégories pertinentes. Il convient de noter que dans presque tous les cas, on peut simplement trouver des polyominos qui restent (ceux pliables sur des cubes) et rechercher simplement des sommes de six. Il y a deux exceptions:

• Un tromino d'angle et un tromino de ligne ne peuvent pas former un cube
• Une ligne tetromino et un domino ne peuvent pas former un cube

Afin de pouvoir tenir compte de cette restriction, nous formons 8 catégories, à partir de AH: A pour les monominos (carreaux isolés), B pour les dominos, C pour les tromino d'angle, D pour les trominoes de ligne, E pour les tétrominoes de ligne, F pour les autres tétrominoes, G pour les pentominos et H pour les hexominos. Tout ce qui ne tombe pas dans l'une de ces catégories est simplement ignoré. Il suffit de compter les polyominos qui entrent dans chaque catégorie.

À la fin, nous renvoyons juste la vérité ou la fausseté basée sur une équation géante et ces tabulations.

Non golfé avec des commentaires

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
      ;
}