58 lines
1.2 KiB
Python
58 lines
1.2 KiB
Python
|
|
|
|
def tiles(size):
|
|
""" Returns the number of tiles for a square of the given size. """
|
|
return size * 4 - 4
|
|
|
|
|
|
def tiles_for_outer(size):
|
|
""" Returns the number of tiles for all possible laminae given the size of
|
|
the outermost ring. """
|
|
|
|
n_outer = tiles(size)
|
|
r = [n_outer]
|
|
for ni in range(size - 2, 2, -2):
|
|
n_outer += tiles(ni)
|
|
r.append(n_outer)
|
|
return r
|
|
|
|
|
|
def count_tiles(size, n_max):
|
|
|
|
""" Count how many possible laminae with a size smaller the `n_max` are
|
|
possible for the given outermost ring `size`. """
|
|
|
|
n_outer = tiles(size)
|
|
if n_outer > n_max:
|
|
return 0
|
|
|
|
count = 1
|
|
for ni in range(size - 2, 2, -2):
|
|
n_outer += tiles(ni)
|
|
if n_outer > n_max:
|
|
break
|
|
count += 1
|
|
return count
|
|
|
|
|
|
def euler_173():
|
|
assert tiles(3) == 8
|
|
assert tiles(4) == 12
|
|
assert tiles(6) == 20
|
|
assert tiles(9) == 32
|
|
|
|
count = 0
|
|
n_max = 10**6
|
|
edge_length = 3
|
|
for edge_length in range(3, n_max):
|
|
if tiles(edge_length) > n_max:
|
|
break
|
|
count += count_tiles(edge_length, n_max)
|
|
return count
|
|
|
|
|
|
if __name__ == "__main__":
|
|
solution = euler_173()
|
|
print("e173.py: " + str(solution))
|
|
assert solution == 1572729
|