큐브 그물 낚시 스 니펫 표시 document.getElementById(“asdfasdf”).style.display = “block”; <div id=”asdfasdf”

큐브는 측면으로 6 개의 사각형으로 만들 수 있습니다. 그러나 두 개의 2×1 사각형을 반으로 접어 서로 붙일 수 있습니다. 이제이 도전에서 당신은 각각 정사각형으로 만들어진 일련의 조각을 얻습니다. 그리고 당신은 당신이 단위 큐브를 형성하기 위해 조각을 선택할 수 있는지를 결정해야합니다. 모든 조각을 사용해야하는 것은 아니며 일부가 남아있을 수 있습니다.

세부

조각은 두 개의 다른 문자로 된 문자열이나 흑백 이미지 또는 편리한 2D 래스터 형식으로 제공됩니다. 다음에서는 조각을 형성하는 픽셀이 검은 색이고 배경이 흰색이라고 가정합니다.

한면을 공유하는 두 개의 픽셀은 같은 조각에 속하는 것으로 간주됩니다. 조각은 픽셀을 분리하는 눈금 선을 따라 접을 수만 있으며 잘라낼 수 없습니다. 큐브의 각면의 크기는 1 픽셀이며 큐브의 각면은 단일 레이어로만 만들 수 있습니다.

결과는 진실 또는 거짓 값 이어야 합니다.

테스트 케이스

다음에서 공백 은 배경이며 해시 기호 #는 조각을 나타냅니다.

(추가 할 내용)

유효한

##
 ##
  ##

 #
####
 #

# # # # # # #

# ##
## #

잘못된

###
###

#  #
####

### ## ####

더 많은 테스트 사례를 보려면 다음 스 니펫을 실행하십시오.

코드 스 니펫 표시

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>
Expand snippet

추신 : 이것은 이 도전 의 일반화입니다

답변

C, 824803 바이트

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

참고 : 버그 수정이 포함되어 있습니다 (이전 항목에서는 큐브를 구성하는 것으로 트로 미노와 두 개의 도미노를 잘못 식별했습니다).
TIO 드라이버 코드에는 더 많은 테스트 사례가 있으며 이제 합격 / 불합격 추적기가 있습니다. 헥소 미노 테스트 사례가 라벨의 예상 합격 / 불합격 값으로 업데이트되었습니다.

온라인으로 사용해보십시오!

… 그리고 이것을 자세히 설명하기 전에 높은 수준의 개요를 볼 가치가 있습니다.

기본 개요

이 알고리즘은 패턴 매처를 적용하여 주어진 패턴을 서브셋으로 사용하여 찾은 각 폴리 노 미노를 분류합니다. 폴리 노 미노가 일치하면 패턴 일치에서 다시 제외하고 “표시되지 않음”입니다. 매 처가 제공 한 초기 분류는 단순히 polyomino의 타일 수입니다.

정합 기는 큐브에 접을 수없는 모든 폴리 아미노를 제거하기 위해 먼저 적용됩니다. 이 polyominos의 분류는 폐기됩니다. 이러한 폴리 노 미노가 더 높은 수준 내에 있으면 일치합니다. 따라서 우리는 각 클래스에 대한 “펼칠 수없는”의 가장 작은 부분 집합에만 관심이 있습니다. 패딩 된 인코딩과 함께 여기에 표시되는 모든 폴리 아미노는 (수직 반사 제외)입니다. 인코딩은 각 문자의 4-0 비트를 사용하여 각 행의 사각형을 나타냅니다.

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

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

이러한 폴리 아미노가 제거되면 나머지 폴리 아미노는 관련 범주로 분류됩니다. 에 그 지적이의 가치가 거의 모든 경우에, 하나는 단지 (큐브 위에 그 접이식)을 유지하고 단순히 여섯의 합계를 검색 polyominoes를 찾을 수 있습니다. 두 가지 예외가 있습니다.

  • 코너 트로 미노와 라인 트로 미노는 큐브를 만들 수 없습니다
  • 라인 테트로 미노와 도미노는 큐브를 만들 수 없습니다

이러한 제한을 수용하기 위해 AH에서 A : 모노 노미 (A) (모노 타일), B (도미노), C (코너 트로 미노), D (라인 트로 미노), E (테로 미노 F), G 펜토미노의 경우 H, 헥소 미노의 경우 H 이러한 범주 중 하나에 속하지 않는 것은 무시됩니다. 각 범주에 해당하는 폴리오 미노를 계산하면 충분합니다.

결국, 우리는 거대한 방정식과 이러한 표를 기반으로 진실성 또는 허위성을 반환합니다.

댓글이없는 언 골프

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

답변