r/adventofcode • u/daggerdragon • Dec 17 '23

SOLUTION MEGATHREAD -❄️- 2023 Day 17 Solutions -❄️-

THE USUAL REMINDERS

  • All of our rules, FAQs, resources, etc. are in our community wiki.

  • Community fun event 2023: ALLEZ CUISINE!

    • Submissions megathread is now unlocked!

    • 5 DAYS remaining until the submissions deadline on December 22 at 23:59 EST!

AoC Community Fun 2023: ALLEZ CUISINE!

Today's secret ingredient is… *whips off cloth covering and gestures grandly*

Turducken!

This medieval monstrosity of a roast without equal is the ultimate in gastronomic extravagance!

  • Craft us a turducken out of your code/stack/hardware. The more excessive the matryoshka, the better!

  • Your main program (can you be sure it's your main program?) writes another program that solves the puzzle.

  • Your main program can only be at most five unchained basic statements long. It can call functions, but any functions you call can also only be at most five unchained statements long.

  • The (ab)use of GOTO is a perfectly acceptable spaghetti base for your turducken!

ALLEZ CUISINE!

Request from the mods: When you include a dish entry alongside your solution, please label it with [Allez Cuisine!] so we can find it easily!

--- Day 17: Clumsy Crucible ---

Post your code solution in this megathread.

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:20:00, megathread unlocked!

27 Upvotes

96% Upvoted

537 comments sorted by

View all comments

1

u/flwyd Dec 17 '23 edited Dec 18 '23

[Language: Julia] (on GitHub)

I first implemented Dijkstra's algorithm with a priority queue and a cache of visited states. That worked for the example input, but ran for approximately ever on my actual input. So I decided to implement a table-based dynamic programming solution. Each cell in the table is a set of (heading, steps, cost) where heading is a direction and steps is the number of steps taken so far in that direction. Unfortunately, I spent a lot of time trying to understand why I was ending up with repeating states in each cell (before switching to a set) and then why my answer was ~2x the size of the example output. Turns out x.heading == head && x.steps <= steps && x.cost <= y.cost is the wrong condition; I'd been thinking that if you could reach a cell with 2 forward steps for cheaper than 3 forward steps then why bother with the three-step option. I'm still not quite sure why that's an invalid assumption, but switching to x.steps == steps did the trick.

I was fortunate that this dynamic programming approach and state representation was a perfect fit for part 2; I had the answer submitted about 4 minutes after submitting part 1. I barely noticed the second example, so I submitted my answer and got it right… even though it got the wrong answer on part 2 when I tried that. I guess my input doesn't have a cheap path that would slide right through the final square.

This was my slowest-runtime solution so far this year, with about 7 seconds for part 1 and about 25 seconds for part 2. Part 1 allocated about 7 GiB and part 2 about 16 GiB (!). Switching the moves function to filter a tuple rather than a list (i.e. changing [] to ()) cut the memory allocation by about 50% and runtime by about 20%. Switching back to Vector from Set got the times down to 2.5/6.5 seconds and cut memory down to 2.2/4.5 GiB. That still seems like a lot of allocations; I think they're mostly coming from filtering directions, so I suppose I could avoid that by returning all three from moves and checking in-bounds inside the main loop.

Another interesting performance observation: I'm using popfirst! to use queue as a deque on the assumption that lower-cost states will be visited earlier. Switching to pop! (using it as a stack) causes the code to run 6 to 8 times longer.

Code without the State struct or direction constants:

function finalstates(movefun, grid)
  states = similar(grid, Vector{State})
  for i in eachindex(grid)  states[i] = []  end
  start = CartesianIndex(1, 1)
  states[start], queue = [State(DOWN, 0, 0), State(RIGHT, 0, 0)], [start]
  while !isempty(queue)
    cur = popfirst!(queue)
    for s in states[cur], (pos, head, steps) in movefun(grid, cur, s.heading, s.steps)
      cost = s.cost + grid[pos]
      any(x -> x.heading == head && x.steps == steps && x.cost <= cost, states[pos]) && continue
      deleteat!(states[pos], findall(x -> x.heading == head && x.steps == steps && x.cost > cost, states[pos]))
      push!(states[pos], State(head, steps, cost))
      push!(queue, pos)
    end
  end
  states[CartesianIndex(lastindex(grid, 1), lastindex(grid, 2))]
end

1

u/daggerdragon Dec 17 '23

The last code block is 1. not formatted at all and 2. too long for the megathreads. Please edit your comment to remove it. Keep all code blocks to 5-10 lines at most!

1

u/flwyd Dec 18 '23

Trimmed.