43 lines
881 B
Python
43 lines
881 B
Python
from collections import defaultdict
|
|
|
|
|
|
def tiles(size):
|
|
""" Returns the number of tiles for a square of the given size. """
|
|
return size * 4 - 4
|
|
|
|
|
|
def tiles_for_outer(size, ts, limit):
|
|
""" Adds t to ts for given outer size as long as t is
|
|
smaller than the limit. """
|
|
t = tiles(size)
|
|
if t > limit:
|
|
return
|
|
ts[t] += 1
|
|
for ni in range(size - 2, 2, -2):
|
|
t += tiles(ni)
|
|
if t > limit:
|
|
break
|
|
ts[t] += 1
|
|
|
|
|
|
def euler_173():
|
|
ts = defaultdict(int)
|
|
limit = 1_000_000
|
|
|
|
for outer_size in range(3, limit // 4):
|
|
tiles_for_outer(outer_size, ts, limit)
|
|
|
|
c = 0
|
|
for n in range(1, 11):
|
|
for v in ts.values():
|
|
if v == n:
|
|
c += 1
|
|
|
|
return c
|
|
|
|
|
|
if __name__ == "__main__":
|
|
solution = euler_173()
|
|
print("e173.py: " + str(solution))
|
|
assert solution == 209566
|