Unikalne płytki ceglane w prostokącie


13

Przeglądałem Stackoverflow i zobaczyłem to pytanie o kafelkowanie prostokąta MxN i pomyślałem, że będzie to świetne miejsce do gry w golfa. Oto zadanie.

Biorąc pod uwagę wymiary M i N, napisz program, który wyświetli, ile unikalnych sposobów można prostokątować prostokątem MxN (N to liczba wierszy, a nie kolumn. To nie ma znaczenia), biorąc pod uwagę te ograniczenia.

  1. Wszystkie płytki to 2x1 lub 3x1
  2. Wszystkie płytki pozostają w swoim rzędzie (tzn. Wszystkie są poziome)
  3. Pomiędzy każdym dwoma sąsiadującymi rzędami płytki nie powinny być wyrównane, z wyjątkiem dwóch końców
  4. Gwarantowane jest, że M i N wynoszą co najmniej 1

Na przykład poprawne kafelkowanie macierzy 8x3 to

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

Ale następujące elementy byłyby nieprawidłowe, ponieważ wiersze są wyrównane

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

Przypadki testowe:

8x3: 4

3x1: 1

1x1: 0

9x4: 10

Code golf, więc najkrótsza odpowiedź wygrywa.


2
Twój opis wielkości płytek wydaje się używać innej konwencji niż rozmiar prostokąta. Czy płytki są rzeczywiście 2x1czy 3x1? Czy jest również wyjście dla 4x1zera?
FryAmTheEggman

1
Witamy. Fajna koncepcja wyzwania, jednak zwykle najlepiej jest użyć piaskownicy, aby opracować pomysły na wyzwania, zanim opublikujesz je na main.
Beefster

@FryAmTheEggman Wygląda OP próbowali |a nie przyczyniają się do długości rzędu stosując reprezentację jak to (w których, o ile nie jest to rura ( |), to jest przestrzeń).
Erik the Outgolfer


1
Odpowiedzi na pytanie dotyczące SO już nie ma.
Arnauld

Odpowiedzi:


5

Galaretka , 20 bajtów

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

Wypróbuj online!


Wiem, że prędkość nie była częścią specyfikacji, ale upłynęło to nawet 11x10, gdy uruchomiono na tio. Byłbym zainteresowany wyjaśnieniem, aby zrozumieć, dlaczego.
Nick Kennedy

@NickKennedy To zbyt duży wkład. Dla szerokości 11 każdy rząd może mieć jeden z 9 różnych nachyleń. Dla szerokości 11 i wysokości 10 istnieje 9¹⁰ = 3486784401 możliwe ściany, w tym nieprawidłowe. Tak działa siła kartezjańska. Oczywiście, TIO nie ma czasu, aby moje rozwiązanie obliczyło całą ścianę (upływa limit czasu po 60 sekundach). Dodam wyjaśnienie, kiedy będę miał czas.
Erik the Outgolfer

dzięki. Patrzyłem trochę na galaretkę, ale w tej chwili polegam na komentowanych wyjaśnieniach, aby zrozumieć, co robi ludzki kod. Założyłem, biorąc pod uwagę problem z czasem, że brutalny kod wymusza rozwiązanie, co jest rozsądnym sposobem na zminimalizowanie wymagań dotyczących kodu.
Nick Kennedy

W interesie odtworzyłem w Galarecie metodę w moim kodzie R, używając pierwszej części twojego kodu. Jest na Wypróbuj online! i chociaż jest znacznie dłuższy niż twój, obsługuje większe liczby. Zauważ, że obecnie nie obsługuje poprawnie 1 rzędu. Podejrzewam, że mogłoby być o wiele bardziej zwięzłe, ale jestem nowy w Jelly.
Nick Kennedy

4

JavaScript (ES6),  119 110 106 96  91 bajtów

(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

Wypróbuj online!

Skomentował

gfhg

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

1

R , 243 231 bajtów

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

Wypróbuj online!

Wersja z podziałami linii:

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

Nie zauważaj rekurencji i obsługuje dość duże wartości min (np. 24x20 -> 3,3e19)

Oto skomentowana odpowiedź, która działa mniej więcej tak samo jak powyżej, ale usunąłem wszystkie funkcje, więc jest w rzeczywistości czytelna:

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)

Metoda pobierania macierzy i jej wielokrotnego mnożenia pochodzi z pytania o przepełnienie stosu . To podejście działa tutaj, ponieważ skutecznie oblicza łączną liczbę gałęzi w różnych możliwych rzędach cegieł.

Jeśli dozwolone są pakiety zewnętrzne, mogę sprowadzić je do 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)))

1

Galaretka , 26 bajtów

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

Wypróbuj online!

Zepsuty:

Wygeneruj listę możliwych ścian jako sumy zbiorcze z usuniętym końcem:

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

Znajdź zewnętrzny stół wszystkich możliwych ścian, które nie mają żadnych skrzyżowań:

œ&L¬ɗþ`

Weź tę macierz do potęgi (N-1), a następnie podsumuj wszystko:

æ*⁴’¤SS

Używa pierwszego bitu z odpowiedzi @ EriktheOutgolfer, aby wygenerować listę możliwych ścian, a następnie stosuje podejście przecięcia macierzy i wykładnika macierzy z mojej odpowiedzi R. Jako taki, działa dobrze nawet z dużymi N. To jest moja pierwsza odpowiedź na żelki i podejrzewam, że można więcej grać w golfa. Idealnie chciałbym również zmienić pierwszą sekcję, aby wymagania dotyczące czasu i pamięci nie skalowały się wykładniczo z M.


0

05AB1E , 42 bajty

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

Jestem prawie zbyt zawstydzony, aby to opublikować, i zdecydowanie może grać w golfa przez LOT z innym podejściem, ale ponieważ zajęło to trochę czasu, postanowiłem opublikować to i odtąd grać w golfa. Wyzwanie wygląda na łatwiejsze niż jest na Imo, ale zdecydowanie używam tutaj niewłaściwego podejścia i mam wrażenie, że 05AB1E może zrobić około 25 bajtów ..

Wypróbuj online. UWAGA: Jest nie tylko długi, ale także nieefektywny, ponieważ 9x4przypadek testowy działa na TIO w około 40 sekund.

Wyjaśnienie:

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

0

Węgiel drzewny , 89 bajtów

Nθ⊞υ⟦⟧≔⟦⟧ηFυF⟦²¦³⟧«≧⁺∧Lι§ι⁰κ¿⁼κθ⊞ηι¿‹κθ⊞υ⁺⟦κ⟧ι»≔Eη⟦ι⟧ζF⊖N«≔ζι≔⟦⟧ζFιFη¿¬⊙§κ⁰№λμ⊞ζ⁺⟦λ⟧κ»ILζ

Wypróbuj online! Link jest do pełnej wersji kodu. Działa w przypadku prostokątów o wielkości do około 12 w TIO, ale można je wykonać około trzy razy szybciej, kosztem 2 bajtów, stosując kręcenie bitów zamiast przecinania listy. Wyjaśnienie:

Nθ

Wprowadź szerokość.

⊞υ⟦⟧

Zacznij od rzędu bez cegieł.

≔⟦⟧η

Zacznij bez zakończonych wierszy.

Fυ

Pętla nad rzędami.

F⟦²¦³⟧«

Pętla nad cegłami.

≧⁺∧Lι§ι⁰κ

Dodaj szerokość cegły do ​​bieżącej szerokości wiersza.

¿⁼κθ⊞ηι

Jeśli spowoduje to szerokość wejściową, dodaj ten wiersz do listy zakończonych wierszy.

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

W przeciwnym razie, jeśli jest to nadal mniej niż szerokość wejściowa, dodaj nowy wiersz do listy wierszy, powodując, że zostanie on przechwycony przez późniejszą iterację.

≔Eη⟦ι⟧ζ

Zrób listę ścian jednego rzędu.

F⊖N«

Zapętlić o jeden mniej niż wysokość.

≔ζι

Zapisz listę ścian.

≔⟦⟧ζ

Wyczyść listę ścian.

Fι

Pętla nad zapisaną listą ścian.

Fη

Pętlę nad ukończonymi rzędami.

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

Jeśli wiersz można dodać do tej ściany, dodaj go do listy ścian.

ILζ

Podaj długość końcowej listy ścian.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.