Tiling a staircase with staircases

Question

Background

A staircase polyomino is a polyomino made of unit squares whose shape resembles a staircase. More formally, a staircase polyomino of size \$n\$ is defined as follows:

• A staircase polyomino of size 1 is a single unit square.
• A staircase polyomino of size \$n\$ is the same as that of size \$n-1\$ with a horizontal bar of length \$n\$ attached to the bottom, left-aligned.

Let's call them just staircases for brevity.

For example, here are the staircases of size 1 to 4:

#

#
##

#
##
###

#
##
###
####

Challenge

Given a positive integer \$n\$, calculate the number of ways the staircase of size \$n\$ can be tiled with one or more staircases.

Multiple staircases of same size can be used in a tiling, and the staircases can be rotated. So the following are valid tilings for \$n=4\$:

A
BC
DEF
GHIJ

A
AA
AAA
AAAA

A
AA
BBC
BDCC

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

Generated using this Python 3 reference solution.

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

Answer 1

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

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

Try it online!

How?

The size-\$n\$ staircase is described with an array \$a[\:]\$ of \$n\$ bit masks, going from the longest to the shortest row.

For \$n=4\$, this gives:

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

At each iteration, we remove all the leading empty rows in \$a[\:]\$ and look for the least significant non-zero bit \$x\$ in the first non-empty row. Note that \$x\$ is not set to the index of this bit, but to the corresponding power of \$2\$.

For each \$s\in[0\:..\:n-1]\$ we try to cover the main staircase with another staircase of size \$s+1\$ anchored to the non-zero bit, and whose rows are described with the bit mask \$m\$. If \$s=0\$, we only try the orientation \$d=0\$. Otherwise, we try \$d=0\$ to \$d=3\$.

The table below describes for each value of \$d\$:

• the initial value of \$m\$
• the index of the bit that must be inverted in \$m\$ to generate the next row
• the shift applied to \$m\$

The non-zero bit to which the staircase is anchored is marked with an A. In all cases, \$m\$ is first multiplied by \$x\$ before being shifted. All examples are given with \$x=16\$ and \$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

Note: Given that the bits to the right of the non-zero bit are all cleared by definition and given that we go from top to bottom, the anchor point of the covering staircase is unambiguously defined for each orientation.

Answer 2

Charcoal, 91 88 87 83 81 78 bytes

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

Try it online! Link is to verbose version of code. This has so many loops that I reached the v variable for the first time ever. Explanation:

≔⊕Ｎθ

Input the size of the staircase and increment it.

⊞υＥθ⁻Ｘ²θＸ²ι

Create a staircase of that size in such a way that the hole is at the origin. The hole is one size lower, which is the original size we wanted. This becomes our initial tiling (which represents tiling the original staircase with size 1 staircases). The staircase is represented as an array of bit masks.

Ｆ⊖θ

Consider all staircase sizes greater than 1. (Size 1 staircases are considered by simply assuming that they will be used to fill any hole remaining for each potential tiling.)

Ｆθ

Consider all horizontal translations.

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

Consider the horizontally translated staircase and its horizontal reflection (actually obtained by shearing).

Ｆ⟦λ⮌λ⟧

Also consider the vertical reflections of those staircases. (This works because the vertical translations are cyclic.)

Ｆθ

Also consider all cyclic vertical translations of those staircases. The vertical translation is cyclic so that translations that move the piece too far horizontally will still always overlap the staircase.

Ｆυ

Loop through all of the tilings collected so far.

Ｆ¬⊙ξ＆π§μ⁻ρν

If the staircase fits in the hole in this position, then...

⊞υＥξ｜ρ§μ⁻ςν

... append the result of placing it in the hole to the list of tilings. (Note that Charcoal will find this result in the list again, but of course won't be able to place it twice.)

ＩＬυ

Output the number of tilings discovered.

Example of avoiding placing a staircase in an impossible position:

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

As an example, the double reflection of the size 2 staircase could be moved by 3 horizontally and vertically which would normally cause it to fall outside the original staircase, missing the hole completely. However, the vertical translation is cyclic, so the actual result is as follows:

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

This is therefore detected as an illegal tiling.