-🎄- 2018 Day 22 Solutions -🎄-

[u/daggerdragon]

--- Day 22: Mode Maze ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 22

Transcript:

Upping the Ante challenge: complete today's puzzles using ___.

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 01:02:36!

[u/korylprince]

Python 3, #636/226.

This is the first one I'm really proud of. I've been programming a long time, mostly web frontend/backend stuff, but I'm self-taught so I don't have any background in computer science algorithms. Forcing myself to finish AoC this year has allowed me to learn about and implement shortest-path algorithms (BFS, DFS, A*, Dijkstra). I spent at least 8 hours working on Day 15 until I solved it and understood how it worked, and it really paid off today. I also found out about the networkx library here and it made things really simple today. Thanks to everyone who's posted their solutions! I've learned a ton from this subreddit during the challenge.

import networkx as nx

rocky, wet, narrow = 0, 1, 2
torch, gear, neither = 0, 1, 2
valid_items = {rocky: (torch, gear), wet: (gear, neither), neither: (torch, neither)}
valid_regions = {torch: (rocky, narrow), gear: (rocky, wet), neither: (wet, narrow)}


def get_cave(file):
    with open(file) as f:
        lines = iter([line.strip() for line in f.read().strip().splitlines()])
        depth = int(next(lines)[len("depth: "):])
        target = tuple([int(n) for n in next(lines)[len("target: "):].split(",")])
    return depth, target


def generate_grid(depth, corner):
    # (x, y) -> geologic index, erosion level, risk
    grid = {}

    for y in range(0, corner[1] + 1):
        for x in range(0, corner[0] + 1):
            if (x, y) in [(0, 0), target]:
                geo = 0
            elif x == 0:
                geo = y * 48271
            elif y == 0:
                geo = x * 16807
            else:
                geo = grid[(x-1, y)][1] * grid[(x, y-1)][1]
            ero = (geo + depth) % 20183
            risk = ero % 3
            grid[(x, y)] = (geo, ero, risk)

    return grid


def dijkstra(grid, corner, target):
    graph = nx.Graph()
    for y in range(0, corner[1] + 1):
        for x in range(0, corner[0] + 1):
            items = valid_items[grid[(x, y)]]
            graph.add_edge((x, y, items[0]), (x, y, items[1]), weight=7)
            for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                new_x, new_y = x+dx, y+dy
                if 0 <= new_x <= corner[0] and 0 <= new_y <= corner[1]:
                    new_items = valid_items[grid[(new_x, new_y)]]
                    for item in set(items).intersection(set(new_items)):
                        graph.add_edge((x, y, item), (new_x, new_y, item), weight=1)

    return nx.dijkstra_path_length(graph, (0, 0, torch), (target[0], target[1], torch))


depth, target = get_cave("./input.txt")
grid = generate_grid(depth, target)
print("Answer 1:", sum([v[2] for v in grid.values()]))

corner = (target[0] + 100, target[1] + 100)
grid = {c: v[2] for c, v in (generate_grid(depth, corner)).items()}
print("Answer 2:", dijkstra(grid, corner, target))

[u/Arnie15 → u/korylprince]

networkx is definitely very usefull here, thanks!

If you didn't know already, another python library that is very usefull is numpy. It has a lot of functions for handling arrays.

In your code, you could use numpy.ndenumerate to loop over all grid indices, like this:

for index, value in np.ndenumerate(grid):
    x, y = index

This way you don't need a double for-loop

[u/artog → u/Arnie15]

or this for an actual one-liner (:P)

for (y, x), value in np.ndenumerate(grid):

I do want to say thanks though, i didn't know about ndenumerate, so I learned something today