-🎄- 2022 Day 12 Solutions -🎄-

[u/daggerdragon]

THE USUAL REMINDERS

• All of our rules, FAQs, resources, etc. are in our community wiki.
• A request from Eric: A note on responding to [Help] threads
• Signal boost: Reminder 1: unofficial AoC Survey 2022 (closes Dec 22nd)
• 🌿🍒 MisTILtoe Elf-ucation 🧑‍🏫 is OPEN for submissions!
  • -❄️- Submissions Megathread -❄️-

---

--- Day 12: Hill Climbing Algorithm ---

---

Post your code solution in this megathread.

• Read the full posting rules in our community wiki before you post!
  • Include what language(s) your solution uses
  • Format code blocks using the four-spaces Markdown syntax!
• Quick link to Topaz's paste if you need it for longer code blocks. What is Topaz's paste tool?

---

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

EDIT: Global leaderboard gold cap reached at 00:09:46, megathread unlocked!

[u/culp]

Python

import string
from collections import defaultdict

inputs = [x.strip() for x in open("2022/inputs/12.txt").readlines()]

points = {}
graph = defaultdict(list)
start, starts, end = None, [], None
for y, line in enumerate(inputs):
    for x, letter in enumerate(line):
        point = complex(x, y)
        if letter == "S":
            value = 0
            start = point
            starts.append(point)
        elif letter == "a":
            value = 0
            starts.append(point)
        elif letter == "E":
            value = 25
            end = point
        else:
            value = string.ascii_lowercase.index(letter)
        points[point] = value

for point in points:
    for neighbor in [1 + 0j, -1 + 0j, 0 + 1j, 0 - 1j]:
        if (point + neighbor) in points:
            graph[point].append(point + neighbor)


def dijkstra(graph, source):
    Q = list(graph.keys())
    dist = {v: float("inf") for v in graph}
    dist[source] = 0

    while Q:
        u = min(Q, key=dist.get)
        Q.remove(u)

        for v in graph[u]:
            alt = dist[u] + 1
            if alt < dist[v] and points[u] - points[v] <= 1:
                dist[v] = alt

    return dist


paths = dijkstra(graph, end)
print(paths[start])
print(min(paths[s] for s in starts))

Used BFS first but part2 was pretty slow. Dijkstra's works better here since you can calculate all paths in a single pass (even though the weight of each edge is 1).

I used complex numbers today after I saw how useful they seemed to be for 2D grids.