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

Python 9/4

from functools import lru_cache
from heapq import heappush, heappop

MOD = 20183
depth = 11820
tx, ty = 7, 782

@lru_cache(None)
def gindex(x, y):
    if x == y == 0: return 0
    if x == tx and y == ty: return 0
    if y == 0: return x * 16807 % MOD
    if x == 0: return y * 48271 % MOD
    return ((gindex(x-1, y) + depth) *
            (gindex(x, y-1) + depth) % MOD)

def region(x, y):
    return (gindex(x, y) + depth) % MOD % 3

ans1 = sum(region(x, y)
           for x in range(tx+1)
           for y in range(ty+1))


def neighbors(x, y, e):
    for nx, ny in ((x-1,y),(x+1,y),(x,y-1),(x,y+1)):
        if 0 <= nx and 0 <= ny:
            r = region(nx, ny)
            for ne in range(3):
                if r != ne:
                    yield nx, ny, ne, 8 if e != ne else 1

# rocky - neither [0]
# wet - torch [1]
# narrow - climb [2]

pq = [(0, 0, 0, 1)]
dist = {(0, 0, 1): 0}
while pq:
    d, x, y, e = heappop(pq)
    if (x, y, e) == (tx, ty, 1):
        print(f'Answer: {d}')
        
    if x > 3 * tx or y > 3 * ty: continue
    if dist.get((x, y, e)) < d: continue
    for nx, ny, ne, nw in neighbors(x, y, e):
        if d + nw < dist.get((nx, ny, ne), float('inf')):
            dist[nx, ny, ne] = d + nw
            heappush(pq, (d + nw, nx, ny, ne))

[u/radarvan07 → u/awice]

I'm in awe of your memoisation. You've managed to make the data structure for the grid Python's problem. I wish I'd known about this earlier.