Solution for Advent of Code 2018 - Day 22: Mode Maze

Link to the puzzle text

Part 1

In this puzzle, we have a way of creating a 2d grid of cells describing a cavern. Depending on a input value (the current depth) and the coordinates a cells belongs to one of 3 differenty types of terrain. The borders of the caverns, where either x or y are 0, the terrain type depends directly on the coordinate and depth values. For a special target show, the terrain type is a fixed value. For other cells, the terrain depends on the cells directly left and above the current cell. Finally the values are taken modulo 3 for the terrain type between 0 and 2. We should get the terrain type of all cells starting from (0,0) to a given target cell and sum up the values of the terrain types.

We create a 2d numpy array for the terrain type. Going line by line starting a the top, we use the given method for determining the terrain type:

def calc_geo_types(target_cell):
    erosion_level = np.zeros((target_cell[0] + 1, target_cell[1] + 1))
    for y in range(len(erosion_level)):
        for x in range(len(erosion_level[0])):
            if (x, y) == target_cell:
                cell_geo_index = 0
            elif y == 0:
                cell_geo_index = x * 16807
            elif x == 0:
                cell_geo_index = y * 48271
            else:
                cell_geo_index = erosion_level[y - 1, x] * erosion_level[y, x - 1]
            erosion_level[y, x] = (cell_geo_index + depth) % 20183
    geo_type = erosion_level % 3
    return geo_type 

Summing up the grid returns the answer. 

Part 2

In part 2, we should use the determined 2 grid as a map for determining the fastest path from (0,0) to the target cell. The length is calculated from both movement costs and equipement change costs. Movements between cells is only possible for certain equiped items, so sometimes changing equipments is necessary for a faster total time. There are three different types of equipment, each allowing 2 terrains each and disabling movement to the third terrain type.

We use a A* search for finding the quickest path through the grid. In addition to the current coordinates, we track the current equipment. When determining the next possible movements, we filter the cells where movement is currently forbidden due to the current equipment. We also add the action of staying at the current position and changing equipment. Whenever we reach the target cell equipped with the target equipment, we can stop the search and return the answer.

Originally we only searched for the quickest path in the grid created in part 1, but some quicker paths may lead outside. We therefore expanded the grid from part 1 whenever we move to the right or lower border of the grid.

Link to my solutions