Würfel können aus sechs Quadraten als Seiten bestehen. Sie können aber auch drei 2x1-Rechtecke in zwei Hälften falten und zu einem Würfel zusammenkleben. In dieser Herausforderung erhalten Sie eine Reihe von Teilen, die jeweils aus Quadraten bestehen, und Sie müssen bestimmen, ob Sie Teile auswählen können, um einen Einheitswürfel zu bilden. Es müssen nicht alle Teile verwendet werden, möglicherweise sind noch einige übrig.

Einzelheiten

Die Stücke werden als Zeichenfolge mit zwei verschiedenen Zeichen oder als Schwarzweißbild oder in einem beliebigen geeigneten 2D-Rasterformat ausgegeben. Im Folgenden gehe ich davon aus, dass die Pixel, aus denen die Teile bestehen, schwarz und der Hintergrund weiß sind.

Zwei Pixel, die sich eine Seite teilen, gehören zum selben Objekt. Die Teile können nur entlang der Gitterlinien gefaltet werden, die die Pixel trennen, und sie können nicht geschnitten werden. Jede Seite des Würfels hat die Größe eines Pixels, und jede Seite des Würfels kann nur aus einer einzelnen Schicht bestehen.

Die Ausgabe muss ein wahrer oder falscher Wert sein.

Testfälle

Im Folgenden sind die Leerzeichen Hintergrund- und Raute-Symbole #repräsentieren die Teile.

(mehr hinzugefügt werden)

Gültig

##  
 ## 
  ##

 #  
####
 #  

# # # # # # #

# ##
## #

Ungültig

###
###

#  #
####

### ## ####

Führen Sie das folgende Snippet aus, um weitere Testfälle zu erhalten.

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: Dies ist eine Verallgemeinerung dieser Herausforderung}

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

Hinweis: Beinhaltet eine Fehlerbehebung (im vorherigen Eintrag wurden fälschlicherweise ein Tromino und zwei Dominosteine ​​als Würfel identifiziert). Im TIO-Treibercode gibt es weitere Testfälle und einen Pass / Fail-Tracker. Hexomino-Testfälle wurden mit dem erwarteten Pass / Fail-Wert auf dem Etikett aktualisiert.

Probieren Sie es online!

... und bevor Sie dies im Detail erläutern, lohnt sich ein Überblick auf hoher Ebene.

Grundlegende Übersicht

Dieser Algorithmus wendet einen Mustervergleicher an, um jedes gefundene Polyomino mit einem bestimmten Muster als Teilmenge zu klassifizieren. Wenn Polyominoes abgeglichen werden, werden sie "nicht markiert", wodurch sie vom erneuten Mustervergleich ausgeschlossen werden. Die vom Matcher angegebene anfängliche Klassifizierung ist einfach eine Zählung der Anzahl der Kacheln im Polyomino.

Der Matcher wird zuerst angewendet, um alle Polyominoes zu entfernen, die nicht auf einen Würfel gefaltet werden können. Die Klassifizierung dieser Polyominos wird verworfen. Das Match ist erfolgreich, wenn diese Polyomino in höheren Levels erscheinen. Daher kümmern wir uns nur um die kleinste Teilmenge von "entfaltbar" für jede Klasse. Zusammen mit den gepolsterten Codierungen sind hier alle derartigen Polyominoe (mit Ausnahme ihrer vertikalen Reflexionen) gezeigt. Die Codierung verwendet die Bits 4-0 jedes Zeichens, um Quadrate in jeder Zeile darzustellen:

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

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

Sobald diese Polyominoes ausgesondert sind, kategorisieren wir die verbleibenden Polyominoes in relevante Kategorien. Es ist erwähnenswert, dass man in fast allen Fällen nur noch verbleibende Polyominoes (die auf Würfel faltbar sind) finden und einfach nach sechs suchen kann. Es gibt zwei Ausnahmen:

• Ein Eck- und ein Linientromino können keinen Würfel bilden
• Ein Linientetromino und ein Domino können keinen Würfel bilden

Um dieser Einschränkung gerecht zu werden, bilden wir 8 Kategorien, von AH: A für Monominoes (Einzelplättchen), B für Dominoes, C für Ecktrominoes, D für Linientrominoes, E für Linientetrominoes, F für andere Tetrominoes, G für Pentominos und H für Hexominos. Alles, was nicht in eine dieser Kategorien fällt, wird einfach ignoriert. Es reicht aus, Polyominoes zu zählen, die in jede Kategorie fallen.

Am Ende geben wir nur Wahrhaftigkeit oder Falschheit zurück, basierend auf einer riesigen Gleichung und diesen Tabellen.

Ungolfed mit Kommentaren

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