Ich habe beim Stöbern in Stackoverflow diese Frage zum Kacheln eines MxN-Rechtecks ​​gesehen und dachte, es wäre großartig zum Golfen. Hier ist die Aufgabe.

In Anbetracht der Dimensionen M und N schreiben Sie ein Programm, das ausgibt, wie viele eindeutige Arten ein MxN-Rechteck (N ist die Anzahl der Zeilen, nicht die Anzahl der Spalten. Nicht, dass es wirklich wichtig ist) unter Berücksichtigung dieser Einschränkungen nebeneinander angeordnet werden kann.

1. Alle Kacheln sind 2x1 oder 3x1
2. Alle Kacheln bleiben in ihrer Reihe (dh sie sind alle horizontal)
3. Zwischen jeweils zwei benachbarten Reihen sollten außer an den beiden Enden keine Kacheln ausgerichtet werden
4. M und N sind garantiert mindestens 1

Zum Beispiel wäre eine gültige Kachelung einer 8x3-Matrix

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

Das Folgende wäre jedoch ungültig, da die Zeilen ausgerichtet sind

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

Testfälle:

8x3: 4

3x1: 1

1x1: 0

9 x 4: 10

Code Golf, so dass die kürzeste Antwort gewinnt.

Gelee , 20 Bytes

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

Probieren Sie es online!

JavaScript (ES6),  119 110 106 96  91 Byte

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

Probieren Sie es online!

Kommentiert

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

Probieren Sie es online!

Version mit Zeilenumbrüchen:

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

Man beachte keine Rekursion und handhabt ziemlich große Werte von m und n (zB 24x20 -> 3.3e19)

Hier ist eine kommentierte Antwort, die mehr oder weniger wie oben funktioniert, aber ich habe alle Funktionen nicht verschachtelt, damit sie tatsächlich lesbar sind:

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)

Die Methode zum Aufnehmen und wiederholten Multiplizieren einer Matrix ergibt sich aus einer Frage zum Stapelüberlauf . Dieser Ansatz funktioniert hier, weil er effektiv die kumulative Anzahl von Zweigen durch die verschiedenen möglichen Reihen von Steinen berechnet.

Wenn externe Pakete erlaubt sind, kann ich es auf 192 bringen:

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

Gelee , 26 Bytes

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

Probieren Sie es online!

Heruntergebrochen:

Generieren Sie eine Liste möglicher Wände als kumulative Summe, wobei das Ende entfernt wird:

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

Finden Sie die äußere Tabelle aller möglichen Wände gegeneinander, die keine Schnittpunkte haben:

œ&L¬ɗþ`

Nimm diese Matrix hoch (N-1) und fasse alles zusammen:

æ*⁴’¤SS

Verwendet das erste Bit aus @ EriktheOutgolfers Antwort, um die Liste der möglichen Wände zu generieren, und verwendet dann den Matrixschnittpunkt- und Matrixexponentierungsansatz aus meiner R-Antwort. Als solches funktioniert es auch mit großem N. Dies ist meine erste Gelee-Antwort, und ich vermute, es kann mehr Golf gespielt werden. Idealerweise möchte ich auch den ersten Abschnitt so ändern, dass der Zeit- und Speicherbedarf nicht exponentiell mit M skaliert.

05AB1E , 42 Bytes

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

Ich schäme mich fast, dies zu posten, und es kann definitiv von VIELEN mit einer anderen Herangehensweise golfen werden, aber da es eine Weile gedauert hat, habe ich beschlossen, es trotzdem zu posten und von hier aus zu golfen. Die Herausforderung sieht einfacher aus als es imo ist, aber ich gehe hier definitiv falsch vor und habe das Gefühl, dass 05AB1E ungefähr 25 Bytes schaffen könnte.

Probieren Sie es online aus. HINWEIS: Es ist nicht nur lang, sondern auch ineffizient, da der 9x4Testfall unter TIO in etwa 40 Sekunden ausgeführt wird.

Erläuterung:

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

Kohle , 89 Bytes

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

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Funktioniert mit TIO für Rechtecke mit einer Größe von bis zu etwa 12, kann jedoch mit einem Aufwand von 2 Bytes etwa dreimal schneller ausgeführt werden, indem Bit-Twiddling anstelle von Listenschnitt verwendet wird. Erläuterung:

Ｎθ

Geben Sie die Breite ein.

⊞υ⟦⟧

Beginnen Sie mit einer Reihe ohne Steine.

≔⟦⟧η

Beginnen Sie ohne abgeschlossene Zeilen.

Ｆυ

Schleife über die Reihen.

Ｆ⟦²¦³⟧«

Schlinge dich über die Ziegel.

≧⁺∧Ｌι§ι⁰κ

Fügen Sie die Ziegelbreite zur aktuellen Zeilenbreite hinzu.

¿⁼κθ⊞ηι

Wenn dies zu einer Eingabebreite führt, fügen Sie diese Zeile der Liste der abgeschlossenen Zeilen hinzu.

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

Andernfalls, wenn dies immer noch weniger als die Eingabebreite ist, fügen Sie die neue Zeile zur Liste der Zeilen hinzu, sodass sie bei einer späteren Iteration erfasst wird.

≔Ｅη⟦ι⟧ζ

Machen Sie eine Liste von Wänden einer Reihe.

Ｆ⊖Ｎ«

Schleife über eine weniger als die Höhe.

≔ζι

Speichern Sie die Liste der Wände.

≔⟦⟧ζ

Löschen Sie die Liste der Wände.

Ｆι

Durchlaufen Sie die gespeicherte Liste der Wände.

Ｆη

Schleife über die fertigen Zeilen.

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

Wenn die Zeile zu dieser Wand hinzugefügt werden kann, fügen Sie sie der Liste der Wände hinzu.

ＩＬζ

Geben Sie die Länge der endgültigen Liste der Wände aus.