The math behind this one was pretty simple, which is what made this problem so cool. I calculated for each different size of rectangle within the larger rectangle, the number of possible places this size could be. Then add all those together, and the final number of possible recangles appears!
The challenge for some reason for me was finding how to get to the optimal rectangle. I knew I couldn’t search through every single one, of every single size, espcially knowing that the orientation of height and width didn’t matter. I used the guess and check method to figure out how to do it.
close = [2*10**6, 0]
for height in range(1, 2*10**6):
last_width = 0
for width in range(1, height):
count = 0
for y in range(height):
for x in range(width):
count += ((width-x)*(height-y))
this_close = [abs(2*10**6 - count), count, height, width, width*height]
print this_close
if this_close[0] < close[0]:
close = this_close
print '^ NEW ^'
if count > 2*10**6 + close[0]:
last_width = width
break
if last_width == 1:
break
print close