Code takes a lot of time to run for large numbers

Question

Given the number of squares in a board (e.g. scrabble or chess board), N and dimensions AxB, this code tries to determine all possible dimensional combinations that can give N number of squares in the board.

Example: N = 8

There are four possible dimensional combinations to obtain exactly 8 squares in the board. So, the code outputs board dimensions 1x8 2x3, 3x2 and 8x1. The 8x1 boards have eight 1x1 squares; the 3x2 boards have six 1x1 squares and two 2x2 squares.

Here is my solution:

def dims(num_sqrs):
    dim_list=[]
    for i in range(1,num_sqrs+1):
        temp = []
        for x in range(1,num_sqrs+1):
            res = 0
            a = i
            b = x
            while (a != 0) and (b !=0):
                res = res + (a*b)
                a = a -1
                b = b-1
            if res == num_sqrs:
                dim_list.append((i,x))
    print(dim_list)

dims(8)

However, this code takes too much time to run for large values of N. Any suggestion to optimize the efficiency of the code will be much appreciated.

Answer 1

This uses the formula derived in the link provided by the OP. The only real optimization is trying not to look at dimensions that cannot produce the result. Pre-loading the results with the two end cases (figures = [(1,n_squares),(n_squares,1)]) saved a lot with big numbers. I think there are others chunks that can be discarded but I haven't figured them out yet.

def h(n_squares):
    # easiest case for a n x m figure:
    # n = 1 and m = n_squares
    figures = [(1,n_squares),(n_squares,1)]
    for n in range(2, n_squares+1):
        for m in range(n, n_squares+1):
            t = m - n
            x = int((n * (n + 1) / 6) * ((2 * n) + (3 * t) + 1))
            if x > n_squares:
                break
            if x == n_squares:
                figures.extend([(n,m),(m,n)])
                #print(f'{n:>6} x {m:<6} has {n_squares} squares')
        if x > n_squares and n == m:
            break
    return figures    

It also doesn't make lots of lists which can blow up your computer with really big numbers like 21493600 (400x401).

---

Formula derivation from link in OP's comment (in case that resource disappears):
text from Link

courtesy:

• Doctor Anthony, The Math Forum
  Link

If we have an 8 x 9 board the numbers of squares are as follows:

Size of Square        Number of Squares  
--------------        -----------------
    1 x 1                8 x 9  = 72
    2 x 2                7 x 8  = 56
    3 x 3                6 x 7  = 42
    4 x 4                5 x 6  = 30
    5 x 5                4 x 5  = 20
    6 x 6                3 x 4  = 12
    7 x 7                2 x 3  =  6
    8 x 8                1 x 2  =  2
  ----------------------------------------
                         Total  = 240

For the general case of an n x m board, where m = n + t We require

         n                n
        SUM[r(r + t)]  = SUM[r^2 + rt} 
        r=1              r=1

       = n(n + 1)(2n + 1)/6 + tn(n + 1)/2

       = [n(n + 1)/6]*[2n + 1 + 3t]

No. of squares =

             [n(n + 1)/6]*[2n + 3t + 1]  .......(1)

In the example above t = 1 and so

 No. of squares  = 8 x 9/6[16 + 3 + 1]

                 = (72/6)[20]

                 = 240    (as required)

The general formula for an (n x n+t) board is that given in (1) above.

No. of squares = [n(n + 1)/6]*[2n + 3t + 1]

Answer 2

Here are two pretty obvious observations:

1. The square count for AxB is the same as the square count for BxA

2. If C>B then the square count for AxC is greater than the square count for AxB

Given those facts, it should be clear that:

1. We only need to consider AxB for A≤B, since we can just add BxA to the list if A≠B

2. For a given A and N, there is at most one value of B which has a square count of N.

The code below is based on the above. It tries each AxA in turn, for each one checking to see if there is some B≥A which produces the correct square count. It stops when the square count for AxA exceeds N.

Now, to find the correct value of B, a couple of slightly less obvious observations.

1. Suppose the square count for AxA is N. Then the square count for (A+1)x(Ax1) is N + (A+1)².

   Proof: Every square in AxA can be identified by its upper left co-ordinate [i, j] and its size s. I'll write that as [s: *i, j]. (Here I'm assuming that coordinates are zero-based and go from top to bottom and left to right.)

   For each such square 0 ≤ i + s < A and 0 ≤ j + s < A (assuming 0-based coordinates).

   Now, suppose we change each square [s: i, j] into the square based at the same coordinate but with a size one larger, [s+1: i, j]. That new square is a square in (A+1)x(A+1), because 0 ≤ i + s + 1 < A + 1 (and similarly for j). So that transformation gives us every square in A + 1 whose size is at least 2. The only squares which we've missed are the squares of size 1, and there are exactly (A+1)×(A+1) of them.

2. Suppose the square count for AxB is N, and B≥A. Then the square count for Ax(B+1) is N + the sum of each integer from 1 to A. (These are the triangular number, which are A×(A+1)/2; I think that's well-known.)

   Proof: The squares in Ax(B+1) are precisely the squares in AxB plus the squares whose right-hand side includes the last column of Ax(B+1). So we only need to count those. There is one such square of size A, two of size A-1, three of size A-2, and so on up to A squares of size 1.

So for a given A, we can compute the square count for AxA and the increment in the square count for each increase in B. If the increment even divides the difference between the target count and the count of AxA, then we've found an AxB.

The program below also relies on one more algebraic identity, which is pretty straight-forward: the sum of two consecutive triangular numbers is a square. That's obvious by just arranging the two triangles. The larger one contains the diagonal of the square. These facts are used to compute the next base value and increment for the next value of A.

def finds(n):
  a = 1
  base = 1   # Square count for AxA
  inc = 1    # Difference between count(AxB) and count(AxB+1)
  rects = []
  while base < n:
    if (n - base) % inc == 0:
      rects.append((a, a + (n - base) // inc))
    a += 1
    newinc = inc + a
    base += inc + newinc
    inc = newinc
  if base == n:
    return rects + [(a, a)] + list(map(lambda p:p[::-1], reversed(rects)))
  else:
    return rects + list(map(lambda p:p[::-1], reversed(rects)))

The slowest part of that function is adding the reverse of the reverses of the AxB solutions at the end, which I only did to simplify counting the solutions correctly. My first try, which was almost twice as fast, used the loop while base <= n and then just returned rects. But it's still fast enough.

For example:

>>> finds(1000000)
[(1, 1000000), (4, 100001), (5, 66668), (15, 8338), (24, 3341),
 (3341, 24), (8338, 15), (66668, 5), (100001, 4), (1000000, 1)]

>>> finds(760760)
[(1, 760760), (2, 253587), (3, 126794), (4, 76077), (7, 27172),
 (10, 13835), (11, 11530), (12, 9757), (13, 8364), (19, 4010),
 (20, 3629), (21, 3300), (38, 1039), (39, 988), (55, 512),
 (56, 495), (65, 376), (76, 285), (285, 76), (376, 65),
 (495, 56), (512, 55), (988, 39), (1039, 38), (3300, 21),
 (3629, 20), (4010, 19), (8364, 13), (9757, 12), (11530, 11),
 (13835, 10), (27172, 7), (76077, 4), (126794, 3), (253587, 2), 
 (760760, 1)]

The last one came out of this test, which took a few seconds: (It finds each successive maximum number of solutions, if you don't feel like untangling the functional elements)

>>> from functools import reduce
>>> print('\n'.join(
      map(lambda l:' '.join(map(lambda ab:"%dx%d"%ab, l)),
          reduce(lambda a,b: a if len(b) <= len(a[-1]) else a + [b],
                 (finds(n) for n in range(2,1000001)),[[(1,1)]])))) 
1x1
1x2 2x1
1x5 2x2 5x1
1x8 2x3 3x2 8x1
1x14 2x5 3x3 5x2 14x1
1x20 2x7 3x4 4x3 7x2 20x1
1x50 2x17 3x9 4x6 6x4 9x3 17x2 50x1
1x140 2x47 3x24 4x15 7x7 15x4 24x3 47x2 140x1
1x280 4x29 5x20 6x15 7x12 12x7 15x6 20x5 29x4 280x1
1x770 2x257 3x129 4x78 10x17 11x15 15x11 17x10 78x4 129x3 257x2 770x1
1x1430 2x477 3x239 4x144 10x29 11x25 12x22 22x12 25x11 29x10 144x4 239x3 477x2 1430x1
1x3080 2x1027 3x514 4x309 7x112 10x59 11x50 20x21 21x20 50x11 59x10 112x7 309x4 514x3 1027x2 3080x1
1x7700 2x2567 3x1284 4x771 7x277 10x143 11x120 20x43 21x40 40x21 43x20 120x11 143x10 277x7 771x4 1284x3 2567x2 7700x1
1x10010 2x3337 3x1669 4x1002 10x185 11x155 12x132 13x114 20x54 21x50 50x21 54x20 114x13 132x12 155x11 185x10 1002x4 1669x3 3337x2 10010x1
1x34580 2x11527 3x5764 4x3459 7x1237 12x447 13x384 19x188 20x171 38x59 39x57 57x39 59x38 171x20 188x19 384x13 447x12 1237x7 3459x4 5764x3 11527x2 34580x1
1x40040 2x13347 3x6674 4x4005 7x1432 10x731 11x610 12x517 13x444 20x197 21x180 39x64 64x39 180x21 197x20 444x13 517x12 610x11 731x10 1432x7 4005x4 6674x3 13347x2 40040x1
1x100100 2x33367 3x16684 4x10011 7x3577 10x1823 11x1520 12x1287 13x1104 20x483 21x440 25x316 39x141 55x83 65x68 68x65 83x55 141x39 316x25 440x21 483x20 1104x13 1287x12 1520x11 1823x10 3577x7 10011x4 16684x3 33367x2 100100x1
1x340340 2x113447 3x56724 4x34035 7x12157 10x6191 11x5160 12x4367 13x3744 20x1627 21x1480 34x583 39x449 55x239 65x180 84x123 123x84 180x65 239x55 449x39 583x34 1480x21 1627x20 3744x13 4367x12 5160x11 6191x10 12157x7 34035x4 56724x3 113447x2 340340x1
1x760760 2x253587 3x126794 4x76077 7x27172 10x13835 11x11530 12x9757 13x8364 19x4010 20x3629 21x3300 38x1039 39x988 55x512 56x495 65x376 76x285 285x76 376x65 495x56 512x55 988x39 1039x38 3300x21 3629x20 4010x19 8364x13 9757x12 11530x11 13835x10 27172x7 76077x4 126794x3 253587x2 760760x1

Answer 3

Start with basic algebraic analysis. I derived my own formula for the sums of various sizes. From the initial analysis, we get that for a board of size n x m, there are (n-k)*(m-k) squares of size k. Summing this for k in [0, min(m, n)] we have a simple calculation formula:

sum(((n-k) * (m-k) for k in range(0, min(n, m))))

I expanded the product to nm - k(n+m) + k^2, re-derived the individual series sums, and made a non-iterative formula, assuming n <= m:

n * n * m 
- n * (n - 1) / 2 * (n + m)
+ ((n - 1) * n * (2 * n - 1))/6

This first link then spoiled my fun with an even shorter formula:

t = m - n
n * (n + 1) / 6 * (2 * n + 3 * t + 1)

which follows from mine with a bit of nifty rearrangement of terms.

---

Now to the point of this exercise: given a desired count of squares, Q, find all rectangle dimensions (n, m) that have exactly that many squares. Starting with the formula above:

q = n * (n + 1) / 6 * (2 * n + 3 * t + 1)

Since we're given Q, the desired value for q, we can iterate through all values of n, finding whether there is a positive, integral value for t that satisfies the formula. Start by solving this for t:

t = (6/(n*(n+1)) * q - 2*n - 1) / 3

combining the denominators:

t = (6*q) / (3*n*(n+1)) - (2*n + 1)/3

I'll use the first version. Since a solution of n x m implies a solution of m x n, we can limit our search to only those cases n <= m. Also, since the numerator shrinks (negative n^3 term), we can limit the search for values of n that allow t >= 1 -- in other words, have the combined numerator at least as large as the denominator:

numer = 6 * num_sqrs - n * (n+1) * (2*n+1)
denom = 3 * n * (n+1)

Solving this:

num_sqrs > (n * (n+1) * (n+2)) / 3

Thus, the (cube root of n) / 3 is a convenient upper bound for our loop limits.

This gives us a simple iteration loop in the code:

def dims(num_sqrs):
    dim = [(1, num_sqrs)]
    limit = ceil((3*num_sqrs)**(1.0/3.0))
    for n in range(2, limit):
        numer = 6 * num_sqrs - n * (n+1) * (2*n+1)
        denom = 3 * n * (n+1)
        if numer % denom == 0:
            t = numer // denom
            if t >= 0:
                dim.append((n, n+t))

    return dim

Output for a couple of test cases:

>>> print(dims(8))
[(1, 8), (2, 3)]

>>> print(dims(2000))
[(1, 2000), (2, 667), (3, 334), (4, 201)]

>>> print(dims(1000000))
[(1, 1000000), (4, 100001), (5, 66668), (15, 8338), (24, 3341)]

>>> print(dims(21493600))
[(1, 21493600), (4, 2149361), (5, 1432908), (15, 179118), (24, 71653), (400, 401)]

These return immediately, so I expect that this solution is fast enough for OP's purposes.

It's quite possible that a parameterized equation would give us direct solutions, rather than iterating through possibilities. I'll leave that for the Project Euler folks. :-)

Answer 4

I think the critical detail is that @Qudus is looking for boards where there are N squares of any size.

One simple optimization is to just break when res > n. Another optimization to make it about twice as fast is to only run it for boards where length >= width.

def dims(num_sqrs):
    dim_list=[]
    for i in range(1, num_sqrs + 1):
        temp = []
        for x in range(1, i + 1):
            res = 0
            a = i
            b = x
            while (a != 0) and (b != 0):
                res = res + (a * b)
                a = a - 1
                b = b - 1
                if res > num_sqrs:
                    break
            if res == num_sqrs:
                dim_list.append((i, x))
                if i != x:
                    dim_list.append((x, i))
    print(dim_list)

Here's a much faster solution that takes a different approach:

def dims(num_sqrs):
    dim_list = []
    sum_squares = [0]
    sums = [0] 
    for i in range(1, num_sqrs + 1):
        sums.append(sums[-1] + i)
        sum_squares.append(sum_squares[-1] + i * i)

    for i in range(1, num_sqrs + 1):
        if sum_squares[i] > num_sqrs:
            break
        if sum_squares[i] == num_sqrs:
            dim_list.append((i, i))
            break
        for x in range(i + 1, num_sqrs + 1):
            total_squares = sum_squares[i] + sums[i] * (x - i)
            if total_squares == num_sqrs:
                dim_list.append((x, i))
                dim_list.append((i, x))
                break
            if total_squares > num_sqrs:
                break
    return dim_list