Como seguimiento a este desafío , ahora queremos contar el número de rectángulos en la cuadrícula con r filas yc columnas donde hay una línea que cruza cada diagonal de un cuadrado en la cuadrícula. Ahora, seguimos contando los mismos rectángulos que antes, pero esta vez también debemos incluir rectángulos que estén inclinados 45 grados.

Su objetivo es crear una función o programa que, dada la cantidad de filas r y columnas c, genere la cantidad de rectángulos en una cuadrícula diagonal con dimensiones ( r , c ).

Como demostración, esta es una animación que recorre los 37 rectángulos formados por una cuadrícula diagonal (2 x 3).

Casos de prueba

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

Reglas

• Este es el código de golf, por lo que gana el código más corto.
• Los componentes que resuelven esto no están permitidos.

Ruby, 58 bytes

Esta es una implementación directa del algoritmo en Liberar la respuesta C de 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}

He estado investigando por qué funciona esta fórmula, con un éxito limitado. Es fácil confirmar que el número de rectángulos verticales es igual (m+1)*m/2 * (n+1)*n/2, el número de rectángulos diagonales es un poco más difícil de alcanzar.

Neil ha confirmado para m==nque el número de rectángulos inclinados en un n*ncuadrado es(4*n**4-n*n-3*n)/6 y que cuando m>n es necesario agregar un adicional (m-n)(n*(4*n*n-1)/3)(relacionado con OEIS A000447 ), aunque esto no explica que estas dos fórmulas de procedencia. He encontrado parte de la respuesta.

por m==n , la forma dentro de la cuadrícula es un diamante azteca .

El número de rectángulos en un diamante azteca es la suma del número de rectángulos grandes superpuestos para hacerlo (para el cuarto diamante, que se encuentra en un 5x5 cuadrícula, 2x8, 4x6, 6x4, y 8x2) menos el número de los rectángulos contados dos veces (el número de rectángulos en el diamante azteca anterior ).

La fórmula aquí es (TeX se agregará más adelante):

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

Según Wolfram Alpha, la forma cerrada para f decir 1/30*(n-1)*n*(4*n**3+14*n**2+19*n+9)y la forma cerrada para aztec_rectdecir, como Neil descubrió, 1/6*n*(n-1)*(4*n**2+4*n+3) == 1/6*(4*n**4-n**2-3*n).

Todavía tengo que descubrir por qué (m-n)(n*(4*n*n-1)/3) funciona, aunque sospecho que es porque una definición de A000447 es binomial(2*n+1, 3). Te mantendré informado.

Actualizar: Tengo razones para creer que la función del número de rectángulos en un diamante azteca extendido m>nestá relacionada con el número de 2k*2(n-k)rectángulos superpuestos en el diamante menos F(m-1,n-1). Más resultados cuando los tengo.

Actualizar: probé una ruta diferente y terminé con otra fórmula para diamantes aztecas extendidos que es explicable en su mayoría pero tiene un término que aún no entiendo. 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)

Un desglose rápido de esa última fórmula:

• (m-n+1)*(4*n**4-n*n-3*n)/6es el número de diamantes aztecas superpuestos de tamaño nen la estructura, como f(n,n) = (4*n**4-n*n-3*n)/6. f(7,3)tiene 5 diamantes superpuestos de tamaño azteca3 , mientras que f(3,3)solo tiene 1 diamante.
• -f(m-1,n-1) elimina algunos de los rectángulos duplicados del centro de los diamantes superpuestos.
• +(m-n)*2representa 2 extra 2-por-(2n-1) rectángulos para cada diamante adicional.
• +(m-n)*(n-2)representa un extra n-by- ncuadrado para cada diamante adicional.
• -(m-n-1)*f(n-1,n-1)Este es el nuevo término desconcertante. Aparentemente, no he tenido en cuenta algunos cuadrados adicionales en mi conteo, pero no he descubierto dónde están en el diamante extendido.

Nota: cuando m==n, m-n-1 = -1lo que significa que este último término agrega cuadrados al conteo. Puede que me falte algo en mi fórmula habitual. Revelación completa, esto solo pretendía ser un parche para un borrador anterior de esta fórmula que acaba de funcionar. Claramente, todavía necesito profundizar en lo que está sucediendo, y puede ser que mi fórmula tenga algunos errores. Te mantendré informado.

_{Russell, Gary y Weisstein, Eric W. "Diamante azteca". De MathWorld: un recurso web de Wolfram. http://mathworld.wolfram.com/AztecDiamond.html}

DO, 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;}

Pruébalo en Ideone

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)

Y aunque la siguiente versión tiene un bytecount más alto (75), fue un buen ejercicio para encontrar lugares para usar ~:

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

Convexo, 37 36 bytes

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

Pruébalo en línea!

Utiliza el algoritmo de betseg modificado y optimizado para un lenguaje basado en pila. Explicación por venir cuando tenga más tiempo libre. Apuesto a que esto se puede acortar, pero no voy a molestar en este momento.

Lote, 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