55 lines
1.3 KiB
Python
55 lines
1.3 KiB
Python
from collections import namedtuple
|
|
from collections import deque
|
|
|
|
Rect = namedtuple("Rect", ["cols", "rows"])
|
|
|
|
|
|
def sub_rectangles(rect):
|
|
r = [Rect(i, j)
|
|
for i in range(1, rect.cols + 1)
|
|
for j in range(1, rect.rows + 1)]
|
|
return r
|
|
|
|
def flat_fit(n_inner, n_outer):
|
|
return n_outer - n_inner + 1
|
|
|
|
def count_fits(sub_rect, main_rect):
|
|
row_fits = flat_fit(sub_rect.rows, main_rect.rows)
|
|
col_fits = flat_fit(sub_rect.cols, main_rect.cols)
|
|
return row_fits * col_fits
|
|
|
|
|
|
def count_sub_rectangles(rect):
|
|
r = 0
|
|
for sub_rect in sub_rectangles(rect):
|
|
r += count_fits(sub_rect, rect)
|
|
return r
|
|
|
|
|
|
def euler_085():
|
|
limit = 2 * 10**6
|
|
nearest = 0
|
|
canditate_rects = deque([Rect(1, 1)])
|
|
|
|
while canditate_rects:
|
|
rect = canditate_rects.popleft()
|
|
sub_count = count_sub_rectangles(rect)
|
|
# print(rect, sub_count)
|
|
|
|
if sub_count < limit and sub_count > nearest:
|
|
nearest = sub_count
|
|
|
|
if sub_count == 1999998:
|
|
return rect.cols * rect.rows
|
|
elif sub_count < limit:
|
|
canditate_rects.append(Rect(rect.cols + 0, rect.rows + 1))
|
|
else:
|
|
canditate_rects.append(Rect(rect.cols + 1, 1))
|
|
|
|
|
|
if __name__ == "__main__":
|
|
s = euler_085()
|
|
print("e085.py: " + str(s))
|
|
assert(s == 2772)
|
|
|