Project Euler Problem #85

Problem #85 concerns finding the number of rectangles with sides along a lattice grid. The question reads:

This problem is very well known among those who participate in math competitions. Here is my solution:

Solution #1: Combinatorial Approach

We can observe that in a grid with m horizontal lines and n vertical lines, any rectangle with sides along the grid lines must have sides that coincide with 2 of the horizontal lines and 2 of the vertical lines. Thus, the number of rectangles is (m choose 2) * (n choose 2). Thus, it suffices to find the product of two values of (n choose 2) which is closest to two million. We can do this by listing all triangular numbers up to n and then checking which products are closest. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Combinatorial Approach to Project Euler Problem #85
 '''
 
 import time
 
 def projectEulerProblemEightyFive(n):
     triangles = []
     c = 1
     v = 1
     while(v<=n):
         triangles.append(v)
         c+=1
         v+=c
     l = len(triangles)
     
     closestFound = -1
     smallestDiff = n
     for a in range(l):
         for b in range(a,l):
             c = triangles[a]
             d = triangles[b]
             v = abs(c*d-n)
             if(v<smallestDiff):
                 smallestDiff = v
                 closestFound = (a+1)*(b+1)
     return closestFound
 
 start = time.time()
 print projectEulerProblemEightyFive(2000000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 2772
 --- 0.207247018814 seconds ---
 
 for input of n = 2000000.
 ''' 

And with that, we’re done. Looking back on this solution, I realize that I forgot to deal with the case where the closest grid has 2 lines in one direction and n lines in another direction so that n choose 2 is barely greater than the input. I am too lazy to make this change to make the solution universal at the moment. I may come back to this problem eventually to search for a more optimal solution.

Thanks for reading! See you tomorrow.