https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2022 day 12> :thread:
# advent-of-code
a
k
The fastest way to code part 2 with my utils, was to make it off by one (having it take a step from 'initial' to all possible first locations) but the path of part 2 was only 1 cell shorter than part 1 so they were giving the same value and I thought intellij was just bugged and running my part 1 code instead of part 2
d
message has been deleted
r
@Dan Fingal-Surma the same for me, reused solution from 2021 day 1x
m
I kinda read over the 'you can yeet yourself off a cliff' part of the assignment on part1
m
I read “To maximize exercise while hiking” in part 2 and returned the longest path of all the shortest paths. Lost so much time debugging before I realized I should return the shortest of all. AdventOfReadingComprehension.com strikes again.
n
I had a readymade BFS which got me a very good ranking (for me; not competitive). But I neglected to consider that my readymade BFS still delivered the results of its exploration even if the end condition was not met. Debugging this took way too long. So I went from 876th in part 1 to 3099th. 😞
j
why do I get 8 instead of 31 for the example for part1, sad
r
@Jonathan Kolberg do you take into account that each next step has to be the same value or 1 higher than step before?
j
i had my graph the wrong way around
hm for part2 just checking everything seems to not be the correct way
ok just trying everything works for part2 but take a 2-5 minutes
m
Copy code
typealias Point = Pair<Int, Int>
fun Point.neighbours() = sequenceOf(
    first - 1 to second,
    first to second + 1,
    first + 1 to second,
    first to second - 1
)
object Day12 : Challenge() {
    private lateinit var startPoint: Point
    private lateinit var endPoint: Point

    val parsed = input.lines().withIndex().flatMap { (y, line) ->
        line.withIndex().map { (x, char) ->
            val point = y to x
            when (char) {
                'S' -> point to 'a'.also { startPoint = point }
                'E' -> point to 'z'.also { endPoint = point }
                else -> point to char
            }
        }
    }.toMap()

    private val countMap = buildMap {
        var count = 0
        var currentCandidates = setOf(endPoint)
        while (currentCandidates.isNotEmpty()) {
            currentCandidates = buildSet {
                for (candidate in currentCandidates) {
                    if (putIfAbsent(candidate, count) != null) continue
                    val value = parsed.getValue(candidate)
                    for (neighbour in candidate.neighbours()) {
                        parsed[neighbour]?.also {
                            if (value - it <= 1) {
                                add(neighbour)
                            }
                        }
                    }
                }
            }
            count++
        }
    }

    override fun part1() = countMap[startPoint]

    override fun part2() = parsed.filterValues('a'::equals)
        .filterKeys(countMap::containsKey)
        .keys.minOf(countMap::getValue)
}
I built a countMap so I can just get all the points of interest in hindsight :)
d
Cut and pasted and edited problem 15 2021
r
For part 2, I think the best way is to start at the end point. You just have to reverse your elevation diff rule, and change your termination condition
d
My solution computed the distance for all points already, so when I got to part 2 I flipped the starting point, easy peasy
Yes that’s correct
j
At this time I lost track on how many times I reimplemented BFS from scratch, just for the fun of doing it over and over again 🙂
m
@Dan Fingal-Surma you could make your frontier a sortedSet so that you aren't searching your entire frontier every single iteration
d
You can use java.util.PriorityQueue but you can't use sorted set
Sorted set requires a total ordering over all elements, it would dedupe same distances
j
what would you gain from Priority Queue that ArrayList does not provide?
d
Dijkstra reduces to BFS when all weights are the same
So you can just use a queue (ArrayDeque)
But I had Dijkstra handy
c
Wrote my own A* for part 1, then had to re-write it to breadth-first for part 2. What I get for not already writing my own utils for either before today.
m
mhh I thought sortedsets worked like normal sets (on equality and hashcode of the classes) but you right, has to be PQ then
d
A* is overkill 😄
Last year I kept thinking I needed A* and plain Dijkstra kept coming up
m
I don't think there was ever a year A* was needed I think, BFS hath always been enough
j
I don’t get it, anything outside BFS with plain ArrayList as a queue seems way overkill for this puzzle :)
c
for part 1 you have a specified start and end so it's just sorting a priority queue by fitness. But I didn't think ahead enough on how part 2 could have rolled out, which in hindsight obviously had to change either your start or end conditions in some way
d
I copy pasted problem 15 2021 which required Dijkstra because weights varied by vertex
m
@Jakub Gwóźdź it depends how you define your 'to visit' nodes. You can do it in a single queue like @Dan Fingal-Surma and have your count embedded in a class or You can do it in a sequence of queues where you keep track of your count and just update your 'to visit' nodes based on its neighbours
n
A* has no benefit since the graph isn't weighted. Dijkstra turns into BFS, but slower. I found DFS to be faster, actually, though I didn't really benchmark it (just used java timers).
m
the former needs a PQ for performance, the latter not
d
Last year I moved Problem 15's solution from PQ to Set with minByOrNull so as to be pure Kotlin, no Java imports. The frontiers are small enough that the perf is acceptable
Yeah in Dijkstra the natural thing to do is label each vertex with its min distance
m
yeah but the stuff isn't weighted anyways
every step is one further from the previous
n
My Dijkstra uses the java.util PQ, and my BFS/DFS use the java.util ArrayDeque. I actually implemented my own Binary Heap, but that version is slightly slower than the Java PQ. In part because it uses Lists instead of Arrays, due to it being really hard (impossible?) to have an empty generic Array in Kotlin.
d
right
j
Ok so I have it split into different files, but the general idea for BFS is like this. Probably I could gain something by sorting the 
possibleUp
output by the distance to “E”, but it does not seem to be worth the effort.
Untitled.kt
s
Spent so much time figuring out that you can also go down.
d
Probably I could gain something by sorting the  possibleUp output by the distance to "E", but it does not seem to be worth the effort.
— then you have A* haha
As Michael said, unnecessary for unweighted graphs, and for small graphs generally
e
dumb bug: I originally had 
b - a <= 1
(where 
a: Char
, 
b: Char
) as my condition, but that allows for stepping from 
'x' -> 'E'
. took me waaay too long to track down…
initially I just did part 2 by running part 1 on every 
'a'
. it worked but I realized soon after that I could just run the search in reverse
no Dijkstra or A*; plain BFS is enough for today
j
@ephemient hah this one I guarded at the beginning, checking if both are 
.isLowerCase
🙂
l
I switched everything to ints to avoid those bugs 😅
d
Alright I converted my code to direct BFS, no labeling the vertexes themselves with distances, ends up with slightly more code (edit: managed to shave excess lines)
Copy code
fun findShortedPath(target: Char): Int? {
        val end = vertexes.flatten().single { it.code == 'E' }
        val frontier = ArrayDeque<Pair<Vertex, Int>>(listOf(end to 0))
        val seen = mutableSetOf<Vertex>(end)
        while (!frontier.isEmpty()) {
            val (vertex, distance) = frontier.removeFirst()
            if (vertex.code == target) return distance
            vertex.neighbors().filter { it.height + 1 >= vertex.height }.forEach { 
                if (seen.add(it)) frontier.add(it to distance + 1)
            }
        }
        return null
    }
n
@Michael de Kaste
I don't think there was ever a year A* was needed I think, BFS hath always been enough
There have definitely been weighted graphs where regular BFS won't work. 2018 Day 22 being a good example. But you're right that A* has never been needed. I only used it twice (2018 Day 22 and 2021 Day 15) and it only made a big change for the 2018 one.
z
Do all real inputs have this wall of `b`s as the second column (and no `b`s anywhere else)? I used this to be lazy and just perform the search written in part 1 from all the `a`s at the beginning of each row for part 2 and take the min of those. Edit: here's my solution given that assumption https://github.com/zsmb13/advent-of-code-2022/blob/main/src/Day12.kt
d
Yeah mine looks like that
n
That is a neat optimization! But neater still is to run the BFS in reverse and grab all the 'a's in one search. Not that I did either in my initial solution. 🙂
o
https://github.com/Oziomajnr/AdventOfCodeSolutions/blob/main/solutions/src/year_2022/day12/ShortestPath.kt Reused solution from day 15 last year Dijkstra… modeled the input as a graph with the lowest point having a height of 1… If the lowest point has a height of zero, it would not work because there would be no cost for going through that part. Apparently simple bfs would work too but I didn’t think of it until someone told me.
d
So happy I implemented an A* algorithm for day 15 of last year 🌻 And of course probs to mr E.W.D.

https://i.kym-cdn.com/photos/images/original/002/472/808/623.png▾

Here is a visualization of the route I also made last year for d15:
s
p
d
Decided to have some fun with the visualization:
It's a 'relief map' with blue being 'lowest' and red being 'highest' (going through cyan, green, yellow, magenta) with the route in black starting from the a in the left
It's funny to see it can almost make landfall at the bottom left edge of the 'island' but has to go around to get to some higher ground to enter the shallow waters as it can not jump from c to f
It only has to jump down once, from s in the middle right to q, then loop around to v, this jumping down may trip up some solutions I guess 😉
f
cool @Davio!
d
I used ANSII codes to set the background and foreground, basically if you print a control character first, then you can easily set background and foreground color, see: https://www.lihaoyi.com/post/BuildyourownCommandLinewithANSIescapecodes.html, just don't forget to print an ANSII reset where applicable (you can print it after each character to be safe)
I also set my IntelliJ console font to a monospaced font (my default font is Fira Sans with ligatures) with a line height of 1
o
Nice
d
You can set your line height to something like 
0.8
to make it look more like an actual square, your choice 🙂
f
@Davio I tried your code:
also: waiting for @Olaf Gottschalk to come up with something amazing 😉
d
@Fredrik Rødland you have one jump down as well, from k to i, I reckon this is intentional to mess up algorithms who thought it was monotonically increasing
I don't know whether it's a coincidence but in my case the new starting location was actually next to the one from part 1 😮 and the path was only 1 step shorter
k
@Davio same here, it actually cost me some points cause I thought I had done something wrong. (Did you also have 481/480)
d
No, I had 350 and 349
Maybe it's just a side effect of how the input is generated, could be that they work backwards from the 'island' to the start and just branch off somewhere close to the original start
c
My part 2 was only 1 less than part 1 as well. Just nabbed my solution from Day 15 last year.
m
My part 2
f
mine was 5 shorter - you can actually see it above - the part1 path goes up 6 a's in the start
d
I remember from last year when I tried to manually craft a search algorithm that it would refuse to go back, it would only ever want to go in the direction of the goal (either right or down if it was to the right and down of the start) so I'm glad I solved that issue last year and could reuse it this time 😄
r
Going to clean it up later - I just used 
BFS
https://github.com/ritesh-singh/aoc-2022-kotlin/blob/main/src/day12/Day12.kt But - i had missed this part initially and only read the statement in bold 
This also means that the elevation of the destination square can be much lower than the elevation of your current square.
a
I don’t get why it is wrong path. 😄 Still trying to debug first part of the solution.
r
C->E is wrong 
the elevation of the destination square can be at most one higher
a
it is D -> E
r
message has been deleted
a
Yeah @ritesh it is going right to to c -> then top -> c -> d -> e back to the bottom
)))
r
Ohh okay, i thought its down -> top. My bad.
z
@Alex J. "the best signal (
E
) has elevation 
z
." This got me too, made 2 extra steps because of it...
a
Hmm need to check
Thank you
d
My A* algorithm counts the number of nodes (actually it generates a list of all visited nodes including start and end), so for the number of actual steps I needed to subtract 1 at the end
f
@Davio I modified your print-function a tad to better match my data structure by letting it accept functions for: • which character to print and • which colour to have as to background. given a Position (x,y) https://github.com/fmmr/advent/blob/master/src/main/kotlin/no/rodland/advent/IntGrid.kt#L47-L75 I call it like this:
Copy code
grid.printRoute(
            { p -> (grid[p] - 'a'.code).toDouble() / ('z'.code - 'a'.code) },
            { p: Pos -> if (p in shortestPath) Char(grid[p]) else ' ' }
        )
d
👍
p
Dusted off my 2021-Day15 Dijkstra and adapted to BFS.
Day12.kt
k
n
Welp, after pooping all over A* and (to a lesser extent) @zsmb's optimization, I came to the realization that 1) A* works really well here, just keeping the search moving towards the goal; and 2) that knowing all the possible a's are on the far left makes for a killer heuristic, just using the x value. Such that two goal-directed A* searches are about the same speed as one general BFS.
e
I thought a bit more and realized I could get both parts done in a single pass
f
@ephemient because the path in part 2 is contained in the path of part 1 (which it is in several examples here), or as a more general solution?
e
both parts can be solved by starting at 
E
and finding the shortest path to 
S
or 
a
. if we just keep going until we find both, the total time taken is less than searching from 
S
to 
E
- at least on my input
n
That's easy to do with my solution because my BFS returns full path of nodes visited, so I can just search for 'S' and grab the first 'a' along that path. But it's inconsequential for my input as it only culls about 150 nodes from the search rather than searching the entire space from 'E'.
e
that's not necessarily the correct thing to do:
Copy code
Ezxy...cbbaS
........a...
the first 
a
along the path to 
S
is not the nearest 
a
what I mean is that with a BFS starting from 
E
, you do visit the first 
a
first, and then the 
S
. since I'm always looking for 
S
anyway, finding the 
a
during the search means I don't have to do an additional search for it
f
nod and you know the path to S is longer since S is a in height. so you can store the path the first time you see any a. <- just trying to wrap my head around this
e
since my BFS returns a sequence of everything it visits in order, this is easy. https://github.com/ephemient/aoc2022/blob/main/kt/src/commonMain/kotlin/com/github/ephemient/aoc2022/Day12.kt
n
Sorry, I mispoke. My BFS doesn't just return the path but every node that it has visited until it hits the end condition.
t
I did BFS for both parts. Part two starts at the end and stops when it finds any of the low points. The BFS function itself takes in the starting point, a predicate to determine if we’ve found the goal, and a function to determine if we’re allowed to move between spots. Overall I’m pretty happy with my solution. • Blog • Code
n
@ephemient But I like your way better. This year's AoC is the first time I'm really getting into the power of Sequences. My BFS/DFS/Dijkstra all take an endCondition function, then they do a check within the main loop every time. Even if there is no endCondition, then it just uses a default function that returns null. It's very kludgy. Much better to isolate the traversal in a sequence and then you can do whatever you want with it by adding conditions to the sequence.
k
Part 2

https://www.youtube.com/watch?v=W2bfIi44_3k▾

Part 1

https://www.youtube.com/watch?v=n-BwCHhT_1E▾

a
I was stuck in Day 12 Part 1 only to find out now that I am allowed to take a step down of any size. In my case from r downto p. Why? 😢
m
11 Views
Open in Slack
PreviousNext
Powered by