Lát gạch cầu thang

Question

Lý lịch

Một polyomino cầu thang là một polyomino làm bằng ô vuông đơn vị có hình dạng giống như một cầu thang. Chính thức hơn, một polyomino cầu thang có kích thước \$n\$ được định nghĩa như sau:

• Polyomino cầu thang có kích thước 1 là một hình vuông đơn vị.
• Polyomino cầu thang có kích thước \$n\$giống với kích thước \$n-1\$với một thanh ngang có chiều dài \$n\$ gắn vào dưới cùng, căn trái.

Hãy gọi chúng chỉ là cầu thang cho ngắn gọn.

Ví dụ, đây là các cầu thang có kích thước từ 1 đến 4:

#

#
##

#
##
###

#
##
###
####

Thử thách

Cho một số nguyên dương \$n\$, tính số cách cầu thang có kích thước \$n\$ có thể lát gạch một hoặc nhiều bậc cầu thang.

Có thể ốp lát nhiều cầu thang cùng kích thước và các cầu thang có thể xoay được. Vì vậy, sau đây là các thông tin hợp lệ cho \$n=4\$:

A
BC
DEF
GHIJ

A
AA
AAA
AAAA

A
AA
BBC
BDCC

Luật chơi gôn tiêu chuẩn được áp dụng. Mã ngắn nhất tính bằng byte sẽ thắng.

Các trường hợp thử nghiệm

Được tạo bằng giải pháp tham chiếu Python 3 này .

1 -> 1
2 -> 2
3 -> 8
4 -> 57
5 -> 806
6 -> 20840
7 -> 1038266

Answer 1

JavaScript (ES10),  250 ... 228  227 byte

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

Hãy thử nó trực tuyến!

Làm sao?

Kích thước- \$n\$cầu thang được mô tả bằng một mảng \$a[\:]\$trong số \$n\$ mặt nạ bit, đi từ hàng dài nhất đến hàng ngắn nhất.

Đối với \$n=4\$, điều này mang lại:

# # # #  0b1111 = 15
. # # #  0b0111 = 7
. . # #  0b0011 = 3
. . . #  0b0001 = 1  --> a = [ 15, 7, 3, 1 ]

Ở mỗi lần lặp, chúng tôi xóa tất cả các hàng trống hàng đầu trong \$a[\:]\$và tìm kiếm các ý nghĩa khác không chút ít nhất \$x\$trong hàng không trống đầu tiên. Lưu ý rằng \$x\$không được đặt thành chỉ mục của bit này, mà là sức mạnh tương ứng của \$2\$.

Đối với mỗi \$s\in[0\:..\:n-1]\$chúng tôi cố gắng che cầu thang chính bằng một cầu thang khác có kích thước \$s+1\$được neo vào bit khác 0 và các hàng của nó được mô tả bằng bit mask \$m\$. Nếu \$s=0\$, chúng tôi chỉ thử định hướng \$d=0\$. Nếu không, chúng tôi thử \$d=0\$đến \$d=3\$.

Bảng dưới đây mô tả cho từng giá trị của \$d\$:

• giá trị ban đầu của \$m\$
• chỉ số của bit phải được đảo ngược trong \$m\$ để tạo hàng tiếp theo
• sự thay đổi được áp dụng cho \$m\$

Bit khác 0 mà cầu thang được neo vào được đánh dấu bằng một A. Trong mọi trường hợp, \$m\$được nhân đầu tiên với \$x\$trước khi được chuyển dịch. Tất cả các ví dụ được đưa ra với \$x=16\$và \$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

Lưu ý: Cho rằng các bit ở bên phải của bit khác 0 đều bị xóa theo định nghĩa và cho rằng chúng ta đi từ trên xuống dưới, điểm neo của cầu thang bao phủ được xác định rõ ràng cho mỗi hướng.

Answer 2

Than củi , 91 88 87 83 81 78 byte

≔⊕Ｎθ⊞υＥθ⁻Ｘ²θＸ²ιＦ⊖θＦθＦＥ²Ｅθ×÷⊖Ｘ²θＸ²⁺ινＸ²⁺κ∧λνＦ⟦λ⮌λ⟧ＦθＦυＦ¬⊙ξ＆π§μ⁻ρν⊞υＥξ｜ρ§μ⁻ςνＩＬυ

Hãy thử nó trực tuyến! Liên kết là phiên bản dài của mã. Điều này có rất nhiều vòng lặp mà tôi đã đạt đến vbiến lần đầu tiên. Giải trình:

≔⊕Ｎθ

Nhập kích thước của cầu thang và tăng dần.

⊞υＥθ⁻Ｘ²θＸ²ι

Tạo một cầu thang với kích thước đó sao cho lỗ ở gốc. Lỗ thấp hơn một kích thước, đó là kích thước ban đầu mà chúng tôi muốn. Điều này trở thành lát gạch ban đầu của chúng tôi (đại diện cho việc lát cầu thang ban đầu với cầu thang kích thước 1). Cầu thang được biểu diễn dưới dạng một mảng mặt nạ bit.

Ｆ⊖θ

Xem xét tất cả các kích thước cầu thang lớn hơn 1. (Cầu thang kích thước 1 được xem xét đơn giản bằng cách giả định rằng chúng sẽ được sử dụng để lấp đầy bất kỳ lỗ nào còn lại cho mỗi lần lát gạch tiềm năng.)

Ｆθ

Xem xét tất cả các bản dịch ngang.

ＦＥ²Ｅθ×÷⊖Ｘ²θＸ²⁺ινＸ²⁺κ∧λν

Hãy xem xét cầu thang dịch theo chiều ngang và phản xạ ngang của nó (thực tế thu được bằng cách cắt).

Ｆ⟦λ⮌λ⟧

Cũng nên xem xét phản xạ dọc của những cầu thang đó. (Điều này hoạt động vì các bản dịch dọc là theo chu kỳ.)

Ｆθ

Cũng xem xét tất cả các phép tịnh tiến theo chiều dọc tuần hoàn của các cầu thang đó. Phép tịnh tiến theo phương thẳng đứng là tuần hoàn nên các phép tịnh tiến di chuyển mảnh đi quá xa theo phương ngang vẫn sẽ luôn trùng với cầu thang.

Ｆυ

Lặp lại tất cả các ô đã thu thập được cho đến nay.

Ｆ¬⊙ξ＆π§μ⁻ρν

Nếu cầu thang vừa với lỗ ở vị trí này, thì ...

⊞υＥξ｜ρ§μ⁻ςν

... thêm kết quả của việc đặt nó trong lỗ vào danh sách các lát gạch. (Lưu ý rằng Charcoal sẽ tìm lại kết quả này trong danh sách, nhưng tất nhiên sẽ không thể đặt nó hai lần.)

ＩＬυ

Đưa ra số thứ tự được phát hiện.

Ví dụ về việc tránh đặt cầu thang ở vị trí bất khả thi:

   \
  \\
 \\\
\\\\/
   //

Ví dụ, phản xạ kép của cầu thang kích thước 2 có thể bị dịch chuyển 3 chiều ngang và dọc, điều này thường khiến nó rơi ra bên ngoài cầu thang ban đầu, mất hoàn toàn lỗ hổng. Tuy nhiên, phép tịnh tiến theo chiều dọc là tuần hoàn, do đó kết quả thực tế như sau:

   X/
  \\
 \\\
\\\\/

Do đó, điều này được phát hiện là một cách lát gạch bất hợp pháp.