🍵 - 2023 DAY 17 SOLUTIONS -🍵

Day 17: Clumsy Crucible

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

cacheson,
cacheson avatar

Nim

Another tough one. Judging by the relative lack of comments here, I wasn't the only one that had trouble. For me this one was less frustrating and more interesting than day 12, though.

I solved part 1 by doing a recursive depth-first search, biasing towards a zigzag path directly to the goal in order to establish a baseline path cost. Path branches that got more expensive than the current best path terminated early. I also stored direction, speed, and heat loss data for each tile entered. Any path branch that entered a tile in the same direction and at the same (or greater) speed as a previous path was terminated, unless it had a lower temperature loss.

This ran pretty slowly, taking around an hour to finish. I took a break and just let it run. Once it completed, it had gotten pretty late, so I did a quick naive modification for part 2 to account for the new movement restrictions, and let that run overnight. The next day it was still running, so I spent some time trying to think of a way to speed it up. Didn't really get anywhere on my own, so I started reading up on A* to refresh my memory on how it worked.

The solution that I arrived at for the rewrite was to use Dijkstra's algorithm to pre-compute a map of what the minimum possible costs would be from each tile to the goal, if adjacent tiles could be moved to without restriction. I then used that as the heuristic for A*. While I was writing this, the original part 2 program did finish and gave the correct answer. Since I was already this far in though, I figured I'd finish the rewrite anyway.

The new program got the wrong answer, but did so very quickly. It turned out that I had a bug in my Dijkstra map. I was sorting the node queue by the currently computed cost to move from that node to the goal, when it instead should have been sorted by that plus the cost to enter that node from a neighbor. Since the node at the head of the queue is removed and marked as finalized on each iteration, some nodes were being finalized before their actual minimum costs were found.

When using the A* algorithm, you usually want your heuristic cost estimate to underestimate the actual cost to reach the goal from a given node. If it overestimates instead, the algorithm will overlook routes that are potentially more optimal than the computed route. This can be useful if you want to find a "good enough" route quickly, but in this case we need the actual best path.

cacheson,
cacheson avatar

The rest of the code:

Massahud,

Python github.com/massahud/…/day17.ipynb

LeixB,

Haskell


<span style="color:#323232;">import Data.Array.Unboxed
</span><span style="color:#323232;">import qualified Data.ByteString.Char8 as BS
</span><span style="color:#323232;">import Data.Char (digitToInt)
</span><span style="color:#323232;">import Data.Heap hiding (filter)
</span><span style="color:#323232;">import qualified Data.Heap as H
</span><span style="color:#323232;">import Relude
</span><span style="color:#323232;">
</span><span style="color:#323232;">type Pos = (Int, Int)
</span><span style="color:#323232;">
</span><span style="color:#323232;">type Grid = UArray Pos Int
</span><span style="color:#323232;">
</span><span style="color:#323232;">data Dir = U | D | L | R deriving (Eq, Ord, Show, Enum, Bounded, Ix)
</span><span style="color:#323232;">
</span><span style="color:#323232;">parse :: ByteString -> Maybe Grid
</span><span style="color:#323232;">parse input = do
</span><span style="color:#323232;">  let l = fmap (fmap digitToInt . BS.unpack) . BS.lines $ input
</span><span style="color:#323232;">      h = length l
</span><span style="color:#323232;">  w &lt;- fmap length . viaNonEmpty head $ l
</span><span style="color:#323232;">  pure . listArray ((0, 0), (w - 1, h - 1)) . concat $ l
</span><span style="color:#323232;">
</span><span style="color:#323232;">move :: Dir -> Pos -> Pos
</span><span style="color:#323232;">move U = first pred
</span><span style="color:#323232;">move D = first succ
</span><span style="color:#323232;">move L = second pred
</span><span style="color:#323232;">move R = second succ
</span><span style="color:#323232;">
</span><span style="color:#323232;">nextDir :: Dir -> [Dir]
</span><span style="color:#323232;">nextDir U = [L, R]
</span><span style="color:#323232;">nextDir D = [L, R]
</span><span style="color:#323232;">nextDir L = [U, D]
</span><span style="color:#323232;">nextDir R = [U, D]
</span><span style="color:#323232;">
</span><span style="color:#323232;">-- position, previous direction, accumulated loss
</span><span style="color:#323232;">type S = (Int, Pos, Dir)
</span><span style="color:#323232;">
</span><span style="color:#323232;">doMove :: Grid -> Dir -> S -> Maybe S
</span><span style="color:#323232;">doMove g d (c, p, _) = do
</span><span style="color:#323232;">  let p' = move d p
</span><span style="color:#323232;">  guard $ inRange (bounds g) p'
</span><span style="color:#323232;">  pure (c + g ! p', p', d)
</span><span style="color:#323232;">
</span><span style="color:#323232;">doMoveN :: Grid -> Dir -> Int -> S -> Maybe S
</span><span style="color:#323232;">doMoveN g d n = foldl' (>=>) pure . replicate n $ doMove g d
</span><span style="color:#323232;">
</span><span style="color:#323232;">doMoves :: Grid -> [Int] -> S -> Dir -> [S]
</span><span style="color:#323232;">doMoves g r s d = mapMaybe (flip (doMoveN g d) s) r
</span><span style="color:#323232;">
</span><span style="color:#323232;">allMoves :: Grid -> [Int] -> S -> [S]
</span><span style="color:#323232;">allMoves g r s@(_, _, prev) = nextDir prev >>= doMoves g r s
</span><span style="color:#323232;">
</span><span style="color:#323232;">solve' :: Grid -> [Int] -> UArray (Pos, Dir) Int -> Pos -> MinHeap S -> Maybe Int
</span><span style="color:#323232;">solve' g r distances target h = do
</span><span style="color:#323232;">  ((acc, pos, dir), h') &lt;- H.view h
</span><span style="color:#323232;">
</span><span style="color:#323232;">  if pos == target
</span><span style="color:#323232;">    then pure acc
</span><span style="color:#323232;">    else do
</span><span style="color:#323232;">      let moves = allMoves g r (acc, pos, dir)
</span><span style="color:#323232;">          moves' = filter ((acc, p, d) -> acc &lt; distances ! (p, d)) moves
</span><span style="color:#323232;">          distances' = distances // fmap ((acc, p, d) -> ((p, d), acc)) moves'
</span><span style="color:#323232;">          h'' = foldl' (flip H.insert) h' moves'
</span><span style="color:#323232;">      solve' g r distances' target h''
</span><span style="color:#323232;">
</span><span style="color:#323232;">solve :: Grid -> [Int] -> Maybe Int
</span><span style="color:#323232;">solve g r = solve' g r (emptyGrid ((lo, minBound), (hi, maxBound))) hi (H.singleton (0, (0, 0), U))
</span><span style="color:#323232;">  where
</span><span style="color:#323232;">    (lo, hi) = bounds g
</span><span style="color:#323232;">    emptyGrid = flip listArray (repeat maxBound)
</span><span style="color:#323232;">
</span><span style="color:#323232;">part1, part2 :: Grid -> Maybe Int
</span><span style="color:#323232;">part1 = (`solve` [1 .. 3])
</span><span style="color:#323232;">part2 = (`solve` [4 .. 10])
</span>
hades,

Python

Also on Github

749 line-seconds


<span style="font-weight:bold;color:#a71d5d;">import </span><span style="color:#323232;">collections
</span><span style="font-weight:bold;color:#a71d5d;">import </span><span style="color:#323232;">dataclasses
</span><span style="font-weight:bold;color:#a71d5d;">import </span><span style="color:#323232;">heapq
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">import </span><span style="color:#323232;">numpy </span><span style="font-weight:bold;color:#a71d5d;">as </span><span style="color:#323232;">np
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">from .</span><span style="color:#323232;">solver </span><span style="font-weight:bold;color:#a71d5d;">import </span><span style="color:#323232;">Solver
</span><span style="color:#323232;">
</span><span style="color:#323232;">
</span><span style="color:#323232;">@dataclasses.dataclass(order</span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#0086b3;">True</span><span style="color:#323232;">)
</span><span style="font-weight:bold;color:#a71d5d;">class </span><span style="color:#0086b3;">QueueEntry</span><span style="color:#323232;">:
</span><span style="color:#323232;">  price: </span><span style="color:#0086b3;">int
</span><span style="color:#323232;">  x: </span><span style="color:#0086b3;">int
</span><span style="color:#323232;">  y: </span><span style="color:#0086b3;">int
</span><span style="color:#323232;">  momentum_x: </span><span style="color:#0086b3;">int
</span><span style="color:#323232;">  momentum_y: </span><span style="color:#0086b3;">int
</span><span style="color:#323232;">  deleted: </span><span style="color:#0086b3;">bool
</span><span style="color:#323232;">
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">class </span><span style="color:#0086b3;">Day17</span><span style="color:#323232;">(</span><span style="color:#0086b3;">Solver</span><span style="color:#323232;">):
</span><span style="color:#323232;">  lines: </span><span style="color:#0086b3;">list</span><span style="color:#323232;">[</span><span style="color:#0086b3;">str</span><span style="color:#323232;">]
</span><span style="color:#323232;">  sx: </span><span style="color:#0086b3;">int
</span><span style="color:#323232;">  sy: </span><span style="color:#0086b3;">int
</span><span style="color:#323232;">  lower_bounds: np.ndarray
</span><span style="color:#323232;">
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#62a35c;">__init__</span><span style="color:#323232;">(self):
</span><span style="color:#323232;">    </span><span style="color:#62a35c;">super</span><span style="color:#323232;">().</span><span style="color:#62a35c;">__init__</span><span style="color:#323232;">(</span><span style="color:#0086b3;">17</span><span style="color:#323232;">)
</span><span style="color:#323232;">
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#323232;">presolve</span><span style="color:#323232;">(self, input: </span><span style="color:#0086b3;">str</span><span style="color:#323232;">):
</span><span style="color:#323232;">    self.lines </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#62a35c;">input</span><span style="color:#323232;">.splitlines()
</span><span style="color:#323232;">    self.sx </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#62a35c;">len</span><span style="color:#323232;">(self.lines[</span><span style="color:#0086b3;">0</span><span style="color:#323232;">])
</span><span style="color:#323232;">    self.sy </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#62a35c;">len</span><span style="color:#323232;">(self.lines)
</span><span style="color:#323232;">    start </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">(self.sx </span><span style="font-weight:bold;color:#a71d5d;">- </span><span style="color:#0086b3;">1</span><span style="color:#323232;">, self.sy </span><span style="font-weight:bold;color:#a71d5d;">- </span><span style="color:#0086b3;">1</span><span style="color:#323232;">)
</span><span style="color:#323232;">    self.lower_bounds </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">np.zeros((self.sx, self.sy)) </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#323232;">np.inf
</span><span style="color:#323232;">    self.lower_bounds[start] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">0
</span><span style="color:#323232;">    queue: </span><span style="color:#0086b3;">list</span><span style="color:#323232;">[QueueEntry] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">[QueueEntry(</span><span style="color:#0086b3;">0</span><span style="color:#323232;">, self.sx </span><span style="font-weight:bold;color:#a71d5d;">- </span><span style="color:#0086b3;">1</span><span style="color:#323232;">, self.sy </span><span style="font-weight:bold;color:#a71d5d;">- </span><span style="color:#0086b3;">1</span><span style="color:#323232;">, </span><span style="color:#0086b3;">0</span><span style="color:#323232;">, </span><span style="color:#0086b3;">0</span><span style="color:#323232;">, </span><span style="color:#0086b3;">False</span><span style="color:#323232;">)]
</span><span style="color:#323232;">    queue_entries: </span><span style="color:#0086b3;">dict</span><span style="color:#323232;">[</span><span style="color:#0086b3;">tuple</span><span style="color:#323232;">[</span><span style="color:#0086b3;">int</span><span style="color:#323232;">, </span><span style="color:#0086b3;">int</span><span style="color:#323232;">], QueueEntry] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">{start: queue[</span><span style="color:#0086b3;">0</span><span style="color:#323232;">]}
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">while </span><span style="color:#323232;">queue:
</span><span style="color:#323232;">      cur_price, x, y, _, _, deleted </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">dataclasses.astuple(heapq.heappop(queue))
</span><span style="color:#323232;">      </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">deleted:
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">continue
</span><span style="color:#323232;">      </span><span style="font-weight:bold;color:#a71d5d;">del </span><span style="color:#323232;">queue_entries[(x, y)]
</span><span style="color:#323232;">      self.lower_bounds[x, y] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">cur_price
</span><span style="color:#323232;">      price </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">cur_price </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#0086b3;">int</span><span style="color:#323232;">(self.lines[y][x])
</span><span style="color:#323232;">      </span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">dx, dy </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">((</span><span style="font-weight:bold;color:#a71d5d;">-</span><span style="color:#0086b3;">1</span><span style="color:#323232;">, </span><span style="color:#0086b3;">0</span><span style="color:#323232;">), (</span><span style="color:#0086b3;">1</span><span style="color:#323232;">, </span><span style="color:#0086b3;">0</span><span style="color:#323232;">), (</span><span style="color:#0086b3;">0</span><span style="color:#323232;">, </span><span style="font-weight:bold;color:#a71d5d;">-</span><span style="color:#0086b3;">1</span><span style="color:#323232;">), (</span><span style="color:#0086b3;">0</span><span style="color:#323232;">, </span><span style="color:#0086b3;">1</span><span style="color:#323232;">)):
</span><span style="color:#323232;">        nx, ny </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">x </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#323232;">dx, y </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#323232;">dy
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">if not </span><span style="color:#323232;">(</span><span style="color:#0086b3;">0 </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt;= nx </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt; self.sx) </span><span style="font-weight:bold;color:#a71d5d;">or not </span><span style="color:#323232;">(</span><span style="color:#0086b3;">0 </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt;= ny </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt; self.sy):
</span><span style="color:#323232;">          </span><span style="font-weight:bold;color:#a71d5d;">continue
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">price </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt; self.lower_bounds[nx, ny]:
</span><span style="color:#323232;">          self.lower_bounds[nx, ny] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">price
</span><span style="color:#323232;">          </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">(nx, ny) </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">queue_entries:
</span><span style="color:#323232;">            queue_entries[(nx, ny)].deleted </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">True
</span><span style="color:#323232;">          queue_entries[(nx, ny)] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">QueueEntry(price, nx, ny, </span><span style="color:#0086b3;">0</span><span style="color:#323232;">, </span><span style="color:#0086b3;">0</span><span style="color:#323232;">, </span><span style="color:#0086b3;">False</span><span style="color:#323232;">)
</span><span style="color:#323232;">          heapq.heappush(queue, queue_entries[(nx, ny)])
</span><span style="color:#323232;">
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#323232;">_solve</span><span style="color:#323232;">(self, maximum_run: </span><span style="color:#0086b3;">int</span><span style="color:#323232;">, minimum_run_to_turn: </span><span style="color:#0086b3;">int</span><span style="color:#323232;">):
</span><span style="color:#323232;">    came_from: </span><span style="color:#0086b3;">dict</span><span style="color:#323232;">[</span><span style="color:#0086b3;">tuple</span><span style="color:#323232;">[</span><span style="color:#0086b3;">int</span><span style="color:#323232;">, </span><span style="color:#0086b3;">int</span><span style="color:#323232;">, </span><span style="color:#0086b3;">int</span><span style="color:#323232;">, </span><span style="color:#0086b3;">int</span><span style="color:#323232;">], </span><span style="color:#0086b3;">tuple</span><span style="color:#323232;">[</span><span style="color:#0086b3;">int</span><span style="color:#323232;">, </span><span style="color:#0086b3;">int</span><span style="color:#323232;">, </span><span style="color:#0086b3;">int</span><span style="color:#323232;">, </span><span style="color:#0086b3;">int</span><span style="color:#323232;">]] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">{}
</span><span style="color:#323232;">    start </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">(</span><span style="color:#0086b3;">0</span><span style="color:#323232;">, </span><span style="color:#0086b3;">0</span><span style="color:#323232;">, </span><span style="color:#0086b3;">0</span><span style="color:#323232;">, </span><span style="color:#0086b3;">0</span><span style="color:#323232;">)
</span><span style="color:#323232;">    queue: </span><span style="color:#0086b3;">list</span><span style="color:#323232;">[QueueEntry] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">[QueueEntry(self.lower_bounds[</span><span style="color:#0086b3;">0</span><span style="color:#323232;">, </span><span style="color:#0086b3;">0</span><span style="color:#323232;">], </span><span style="font-weight:bold;color:#a71d5d;">*</span><span style="color:#323232;">start, </span><span style="color:#0086b3;">False</span><span style="color:#323232;">)]
</span><span style="color:#323232;">    queue_entries: </span><span style="color:#0086b3;">dict</span><span style="color:#323232;">[</span><span style="color:#0086b3;">tuple</span><span style="color:#323232;">[</span><span style="color:#0086b3;">int</span><span style="color:#323232;">, </span><span style="color:#0086b3;">int</span><span style="color:#323232;">, </span><span style="color:#0086b3;">int</span><span style="color:#323232;">, </span><span style="color:#0086b3;">int</span><span style="color:#323232;">], QueueEntry] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">{start: queue[</span><span style="color:#0086b3;">0</span><span style="color:#323232;">]}
</span><span style="color:#323232;">    route: </span><span style="color:#0086b3;">list</span><span style="color:#323232;">[</span><span style="color:#0086b3;">tuple</span><span style="color:#323232;">[</span><span style="color:#0086b3;">int</span><span style="color:#323232;">, </span><span style="color:#0086b3;">int</span><span style="color:#323232;">]] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">[]
</span><span style="color:#323232;">    prices: </span><span style="color:#0086b3;">dict</span><span style="color:#323232;">[</span><span style="color:#0086b3;">tuple</span><span style="color:#323232;">[</span><span style="color:#0086b3;">int</span><span style="color:#323232;">, </span><span style="color:#0086b3;">int</span><span style="color:#323232;">, </span><span style="color:#0086b3;">int</span><span style="color:#323232;">, </span><span style="color:#0086b3;">int</span><span style="color:#323232;">], </span><span style="color:#0086b3;">float</span><span style="color:#323232;">] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">collections.defaultdict(</span><span style="font-weight:bold;color:#a71d5d;">lambda</span><span style="color:#323232;">: np.inf)
</span><span style="color:#323232;">    prices[start] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">0
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">while </span><span style="color:#323232;">queue:
</span><span style="color:#323232;">      _, current_x, current_y, momentum_x, momentum_y, deleted </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">dataclasses.astuple(heapq.heappop(queue))
</span><span style="color:#323232;">      cur_price </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">prices[(current_x, current_y, momentum_x, momentum_y)]
</span><span style="color:#323232;">      </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">deleted:
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">continue
</span><span style="color:#323232;">      </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">((current_x, current_y) </span><span style="font-weight:bold;color:#a71d5d;">== </span><span style="color:#323232;">(self.sx </span><span style="font-weight:bold;color:#a71d5d;">- </span><span style="color:#0086b3;">1</span><span style="color:#323232;">, self.sy </span><span style="font-weight:bold;color:#a71d5d;">- </span><span style="color:#0086b3;">1</span><span style="color:#323232;">) </span><span style="font-weight:bold;color:#a71d5d;">and
</span><span style="color:#323232;">          (momentum_x </span><span style="font-weight:bold;color:#a71d5d;">>= </span><span style="color:#323232;">minimum_run_to_turn </span><span style="font-weight:bold;color:#a71d5d;">or </span><span style="color:#323232;">momentum_y </span><span style="font-weight:bold;color:#a71d5d;">>= </span><span style="color:#323232;">minimum_run_to_turn)):
</span><span style="color:#323232;">        previous </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">came_from.get((current_x, current_y, momentum_x, momentum_y))
</span><span style="color:#323232;">        route.append((current_x, current_y))
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">while </span><span style="color:#323232;">previous:
</span><span style="color:#323232;">          x, y, </span><span style="font-weight:bold;color:#a71d5d;">*</span><span style="color:#323232;">_ </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">previous
</span><span style="color:#323232;">          </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">x </span><span style="font-weight:bold;color:#a71d5d;">!= </span><span style="color:#0086b3;">0 </span><span style="font-weight:bold;color:#a71d5d;">or </span><span style="color:#323232;">y </span><span style="font-weight:bold;color:#a71d5d;">!= </span><span style="color:#0086b3;">0</span><span style="color:#323232;">:
</span><span style="color:#323232;">            route.append((x, y))
</span><span style="color:#323232;">          previous </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">came_from.get(previous)
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">break
</span><span style="color:#323232;">      </span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">dx, dy </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">((</span><span style="font-weight:bold;color:#a71d5d;">-</span><span style="color:#0086b3;">1</span><span style="color:#323232;">, </span><span style="color:#0086b3;">0</span><span style="color:#323232;">), (</span><span style="color:#0086b3;">1</span><span style="color:#323232;">, </span><span style="color:#0086b3;">0</span><span style="color:#323232;">), (</span><span style="color:#0086b3;">0</span><span style="color:#323232;">, </span><span style="font-weight:bold;color:#a71d5d;">-</span><span style="color:#0086b3;">1</span><span style="color:#323232;">), (</span><span style="color:#0086b3;">0</span><span style="color:#323232;">, </span><span style="color:#0086b3;">1</span><span style="color:#323232;">)):
</span><span style="color:#323232;">        dot_product </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">dx </span><span style="font-weight:bold;color:#a71d5d;">* </span><span style="color:#323232;">momentum_x </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#323232;">dy </span><span style="font-weight:bold;color:#a71d5d;">* </span><span style="color:#323232;">momentum_y
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">dot_product </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt; </span><span style="color:#0086b3;">0 </span><span style="font-weight:bold;color:#a71d5d;">or </span><span style="color:#323232;">dot_product </span><span style="font-weight:bold;color:#a71d5d;">>= </span><span style="color:#323232;">maximum_run:
</span><span style="color:#323232;">          </span><span style="font-weight:bold;color:#a71d5d;">continue
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">((momentum_x </span><span style="font-weight:bold;color:#a71d5d;">or </span><span style="color:#323232;">momentum_y) </span><span style="font-weight:bold;color:#a71d5d;">and </span><span style="color:#323232;">dot_product </span><span style="font-weight:bold;color:#a71d5d;">== </span><span style="color:#0086b3;">0 </span><span style="font-weight:bold;color:#a71d5d;">and
</span><span style="color:#323232;">            </span><span style="color:#62a35c;">abs</span><span style="color:#323232;">(momentum_x) </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt; minimum_run_to_turn </span><span style="font-weight:bold;color:#a71d5d;">and </span><span style="color:#62a35c;">abs</span><span style="color:#323232;">(momentum_y) </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt; minimum_run_to_turn):
</span><span style="color:#323232;">          </span><span style="font-weight:bold;color:#a71d5d;">continue
</span><span style="color:#323232;">        new_x, new_y </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">current_x </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#323232;">dx, current_y </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#323232;">dy
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">if not </span><span style="color:#323232;">(</span><span style="color:#0086b3;">0 </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt;= new_x </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt; self.sx) </span><span style="font-weight:bold;color:#a71d5d;">or not </span><span style="color:#323232;">(</span><span style="color:#0086b3;">0 </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt;= new_y </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt; self.sy):
</span><span style="color:#323232;">          </span><span style="font-weight:bold;color:#a71d5d;">continue
</span><span style="color:#323232;">        new_momentum_x, new_momentum_y </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">(dx, dy) </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">dot_product </span><span style="font-weight:bold;color:#a71d5d;">== </span><span style="color:#0086b3;">0 </span><span style="font-weight:bold;color:#a71d5d;">else </span><span style="color:#323232;">(momentum_x </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#323232;">dx, momentum_y </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#323232;">dy)
</span><span style="color:#323232;">        new_position </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">(new_x, new_y, new_momentum_x, new_momentum_y)
</span><span style="color:#323232;">        potential_new_price </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">cur_price </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#0086b3;">int</span><span style="color:#323232;">(self.lines[new_y][new_x])
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">potential_new_price </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt; prices[new_position]:
</span><span style="color:#323232;">          queue_entry </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">queue_entries.get(new_position)
</span><span style="color:#323232;">          </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">queue_entry:
</span><span style="color:#323232;">            queue_entry.deleted </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">True
</span><span style="color:#323232;">          queue_entries[new_position] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">QueueEntry(potential_new_price </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#323232;">self.lower_bounds[new_x, new_y],
</span><span style="color:#323232;">                                                   </span><span style="font-weight:bold;color:#a71d5d;">*</span><span style="color:#323232;">new_position, </span><span style="color:#0086b3;">False</span><span style="color:#323232;">)
</span><span style="color:#323232;">          came_from[new_position] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">(current_x, current_y, momentum_x, momentum_y)
</span><span style="color:#323232;">          prices[new_position] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">potential_new_price
</span><span style="color:#323232;">          heapq.heappush(queue, queue_entries[new_position])
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#62a35c;">sum</span><span style="color:#323232;">(</span><span style="color:#0086b3;">int</span><span style="color:#323232;">(self.lines[y][x]) </span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">x, y </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">route)
</span><span style="color:#323232;">
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#323232;">solve_first_star</span><span style="color:#323232;">(self) -> </span><span style="color:#0086b3;">int</span><span style="color:#323232;">:
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#323232;">self._solve(</span><span style="color:#0086b3;">3</span><span style="color:#323232;">, </span><span style="color:#0086b3;">0</span><span style="color:#323232;">)
</span><span style="color:#323232;">
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#323232;">solve_second_star</span><span style="color:#323232;">(self) -> </span><span style="color:#0086b3;">int</span><span style="color:#323232;">:
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#323232;">self._solve(</span><span style="color:#0086b3;">10</span><span style="color:#323232;">, </span><span style="color:#0086b3;">4</span><span style="color:#323232;">)
</span>
sjmulder, (edited )

C

Very not pretty and not efficient. Using what I think is dynamic programming - essentially I just propagate cost total through a (x, y, heading, steps in heading) state space, so every cell in that N-dimensional array holds the minimum total cost known to get to that state which is updated iteratively from the neighbours until it settles down.

Debugging was annoying because terminals aren’t great at showing 4D grids. My mistakes were in the initial situation and missing the “4 steps to come to a stop at the end” aspect in part 2.

github.com/sjmulder/aoc/blob/master/…/day17.c

Sekoia,

Rust: codeberg.org/Sekoia/adventofcode/src/…/day17.rs

WOW that took me forever. Completely forgot how to dijkstra’s and then struggled with the actual puzzle too. 1h20 total, but I was still top 1500, which I guess means most people really struggled with this, huh.

lwhjp,
@lwhjp@lemmy.sdf.org avatar

Yeah, finding a good way to represent the “last three moves” constraint was a really interesting twist. You beat me to it, anyway!

cvttsd2si,

Scala3

Learning about scala-graph yesterday seems to have paid off already. This explicitly constructs the entire graph of allowed moves, and then uses a naive dijkstra run. This works, and I don’t have to write a lot of code, but it is fairly inefficient.


<span style="font-weight:bold;color:#a71d5d;">import </span><span style="color:#323232;">day10._
</span><span style="font-weight:bold;color:#a71d5d;">import </span><span style="color:#323232;">day10.Dir._
</span><span style="font-weight:bold;color:#a71d5d;">import </span><span style="color:#323232;">day11.Grid
</span><span style="color:#323232;">
</span><span style="font-style:italic;color:#969896;">// standing on cell p, having entered from d
</span><span style="font-weight:bold;color:#a71d5d;">case class </span><span style="color:#0086b3;">Node</span><span style="color:#323232;">(p: </span><span style="color:#0086b3;">Pos</span><span style="color:#323232;">, d: </span><span style="color:#0086b3;">Dir</span><span style="color:#323232;">)
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">connect</span><span style="color:#323232;">(p: </span><span style="color:#0086b3;">Pos</span><span style="color:#323232;">, d: </span><span style="color:#0086b3;">Dir</span><span style="color:#323232;">, g: </span><span style="color:#0086b3;">Grid</span><span style="color:#323232;">[</span><span style="font-weight:bold;color:#a71d5d;">Int</span><span style="color:#323232;">], dists: </span><span style="color:#0086b3;">Range</span><span style="color:#323232;">) </span><span style="font-weight:bold;color:#a71d5d;">= 
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">val </span><span style="color:#323232;">from </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">Seq</span><span style="color:#323232;">(-</span><span style="color:#0086b3;">1</span><span style="color:#323232;">, </span><span style="color:#0086b3;">1</span><span style="color:#323232;">).map(i </span><span style="font-weight:bold;color:#a71d5d;">=> </span><span style="color:#0086b3;">Dir</span><span style="color:#323232;">.from(d.n + i)).map(</span><span style="color:#0086b3;">Node</span><span style="color:#323232;">(p, _))
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">val </span><span style="color:#323232;">ends </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">List</span><span style="color:#323232;">.iterate(p, dists.last + </span><span style="color:#0086b3;">1</span><span style="color:#323232;">)(walk(_, d)).filter(g.inBounds)
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">val </span><span style="color:#323232;">costs </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> ends.drop(</span><span style="color:#0086b3;">1</span><span style="color:#323232;">).scanLeft(</span><span style="color:#0086b3;">0</span><span style="color:#323232;">)(_ + g(_))
</span><span style="color:#323232;">    from.flatMap(f </span><span style="font-weight:bold;color:#a71d5d;">=></span><span style="color:#323232;"> ends.zip(costs).drop(dists.start).map((dest, c) </span><span style="font-weight:bold;color:#a71d5d;">=> </span><span style="color:#0086b3;">WDiEdge</span><span style="color:#323232;">(f, </span><span style="color:#0086b3;">Node</span><span style="color:#323232;">(dest, d), c)))
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">parseGrid</span><span style="color:#323232;">(a: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="font-weight:bold;color:#a71d5d;">Char</span><span style="color:#323232;">]], dists: </span><span style="color:#0086b3;">Range</span><span style="color:#323232;">) </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">val </span><span style="color:#323232;">g </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">Grid</span><span style="color:#323232;">(a.map(_.map(_.getNumericValue)))
</span><span style="color:#323232;">    </span><span style="color:#0086b3;">Graph</span><span style="color:#323232;">() ++ g.indices.flatMap(p </span><span style="font-weight:bold;color:#a71d5d;">=> </span><span style="color:#0086b3;">Dir</span><span style="color:#323232;">.all.flatMap(d </span><span style="font-weight:bold;color:#a71d5d;">=></span><span style="color:#323232;"> connect(p, d, g, dists)))
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">compute</span><span style="color:#323232;">(a: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">String</span><span style="color:#323232;">], dists: </span><span style="color:#0086b3;">Range</span><span style="color:#323232;">): </span><span style="font-weight:bold;color:#a71d5d;">Long =
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">val </span><span style="color:#323232;">g </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> parseGrid(a.map(_.toList), dists)
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">val </span><span style="color:#323232;">source </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">Node</span><span style="color:#323232;">(</span><span style="color:#0086b3;">Pos</span><span style="color:#323232;">(-</span><span style="color:#0086b3;">1</span><span style="color:#323232;">, -</span><span style="color:#0086b3;">1</span><span style="color:#323232;">), </span><span style="color:#0086b3;">Right</span><span style="color:#323232;">)
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">val </span><span style="color:#323232;">sink </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">Node</span><span style="color:#323232;">(</span><span style="color:#0086b3;">Pos</span><span style="color:#323232;">(-</span><span style="color:#0086b3;">2</span><span style="color:#323232;">, -</span><span style="color:#0086b3;">2</span><span style="color:#323232;">), </span><span style="color:#0086b3;">Right</span><span style="color:#323232;">)
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">val </span><span style="color:#323232;">start </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">Seq</span><span style="color:#323232;">(</span><span style="color:#0086b3;">Down</span><span style="color:#323232;">, </span><span style="color:#0086b3;">Right</span><span style="color:#323232;">).map(d </span><span style="font-weight:bold;color:#a71d5d;">=> </span><span style="color:#0086b3;">Node</span><span style="color:#323232;">(</span><span style="color:#0086b3;">Pos</span><span style="color:#323232;">(</span><span style="color:#0086b3;">0</span><span style="color:#323232;">, </span><span style="color:#0086b3;">0</span><span style="color:#323232;">), d)).map(</span><span style="color:#0086b3;">WDiEdge</span><span style="color:#323232;">(source, _, </span><span style="color:#0086b3;">0</span><span style="color:#323232;">))
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">val </span><span style="color:#323232;">end </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">Seq</span><span style="color:#323232;">(</span><span style="color:#0086b3;">Down</span><span style="color:#323232;">, </span><span style="color:#0086b3;">Right</span><span style="color:#323232;">).map(d </span><span style="font-weight:bold;color:#a71d5d;">=> </span><span style="color:#0086b3;">Node</span><span style="color:#323232;">(</span><span style="color:#0086b3;">Pos</span><span style="color:#323232;">(a(</span><span style="color:#0086b3;">0</span><span style="color:#323232;">).size - </span><span style="color:#0086b3;">1</span><span style="color:#323232;">, a.size - </span><span style="color:#0086b3;">1</span><span style="color:#323232;">), d)).map(</span><span style="color:#0086b3;">WDiEdge</span><span style="color:#323232;">(_, sink, </span><span style="color:#0086b3;">0</span><span style="color:#323232;">))
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">val </span><span style="color:#323232;">g2 </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> g ++ start ++ end
</span><span style="color:#323232;">    g2.get(source).shortestPathTo(g2.get(sink)).map(_.weight).getOrElse(-</span><span style="color:#0086b3;">1.0</span><span style="color:#323232;">).toLong
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">task1</span><span style="color:#323232;">(a: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">String</span><span style="color:#323232;">]): </span><span style="font-weight:bold;color:#a71d5d;">Long =</span><span style="color:#323232;"> compute(a, </span><span style="color:#0086b3;">1</span><span style="color:#323232;"> to </span><span style="color:#0086b3;">3</span><span style="color:#323232;">)
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">task2</span><span style="color:#323232;">(a: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">String</span><span style="color:#323232;">]): </span><span style="font-weight:bold;color:#a71d5d;">Long =</span><span style="color:#323232;"> compute(a, </span><span style="color:#0086b3;">4</span><span style="color:#323232;"> to </span><span style="color:#0086b3;">10</span><span style="color:#323232;">)
</span>
lwhjp, (edited )
@lwhjp@lemmy.sdf.org avatar

Haskell

Wowee, I took some wrong turns solving today’s puzzle! After fixing some really inefficient pruning I ended up with a Dijkstra search that runs in 2.971s (for a less-than-impressive 124.782 l-s).

Solutionimport Control.Monad import Data.Array.Unboxed (UArray) import qualified Data.Array.Unboxed as Array import Data.Char import qualified Data.HashSet as Set import qualified Data.PQueue.Prio.Min as PQ readInput :: String -> UArray (Int, Int) Int readInput s = let rows = lines s in Array.amap digitToInt . Array.listArray ((1, 1), (length rows, length $ head rows)) $ concat rows walk :: (Int, Int) -> UArray (Int, Int) Int -> Int walk (minStraight, maxStraight) grid = go Set.empty initPaths where initPaths = PQ.fromList [(0, ((1, 1), (d, 0))) | d <- [(0, 1), (1, 0)]] goal = snd $ Array.bounds grid go done paths = case PQ.minViewWithKey paths of Nothing -> error “no route” Just ((n, (p@(y, x), hist@((dy, dx), k))), rest) | p == goal && k >= minStraight -> n | (p, hist) Set.member done -> go done rest | otherwise -> let next = do h’@((dy’, dx’), _) <- join [ guard (k >= minStraight) >> [((dx, dy), 1), ((-dx, -dy), 1)], guard (k < maxStraight) >> [((dy, dx), k + 1)] ] let p’ = (y + dy’, x + dx’) guard $ Array.inRange (Array.bounds grid) p’ return (n + grid Array.! p’, (p’, h’)) in go (Set.insert (p, hist) done) $ (PQ.union rest . PQ.fromList) next main = do input <- readInput <$> readFile “input17” print $ walk (0, 3) input print $ walk (4, 10) input(edited for readability)

  • All
  • Subscribed
  • Moderated
  • Favorites
  • •
  • advent_of_code@programming.dev
  • ngwrru68w68
  • DreamBathrooms
  • thenastyranch
  • magazineikmin
  • InstantRegret
  • GTA5RPClips
  • Youngstown
  • everett
  • slotface
  • rosin
  • osvaldo12
  • mdbf
  • kavyap
  • cubers
  • megavids
  • modclub
  • normalnudes
  • tester
  • khanakhh
  • Durango
  • ethstaker
  • tacticalgear
  • Leos
  • provamag3
  • anitta
  • cisconetworking
  • JUstTest
  • lostlight
  • All magazines
    •