Jako następcze w stosunku do tego wyzwania , teraz chcemy policzyć liczbę prostokątów w siatce z r wierszy i c kolumn gdzie jest przejście przez każdy linia przekątna kwadratu siatki. Teraz nadal liczymy te same prostokąty, co wcześniej, ale tym razem musimy również uwzględnić prostokąty, które są przechylone o 45 stopni.

Twoim celem jest stworzenie funkcji lub programu, który na podstawie liczby wierszy ri kolumn c wyprowadza liczbę prostokątów na siatce ukośnej o wymiarach ( r , c ).

Jako demonstracja jest to animacja, która iteruje wszystkie 37 prostokątów utworzonych przez siatkę ukośną (2 x 3).

Przypadki testowe

Each case is [rows, columns] = # of rectangles
[0, 0] = 0
[0, 1] = 0
[1, 0] = 0
[1, 1] = 1
[3, 2] = 37
[2, 3] = 37
[6, 8] = 2183
[7, 11] = 5257
[18, 12] = 40932
[42, 42] = 2889558
[51, 72] = 11708274

Zasady

• To jest golf golfowy, więc wygrywa najkrótszy kod.
• Wbudowane rozwiązania tego problemu są niedozwolone.

Rubinowy, 58 bajtów

Jest to prosta implementacja algorytmu w wyzwalaniu odpowiedzi C Helium Nuclei .

g=->m,n{n>m ?g[n,m]:m*~m*n*~n/4+n*((2*m-n)*(4*n*n-1)-3)/6}

Badałem, dlaczego ta formuła działa, z ograniczonym powodzeniem. Łatwo jest potwierdzić, że liczba prostokątów pionowych jest równa (m+1)*m/2 * (n+1)*n/2, liczba prostokątów diagonalnych jest nieco bardziej nieuchwytna.

Neil został potwierdzony przez m==nże liczba pochylonych prostokątów w n*nkwadracie jest (4*n**4-n*n-3*n)/6i że kiedy m>n trzeba dodać dodatkowy (m-n)(n*(4*n*n-1)/3)(związane OEIS A000447 ), choć nie wyjaśnia, gdzie te dwie formuły pochodzi. Znalazłem część odpowiedzi.

Ponieważ m==nkształt wewnątrz siatki to diament Azteków .

Liczba prostokątów w Azteków diamentu jest sumą liczby dużych prostokątów nałożony aby uczynić go (za czwarty diament, który znajduje się w 5x5sieci, 2x8, 4x6, 6x4, i 8x2) minus liczba prostokątów liczone dwukrotnie (liczba prostokąty w poprzednim diamentie azteckim).

Formuła tutaj jest (TeX do dodania później):

# superimposed rectangles, 2x(2n-2), 4*(2n-4), ...
f = lambda n: sum( (2*k)*(2*k+1)/2 * (2*n-2*k)*(2*n-2*k+1)/2 for k in range(1, n) )
aztec_rect = f(n) - f(n-1)

Zgodnie z Wolfram Alpha, zamkniętej formie za fIs 1/30*(n-1)*n*(4*n**3+14*n**2+19*n+9)a zamkniętym formularz aztec_rectjest, jak Neil odkryto 1/6*n*(n-1)*(4*n**2+4*n+3) == 1/6*(4*n**4-n**2-3*n).

Muszę jeszcze odkryć, dlaczego (m-n)(n*(4*n*n-1)/3)działa, ale podejrzewam, że dzieje się tak, ponieważ jedna definicja A000447 jest binomial(2*n+1, 3). Będę cię informować.

Aktualizacja: Mam powody sądzić, że funkcja liczby prostokątów w rozszerzonym azteckim diamentie m>njest związana z liczbą nałożonych 2k*2(n-k)prostokątów w diamentie minus F(m-1,n-1). Więcej wyników, gdy je mam.

Aktualizacja: Próbowałem innej drogi i skończyłem z inną formułą dla rozszerzonych diamentów azteckich, która jest w większości możliwa do wyjaśnienia, ale ma jeden termin, którego jeszcze nie rozumiem. Huzzah! :RE

def f(m,n):
 if n > m:
     return f(n,m)
 if n == 0:
     return 0
 else:
     return(m-n+1)*(4*n**4-n*n-3*n)/6-f(m-1,n-1)+(m-n)*2+(m-n)*(n-2)-(m-n-1)*f(n-1,n-1)

Szybki podział tej ostatniej formuły:

• (m-n+1)*(4*n**4-n*n-3*n)/6to liczba nałożonych na siebie diamentów azteckich wielkości nw strukturze, jak f(n,n) = (4*n**4-n*n-3*n)/6. f(7,3)ma 5 nałożonych na siebie diamentów Azteków 3, a f(3,3)ma tylko 1 diament.
• -f(m-1,n-1) usuwa niektóre zduplikowane prostokąty ze środka nałożonych diamentów.
• +(m-n)*2Rachunki dla 2 dodatkowych 2-by- (2n-1)prostokątów dla każdego dodatkowego diamentu.
• +(m-n)*(n-2)Rachunki za dodatkową n-by- nkwadratowy dla każdego dodatkowego diamentu.
• -(m-n-1)*f(n-1,n-1)To nowy zagadkowy termin. Najwyraźniej nie uwzględniłem dodatkowych kwadratów w moim liczeniu, ale nie zorientowałem się, gdzie znajdują się w przedłużonym diamentie.

Uwaga: kiedy m==n, m-n-1 = -1co oznacza, że ​​ten ostatni termin dodaje kwadraty do liczenia. Być może brakuje mi czegoś w mojej regularnej formule. Pełne ujawnienie, miało to być jedynie łatka do wcześniejszego szkicu tej formuły, która właśnie się sprawdziła. Oczywiście nadal muszę zagłębiać się w to, co się dzieje i być może moja formuła zawiera w sobie pewne błędy. Będę was informować.

_{Russell, Gary i Weisstein, Eric W. „Aztec Diamond”. From MathWorld - zasoby internetowe Wolfram. http://mathworld.wolfram.com/AztecDiamond.html}

DO, 71 64 bajty

f(m,n){return n>m?f(n,m):m*~m*n*~n/4+n*((2*m-n)*(4*n*n-1)-3)/6;}

Wypróbuj na Ideone

Python, 73 68 bajtów

x=lambda m,n:m*~m*n*~n/4+n*((2*m-n)*(4*n*n-1)-3)/6if m>n else x(n,m)

I chociaż następująca wersja ma większą liczbę bajtów (75), było to miłe ćwiczenie w znajdowaniu miejsc do użycia ~:

def f(r,c):
 if r<c:r,c=c,r
 x=(4*c**3-c)/3
 return r*c*~r*~c/4+x*r--~x*c/2

Wypukły, 37 36 bajtów

__:)+×½½\~æ<{\}&:N\¦\-N¦¦N*(*3-N*6/+

Wypróbuj online!

Wykorzystuje zmodyfikowany i zoptymalizowany algorytm betsega dla języka opartego na stosie. Wyjaśnienie, które nastąpi, kiedy będę miał więcej wolnego czasu. Założę się, że można to skrócić, ale w tej chwili nie zamierzam się tym przejmować.

Partia, 82 bajty

@if %2 gtr %1 %0 %2 %1
@cmd/cset/a%1*~%1*%2*~%2/4+((%1+%1-%2)*(%2*%2*4-1)-3)*%2/6