Zählen Sie die Rechtecke in einem diagonalen Raster

21

Als Reaktion auf diese Herausforderung möchten wir nun die Anzahl der Rechtecke im Raster mit r Zeilen und c Spalten zählen, wobei sich eine Linie durch jede Diagonale eines Quadrats im Raster kreuzt. Jetzt zählen wir immer noch die gleichen Rechtecke wie zuvor, aber dieses Mal müssen wir auch Rechtecke einbeziehen, die um 45 Grad geneigt sind.

Ihr Ziel ist es, eine Funktion oder ein Programm zu erstellen, die bzw. das bei gegebener Anzahl von Zeilen r und Spalten c die Anzahl von Rechtecken in einem diagonalen Raster mit den Abmessungen ( r , c ) ausgibt .

Als Demonstration ist dies eine Animation, die alle 37 Rechtecke durchläuft, die durch ein (2 x 3) Diagonalgitter gebildet werden.

Beispiel

Testfälle

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

Regeln

  • Das ist also gewinnt der kürzeste Code.
  • Builtins, die dies lösen, sind nicht erlaubt.
Meilen
quelle
7
Nur Mathematica konnte einen eingebauten Code für diesen XD haben
Conor O'Brien
3
Meine Güte
5
Siehe ähnliche Herausforderung projecteuler.net/problem=147
Marcus Andrews
1
Ich denke, Einbauten sollten erlaubt sein. Ich mag es, diese Antworten zu sehen.
mbomb007

Antworten:

8

Ruby, 58 Bytes

Dies ist eine einfache Implementierung des Algorithmus in der C-Antwort von Releasing 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}

Ich habe mit begrenztem Erfolg untersucht, warum diese Formel funktioniert. Es ist leicht zu bestätigen, dass die Anzahl der aufrechten Rechtecke gleich ist (m+1)*m/2 * (n+1)*n/2, die Anzahl der diagonalen Rechtecke ist etwas schwerer zu bestimmen.

Neil hat bestätigt , für m==ndass die Anzahl der geneigten Rechtecken in einem n*nQuadrat ist (4*n**4-n*n-3*n)/6und dass , wenn m>n Sie eine zusätzliche hinzufügen müssen (m-n)(n*(4*n*n-1)/3)(bezogen auf OEIS A000447 ), obwohl dies nicht erklären , wo diese beiden Formeln herkam. Ich habe einen Teil der Antwort gefunden.

Denn m==ndie Form innerhalb des Gitters ist ein aztekischer Diamant .

Aztekisches Diamantbild von Wolfram Alpha

Die Anzahl der Rechtecken in einem Aztec Diamanten ist die Summe der Anzahl von großen Rechtecken überlagerte zu machen (zum vierten Diamanten, der in einem gefunden wird 5x5Gitter, 2x8, 4x6, 6x4, und 8x2) minus der Anzahl der Rechtecken zweimal gezählt (die Anzahl der Rechtecke im vorherigen aztekischen Diamanten).

Die Formel lautet hier (TeX wird später hinzugefügt):

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

Laut Wolfram Alpha, die geschlossene Form für fIS 1/30*(n-1)*n*(4*n**3+14*n**2+19*n+9)und die geschlossene Form für aztec_rectist, wie Neil entdeckt 1/6*n*(n-1)*(4*n**2+4*n+3) == 1/6*(4*n**4-n**2-3*n).

Ich habe noch warum entdecken (m-n)(n*(4*n*n-1)/3)Werke, obwohl ich vermute , dass es ist , weil eine Definition von A000447 ist binomial(2*n+1, 3). Ich halte dich auf dem laufenden.

Update: Ich habe Grund zu der Annahme, dass die Funktion der Anzahl der Rechtecke in einem erweiterten Azteken-Diamanten m>nmit der Anzahl der übereinanderliegenden 2k*2(n-k)Rechtecke im Diamanten-Minus zusammenhängt F(m-1,n-1). Mehr Ergebnisse, wenn ich sie habe.

Update: Ich habe eine andere Route ausprobiert und eine andere Formel für erweiterte aztekische Diamanten gefunden, die größtenteils erklärbar ist, aber einen Begriff hat, den ich noch nicht verstehe. Huzzah! : D

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)

Eine kurze Aufschlüsselung dieser letzten Formel:

  • (m-n+1)*(4*n**4-n*n-3*n)/6ist die Anzahl der überlagerten aztekischen Diamanten der Größe nin der Struktur, wie f(n,n) = (4*n**4-n*n-3*n)/6. f(7,3)hat 5 überlagerte aztekische Diamanten 3, während f(3,3)nur 1 Diamant hat.
  • -f(m-1,n-1) Entfernt einige der duplizierten Rechtecke aus der Mitte der überlagerten Diamanten.
  • +(m-n)*2Konten für 2 zusätzliche 2-by- (2n-1)Rechtecke für jede zusätzliche Diamanten.
  • +(m-n)*(n-2)Für jeden zusätzlichen Diamanten wird ein zusätzliches Quadrat nberechnet n.
  • -(m-n-1)*f(n-1,n-1)Dies ist der neue rätselhafte Begriff. Anscheinend habe ich einige zusätzliche Quadrate bei meiner Zählung nicht berücksichtigt, aber ich habe nicht herausgefunden, wo sie sich in dem erweiterten Diamanten befinden.

Hinweis: when m==n, m-n-1 = -1bedeutet, dass dieser letzte Term der Zählung Quadrate hinzufügt . In meiner regulären Formel fehlt mir möglicherweise etwas. Vollständige Offenlegung, dies sollte nur ein Patch für einen früheren Entwurf dieser Formel sein, der gerade funktioniert hat. Klar, ich muss noch nachdenken, was los ist, und es kann sein, dass meine Formel einige Fehler enthält. Ich werde euch auf dem Laufenden halten.

Russell, Gary und Weisstein, Eric W. "Aztec Diamond". Aus MathWorld - Eine Wolfram-Webressource. http://mathworld.wolfram.com/AztecDiamond.html

Sherlock9
quelle
Mir gefällt, dass diese Antwort mehr positive Stimmen hat als die ursprüngliche Antwort und ein Kopfgeld von +100 ...: P
HyperNeutrino
5

C, 71 64 Bytes

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

Probieren Sie es auf Ideone

betseg
quelle
2
Ich würde gerne wissen, was hier vor sich geht und wie Sie zu dieser Lösung gekommen sind.
Jordanien
1
@Jordan Bisher habe ich die zweite Hälfte der Formel überprüft für m==n: Die Anzahl der geneigten Rechtecke in einem n*nQuadrat ist (4*n*n*n*n-n*n-3*n)/6. Die Sequenz lautet 0, 9, 51, 166, 410, 855, 1589, 2716, 4356, 6645, wird jedoch in OEIS nicht angezeigt.
Neil
1
Ich habe jetzt überprüft, dass, wenn m>nSie eine zusätzliche hinzufügen müssen (m-n)(n*(4*n*n-1)/3)(letzter Teil der Formel aus OEIS A000447 entnommen). Das Umordnen und Hinzufügen ergibt die Formel von @ betseg.
Neil
@Neil Wie bist du zu diesen Formeln gekommen?
Sherlock9
2
@ Sherlock9 Ich habe die Anzahl der gekippten Rechtecke in den ersten 10 Quadraten manuell berechnet und die Sequenz in die OEIS-Suchmaschine eingegeben, die die Sequenz nicht erkannt hat, aber eine Formel dafür gefunden hat, die mit der OP-Formel übereinstimmt m==n. Ich habe dann manuell die Anzahl der gekippten Rechtecke in kleinen Rechtecken berechnet und festgestellt, dass bei einer Vergrößerung der längeren Dimension immer die gleiche Anzahl von Rechtecken für eine bestimmte kürzere Dimension hinzugefügt wurde. Ich habe die Inkremente in OEIS eingespeist, was eine Übereinstimmung mit A000447 ergab.
Neil
4

Python, 73 68 Bytes

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)

Und während die folgende Version ein höheres bytecount (75) hat, war es eine schöne Übung, Orte zu finden, die man benutzen kann ~:

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
Marcus Andrews
quelle
68 Bytes, wenn Sie ein Lambda verwenden: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)
GamrCorps
Ahh, aus irgendeinem Grund nahm ich an, dass wir verwenden mussten def. Vielen Dank! Aktualisiert.
Marcus Andrews
3

Konvex, 37 36 Bytes

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

Probieren Sie es online!

Verwendet den Algorithmus von betseg, der für eine stapelbasierte Sprache modifiziert und optimiert wurde. Erklärung zu kommen, wenn ich etwas mehr Freizeit habe. Ich wette, das kann gekürzt werden, aber ich werde mich im Moment nicht darum kümmern.

GamrCorps
quelle
2

Batch, 82 Bytes

@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
Neil
quelle