55 lines
1.2 KiB
Python
55 lines
1.2 KiB
Python
#!/usr/bin/env python
|
|
|
|
|
|
def get_neighour(heightmap, x, y, deltax, deltay):
|
|
if x+deltax < 0:
|
|
return 10
|
|
if y+deltay < 0:
|
|
return 10
|
|
try:
|
|
return heightmap[y+deltay][x+deltax]
|
|
except IndexError:
|
|
return 10
|
|
|
|
def check_low_point(heightmap, x, y):
|
|
xy = heightmap[y][x]
|
|
for n in ((1,0),(-1,0),(0,1),(0,-1)):
|
|
if get_neighour(heightmap,x, y, n[0], n[1]) <= xy:
|
|
return False
|
|
return True
|
|
|
|
def compute_basin(heightmap, x, y):
|
|
result = 0
|
|
seen = [(x,y)]
|
|
queue = [(x,y)]
|
|
while len(queue):
|
|
cur = queue.pop(0)
|
|
v = get_neighour(heightmap, cur[0], cur[1], 0, 0)
|
|
if v >= 9:
|
|
continue
|
|
result += 1
|
|
for n in ((1,0),(-1,0),(0,1),(0,-1)):
|
|
i = (cur[0]+n[0], cur[1]+n[1])
|
|
if i in seen:
|
|
continue
|
|
seen.append(i)
|
|
queue.append(i)
|
|
return result
|
|
|
|
heightmap = []
|
|
|
|
with open("input01.txt","r") as f:
|
|
for line in f:
|
|
heightmap.append([int(x) for x in list(line.strip())])
|
|
|
|
result = []
|
|
for y in range(len(heightmap)):
|
|
for x in range(len(heightmap[y])):
|
|
low_point = check_low_point(heightmap, x,y)
|
|
if low_point:
|
|
#print("found basin on %d:%d" % (x,y))
|
|
result.append(compute_basin(heightmap, x, y))
|
|
|
|
result.sort(reverse=True)
|
|
print(result[0]*result[1]*result[2])
|