aoc-2018-python

Advent of Code 2018 Solutions in Python
git clone https://git.sinitax.com/sinitax/aoc-2018-python
Log | Files | Refs | README | sfeed.txt

solve.py (2837B)

      1import sys
      2sys.path.append("../common")
      3import aoc
      4import networkx
      5
      6adjacent = [[-1, 0], [0, -1], [1, 0], [0, 1]]
      7
      8# create symbol definitions
      9symbols = [".", "=", "|"]
     10rocky, wet, narrow = 0, 1, 2
     11torch, gear, neither = 0, 1, 2
     12
     13tooloptions = dict()
     14tooloptions[rocky] = (torch, gear)
     15tooloptions[wet] = (gear, neither)
     16tooloptions[narrow] = (torch, neither)
     17
     18# parse input file
     19def parse_input(si):
     20    s = si.split("\n")
     21    depth = int(s[0].split(": ")[1])
     22    target = [int(v) for v in s[1].split(": ")[1].split(",")]
     23    return depth, target
     24
     25# get erosion level from geological index
     26def get_erosion_level(n):
     27    return (n + depth) % 20183
     28
     29# generate map of erosion types
     30def gen_map():
     31    grid = [[0 for x in range(mrange[0])] for y in range(mrange[1])]
     32
     33    # generate values on x side
     34    grid[0] = [get_erosion_level(x * 16807) for x in range(mrange[0])] 
     35
     36    # generate values on y side
     37    for y in range(mrange[1]):
     38        grid[y][0] = get_erosion_level(y * 48271)
     39
     40    # fill in other positions
     41    for y in range(1, mrange[1]):
     42        for x in range(1, mrange[0]):
     43            grid[y][x] = get_erosion_level(grid[y-1][x] * grid[y][x-1])
     44
     45    # mod 3 for env type
     46    grid = [[grid[y][x] % 3 for x in range(mrange[0])] for y in range(mrange[1])]
     47
     48    # start position is rocky
     49    grid[target[1]][target[0]] = 0
     50
     51    return grid
     52
     53# define constants from input file
     54depth, target = parse_input(aoc.data)
     55mrange = (target[0] + 100, target[1] + 100) # 100 block padding for potential hook-paths
     56
     57vmap = gen_map()
     58
     59def risk_level(width, height):
     60    risk = 0
     61    for y in range(height + 1):
     62        for x in range(width + 1):
     63            risk += vmap[y][x]
     64    return risk
     65
     66def adj(p):
     67    return [[p[0] + di[0], p[1] + di[1]] for di in adjacent]
     68
     69def dijkstra():
     70    graph = networkx.Graph()
     71    for y in range(mrange[1]):
     72        for x in range(mrange[0]):
     73            tools = tooloptions[vmap[y][x]]
     74            # always takes 7 minutes to switch, 2 z-options for each tool
     75            graph.add_edge((x, y, tools[0]), (x, y, tools[1]), weight = 7)
     76            for (nx, ny) in adj((x, y)):
     77                if 0 <= nx < mrange[0] and 0 <= ny < mrange[1]:
     78                    ntools = tooloptions[vmap[ny][nx]]
     79                    # if tool is usable in both environments
     80                    for tool in [t for t in tools if t in ntools]:
     81                         # then it only takes 1 minute
     82                        graph.add_edge((x, y, tool), (nx, ny, tool), weight = 1)
     83
     84    return networkx.dijkstra_path_length(graph,
     85        (0, 0, torch), (target[0], target[1], torch))
     86
     87def solve1(args):
     88    return risk_level(target[0], target[1])
     89
     90def solve2(args):
     91    return dijkstra()
     92
     93aoc.run(solve1, solve2, sols=[11359, 976])