#!/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])