À la suite de ce défi , nous voulons maintenant compter le nombre de rectangles dans la grille avec r lignes et c colonnes où il y a une ligne traversant chaque diagonale d'un carré dans la grille. Maintenant, nous comptons toujours les mêmes rectangles qu'auparavant, mais cette fois, nous devons également inclure des rectangles inclinés de 45 degrés.

Votre objectif est de créer une fonction ou un programme qui, compte tenu du nombre de lignes r et de colonnes c, affiche le nombre de rectangles dans une grille diagonale avec des dimensions ( r , c ).

À titre de démonstration, il s'agit d'une animation qui parcourt les 37 rectangles formés par une grille diagonale (2 x 3).

Cas de test

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

Règles

• C'est le code-golf donc le code le plus court l'emporte.
• Les buildins qui résolvent ce problème ne sont pas autorisés.

Rubis, 58 octets

Il s'agit d'une implémentation simple de l'algorithme dans la réponse C de libération des noyaux d'hélium .

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

J'ai cherché pourquoi cette formule fonctionne, avec un succès limité. Il est facile de confirmer que le nombre de rectangles verticaux est égal à (m+1)*m/2 * (n+1)*n/2, le nombre de rectangles diagonaux est un peu plus difficile à cerner.

Neil a confirmé pour m==nque le nombre de rectangles inclinés dans un n*ncarré est (4*n**4-n*n-3*n)/6et que quand m>n vous avez besoin d'ajouter un montant supplémentaire (m-n)(n*(4*n*n-1)/3)(lié à OEIS A000447 ), bien que cela n'explique pas où ces deux formules viennent. J'ai trouvé une partie de la réponse.

Car m==n, la forme à l'intérieur de la grille est un diamant aztèque .

Le nombre de rectangles dans un diamant Aztec est la somme du nombre de grands rectangles superposés pour le faire (pour le quatrième diamant, qui se trouve dans une 5x5grille, 2x8, 4x6, 6x4, et 8x2) moins le nombre des rectangles comptés deux fois (le nombre de rectangles dans le diamant aztèque précédent ).

La formule ici est (TeX à ajouter plus tard):

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

Selon Wolfram Alpha, la forme fermée pour fest 1/30*(n-1)*n*(4*n**3+14*n**2+19*n+9)et la forme fermée pour aztec_rectest, comme Neil l'a découvert 1/6*n*(n-1)*(4*n**2+4*n+3) == 1/6*(4*n**4-n**2-3*n).

Je n'ai pas encore découvert pourquoi (m-n)(n*(4*n*n-1)/3)fonctionne, bien que je soupçonne que c'est parce qu'une définition de A000447 est binomial(2*n+1, 3). Je vous tiendrai au courant.

Mise à jour: J'ai des raisons de croire que la fonction du nombre de rectangles dans un diamant aztèque étendu m>nest liée au nombre de 2k*2(n-k)rectangles superposés dans le diamant moins F(m-1,n-1). Plus de résultats quand je les ai.

Mise à jour: J'ai essayé un itinéraire différent et je me suis retrouvé avec une autre formule pour les diamants aztèques étendus qui est principalement explicable mais a un terme que je ne comprends pas encore. Huzzah! :RÉ

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)

Une ventilation rapide de cette dernière formule:

• (m-n+1)*(4*n**4-n*n-3*n)/6est le nombre de diamants aztèques superposés de taille ndans la structure, en f(n,n) = (4*n**4-n*n-3*n)/6. f(7,3)a 5 diamants aztèques superposés 3, alors qu'il f(3,3)n'a qu'un seul diamant.
• -f(m-1,n-1) supprime certains des rectangles en double du milieu des diamants superposés.
• +(m-n)*2représente 2 rectangles supplémentaires 2par (2n-1)pour chaque diamant supplémentaire.
• +(m-n)*(n-2)représente un extra n- ncarré pour chaque diamant supplémentaire.
• -(m-n-1)*f(n-1,n-1)C'est le nouveau terme déroutant. Apparemment, je n'ai pas compté de carrés supplémentaires dans mon comptage, mais je n'ai pas compris où ils se trouvent dans le diamant étendu.

Remarque: lorsque m==n, m-n-1 = -1ce qui signifie que ce dernier terme ajoute carrés au comptage. Il se peut que je manque quelque chose dans ma formule habituelle. Divulgation complète, cela ne devait être qu'un patch pour un avant-projet de cette formule qui venait juste de fonctionner. De toute évidence, je dois encore creuser ce qui se passe, et il se peut que ma formule contienne des bugs. Je te tiendrai au courant.

_{Russell, Gary et Weisstein, Eric W. «Aztec Diamond». De MathWorld - Une ressource Web Wolfram. http://mathworld.wolfram.com/AztecDiamond.html}

C, 71 64 octets

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

Essayez-le sur Ideone

Python, 73 68 octets

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)

Et bien que la version suivante ait un bytecount plus élevé (75), c'était un bon exercice pour trouver des endroits à utiliser ~:

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

Convexe, 37 36 octets

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

Essayez-le en ligne!

Utilise l'algorithme de betseg modifié et optimisé pour un langage basé sur la pile. Explication à venir quand j'aurai plus de temps libre. Je parie que cela peut être raccourci mais je ne vais pas déranger pour le moment.

Lot, 82 octets

@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