Como acompanhamento desse desafio , agora queremos contar o número de retângulos na grade com r linhas ec colunas onde existe uma linha cruzando todas as diagonais de um quadrado na grade. Agora, ainda estamos contando os mesmos retângulos de antes, mas desta vez também devemos incluir retângulos inclinados em 45 graus.

Seu objetivo é criar uma função ou programa que, dado o número de linhas r e colunas c, produz o número de retângulos em uma grade diagonal com dimensões ( r , c ).

Como demonstração, é uma animação que itera pelos 37 retângulos formados por uma grade diagonal (2 x 3).

Casos de teste

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

Regras

• Isso é código-golfe, então o código mais curto vence.
• Builtins que resolvem isso não são permitidos.

Ruby, 58 bytes

Esta é uma implementação direta do algoritmo na resposta C de liberação dos núcleos de hélio .

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

Tenho investigado por que essa fórmula funciona, com sucesso limitado. É fácil confirmar que o número de retângulos na vertical é igual a (m+1)*m/2 * (n+1)*n/2, o número de retângulos na diagonal é um pouco mais ilusório.

Neil foi confirmada para m==nque o número de retângulos inclinados em uma n*npraça é (4*n**4-n*n-3*n)/6e que quando m>n você precisa adicionar um adicional (m-n)(n*(4*n*n-1)/3)(relacionada com OEIS A000447 ), embora isso não explica onde essas duas fórmulas veio. Eu encontrei parte da resposta.

Pois m==n, a forma dentro da grade é um diamante asteca .

O número de rectângulos em um diamante asteca é a soma do número de grandes rectângulos sobrepostos para torná-la (para o quarto de diamante, que se encontra em uma 5x5grade, 2x8, 4x6, 6x4, e 8x2) menos o número dos rectângulos contado duas vezes (o número de retângulos no diamante asteca anterior ).

A fórmula aqui é (TeX a ser adicionado posteriormente):

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

De acordo com Wolfram Alpha, a forma fechada para fé 1/30*(n-1)*n*(4*n**3+14*n**2+19*n+9)e a forma fechada para aztec_recté, como Neil descobriu 1/6*n*(n-1)*(4*n**2+4*n+3) == 1/6*(4*n**4-n**2-3*n),.

Ainda estou para descobrir por que (m-n)(n*(4*n*n-1)/3)funciona, embora eu suspeite que seja porque uma definição de A000447 é binomial(2*n+1, 3). Vou mantê-lo informado.

Atualização: Tenho motivos para acreditar que a função do número de retângulos em um diamante asteca estendido m>nestá relacionada ao número de 2k*2(n-k)retângulos sobrepostos no diamante menos F(m-1,n-1). Mais resultados quando eu os tiver.

Atualização: Tentei uma rota diferente e acabei com outra fórmula para os diamantes astecas estendidos que são explicáveis ​​principalmente, mas que têm um termo que ainda não entendi. 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)

Um rápido resumo dessa última fórmula:

• (m-n+1)*(4*n**4-n*n-3*n)/6é o número de diamantes astecas sobrepostos de tamanho nna estrutura, como f(n,n) = (4*n**4-n*n-3*n)/6. f(7,3)tem 5 diamantes astecas sobrepostos 3, enquanto f(3,3)tem apenas 1 diamante.
• -f(m-1,n-1) remove alguns retângulos duplicados do meio dos diamantes sobrepostos.
• +(m-n)*2responde por 2 extra 2-by- (2n-1)retângulos para cada diamante extra.
• +(m-n)*(n-2)representa um extra n-by- nquadrado para cada diamante extra.
• -(m-n-1)*f(n-1,n-1)Este é o novo termo intrigante. Aparentemente, eu não contei alguns quadrados extras na minha contagem, mas ainda não descobri onde eles estão no diamante estendido.

Nota: quando m==n, m-n-1 = -1significa que este último termo adiciona quadrados à contagem. Eu posso estar perdendo alguma coisa na minha fórmula regular. Divulgação completa, isso só deveria ser um patch para um rascunho anterior dessa fórmula que funcionava. Claramente, ainda preciso me aprofundar no que está acontecendo, e pode ser que minha fórmula tenha alguns bugs. Vou mantê-lo informado.

_{Russell, Gary e Weisstein, Eric W. "Aztec Diamond". De MathWorld - um recurso da Web da Wolfram. http://mathworld.wolfram.com/AztecDiamond.html}

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

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

E embora a versão a seguir tenha um número de bytes mais alto (75), foi um bom exercício 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/+

Experimente online!

Usa o algoritmo da betseg modificado e otimizado para uma linguagem baseada em pilha. Explicação para vir quando tiver mais tempo livre. Aposto que isso pode ser reduzido, mas não vou incomodar no 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