Day 15

aoc21_day15_broken.py

#!/usr/bin/env python3
import functools

import numpy as np

USE_EXAMPLE = False

example_data = '''\
1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581'''


if not USE_EXAMPLE:
    with open('input.txt') as f:
        d = f.read()
else:
    d = example_data

orig_cave_map = np.array([[int(el) for el in row] for row in d.strip().splitlines()], dtype=np.int64)

assert np.equal(*orig_cave_map.shape)  # N_COLS == N_ROWS


# The problem consists in finding the shortest path in weighted Manhattan distance given edge weights.
#
# For each step, there are two choices: down or right (correct??).
# Max matrix size is 500 x 500 -> max recursion depth ~500 (no problem in python by default)
def find_shortest_path(cave_map):
    BORDER_POS = cave_map.shape[0] - 1

    @functools.cache
    def rec_find(row, col):
        nonlocal cave_map

        # Base case.
        if row == BORDER_POS:
            return np.sum(cave_map[row, col:]), ''.join(map(str, cave_map[row, col:]))
        if col == BORDER_POS:
            return np.sum(cave_map[row:, col]), ''.join(map(str, cave_map[row:, col]))

        # Recursive case.
        cur_val = cave_map[row, col]

        option_1, p1 = rec_find(row + 1, col)
        option_2, p2 = rec_find(row, col + 1)

        if option_1 <= option_2:
            path = str(cur_val) + p1
        else:
            path = str(cur_val) + p2

        return cur_val + min(option_1, option_2), path

    rec_find.cache_clear()  # Just in case...
    # print(rec_find.cache_info())
    r, path = rec_find(0, 0)
    r -= cave_map[0, 0]  # Remove first position.
    print(path)
    # print(rec_find.cache_info())
    return r


def expand_map_5(orig_map: np.ndarray):
    N_LINES = orig_map.shape[0]
    new_map = np.zeros(np.array(orig_map.shape) * 5, dtype=np.int64)

    shifted_maps = [None] * 9
    for i in range(9):
        # stupid 1-based indices...
        shifted_maps[i] = (orig_map - 1 + i) % 9 + 1

    i_r_start = 0
    for t_row in range(5):
        i_r_end = i_r_start + N_LINES
        i_c_start = 0
        for t_col in range(5):
            i_c_end = i_c_start + N_LINES

            # Should be faster than this.
            # new_map[t_row * N_LINES:(t_row + 1) * N_LINES,
            #         t_col * N_LINES:(t_col + 1) * N_LINES] = shifted_maps[t_row + t_col]
            new_map[i_r_start:i_r_end,
                    i_c_start:i_c_end] = shifted_maps[t_row + t_col]

            i_c_start = i_c_end
        i_r_start = i_r_end
    # <for/>
    return new_map


def print_map(cmap: np.ndarray):
    s = ''
    for irow, row in enumerate(cmap):
        # if irow % N_LINES == 0:
        #     s += '\n'
        for el in row:
            s += str(el)
        s += '\n'
    print(s)


#
res1 = find_shortest_path(orig_cave_map)
print(f'{res1=}')

#
new_map = expand_map_5(orig_cave_map)
# print_map(new_map)

res2 = find_shortest_path(new_map)
# 2967 -> too high??
print(f'{res2=}')