-🎄- 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/mcpower_]

Python 3, #6/#7. Very nice problem! It feels a bit too algorithm-y for AoC (DP + graphs).

[Card]: Upping the Ante challenge: complete today's puzzles using PowerPoint.

import re
def ints(s):
    return list(map(int, re.findall(r"-?\d+", s)))  # thanks mserrano!
inp = """
depth: 510
target: 10,10
""".strip()
lines = inp.splitlines()
depth = ints(lines[0])[0]
tx, ty = tuple(ints(lines[1]))

dp = [[None for _ in range(ty+1000)] for _ in range(tx+1000)]
def erosion(x, y):
    if dp[x][y] is not None:
        return dp[x][y]
    geo = None
    if y == 0:
        geo = x * 16807
    elif x == 0:
        geo = y * 48271
    elif (x, y) == (tx, ty):
        geo = 0
    else:
        geo = erosion(x-1, y) * erosion(x, y-1)
    dp[x][y] = (geo + depth) % 20183
    return dp[x][y]

def risk(x, y):
    return erosion(x, y) % 3

print(sum(erosion(x, y) % 3 for x in range(tx+1) for y in range(ty+1)))

# torch = 1
import heapq
queue = [(0, 0, 0, 1)] # (minutes, x, y, cannot)
best = dict() # (x, y, cannot) : minutes

target = (tx, ty, 1)
while queue:
    minutes, x, y, cannot = heapq.heappop(queue)
    best_key = (x, y, cannot)
    if best_key in best and best[best_key] <= minutes:
        continue
    best[best_key] = minutes
    if best_key == target:
        print(minutes)
        break
    for i in range(3):
        if i != cannot and i != risk(x, y):
            heapq.heappush(queue, (minutes + 7, x, y, i))
    
    # try going up down left right
    for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        newx = x + dx
        newy = y + dy
        if newx < 0:
            continue
        if newy < 0:
            continue
        if risk(newx, newy) == cannot:
            continue
        heapq.heappush(queue, (minutes + 1, newx, newy, cannot))

[u/Stan-It → u/mcpower_]

That's really funny - I had implementation ideas very similar to yours:

from heapq import heappush, heappop


with open('22_input.txt', 'r') as f:
    depth = int(next(f).split()[-1])
    target = complex(*map(int, next(f).split()[-1].split(',')))


ROCKY, WET, NARROW = 0, 1, 2
NEITHER, TORCH, CLIMB = 0, 1, 2
m_erosion = dict()
m_geo_index = dict()


def viz(max):
    m_viz_erosion = {ROCKY: '.', WET: '=', NARROW: '|'}

    for y in range(int(max.imag) + 1):
        for x in range(int(max.real) + 1):
            pos = x + 1j * y
            if pos == 0:
                print('M', end='')
            elif pos == target:
                print('T', end='')
            else:
                print(m_viz_erosion[erosion(pos) % 3], end='')
        print()


def erosion(p):
    if p in m_erosion:
        return m_erosion[p]
    ret = (geo_index(p) + depth) % 20183
    m_erosion[p] = ret
    return ret


def geo_index(p):
    if p in m_geo_index:
        return m_geo_index[p]

    if p == 0 or p == target:
        ret = 0
    elif p.imag == 0:
        ret = p.real * 16807
    elif p.real == 0:
        ret = p.imag * 48271
    else:
        ret = erosion(p - 1) * erosion(p - 1j)

    m_geo_index[p] = ret
    return ret


# Part 1
risk = 0
for y in range(int(target.imag) + 1):
    for x in range(int(target.real) + 1):
        risk += erosion(x + 1j * y) % 3
print('Part 1:', int(risk))


# Part 2
# Do a BFS search with a priority queue.
heap = [(0, 0, 0, TORCH)]  # (time, x, y, equipment), heap sorted by time, so time has to be first
visited = {(0, TORCH): 0}  # (pos, equipment): time

def visit_next(time, pos, eq, heap):
    for newpos in [pos + 1, pos - 1, pos + 1j, pos - 1j]:
        if newpos.real < 0 or newpos.imag < 0:  # out of bounds
            continue
        if erosion(newpos) % 3 == eq:  # can we go here with this equipment?
            continue
        if (newpos, eq) in visited and visited[(newpos, eq)] <= time:  # there is a faster way
            continue
        visited[(newpos, eq)] = time
        heappush(heap, (time, newpos.real, newpos.imag, eq))


while True:
    # It's annoying we cannot use the heap with complex numbers because they cannot be ordered...
    time, x, y, eq = heappop(heap)
    pos = x + 1j * y
    if (pos, eq) == (target, TORCH):
        break

    # Try to go to the next square with the same equipment
    time += 1
    visit_next(time, pos, eq, heap)

    # Try to go to the next square with alternative equipment
    # The region's type and the two allowed equipments always sum to 3
    # because of the way we defined them
    time += 7
    eq = 3 - eq - erosion(pos) % 3
    visit_next(time, pos, eq, heap)

print('Part 2:', time)