계단으로 계단 타일링
배경
계단 폴리오 미노는 형상이 계단 부 유사한 사각형 이루어진 폴리오 미노이다. 좀 더 공식적으로, 크기 \ 의 계단 폴리오 미노$n\$ 다음과 같이 정의됩니다.
- 크기 1의 계단 폴리오 미노는 단일 단위 사각형입니다.
- \ 크기의 계단 폴리오 미노$n\$크기와 동일합니다 \$n-1\$가로 막대 길이 \$n\$ 하단에 부착되어 왼쪽 정렬됩니다.
간결함을 위해 그냥 계단 이라고 부르 자 .
예를 들어, 다음은 크기 1에서 4까지의 계단입니다.
#
#
##
#
##
###
#
##
###
####
도전
양의 정수 \$n\$, 크기의 계단 방법의 수를 계산 \$n\$ 하나 이상의 계단으로 바둑판 식으로 배열 할 수 있습니다.
같은 크기의 여러 계단을 타일링에 사용할 수 있으며 계단을 회전 할 수 있습니다. 따라서 다음은 \에 대한 유효한 타일링입니다.$n=4\$:
A
BC
DEF
GHIJ
A
AA
AAA
AAAA
A
AA
BBC
BDCC
표준 코드 골프 규칙이 적용됩니다. 바이트 단위의 가장 짧은 코드가 이깁니다.
테스트 케이스
이 Python 3 참조 솔루션을 사용하여 생성되었습니다 .
1 -> 1
2 -> 2
3 -> 8
4 -> 57
5 -> 806
6 -> 20840
7 -> 1038266
답변
JavaScript (ES10), 250 ... 228227 바이트
n=>(e=g=(a,[x]=a)=>+e?e=0:(x&=-x)?a.map((_,s)=>[b=1<<s,...s?[1,b+=~-b,b]:[]].map((m,d)=>d|x>>s&&g(a.flatMap(S=(v,y)=>(S|=y>s?v:(e|=(v^=M=x*m>>!d*s)&M,m^=1<<[s+~y,y+1,s-y,y][d],v))?v:[])))):n++)([...Array(n)].map(_=>2**n---1))|n
온라인으로 시도하십시오!
어떻게?
크기- \$n\$계단을 배열하여 설명 \$a[\:]\$의 \$n\$ 가장 긴 행에서 가장 짧은 행으로가는 비트 마스크.
대한 \$n=4\$, 이것은 다음을 제공합니다.
# # # # 0b1111 = 15
. # # # 0b0111 = 7
. . # # 0b0011 = 3
. . . # 0b0001 = 1 --> a = [ 15, 7, 3, 1 ]
반복 할 때마다 \의 모든 선행 빈 행을 제거합니다.$a[\:]\$최하위 0이 아닌 비트 \$x\$비어 있지 않은 첫 번째 행. 그 주 \$x\$이 비트의 인덱스로 설정되지 않고 \ 의 해당 거듭 제곱으로 설정됩니다.$2\$.
각 \$s\in[0\:..\:n-1]\$우리는 크기의 또 다른 계단 주요 계단을 커버하려고 \$s+1\$0이 아닌 비트에 고정되고 행이 비트 마스크 \ 로 설명됩니다.$m\$. 만약 \$s=0\$, 우리는 오리엔테이션 \$d=0\$. 그렇지 않으면 \$d=0\$에 \$d=3\$.
아래 표는 \의 각 값에 대해 설명합니다.$d\$:
- 초기 값 \$m\$
- \ 에서 반전되어야하는 비트의 인덱스$m\$ 다음 행을 생성하려면
- \에 적용된 시프트$m\$
계단이 고정되는 0이 아닌 비트는 A. 모든 경우에 \$m\$먼저 \를 곱합니다.$x\$이동하기 전에. 모든 예는 \ 와 함께 제공됩니다.$x=16\$및 \$s=2\$.
x d = 0
. . . . . . . .
y = 0 A init. : 2 ** s
y = 1 # # bit : s + ~y (i.e. s - y - 1)
y = 2 # # # shift : >> s
x d = 1
. . . . . . . .
y = 0 A init. : 1
y = 1 # # bit : y + 1
y = 2 # # # shift : none
x d = 2
. . . . . . . .
y = 0 # # A init. : 2 * (2 ** s) - 1
y = 1 # # bit : s - y
y = 2 # shift : none
x d = 3
. . . . . . . .
y = 0 # # A init. : 2 * (2 ** s) - 1
y = 1 # # bit : y
y = 2 # shift : none
참고 : 0이 아닌 비트의 오른쪽에있는 비트가 정의에 따라 모두 지워지고 위에서 아래로 이동한다는 점을 감안할 때 덮는 계단의 앵커 포인트는 각 방향에 대해 명확하게 정의됩니다.
차콜 , 91 88 87 83 81 78 바이트
≔⊕Ｎθ⊞υＥθ⁻Ｘ²θＸ²ιＦ⊖θＦθＦＥ²Ｅθ×÷⊖Ｘ²θＸ²⁺ινＸ²⁺κ∧λνＦ⟦λ⮌λ⟧ＦθＦυＦ¬⊙ξ＆π§μ⁻ρν⊞υＥξ｜ρ§μ⁻ςνＩＬυ
온라인으로 시도하십시오! 링크는 자세한 코드 버전입니다. 여기에는 루프가 너무 많아서 v처음으로 변수에 도달했습니다 . 설명:
≔⊕Ｎθ
계단의 크기를 입력하고 증가시킵니다.
⊞υＥθ⁻Ｘ²θＸ²ι
구멍이 원점에있는 방식으로 해당 크기의 계단을 만듭니다. 구멍은 우리가 원했던 원래 크기 인 한 크기 더 낮습니다. 이것은 초기 타일링 (크기 1 계단으로 원래 계단의 타일링을 나타냄)이됩니다. 계단은 비트 마스크의 배열로 표시됩니다.
Ｆ⊖θ
1보다 큰 모든 계단 크기를 고려하십시오 (크기 1 계단은 각 잠재적 타일링에 대해 남아있는 구멍을 채우는 데 사용된다고 가정하여 고려됩니다.)
Ｆθ
모든 수평 번역을 고려하십시오.
ＦＥ²Ｅθ×÷⊖Ｘ²θＸ²⁺ινＸ²⁺κ∧λν
수평으로 변환 된 계단과 수평 반사 (실제로 전단에 의해 얻어 짐)를 고려하십시오.
Ｆ⟦λ⮌λ⟧
또한 그 계단의 수직 반사를 고려하십시오. (수직 변환이 주기적이므로 작동합니다.)
Ｆθ
또한 그 계단의 모든 순환 수직 변환을 고려하십시오. 수직 평행 이동은 주기적이므로 조각을 너무 수평으로 이동하는 평행 이동은 항상 계단과 겹칩니다.
Ｆυ
지금까지 수집 된 모든 타일링을 반복합니다.
Ｆ¬⊙ξ＆π§μ⁻ρν
계단이이 위치의 구멍에 맞으면 ...
⊞υＥξ｜ρ§μ⁻ςν
... 구멍에 배치 한 결과를 타일링 목록에 추가합니다. (Charcoal은이 결과를 목록에서 다시 찾을 수 있지만 물론 두 번 배치 할 수는 없습니다.)
ＩＬυ
발견 된 타일링 수를 출력합니다.
불가능한 위치에 계단을 놓지 않는 예 :
\
\\
\\\
\\\\/
//
예를 들어, 크기 2 계단의 이중 반사는 수평 및 수직으로 3만큼 움직일 수 있으며, 이는 일반적으로 원래 계단 밖으로 떨어지고 구멍을 완전히 놓치게합니다. 그러나 수직 변환은 주기적이므로 실제 결과는 다음과 같습니다.
X/
\\
\\\
\\\\/
따라서 이것은 잘못된 타일링으로 감지됩니다.