Unique Brick Tilings Within A Rectangle

Question

I was browsing Stackoverflow and saw this question about tiling an MxN rectangle, and I thought it would be great for golfing. Here is the task.

Given the dimension M and N, write a program that outputs how many unique ways a MxN rectangle (N is the number of rows, not columns. Not that it really matters) can be tiled given these constraints.

1. All tiles are 2x1 or 3x1
2. All tiles stay within their row (ie they are all horizontal)
3. Between every two adjacent rows tiles should not be aligned, except on the two ends
4. M and N are guaranteed to be at least 1

For example, a valid tiling of a 8x3 matrix would be

  2    3     3
  |    |     |
  v    v     v
 _______________
|___|_____|_____| 
|_____|_____|___|
|___|_____|_____|

But the following would be invalid, because the rows align

  2    3     3
  |    |     |
  v    v     v
 _______________
|___|_____|_____| 
|_____|___|_____|
|_____|_____|___|

Test cases:

8x3: 4

3x1: 1

1x1: 0

9x4: 10

Code golf, so shortest answer wins.

Answer 1

Jelly, 20 bytes

2*ḃ€2‘ÄṪ⁼¥Ƈ⁸ṗfƝẸ$€ċ0

Try it online!

Answer 2

JavaScript (ES6),  119 110 106 96  91 bytes

Takes input as \$(N,M)\$.

f=(n,m,p=0,g=(w,h=x=>g(p[g[w-=x]=1,w]||w)*g[w]--)=>w>3?h(2)+h(1):w>1&&f(n,m-1,g))=>m?g(n):1

Try it online!

Commented

NB: This code uses 3 different functions that call each other. This makes it a bit difficult to keep track of the scope of the variables. Keep in mind that \$g\$ is defined within the scope of \$f\$ and \$h\$ is defined within the scope of \$g\$.

f = (                    // f is a recursive function taking:
  n,                     //   n = number of columns
  m,                     //   m = number of rows
  p = 0,                 //   p = object holding the previous row
  g = (                  //   g = recursive function taking:
    w,                   //     w = remaining width that needs to be filled in the
                         //         current row
    h = x =>             //     h = helper function taking x
                         // h body:
      g(                 //   recursive call to g:
        p[g[w -= x] = 1, //     subtract either 2 or 1 from w and mark this width as used
          w              //     test p[w]
        ]                //     pass p[w] if p[w] = 1 (which will force the next iteration
                         //     to fail immediately)
        || w             //     otherwise, pass w
      )                  //   end of recursive call
      * g[w]--           //   then restore g[w] to 0
  ) =>                   // g body:
    w > 3 ?              //   if w > 3, we need to insert at least 2 more bricks:
      h(2) + h(1)        //     invoke h with x = 2 and x = 1
    :                    //   else:
      w > 1              //     this is the last brick; we just check if it can be inserted
      &&                 //     abort if w is equal to 1 (a brick does not fit in there)
      f(                 //     otherwise, do a recursive call to f:
        n,               //       n is unchanged
        m - 1,           //       decrement m
        g                //       pass g as the new reference row
      )                  //     end of recursive call
) =>                     // f body:
  m ? g(n) : 1           //   yield 1 if we made it to the last row or call g otherwise

Answer 3

R, 243 231 bytes

function(m,n,i=2*0:(m%/%6)+m%%2,j=i+(m-3*i)/2,M=Map)`if`(m<2,0,sum((e=eigen(lengths(outer(p<-unlist(M(M,list(function(x,y)cumsum(2+1:y%in%x)),M(combn,j,i,s=F),j),F),p,Vectorize(intersect)))<2))$ve%*%diag(e$va^(n-1))%*%solve(e$ve)))

Try it online!

Version with line breaks:

function(m,n,i=2*0:(m%/%6)+m%%2,j=i+(m-3*i)/2,M=Map)`if`(m<2,0,
sum((e=eigen(lengths(outer(p<-unlist(M(M,list(function(x,y)cumsum(2+1:y%in%x)),
M(combn,j,i,s=F),j),F),p,Vectorize(intersect)))<2))$ve%*%diag(e$va^(n-1))%*%solve(e$ve)))

Note no recursion, and handles fairly large values of m and n (e.g. 24x20 -> 3.3e19)

Here's a commented answer that works more or less the same as the above, but I've unnested all of the functions so it's actually readable:

f <- function(m,n) {
  # First work out what potential combinations of 2s and 3s add up to m
  i <- 2*0:(m %/% 6) + m %% 2 # Vector with numbers of possible 3s
  j <- i + (m - 3 * i) / 2 # Vector with total number of 2s and 3s
  if (m < 2) {
    0 # If wall less than 2 wide, no point in continuing because answer is 0
  } else {
    # Work out all possible positions of threes for each set
    positions_of_threes <- Map(combn, j, i, simplify = FALSE)
    # Function to work out the cumulative distance along the wall for a given
    # Set of three positions and number of bricks
    make_cumulative_bricks <- function(pos_threes, n_bricks) {
      bricks <- 1:n_bricks %in% pos_threes
      cumsum(2 + bricks)
    }
    # Find all possible rows with cumulative width of wall
    # Note because this is a `Map` with depth two that needs to be vectorised
    # for both `positions_of_threes` and `j`, and we're using base R, the
    # function `make_cumulative_bricks` needs to be placed in a list
    cum_bricks <- Map(Map, list(make_cumulative_bricks), positions_of_threes, j)
    # Finally we have the list of possible rows of bricks as a flat list
    cum_bricks_unlisted <- unlist(cum_bricks, recursive = FALSE)
    # Vectorise the intersect function
    intersect_v <- Vectorize(intersect, SIMPLIFY = FALSE)
    # Find the length of all possible intersects between rows
    intersections <- outer(cum_bricks_unlisted, cum_bricks_unlisted, intersect_v)
    n_intersections <- lengths(intersections)
    # The ones not lined up will only have a single intersect at `m`
    not_lined_up <- n_intersections == 1
    # Now use method described at https://stackoverflow.com/a/9459540/4998761
    # to calculate the (matrix of TRUE/FALSE for lined-up) to the power of `n`
    eigen_nlu <- eigen(not_lined_up)
    final_mat <- eigen_nlu$vectors %*%
      diag(eigen_nlu$values ^ (n - 1)) %*%
      solve(eigen_nlu$vectors)
    # The sum of this matrix is what we're looking for
    sum(final_mat)
  }
}
f(20,20)

The method for taking a matrix and repeatedly multiplying it by itself is from a question on stackoverflow. This approach works here because it effectively calculates the cumulative number of branches through the different possible rows of bricks.

If external packages are allowed, I can get it down to 192:

function(m,n,i=2*0:(m%/%6)+m%%2,j=i+(m-3*i)/2,M=purrr::map2)`if`(m<2,0,sum(expm::`%^%`(lengths(outer(p<-unlist(M(M(j,i,combn,s=F),j,M,~cumsum(2+1:.y%in%.)),F),p,Vectorize(intersect)))<2,n-1)))

Answer 4

Jelly, 26 bytes

2*ḃ€2‘ÄṪ⁼¥Ƈ⁸œ&L¬ɗþ`æ*⁴’¤SS

Try it online!

Broken down:

Generate a list of possible walls as cumulative sums with the end removed:

2*ḃ€2‘ÄṪ⁼¥Ƈ⁸

Find the outer table of all possible walls against each other that don’t have any intersections:

œ&L¬ɗþ`

Take this matrix to the power of (N-1) and then sum it all up:

æ*⁴’¤SS

Uses the first bit from @EriktheOutgolfer’s answer to generate the list of possible walls, and then uses the matrix intersection and matrix exponentiation approach from my R answer. As such, it works well even with large N. This is my first Jelly answer, and I suspect it can be golfed more. I’d also ideally like to change the first section so that the time and memory requirements don’t scale exponentially with M.

Answer 5

05AB1E, 42 bytes

Åœʒ23yåP}€œ€`Ùε.¥¦¨}IиI.ÆÙεøyíø‚€€üQOO_P}O

I'm almost too ashamed to post this, and it can definitely be golfed by A LOT with a different approach, but since it took a while to complete I decided to post it anyway and golf it down from here. The challenge looks easier than it is imo, but I'm definitely using a wrong approach here and I have the feeling 05AB1E could do around 25 bytes..

Try it online. NOTE: Not only is it long, it's also inefficient, since the 9x4 test case runs in about 40 seconds on TIO..

Explanation:

Ŝ             # Get all possible ways to sum to the (first) implicit input
               #  i.e. 8 → [[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,2],[1,1,1,1,1,3],[1,1,1,1,2,2],[1,1,1,1,4],[1,1,1,2,3],[1,1,1,5],[1,1,2,2,2],[1,1,2,4],[1,1,3,3],[1,1,6],[1,2,2,3],[1,2,5],[1,3,4],[1,7],[2,2,2,2],[2,2,4],[2,3,3],[2,6],[3,5],[4,4],[8]]
  ʒ23yåP}      # Only leave those consisting of 2s and/or 3s
               #  → [[2,2,2,2],[2,3,3]]
         €œ    # For each: get all permutations
           €`  # Flatten this list of lists once
             Ù # And uniquify it (leaving all possible distinct rows of bricks)
               #  → [[2,2,2,2],[3,3,2],[3,2,3],[2,3,3]]
ε    }         # For each:
 .¥            #  Get the cumulative sum
   ¦¨          #  With the leading 0 and trailing first input removed
               #   → [[2,4,6],[3,6],[3,5],[2,5]]
      Iи       # Repeat this list the second input amount of times
               #  i.e. 3 → [[2,4,6],[3,6],[3,5],[2,5],[2,4,6],[3,6],[3,5],[2,5],[2,4,6],[3,6],[3,5],[2,5]]
        I.Æ    # Get all combinations of lists the size of the second input
           Ù   # And uniquify the result (leaving all possible distinct walls)
               #  → [[[2,4,6],[3,6],[3,5]],[[2,4,6],[3,6],[2,5]],[[2,4,6],[3,6],[2,4,6]],[[2,4,6],[3,6],[3,6]],[[2,4,6],[3,5],[2,5]],[[2,4,6],[3,5],[2,4,6]],[[2,4,6],[3,5],[3,6]],[[2,4,6],[3,5],[3,5]],[[2,4,6],[2,5],[2,4,6]],[[2,4,6],[2,5],[3,6]],[[2,4,6],[2,5],[3,5]],[[2,4,6],[2,5],[2,5]],[[2,4,6],[2,4,6],[3,6]],[[2,4,6],[2,4,6],[3,5]],[[2,4,6],[2,4,6],[2,5]],[[2,4,6],[2,4,6],[2,4,6]],[[3,6],[3,5],[2,5]],[[3,6],[3,5],[2,4,6]],[[3,6],[3,5],[3,6]],[[3,6],[3,5],[3,5]],[[3,6],[2,5],[2,4,6]],[[3,6],[2,5],[3,6]],[[3,6],[2,5],[3,5]],[[3,6],[2,5],[2,5]],[[3,6],[2,4,6],[3,6]],[[3,6],[2,4,6],[3,5]],[[3,6],[2,4,6],[2,5]],[[3,6],[2,4,6],[2,4,6]],[[3,6],[3,6],[3,5]],[[3,6],[3,6],[2,5]],[[3,6],[3,6],[2,4,6]],[[3,6],[3,6],[3,6]],[[3,5],[2,5],[2,4,6]],[[3,5],[2,5],[3,6]],[[3,5],[2,5],[3,5]],[[3,5],[2,5],[2,5]],[[3,5],[2,4,6],[3,6]],[[3,5],[2,4,6],[3,5]],[[3,5],[2,4,6],[2,5]],[[3,5],[2,4,6],[2,4,6]],[[3,5],[3,6],[3,5]],[[3,5],[3,6],[2,5]],[[3,5],[3,6],[2,4,6]],[[3,5],[3,6],[3,6]],[[3,5],[3,5],[2,5]],[[3,5],[3,5],[2,4,6]],[[3,5],[3,5],[3,6]],[[3,5],[3,5],[3,5]],[[2,5],[2,4,6],[3,6]],[[2,5],[2,4,6],[3,5]],[[2,5],[2,4,6],[2,5]],[[2,5],[2,4,6],[2,4,6]],[[2,5],[3,6],[3,5]],[[2,5],[3,6],[2,5]],[[2,5],[3,6],[2,4,6]],[[2,5],[3,6],[3,6]],[[2,5],[3,5],[2,5]],[[2,5],[3,5],[2,4,6]],[[2,5],[3,5],[3,6]],[[2,5],[3,5],[3,5]],[[2,5],[2,5],[2,4,6]],[[2,5],[2,5],[3,6]],[[2,5],[2,5],[3,5]],[[2,5],[2,5],[2,5]]]
ε              # Map all walls `y` to:
 ø             #  Zip/transpose; swapping rows and columns
 yí            #  Reverse each row in a wall `y`
   ø           #  Also zip/transpose those; swapping rows and columns
 ‚             #  Pair both
  €            #  For both:
   €           #   For each column:
    ü          #    For each pair of bricks in a column:
     Q         #     Check if they are equal to each other (1 if truthy; 0 if falsey)
    O          #    Then take the sum of these checked pairs for each column
   O           #   Take the sum of that entire column
   _           #   Then check which sums are exactly 0 (1 if 0; 0 if anything else)
   P           #   And check for which walls this is only truthy by taking the product
}O             # After the map: sum the resulting list
               # (and output it implicitly as result)

Answer 6

Charcoal, 89 bytes

Ｎθ⊞υ⟦⟧≔⟦⟧ηＦυＦ⟦²¦³⟧«≧⁺∧Ｌι§ι⁰κ¿⁼κθ⊞ηι¿‹κθ⊞υ⁺⟦κ⟧ι»≔Ｅη⟦ι⟧ζＦ⊖Ｎ«≔ζι≔⟦⟧ζＦιＦη¿¬⊙§κ⁰№λμ⊞ζ⁺⟦λ⟧κ»ＩＬζ

Try it online! Link is to verbose version of code. Works for rectangles of size up to about 12 on TIO, but could be made about three times faster at a cost of 2 bytes by using bit twiddling instead of list intersection. Explanation:

Ｎθ

Input the width.

⊞υ⟦⟧

Start with a row with no bricks.

≔⟦⟧η

Start with no completed rows.

Ｆυ

Loop over the rows.

Ｆ⟦²¦³⟧«

Loop over the bricks.

≧⁺∧Ｌι§ι⁰κ

Add the brick width to the current row width.

¿⁼κθ⊞ηι

If this results in the input width then add this row to the list of completed rows.

¿‹κθ⊞υ⁺⟦κ⟧ι»

Otherwise if this is still less than the input width then add the new row to the list of rows, thus causing it to be picked up by a later iteration.

≔Ｅη⟦ι⟧ζ

Make a list of walls of one row.

Ｆ⊖Ｎ«

Loop over one less than the height.

≔ζι

Save the list of walls.

≔⟦⟧ζ

Clear the list of walls.

Ｆι

Loop over the saved list of walls.

Ｆη

Loop over the completed rows.

¿¬⊙§κ⁰№λμ⊞ζ⁺⟦λ⟧κ»

If the row can be added to this wall then add that to the list of walls.

ＩＬζ

Output the length of the final list of walls.