Fishing for Cube Nets

Question

Cubes can be made of six squares as sides. But you could also fold three 2x1 rectangles in half and glue them together to form a cube. Now in this challenge you get a set of pieces which are each made from squares, and you have to determine whether you can choose pieces to form a unit cube. Not all of the pieces have to be used, there might be some left over.

Details

The pieces are given as a string of two different characters or a black and white image or any convenient 2D raster format. In the following I assume the pixels that form the pieces are black, and the background is in white.

Two pixels who share a side are considered to belong to the same piece. The pieces can only be folded along the gridlines that separate the pixels, and they cannot be cut. Each side of the cube has the size of one pixel, and each side of the cube can only be made of a single layer.

The output must be a truthy or falsey value.

Testcases

In the following, the spaces are background and hash symbols # represent the pieces.

(more to be added)

Valid

## 
 ## 
 ##

---

 # 
####
 # 

---

# # # # # # #

---

# ##
## #

Invalid

###
###

---

# #
####

---

### ## ####

Run the following snippet for more testcases.

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: This is a generalization of this challenge}

• Magic Octopus Urn: Why is the JS code snippet just printing additional hardcoded testcases? Why not just put them in the post haha?
• flawr: @carusocomputing That was just a measure to prevent the post from being to cluttered.
• Wheat Wizard: Will there always be six pixels on?
• flawr: No, there might more or less on.
• flawr: @Blue Ah no, analyzing the input for pieces is part of the challenge. This input would simplify that quite a bit, so I would not allow that. Thank you for asking!

Answer 1

C, (削除) 824 (削除ここまで) 803 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);}

Note: Includes a bug fix (the previous entry falsely identified a tromino and two dominoes as forming a cube). In the TIO driver code, there are more test cases and there's now a pass/fail tracker; hexomino test cases were updated with the expected pass/fail value in the label.

Try it online!

...and before explaining this in detail, it's worth a high level overview.

Basic Overview

This algorithm applies a pattern matcher to classify each polyomino it finds with a given pattern as its subset. As polyominoes are matched they are "unmarked", excluding them from pattern matching again. The initial classification given by the matcher is simply a count of the number of tiles in the polyomino.

The matcher is applied first to cull out all polyominoes that cannot be folded onto a cube; the classification of these polyominos is discarded. The match succeeds if these polyominoes appear within higher level ones; therefore, we only care about the smallest subset of "unfoldable" for each class. Shown here along with padded encodings are all such polyominoes (excluding their vertical reflections). The encoding uses bits 4-0 of each character to represent squares on each row:

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

Once these polyominoes are culled, we categorize the remaining polyominoes into relevant categories. It's worth noting that in almost all cases, one can just find polyominoes that remain (those foldable onto cubes) and simply search for sums of six. There are two exceptions:

• A corner tromino and a line tromino cannot form a cube
• A line tetromino and a domino cannot form a cube

In order to be able to accommodate this restriction we form 8 categories, from A-H: A for monominoes (lone tiles), B for dominoes, C for corner trominoes, D for line trominoes, E for line tetrominoes, F for other tetrominoes, G for pentominoes, and H for hexominoes. Anything not falling into one of these categories is just ignored. Counting polyominoes that fall into each category suffices.

At the end, we just return truthiness or falsiness based on a giant equation and these tabulations.

Ungolfed with comments

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

• John Dvorak: This won't work. The question says some pieces may be unused
• H Walters: @JanDvorak Thanks for pointing that out!
• mbomb007: To me it seems weird that you spell it tromino instead of triomino, but they are both valid spellings, it seems.