21
\$\begingroup\$

As a follow-up to this challenge, we now want to count the number of rectangles in grid with r rows and c columns where there is a line crossing through every diagonal of a square in the grid. Now, we are still counting the the same rectangles as before, but this time we must also include rectangles that are tilted by 45 degrees.

Your goal is to create a function or program that given the number of rows r and columns c outputs the number of rectangles in a diagonal grid with dimensions (r, c).

As a demonstration, this is an animation that iterates through all 37 rectangles formed by a (2 x 3) diagonal grid.

Example

Test Cases

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

Rules

  • This is so the shortest code wins.
  • Builtins that solve this are not allowed.
\$\endgroup\$
  • 7
    \$\begingroup\$ Only Mathematica could have a builtin for this XD \$\endgroup\$ – Conor O'Brien Aug 3 '16 at 17:08
  • 3
    \$\begingroup\$ Gosh, this is a lot more difficult than the other rectangle ones..... \$\endgroup\$ – GamrCorps Aug 3 '16 at 17:58
  • 5
    \$\begingroup\$ See related challenge projecteuler.net/problem=147 \$\endgroup\$ – Marcus Andrews Aug 3 '16 at 19:47
  • 1
    \$\begingroup\$ I think built-ins should be allowed. I like seeing those answers. \$\endgroup\$ – mbomb007 Aug 3 '16 at 21:55
8
+100
\$\begingroup\$

Ruby, 58 bytes

This is a straightforward implementation of the algorithm in Releasing Helium Nuclei's C answer.

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

I have been investigating why this formula works, with limited success. It's easy to confirm that the number of upright rectangles is equal to (m+1)*m/2 * (n+1)*n/2, the number of diagonal rectangles is a little more elusive.

Neil has confirmed for m==n that the number of tilted rectangles in an n*n square is (4*n**4-n*n-3*n)/6 and that when m>n you need to add an additional (m-n)(n*(4*n*n-1)/3) (related to OEIS A000447), though this does not explain where those two formulas came from. I have found part of the answer.

For m==n, the shape inside the grid is an Aztec diamond.

Aztec Diamond image from Wolfram Alpha

The number of rectangles in an Aztec diamond is the sum of number of large rectangles superimposed to make it (for the fourth diamond, which is found in a 5x5 grid, 2x8, 4x6, 6x4, and 8x2) minus the number of the rectangles counted twice (the number of rectangles in the previous Aztec diamond).

The formula here is (TeX to be added later):

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

According to Wolfram Alpha, the closed form for f is 1/30*(n-1)*n*(4*n**3+14*n**2+19*n+9) and the closed form for aztec_rect is, as Neil discovered, 1/6*n*(n-1)*(4*n**2+4*n+3) == 1/6*(4*n**4-n**2-3*n).

I have yet to discover why (m-n)(n*(4*n*n-1)/3) works, though I suspect that it is because one definition of A000447 is binomial(2*n+1, 3). I will keep you posted.

Update: I have reason to believe that the function of the number of rectangles in an extended Aztec diamond m>n is related to the number of superimposed 2k*2(n-k) rectangles in the diamond minus F(m-1,n-1). More results when I have them.

Update: I tried a different route and ended up with another formula for extended Aztec diamonds that is mostly explainable but has one term that I don't yet understand. 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)

A quick breakdown of that last formula:

  • (m-n+1)*(4*n**4-n*n-3*n)/6 is the number of superimposed Aztec diamonds of size n in the structure, as f(n,n) = (4*n**4-n*n-3*n)/6. f(7,3) has 5 superimposed Aztec diamonds size 3, while f(3,3) has only 1 diamond.
  • -f(m-1,n-1) removes some of the duplicate rectangles from the middle of the superimposed diamonds.
  • +(m-n)*2 accounts for 2 extra 2-by-(2n-1) rectangles for each extra diamond.
  • +(m-n)*(n-2) accounts for an extra n-by-n square for each extra diamond.
  • -(m-n-1)*f(n-1,n-1) This is the new puzzling term. Apparently I have not accounted for some extra squares in my counting, but I haven't figured out where they are in the extended diamond.

Note: when m==n, m-n-1 = -1, meaning that this last term adds squares to the counting. I might be missing something in my regular formula. Full disclosure, this was only meant to be a patch to an earlier draft of this formula that just happened to work. Clearly, I still need to dig into what's going on, and it may be that my formula has some bugs in it. I'll keep you posted.

Russell, Gary and Weisstein, Eric W. "Aztec Diamond." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/AztecDiamond.html

\$\endgroup\$
  • \$\begingroup\$ I like how this answer has more upvotes than the original answer, and a +100 bounty... :P \$\endgroup\$ – HyperNeutrino Jan 26 '17 at 15:48
5
\$\begingroup\$

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

Try it on Ideone

\$\endgroup\$
  • 2
    \$\begingroup\$ I'd love to know what's going on here and how you arrived at this solution. \$\endgroup\$ – Jordan Aug 3 '16 at 21:36
  • 1
    \$\begingroup\$ @Jordan So far I've verified the second half of the formula for m==n: the number of tilted rectangles in an n*n square is (4*n*n*n*n-n*n-3*n)/6. The sequence is 0, 9, 51, 166, 410, 855, 1589, 2716, 4356, 6645 but it doesn't appear in OEIS. \$\endgroup\$ – Neil Aug 5 '16 at 0:34
  • 1
    \$\begingroup\$ I've now verified that when m>n you need to add an additional (m-n)(n*(4*n*n-1)/3) (latter part of formula taken from OEIS A000447). Rearranging and adding gives @betseg's formula. \$\endgroup\$ – Neil Aug 5 '16 at 0:47
  • \$\begingroup\$ @Neil How did you arrive at those formulas? \$\endgroup\$ – Sherlock9 Aug 6 '16 at 15:39
  • 2
    \$\begingroup\$ @Sherlock9 I manually calculated the numbers of tilted rectangles in the first 10 squares and fed the sequence into the OEIS search engine which didn't recognise the sequence but found a formula for it which matched the OP's formula for m==n. I then manually calculated the numbers of tilted rectangles in small rectangles and noticed increasing the longer dimension always added the same amount of rectangles for a given shorter dimension. I fed the increments into OEIS which found a match on A000447. \$\endgroup\$ – Neil Aug 6 '16 at 16:59
4
\$\begingroup\$

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)

And while the following version has a higher bytecount (75), it was a nice exercise in finding places to use ~:

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
\$\endgroup\$
  • \$\begingroup\$ 68 bytes if you use a lambda: 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) \$\endgroup\$ – GamrCorps Aug 3 '16 at 21:52
  • \$\begingroup\$ Ahh, for some reason I assumed we had to use def. Thanks! Updated. \$\endgroup\$ – Marcus Andrews Aug 3 '16 at 22:04
3
\$\begingroup\$

Convex, 37 36 bytes

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

Try it online!

Uses betseg's algorithm modified and optimized for a stack-based language. Explanation to come when I have some more free time. I bet this can be shortened but I'm not going to bother at the moment.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.