Mercurial > repos > other > adventofcode2023
view day17.txt @ 26:eb6c3a7d2f72
Constrained and more optimised route finding
* Track routes so we can see if we have gone straight for
too long
* Track multiple routes so we can use a non-optimal route to
X if it makes another route to Y through X possible (e.g.
optimal route takes three consecutive steps to X, but then
has to turn, whereas a longer straight earlier and two
consecutive steps to X gives a much better next hop to Y)
* We have a start point, so only include the nodes from the
search front in "unvisited" to avoid looking at lots of
irrelevant nodes
| author | IBBoard <dev@ibboard.co.uk> |
|---|---|
| date | Sun, 17 Dec 2023 20:13:03 +0000 |
| parents | 79dc2ba41df2 |
| children |
line wrap: on
line source
--- Day 17: Clumsy Crucible --- A route finding puzzle with the following constraints: * Reduce the sum of values walked (the "cost" of the route) * Do not go in a straight line for more than three blocks * Don't count the starting square (unless you return to it) Start at the top-left and move to the bottom-right Given: 2413432311323 3215453535623 3255245654254 3446585845452 4546657867536 1438598798454 4457876987766 3637877979653 4654967986887 4564679986453 1224686865563 2546548887735 4322674655533 We could go: 2>>34^>>>1323 32v>>>35v5623 32552456v>>54 3446585845v52 4546657867v>6 14385987984v4 44578769877v6 36378779796v> 465496798688v 456467998645v 12246868655<v 25465488877v5 43226746555v> This path never moves more than three consecutive blocks in the same direction and incurs a heat loss of only 102.