В качестве продолжения этой задачи мы теперь хотим подсчитать количество прямоугольников в сетке с r строками и столбцами c, где есть линия, пересекающая каждую диагональ квадрата в сетке. Теперь мы по-прежнему считаем те же прямоугольники, что и раньше, но на этот раз мы должны также включить прямоугольники, наклоненные на 45 градусов.

Ваша цель - создать функцию или программу, которая с учетом числа строк r и столбцов c выводит количество прямоугольников в диагональной сетке с размерами ( r , c ).

В качестве демонстрации это анимация, которая перебирает все 37 прямоугольников, образованных диагональной сеткой (2 x 3).

Тестовые случаи

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

правила

• Это код-гольф, поэтому выигрывает самый короткий код.
• Встроенные функции, которые решают эту проблему, не допускаются.

Рубин, 58 байт

Это простая реализация алгоритма в выпуске 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}

Я изучал, почему эта формула работает, с ограниченным успехом. Нетрудно подтвердить, что количество вертикальных прямоугольников равно (m+1)*m/2 * (n+1)*n/2, а количество диагональных прямоугольников немного неуловимо.

Нил подтвердил для m==nчто количество наклонных прямоугольников в n*nквадрате , (4*n**4-n*n-3*n)/6и что , когда m>n вам нужно добавить дополнительный (m-n)(n*(4*n*n-1)/3)(связанный с OEIS A000447 ), хотя это не объясняет , где эти две формулы пришли. Я нашел часть ответа.

Для m==nформы внутри сетки является Aztec алмаза .

Количество прямоугольников в ацтекском алмазе является сумма ряда крупных прямоугольников накладывается , чтобы сделать это (за четвертый алмаз, который находится в 5x5сетке 2x8, 4x6, 6x4и 8x2) минус число прямоугольников посчитано дважды (число прямоугольники в предыдущем ацтекском алмазе).

Формула здесь (TeX будет добавлен позже):

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

Согласно Вольфраму Альфе, закрытая форма для fis 1/30*(n-1)*n*(4*n**3+14*n**2+19*n+9)и закрытая форма для aztec_rectis, как обнаружил Нейл 1/6*n*(n-1)*(4*n**2+4*n+3) == 1/6*(4*n**4-n**2-3*n).

Мне еще предстоит выяснить, почему (m-n)(n*(4*n*n-1)/3)работает, хотя я подозреваю, что это потому, что одно определение A000447 является binomial(2*n+1, 3). Я буду держать вас в курсе.

Обновление: у меня есть основания полагать, что функция количества прямоугольников в расширенном ацтекском алмазе m>nсвязана с количеством наложенных 2k*2(n-k)прямоугольников в минусе F(m-1,n-1). Больше результатов, когда они у меня есть.

Обновление: я пробовал другой маршрут и в итоге получил другую формулу для расширенных ацтекских алмазов, которая в основном объяснима, но имеет один термин, который я еще не понимаю. Ура! : 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)

Краткое описание этой последней формулы:

• (m-n+1)*(4*n**4-n*n-3*n)/6количество наложенных ацтекских алмазов размера nв структуре, а f(n,n) = (4*n**4-n*n-3*n)/6. f(7,3)имеет 5 наложенных ацтекских бриллиантов размером 3, в то время как f(3,3)имеет только 1 бриллиант.
• -f(m-1,n-1) удаляет некоторые повторяющиеся прямоугольники из середины наложенных алмазов.
• +(m-n)*2составляет 2 дополнительных 2матрицу с размерностью (2n-1)прямоугольников для каждого дополнительного бриллианта.
• +(m-n)*(n-2)счета за дополнительную nматрицу с размерностью nквадрата для каждого дополнительного бриллианта.
• -(m-n-1)*f(n-1,n-1)Это новый загадочный термин. Очевидно, я не учел некоторые дополнительные квадраты в моем подсчете, но я не выяснил, где они находятся в расширенном алмазе.

Примечание: когда m==n, m-n-1 = -1означает, что последний член добавляет квадраты к счету. Я мог бы что-то упустить в моей обычной формуле. Полное раскрытие, это было предназначено только для исправления более ранней версии этой формулы, которая только что сработала. Очевидно, мне все еще нужно разобраться в том, что происходит, и, возможно, в моей формуле есть некоторые ошибки. Я буду держать вас в курсе.

_{Рассел, Гэри и Вайстейн, Эрик У. "Ацтек Алмаз". Из MathWorld - веб-ресурс Wolfram. http://mathworld.wolfram.com/AztecDiamond.html}

C, 71 64 байта

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

Попробуйте это на Ideone

Python, 73 68 байт

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)

И хотя следующая версия имеет более высокое число байтов (75), это было хорошее упражнение в поиске мест для использования ~:

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

Выпуклый, 37 36 байтов

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

Попробуйте онлайн!

Использует алгоритм Betseg, модифицированный и оптимизированный для стекового языка. Объяснение придет, когда у меня будет больше свободного времени. Могу поспорить, что это может быть сокращено, но я не собираюсь беспокоиться в данный момент.

Пакет, 82 байта

@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