https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2023 day 17> :thread:
# advent-of-code
a
kodee happy 2
n
Not gonna win any records for execution time or code cleanliness, but it sure was easy using my A* library, which trades speed for flexibility and allows to set custom end conditions and the like. https://github.com/nbanman/Play2022/blob/master/src/main/kotlin/org/gristle/adventOfCode/y2023/d17/Y2023D17.kt
Canโ€™t wait to see the sophisticated heuristics come in.
m
Took me ages to debug part 2 before I found I had an off by one error in the moving-in-the-same-direction counter at the starting position. Didn't affect part 1, didn't affect the two examples, but did affect the real input.
p
My machine is burning. Now the kids are awake so Iโ€™ll need to push the refactoring and optimizations to the evening ๐Ÿคท https://github.com/PaulWoitaschek/AdventOfCode/pull/48/files
e
https://github.com/ephemient/aoc2023/blob/main/kt/aoc2023-lib/src/commonMain/kotlin/com/github/ephemient/aoc2023/Day17.kt absolutely nothing out of the ordinary here. took a little while finding a part 2 bug
(or even before it can stop at the end)
but it cleaned up fine. adding a heuristic for A* saved such a tiny amount of time that it probably wasn't worthwhile.
k
solution.kt
solution.kt
e
It works perfectly with the Dijkstra algorithm. No need for anything more fancy like A*, though it will not hurt (A* is essentially a generalization of Dijkstra).
๐Ÿ‘ 1
๐Ÿ‘๐Ÿป 1
e
A* will hurt if you use an inadmissible heuristic ๐Ÿ˜›
๐Ÿ‘Œ 1
p
c
My first step was to implement Dijkstra's (which I think gave 91 on the sample but it's been messed up since then) but i'm struggling to incorporate the 3 step max into it. Any pointers? I'm trying to store a list of visited coords on my shortest distances but having no joy. I think it boils down to the shortest path to any given position isn't necessarily the optimal path in the final solution. e.g. I might be able to reach position A with X heat loss but have done so in three steps so can't step right whereas i'd have been better reaching position A with Y (>X) heat loss so I can step right and be on the right path.
m
@Charles Flynn part of the state is something akin to "in what direction did you came in?" and "how many steps forward do you still have left" I had the same problem before, and when I analyzed where my path went wrong, is that a lower score reached a point where he wasn't allowed to walk forward anymore, but a higher score reached that point, but could walk more forward, and it was eventually that path that lead to the shortest answer
m
does anyone else understand this example? it says that the minimum for that example should be 71, however my code gives me 47 since it can keep going right a few more in the top row
m
it didn't come up for my input either, but technically you need to write something like this:
Copy code
if(nextPoint == endPoint && forwardCount >= minimalForward){
                return nextScore
            }
reaching the endpoint before you've done your minimum steps forward doesn't allow you to stop or something?
e
@Manuel Casariego
๐Ÿ‘€ 1
m
@ephemient aaah, didn't even notice that, advent of reading comprehension strikes back, will try to fix it then, weird thing that I managed to get the solution for the real input without that property ๐Ÿ˜“
m
My solution for today, had some trouble this morning defining a proper state for the PQ and the visitation. Ended up on two seperate classes, not too sure if its the best, but it works pretty fast.
day17.txt.kt
p
My 
dijkstra
helper came in handy today. Not entirely happy with the ~700ms solve time, but not sure I'll have time to improve it much today.
Day17.kt
Copy code
Benchmark                 Mode  Cnt    Score      Error  Units
BenchDay17.intArrayPart1  avgt    3   40.432 ยฑ    3.062  ms/op
BenchDay17.intArrayPart2  avgt    3  134.850 ยฑ    6.991  ms/op
BenchDay17.part1          avgt    3  176.998 ยฑ   78.220  ms/op
BenchDay17.part2          avgt    3  752.731 ยฑ  795.443  ms/op
~135ms for part 2 - I'll take it.
Copy code
val bests = IntArray((size * first().size).shl(6)) { Int.MAX_VALUE }
fun Crucible.idx() = (y * size + x).shl(6) + speed.shl(2) + direction.ordinal
Swapped my map for an IntArray to track bests in dijkstra.
e
that's pretty good. even in rust I'm only at 225ms (using hashmap)
p
Could probably acheive the same with a 
[u32;1272384]
in rust ๐Ÿ˜„
e
that's actually slightly non-trivial, since Rust will want to put it on the stack by default, which will cause SEGV if you are unlucky enough to access it in the wrong order and skip over the one page the Linux kernel sets up to detect stack growth
p
a pre-allocated vec should suffice to keep it on heap
e
sure you could 
vec![0u32; 1272384]
. it's not so easy with 
[]
though ๐Ÿ™‚
p
I'll be honest, my rust is (ahem) rusty, but should I get some time I'll be playing.
e
t
This day was really hard for me ๐Ÿ˜ž I didn't come here for any spoilers because I felt I should be able to solve it on my own. Eventually, by caching the search state in some way, I got it to run in feasible time (under a minute for part 1 and part 2 ๐Ÿ˜ฎโ€๐Ÿ’จ), but obviously it's not the target solution. Now that I read about Dijkstra's algorithm, I'll probably give it a try when I find some spare time.
e
there's always been at least one problem requiring Dijkstra's every year, as far as I remember. it's useful in other places too, so it's good to learn
๐Ÿ‘ 1
if you know BFS and priority queue, combine them and then you have Dijkstra's (or A* depending on how you choose your priorities)
๐Ÿ™ 1
t
I tried both DFS (StackOverflow error ๐Ÿ˜„) and BFS (running too long because of backtracking) today. I even remember reading a bit about Dikstra's algorithm before but I've never implemented it and I didn't think about it today. I haven't heard about A* either, so I'll do some reading, thanks! ๐Ÿ™‚
c
Usually Dijkstra's algorithm comes up a bit earlier and a bit more vanilla than this. I eventually got there but was tricky today.
t
I enjoyed that one and got a solution to both parts that I'm happy with. A rare case of waking up, reading the puzzle, and having my very first idea pan out. Part 2 runs in about 800ms for me. Basically, I have a State object which encodes location, direction of travel, and steps in the direction of travel. Using Dijkstra's algorithm, we queue work with that information plus the cumulative heat loss so far (as a Work object), and order the queue by heatloss (lowest to highest). โ€ข Blog โ€ข Code
m
Struggled a bit with that one. Immediately thought on Dijkstra but had some trouble integrating the movement constraint in part 1. After adding direction and number of same direction steps into my state it worked out ok. Part 2 was only a couple of minutes. Performance isn't great but not terrible either (~500 ms for part 2)
m
@todd.ginsberg looking good ๐Ÿ‘ , I thought about splitting up the state and work as well, but ended up with a data class where steps are not part of the primary constructor
๐Ÿ‘๐Ÿป 1
m
@phldavies
Swapped my map for an IntArray to track bests in dijkstra.
That's a neat trick, wouldn't have thought the overhead of a map is that high
p
Has to calculate the hash code for the key, index into the buckets and then scan the bucket for a matching element by equals method. The array approach has a direct index calculation for the "key" and a single value in each "bucket"
n
@ephemient
adding a heuristic for A* saved such a tiny amount of time that it probably wasn't worthwhile.
Just using manhattan distance for heuristic cuts my solve time in half for both parts.
p
Similar to the way for a small set of values is faster to scan over a list for containment than use a hashset
๐Ÿ‘ 1
e
@Neil Banman probably depends on input. I chatted with other people for whom it was slower on theirs
๐Ÿ‘ 1
t
@Michael de Kaste I had something similar originally. One class with all four facts but only three of them in the hash/equal implementations. I didnโ€™t like having to do that so I broke it into two and enclosed one in the other.
e
(which can happen if it just happens to lead to deeper exploration in what is ultimately the wrong direction)
j
each year since I started AoC I have the exact same problem regarding BFS categories. I can have regular BFS, BFS with Priority queue based on cost, BFS with memoization (skip nodes if we were here with lower cost) and ofc BFS with Priority AND memoization. And I always forget which of them are astar and which dijkstra ๐Ÿ˜•
e
A* is really the same as Dijkstra's, just amending your cost metric with a heuristic. ignore it if you want; I don't recall any AoC problems before that require A*. sure some could be faster, but unless there's some particular structure in the graph to exploit, it's an optimization over Dijkstra's, not a big-O improvement
t
I have day one vibes with that one. The test case for part two finds the correct solution for test data, but the real data is too low. Are there things that could easily be missed? I already checked: โ€ข From debugging output the suggested new directions look correct also for the corner cases (<4, >=4 and 10 movements since the last bend). โ€ข I tried to rule out off by one errors in the minimum/maximum segment lengths by changing the numbers (which makes day 1 + test data fail as well). โ€ข I am already using the minimum both starting directions. โ€ข I even tried not adding the heat loss a second if the path should ever cross itself.
e
if it's too low, print out your path and check if it's actually possible?
n
> it needs to move a minimum of four blocks in that direction before it can turn (or even before it can stop at the end) Bolded part is the only thing I can think of that might be tripping you up.
t
Or print the direction you are going every step and make absolutely sure that a) you are making no fewer than 4 steps in the same direction b) you are making no more than 10 steps in the same direction and c) you arenโ€™t at the goal on fewer than 4 steps (edit: not sure if thatโ€™s true) (edit edit: clarified by Neil)
t
I implemented it like this:
Copy code
override fun isStraightPossible(sameDirCount: Int) = sameDirCount < 10
override fun isTurnPossible(sameDirCount: Int) = sameDirCount >= 4
override fun isEndPossible(sameDirCount: Int) = sameDirCount >= 4
And in debugging output I only see the original direction repeated if below four.
@ephemient It is too high.
t
Turning backwards?
t
You mean going back in the direction it came from? Not allowing this...
e
if you're too high, you're possibly pruning too many paths or not searching in the right order
t
Thatโ€™s what I meant yeah. Off by one error in how steps are calculated? Meaning only incrementing when you step? I had an error where Iโ€™d calculate my next state and reset steps to 0 when I turned but it should have been 1.
e
perhaps specific coding help should be in another thread?
๐Ÿ‘๐Ÿป 1
๐Ÿ‘ 1
t
Yes, sorry. I expected common pitfalls like on day one... Found my problem. I counted the starting cell as a first movement in the same direction, while the correct solution did not.
e
I need a rubber ducking. So, in the first part, the solution path start is (0,0)->(0,1)->(0,2)->(1,2)->(1,3)->(1,4)->(1,5)->(0,5). The heat loss in (0,5) is 25. However (0,0)->(0,1)->(0,2)->(1,2)->(1,3)->(1,4)->(0,4)->(0,5) gives heat loss in (0,5) value 24.
Where am I wrong?
p
Follow the path and read this sentence again:
Because it is difficult to keep the top-heavy crucible going in a straight line for very long, it can move at most three blocks
e
(0,0)->(0,2) = 2, (1,2)->(1,4) = 2
I donโ€™t see any path longer than 2 in the second proposal
p
Copy code
2>>34^>>>1323
32v>>>35v5623
This is the optimal path
Copy code
2413432311323
3215453535623
Your way would be:
Copy code
2>>3^>2311323
32v>>53535623
That would force you to turn down at the 1
Copy code
2>>3^>>>11323
32v>>53v35623
e
Aha!
I need to print the path to find a mistake. I implemented kinda Dijkstraโ€™s algorithm with the limitations. But some steps give better weight but will not lead to an optimal path in total. And since I calculate heat loss by summing the weight calculated in the prev point that might be rewritten with more lighter subpath.
Oke, I should change this from using saved prev point weight to pass weight in the calculation
p
Then your key needs to account for how many steps youโ€™ve already been into the direction
If you want to go down you might need to take a higher cost paths coming from the top so you can achieve it with the constraints
e
I think I have it all
Iโ€™m getting 109 now
Drilling down more
Oke, my algorithm was BSF with constraints for the next point (3 in one direction and can not change direction) and on every cell I was saving the min for this cell, and that would prevent algorithm to evaluate this point if the calculated heat loss was more than min in this point. Turns out, that was a not a good algorithm - it was rejecting the final optimal path because it was finding some more optimal pathes to intermediate points.
I changed it to not use calculated min in the previous cell but use value that comes from the previous step
That still giving not optimal path since the check of min calculation in some intermediate point was rejecting the total optimal path
So I removed check with saved min for intermediate cell and now algorithm just runs since nothing stops it to go over same cell over and over
p
Then check what has been visited already
e
I can save number of visit to cell and limit it to max 4
or other number
let me try that
o
Does anyone know how i can avoid remove and adding to the the priority queue (to maintain ordeing) in my implementation of Djikstra?
Copy code
import java.util.PriorityQueue

val pointDistances = mutableMapOf<NodeState, Long>()

fun main() {
    val lines = input.trim().split("\n")
    val startPoint1 = NodeState(Point(0, 0), lines[0][0].digitToInt().toLong(), Direction.RIGHT, 0)
    pointDistances[startPoint1] = startPoint1.value

    val unvisitedPoints = PriorityQueue<NodeState>() { a, b ->
        val thisD = pointDistances[a] ?: Long.MAX_VALUE
        val otherD = pointDistances[b] ?: Long.MAX_VALUE
        (thisD).compareTo(otherD)

    }
    val visitedPoints = mutableSetOf<NodeState>()
    unvisitedPoints.add(startPoint1)

    while (unvisitedPoints.isNotEmpty()) {
        val nodeState = unvisitedPoints.poll()
        val left = if (nodeState.steps >= 4) nodeState.point.turnLeft(nodeState.direction) else null
        val right = if (nodeState.steps >= 4) nodeState.point.turnRight(nodeState.direction) else null
        val forward = if (nodeState.steps < 10) nodeState.point.moveForward(nodeState.direction) else null
//        val left = nodeState.point.turnLeft(nodeState.direction)
//        val right = nodeState.point.turnRight(nodeState.direction)
//        val forward = if (nodeState.steps < 3) nodeState.point.moveForward(nodeState.direction) else null
        visitedPoints.add(nodeState)
        listOfNotNull(
            left, right, forward
        ).filter { it.second.x in lines.indices && it.second.y in lines[0].indices }.mapIndexed { index, value ->
            NodeState(
                value.second,
                lines[value.second.x][value.second.y].digitToInt().toLong(),
                value.first,
                if (value == forward) nodeState.steps + 1 else 1
            )
        }.filter {
            unvisitedPoints.contains(it) || !visitedPoints.contains(it)
        }.forEach { node ->
            if (node.point == Point(lines.lastIndex, lines[0].lastIndex)) {
                println(pointDistances[nodeState]!! + node.value - startPoint1.value)
                return
            }
            val currentDistance = pointDistances[nodeState] ?: Long.MAX_VALUE
            if (currentDistance + node.value < (pointDistances[node]
                    ?: Long.MAX_VALUE)
            ) {
                pointDistances[node] = currentDistance + node.value
            }
            unvisitedPoints.remove(node)
            unvisitedPoints.offer(node)
        }
    }

}


data class NodeState(val point: Point, val value: Long, val direction: Direction, val steps: Int)
e
You cannot avoid it using Javaโ€™s PriorityQueue. One idea is that you donโ€™t have to remove (just remember to skip it when you later remove the stale version from the top). But to have an efficient Dijkstra implementation youโ€™ll need your own binary heap implementation.
o
Ok, thanks.
n
It's better not to remove in most cases. Just discard unneeded points when you poll them by checking to see if they are in visited.
๐Ÿ™ 1
k
could someone please explain, why we can add new state immediately to known states?
e
What do you mean?
k
Copy code
pq.add(initState)
visited.add(initState)
while(pq.notempty) {
  ....
  if () {
    pq.add(newState)
    visited.add(newState)
  }
}
vs
Copy code
pq.add(initState)
while(pq.notempty) {
  visited.add(state)
  ....
  if () {
    pq.add(newState)
  }
}
why is it ok to put new state already to visited states even when we were not there yet? is it guaranteed that later visit will always be same/worse?
e
Where do you check for visited in this code?
k
in the if
e
It should not work for general graphs. You may get better distance later. Maybe there is something special here that it happens to work.
k
yeah, that's my understanding as well, but I found similar statement on reddit and @todd.ginsberg's blog like
Copy code
Because the queue is ordered by heatLoss, so anything we say we've seen now will be the quickest we could have arrived at that state, even if the work is queued up to be evaluated later. So there's not real reason not to do it now.
and I didn't understand why
e
What is a โ€œstateโ€ in your case and how its equals are defined? Does the equals include the total distance (heat loss). If yes, then it would explain it. And it is not a Dijkstra algo. It is a much less efficient algorithm, but it does not care, indeed.
k
state is data class of position (x,y) direction (enum) and "velocity"
n
I concur with Roman. With Dijkstra you should add to visited only after you've pulled it out of the PQ. Otherwise you might mark a longer path as visited and subsequently ignore a shorter path. I don't know for sure why it works with Todd's code, but likely because the State includes direction and number of steps taken in that direction, the State is much more likely to be unique and thus avoid a situation where the same State can be arrived at with less heat loss.
t
Interesting conversation, Iโ€™d have to go back and try it the other way to tell you and Iโ€™m at work so I probably wonโ€™t get to it soon. I guess Iโ€™ve been doing these wrong for years. I think I almost always check for duplicates before adding to the queue rather than after removing it. Itโ€™s probably too many instances to go back and change at this rate, but if I post anything about AOC in the future (somewhat unlikely) Iโ€™ll have to re-read all this and keep it in mind. :)
e
it doesn't matter for unweighted Dijkstra, but it may make a difference if you have weights
42 Views
Open in Slack
PreviousNext
Powered by