Je parcourais Stackoverflow et j'ai vu cette question sur le carrelage d'un rectangle MxN, et j'ai pensé que ce serait parfait pour le golf. Voici la tâche.

Compte tenu de la dimension M et N, écrivez un programme qui affiche le nombre de façons uniques dont un rectangle MxN (N est le nombre de lignes, pas de colonnes. Pas vraiment important) peut être mis en mosaïque compte tenu de ces contraintes.

1. Toutes les tuiles sont 2x1 ou 3x1
2. Toutes les tuiles restent dans leur rangée (c'est-à-dire qu'elles sont toutes horizontales)
3. Entre toutes les deux rangées adjacentes, les tuiles ne doivent pas être alignées, sauf aux deux extrémités
4. M et N sont garantis être au moins 1

Par exemple, un pavage valide d'une matrice 8x3 serait

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

Mais ce qui suit ne serait pas valide, car les lignes s'alignent

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

Cas de test:

8x3: 4

3x1: 1

1x1: 0

9x4: 10

Code golf, donc la réponse la plus courte l'emporte.

Gelée , 20 octets

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

Essayez-le en ligne!

JavaScript (ES6), 119110106  96  91 octets

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

Essayez-le en ligne!

Commenté

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

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

Essayez-le en ligne!

Version avec sauts de ligne:

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

Notez pas de récursivité, et gère des valeurs assez grandes de m et n (par exemple 24x20 -> 3.3e19)

Voici une réponse commentée qui fonctionne plus ou moins de la même manière que ci-dessus, mais j'ai désarchivé toutes les fonctions, donc elle est en fait lisible:

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)

La méthode pour prendre une matrice et la multiplier à plusieurs reprises par elle-même provient d' une question sur stackoverflow . Cette approche fonctionne ici car elle calcule efficacement le nombre cumulé de branches à travers les différentes rangées possibles de briques.

Si les packages externes sont autorisés, je peux le réduire à 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ée , 26 octets

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

Essayez-le en ligne!

En panne:

Générez une liste des murs possibles sous forme de sommes cumulées avec la fin supprimée:

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

Trouvez la table extérieure de tous les murs possibles les uns contre les autres qui n'ont aucune intersection:

œ&L¬ɗþ`

Prenez cette matrice à la puissance de (N-1) et résumez le tout:

æ*⁴’¤SS

Utilise le premier bit de la réponse de @ EriktheOutgolfer pour générer la liste des murs possibles, puis utilise l'approche d'intersection matricielle et d'exponentiation matricielle de ma réponse R. En tant que tel, cela fonctionne bien même avec un grand N. C'est ma première réponse Jelly, et je soupçonne qu'il peut être joué au golf plus. J'aimerais également idéalement modifier la première section afin que les exigences de temps et de mémoire ne soient pas mises à l'échelle de façon exponentielle avec M.

05AB1E , 42 octets

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

J'ai presque trop honte de poster ceci, et il peut certainement être joué par A LOT avec une approche différente, mais comme il a fallu un certain temps pour terminer, j'ai décidé de le publier de toute façon et de le jouer à partir d'ici. Le défi semble plus facile qu'il ne l'est, mais j'utilise certainement une mauvaise approche ici et j'ai le sentiment que 05AB1E pourrait faire environ 25 octets ..

Essayez-le en ligne. REMARQUE: non seulement il est long, mais il est également inefficace, car le 9x4scénario de test s'exécute en environ 40 secondes sur TIO.

Explication:

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

Fusain , 89 octets

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

Essayez-le en ligne! Le lien est vers la version détaillée du code. Fonctionne pour les rectangles de taille jusqu'à environ 12 sur TIO, mais pourrait être rendu environ trois fois plus rapide à un coût de 2 octets en utilisant le twiddling de bits au lieu de l'intersection de liste. Explication:

Ｎθ

Saisissez la largeur.

⊞υ⟦⟧

Commencez avec une rangée sans briques.

≔⟦⟧η

Commencez sans lignes terminées.

Ｆυ

Faites une boucle sur les rangées.

Ｆ⟦²¦³⟧«

Faites une boucle sur les briques.

≧⁺∧Ｌι§ι⁰κ

Ajoutez la largeur de brique à la largeur de ligne actuelle.

¿⁼κθ⊞ηι

Si cela se traduit par la largeur d'entrée, ajoutez cette ligne à la liste des lignes terminées.

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

Sinon, si elle est toujours inférieure à la largeur d'entrée, ajoutez la nouvelle ligne à la liste des lignes, ce qui entraînera sa récupération par une itération ultérieure.

≔Ｅη⟦ι⟧ζ

Faites une liste des murs d'une rangée.

Ｆ⊖Ｎ«

Boucle sur un de moins que la hauteur.

≔ζι

Enregistrez la liste des murs.

≔⟦⟧ζ

Effacez la liste des murs.

Ｆι

Parcourez la liste des murs enregistrée.

Ｆη

Faites une boucle sur les lignes terminées.

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

Si la ligne peut être ajoutée à ce mur, ajoutez-la à la liste des murs.

ＩＬζ

Affiche la longueur de la liste finale des murs.