Kubus dapat dibuat dari enam kotak sebagai sisi. Tetapi Anda juga bisa melipat tiga 2x1 persegi panjang menjadi dua dan menempelkannya menjadi satu kubus. Sekarang dalam tantangan ini Anda mendapatkan satu set potongan yang masing-masing terbuat dari kotak, dan Anda harus menentukan apakah Anda dapat memilih potongan untuk membentuk unit kubus. Tidak semua bagian harus digunakan, mungkin ada beberapa yang tersisa.

Detail

Potongan diberikan sebagai string dari dua karakter yang berbeda atau gambar hitam dan putih atau format raster 2D yang nyaman. Berikut ini saya menganggap piksel yang membentuk potongan berwarna hitam, dan latar belakang berwarna putih.

Dua piksel yang berbagi sisi dianggap milik bagian yang sama. Potongan hanya bisa dilipat di sepanjang garis kisi yang memisahkan piksel, dan tidak dapat dipotong. Setiap sisi kubus memiliki ukuran satu piksel, dan setiap sisi kubus hanya dapat dibuat dari satu lapisan tunggal.

Output harus truthy atau falsey nilai.

Testcases

Berikut ini, spasi adalah latar belakang dan simbol hash #mewakili potongan.

(lebih banyak untuk ditambahkan)

Sah

##  
 ## 
  ##

 #  
####
 #  

# # # # # # #

# ##
## #

Tidak valid

###
###

#  #
####

### ## ####

Jalankan cuplikan berikut untuk lebih banyak 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: Ini generalisasi dari tantangan ini}

C, 824 803 byte

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

Catatan: Termasuk perbaikan bug (entri sebelumnya secara salah mengidentifikasi tromino dan dua kartu domino sebagai bentuk kubus). Dalam kode driver TIO, ada lebih banyak kasus uji dan sekarang ada pelacak lulus / gagal; kasus uji hexomino diperbarui dengan nilai lulus / gagal yang diharapkan pada label.

Cobalah online!

... dan sebelum menjelaskan ini secara terperinci, ada baiknya ikhtisar tingkat tinggi.

Tinjauan Dasar

Algoritma ini menerapkan pencocokan pola untuk mengklasifikasikan setiap polyomino yang ditemukannya dengan pola yang diberikan sebagai subsetnya. Karena polyomino cocok, mereka "tidak ditandai", mengeluarkannya dari pencocokan pola lagi. Klasifikasi awal yang diberikan oleh korek api hanyalah hitungan jumlah ubin di poliomino.

Pencocokan diterapkan terlebih dahulu untuk menyisihkan semua poliomino yang tidak dapat dilipat ke kubus; klasifikasi polyominos ini dibuang. Kecocokan berhasil jika polyomino ini muncul dalam yang tingkat yang lebih tinggi; oleh karena itu, kami hanya peduli pada subset terkecil dari "tidak dapat dilipat" untuk setiap kelas. Ditampilkan di sini bersama dengan penyandian berlapis adalah semua polyominoes tersebut (tidak termasuk refleksi vertikal). Pengkodean menggunakan bit 4-0 dari setiap karakter untuk mewakili kotak pada setiap baris:

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

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

Setelah polyomino ini diambil, kami mengelompokkan polomino yang tersisa ke dalam kategori yang relevan. Perlu dicatat bahwa dalam hampir semua kasus, seseorang hanya dapat menemukan poliomino yang tersisa (yang dapat dilipat menjadi kubus) dan hanya mencari jumlah enam. Ada dua pengecualian:

• Tromino sudut dan tromino garis tidak dapat membentuk kubus
• Tetromino garis dan domino tidak dapat membentuk kubus

Untuk dapat mengakomodasi pembatasan ini, kami membentuk 8 kategori, dari AH: A untuk monomino (ubin tunggal), B untuk domino, C untuk tromino sudut, D untuk tromino garis, E untuk tetromino garis, E untuk tetromino garis, F untuk tetromino garis, F untuk tetromino lainnya, G untuk pentomino, dan H untuk hexomino. Apa pun yang tidak termasuk dalam salah satu dari kategori ini diabaikan saja. Menghitung poliomino yang termasuk dalam setiap kategori sudah cukup.

Pada akhirnya, kami hanya mengembalikan kebenaran atau kepalsuan berdasarkan persamaan raksasa dan tabulasi ini.

Tidak dikoleksi dengan komentar

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