Eu estava navegando no Stackoverflow e vi essa pergunta sobre o mosaico de um retângulo MxN, e achei que seria ótimo para jogar golfe. Aqui está a tarefa.

Dada a dimensão M e N, escreva um programa que mostre quantas maneiras exclusivas um retângulo MxN (N é o número de linhas, não colunas. Não que isso realmente importe) pode ser colocado em mosaico, dadas essas restrições.

1. Todas as peças são 2x1 ou 3x1
2. Todos os blocos permanecem dentro de sua linha (ou seja, todos são horizontais)
3. Entre cada duas linhas adjacentes, os ladrilhos não devem estar alinhados, exceto nas duas extremidades
4. M e N têm garantia de pelo menos 1

Por exemplo, um mosaico válido de uma matriz 8x3 seria

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

Mas o seguinte seria inválido, porque as linhas alinham

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

Casos de teste:

8x3: 4

3x1: 1

1x1: 0

9x4: 10

Código de golfe, a resposta mais curta ganha.

Gelatina , 20 bytes

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

Experimente online!

JavaScript (ES6),  119 110 106 96  91 bytes

$(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

Experimente online!

Comentado

$g$$f$$h$$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

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)))

Experimente online!

Versão com quebras de linha:

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)))

Observe sem recursão e lida com valores razoavelmente grandes de m e n (por exemplo, 24x20 -> 3.3e19)

Aqui está uma resposta comentada que funciona mais ou menos da mesma forma que a anterior, mas anulei todas as funções para que fique legível:

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 /programming//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)

O método para pegar uma matriz e multiplicá-la repetidamente por si só é de uma pergunta no stackoverflow . Essa abordagem funciona aqui porque calcula efetivamente o número acumulado de ramificações através das diferentes linhas possíveis de tijolos.

Se pacotes externos forem permitidos, posso baixá-lo para 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)))

Geléia , 26 bytes

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

Experimente online!

Quebrado:

Gere uma lista de paredes possíveis como somas cumulativas com o final removido:

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

Encontre a mesa externa de todas as paredes possíveis uma contra a outra e sem interseções:

œ&L¬ɗþ`

Leve essa matriz à potência de (N-1) e depois resuma tudo:

æ*⁴’¤SS

Usa o primeiro bit da resposta de @ EriktheOutgolfer para gerar a lista de paredes possíveis e, em seguida, usa a abordagem de interseção e exponenciação de matriz da minha resposta R. Como tal, funciona bem mesmo com N. grande. Esta é a minha primeira resposta Jelly, e suspeito que possa jogar mais. Idealmente, também gostaria de alterar a primeira seção para que os requisitos de tempo e memória não sejam escalonados exponencialmente com M.

05AB1E , 42 bytes

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

Estou quase com vergonha de postar isso, e ele definitivamente pode ser muito jogado de golfe com uma abordagem diferente, mas, como demorou um pouco para ser concluído, decidi publicá-lo de qualquer maneira e jogá-lo daqui. O desafio parece mais fácil do que é imo, mas definitivamente estou usando uma abordagem errada aqui e tenho a sensação de que 05AB1E poderia fazer cerca de 25 bytes.

Experimente online. NOTA: Além de longo, também é ineficiente, pois o 9x4caso de teste é executado em cerca de 40 segundos no TIO.

Explicação:

Ŝ             # 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)

Carvão , 89 bytes

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

Experimente online! Link é a versão detalhada do código. Funciona para retângulos de tamanho de até 12 no TIO, mas pode ser feito três vezes mais rápido, com um custo de 2 bytes, usando o giro de bits em vez da interseção de lista. Explicação:

Ｎθ

Insira a largura.

⊞υ⟦⟧

Comece com uma linha sem tijolos.

≔⟦⟧η

Comece com nenhuma linha concluída.

Ｆυ

Faça um loop pelas linhas.

Ｆ⟦²¦³⟧«

Laço sobre os tijolos.

≧⁺∧Ｌι§ι⁰κ

Adicione a largura do tijolo à largura da linha atual.

¿⁼κθ⊞ηι

Se isso resultar na largura da entrada, adicione essa linha à lista de linhas concluídas.

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

Caso contrário, se ainda for menor que a largura de entrada, adicione a nova linha à lista de linhas, fazendo com que ela seja captada por uma iteração posterior.

≔Ｅη⟦ι⟧ζ

Faça uma lista de paredes de uma linha.

Ｆ⊖Ｎ«

Passe um a menos que a altura.

≔ζι

Salve a lista de paredes.

≔⟦⟧ζ

Limpe a lista de paredes.

Ｆι

Passe pela lista salva de paredes.

Ｆη

Passe pelas linhas concluídas.

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

Se a linha puder ser adicionada a essa parede, adicione-a à lista de paredes.

ＩＬζ

Saída o comprimento da lista final de paredes.