In [1]:
TEST_INPUT_1 = """3 3
1 9 6
2 8 5
3 7 4
4"""
In [2]:
TEST_INPUT_2 ="""7 7
38 33 11 48 19 45 22
47 30 24 15 46 28 3
14 13 2 34 8 21 17
10 9 5 16 27 36 39
18 32 20 1 35 49 12
43 29 4 41 26 31 37
25 6 23 44 7 42 40
35"""
In [3]:
TEST_INPUT_3 = """7 7
15 16 46 1 38 43 44
25 10 7 6 34 42 14
8 19 9 21 13 23 22
32 11 29 36 3 5 47
31 33 45 24 12 18 28
40 41 20 26 39 48 2
49 35 27 4 37 30 17
26"""
In [4]:
import numpy as np
from IPython.display import clear_output
import sys
from time import sleep
In [5]:
START_FILL = 1
FILL_PER_TIME = 1 # Liters
FILL_DEPTH_OFFSET = 1
In [6]:
OFFSETS = np.array([np.array([0, 1]),
np.array([0, -1]),
np.array([-1, 0]),
np.array([1, 0])])
In [7]:
def parse_input(input_string):
_, *data, target = input_string.split("\n")
target = int(target)
grid = np.array([list(map(int, line.split(' '))) for line in data], dtype=int)
multiplier = np.multiply(*grid.shape) * 10
# grid *= multiplier
return grid, target, FILL_PER_TIME * multiplier
In [8]:
def get_target_location(grid, target):
return tuple(np.argwhere(grid == target)[0])
In [9]:
def clear_then_print(item):
clear_output(wait=True)
print(item)
sys.stdout.flush()
In [10]:
def recurse_find_low_point(grid, current_index, current_low_value=None, traversed_locations=tuple()):
if not current_low_value:
current_low_value = grid[current_index]
for (x,y) in map(tuple, OFFSETS + current_index):
if x >= 0 and y >= 0 and x < grid.shape[0] and y < grid.shape[1] and (x,y) not in traversed_locations:
potential_location = (x,y)
traversed_locations = traversed_locations + (potential_location,)
potential_fill_value = grid[potential_location]
if potential_fill_value < current_low_value:
current_index = recurse_find_low_point(grid,
potential_location,
potential_fill_value,
traversed_locations)
return current_index
In [11]:
def recurse_find_low_points(grid,
current_index,
current_low_value=None,
traversed_locations=tuple(),
low_indices=set()):
#print(grid)
#print(current_index)
#print(current_low_value)
#print(traversed_locations)
#print(low_indices)
#print()
if not current_low_value:
current_low_value = grid[current_index]
low_indices = {current_index}
for (x,y) in map(tuple, OFFSETS + current_index):
if x >= 0 and y >= 0 and x < grid.shape[0] and y < grid.shape[1] and (x,y) not in traversed_locations:
potential_location = tuple([x,y])
traversed_locations = traversed_locations + (potential_location,)
potential_fill_value = grid[potential_location]
if potential_fill_value < current_low_value:
low_indices = {potential_location}
current_low_value, low_indices = recurse_find_low_points(grid,
potential_location,
potential_fill_value,
traversed_locations,
low_indices)
elif potential_fill_value == current_low_value:
low_indices |= {potential_location}
current_low_value, low_indices = recurse_find_low_points(grid,
potential_location,
potential_fill_value,
traversed_locations,
low_indices)
return current_low_value, low_indices
In [12]:
def find_lowest_neighbor(grid, low_indices):
neighbor_indices = set()
for index in low_indices:
for offset in OFFSETS:
neighbor = tuple(index + offset)
if neighbor not in low_indices:
x, y = neighbor
if x >= 0 and y >= 0 and x < grid.shape[0] and y < grid.shape[1]:
neighbor_indices.add((x,y))
return min(grid[index] for index in neighbor_indices)
In [13]:
def fill(input_string):
grid, target, fill_per_step = parse_input(input_string)
fill_location = get_target_location(grid, START_FILL*fill_per_step)
target_index = get_target_location(grid, target*fill_per_step)
initial_target_depth = grid[target_index]
square_to_fill = recurse_find_low_point(grid, fill_location)
finished = False
iterations = 0
while not finished:
iterations += 1
for _ in range(fill_per_step):
if grid[target_index] >= initial_target_depth + (FILL_DEPTH_OFFSET * fill_per_step):
finished = True
break
grid[square_to_fill] += 1
square_to_fill = recurse_find_low_point(grid, fill_location)
clear_then_print(grid/fill_per_step)
print(iterations)
In [14]:
def fill_many(input_string):
grid, target, _ = parse_input(input_string)
fill_location = get_target_location(grid, START_FILL)
target_index = get_target_location(grid, target)
initial_target_depth = grid[target_index]
finished = False
iterations = 0
total_fill=0
while not finished:
iterations += 1
low_value, low_indices = recurse_find_low_points(grid, fill_location)
#clear_then_print([low_value, low_indices])
lowest_neighbor = find_lowest_neighbor(grid, low_indices)
#print(lowest_neighbor)
fill_amount_per_square = lowest_neighbor - low_value
#print(fill_amount_per_square)
#print(grid)
for square in low_indices:
grid[square] += fill_amount_per_square
total_fill += fill_amount_per_square
if grid[target_index] >= initial_target_depth + FILL_DEPTH_OFFSET:
finished = True
break
clear_then_print(grid)
sleep(0.25)
print(total_fill)
#print(iterations)
In [15]:
float_formatter = lambda x: "{:>5.2f}".format(x)
np.set_printoptions(formatter={'float_kind':float_formatter})
In [17]:
fill_many(TEST_INPUT_1)
In [18]:
fill_many(TEST_INPUT_2)
In [19]:
fill_many(TEST_INPUT_3)
In [ ]: