https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2024 day 10> (spoilers) :thread:
# advent-of-code
a
b
wow an easy one on day 10
they must be warming us up for more graph stuff
j
A nice change of pace for a while 🙂
p
I accidentally implemented part 2 as an error while implementing part 1 :)
same 6
m
A walk in the park. Or rather a hike on the lava island.
j
All about proper data representation. Then both parts differ only by this ".distinct()" call :)
JakubG day 10.kt
m
Yes, I was quite happy my part 1 solution worked for part 2 almost unmodified.
same 1
j
Today I was glad, that I had lots of the graph algorithmus implemented. After cleanup the code looks acceptable https://github.com/bulldog98/advent-of-code/blob/main/advent2024/src/main/kotlin/year2024/Day10.kt
b
a recursive solution
ah the 
reduce
at the end can be 
sumOf { it.size }
, didn't think about the fact that different starts will never produce the same path...
r
Recursive solutions for part 1 and 2
m
wildest time difference between part1 and 2 for me, I somehow couldn't find the logic of how to count all the paths 🙈 slammed my head after I found out
Day 10 Michael.cpp
b
even better, recursive sequence
m
wow an easy one on day 10
Only if you know the algorithm 🙂
b
true, but if you've done aoc in the past you've likely seen it many times, it gets used a lot
m
I kinda 'cheated' because I had a .bfs() function prepared for part 1, it just completely failed on me for part 2 and I couldn't figure out way. Suffering from success I guess 😂
Decided to rewrite it to never do double work, now it runs in 0.5ms total sonic
Day 10_2 Michael.cpp
o
Copy code
import utils.Point
import java.io.File

fun main() {
    val input =
        File("/Users/oogbe/IdeaProjects/AdventOfCodeSolutions/solutions/src/2024/input.txt").readText().split("\n")
    val points = input.mapIndexed { x, s ->
        s.mapIndexed { y, c ->
            Trail(c.digitToInt(), Point(x, y))
        }
    }
    println(
        "Part1: ${
            points.flatten().filter { it.value == 0 }.sumOf {
                calculateScore(
                    it, points, mutableSetOf(), true
                )
            }
        }"
    )
    println(
        "Part2: ${
            points.flatten().filter { it.value == 0 }.sumOf {
                calculateScore(
                    it, points, mutableSetOf(), false
                )
            }
        }"
    )
}

fun calculateScore(trail: Trail, trails: List<List<Trail>>, visited: Set<Point>, part1: Boolean): Int {
    if (trail.value == 9) return 1
    return listOf(0 to 1, 1 to 0, -1 to 0, 0 to -1).map {
        Point(x = trail.position.x + it.first, y = trail.position.y + it.second)
    }.mapNotNull {
        if (it.x in trails.indices && it.y in trails.first().indices
            && !visited.contains(trails[it.x][it.y].position) && trails[it.x][it.y].value - trail.value == 1
        ) {
            (visited as MutableSet).add(it)
            calculateScore(trails[it.x][it.y], trails, if (part1) visited else visited + it, part1)
        } else null
    }.sum()
}

data class Trail(val value: Int, val position: Point)
e
p
That was a fun and easy one. https://github.com/PaulWoitaschek/AdventOfCode/blob/main/2024/src/main/kotlin/aoc/year2024/Day10.kt I initially messed up because my fancy Point class adjacent function also includes diagonals 🙈
n
Part 2 was easier than Part 1, weird.
Except I guess having to write your own nerfed BFS since most libraries are geared to eliminate visited spots. But we're talking 5 or 6 lines...
a
if doing Part 1 the "typical way", you will run into Part 2's answer first (without knowing it)
💯 1
m
true, but if you've done aoc in the past you've likely seen it many times, it gets used a lot
Sure, but I remember how I struggled in my first season of AoC. 😆
> Except I guess having to write your own nerfed BFS since most libraries are geared to eliminate visited spots. But we're talking 5 or 6 lines Two seasons ago I wrote an IDEA template for Dijkstra, but I don't use it anymore since I'm now faster writing it from scratch. Looking at how long it took me today, I should have done a practice run last week ...
e
Day10.kt did part 1 as a DFS at first, then part 2 as a BFS, then refactored part 1 to use the same shared search pas part 2. it worked out quite elegantly I think
a
after cleaning up and refactoring: (forgot that my 
Point.neighbours()
function also returns diagonal points so that cost a bit more time)
Untitled.cpp
e
BFS with a slight modification of building up the paths as well on the way and returning not only the number of 9s in the discovered points, but also with the number of paths found:
Copy code
solve("Hoof It") {
        val input = lines
            .flatMapIndexed { y, l -> l.mapIndexed { x, c -> Coord(x,y) to c} }
            .filter { it.second != '.' }
            .map { it.first to it.second.digitToInt() }
            .associate { it }

        fun Coord.neighbours() =
            input
                .filterKeys { k -> k in this.NEWS().map { n -> n + this} }
                .filterValues { it == input[this]!! + 1 }
                .keys

        fun bfs(start: Coord): Pair<Int, Int> {
            val discovered = mutableSetOf(start)
            val q = ArrayDeque<Pair<Coord, List<Coord>>>()
            q.add(start to listOf(start))
            var count = 0
            while (q.isNotEmpty()) {
                val (curr, path) = q.removeFirst()

                if (input[curr] == 9) { count++ }

                curr.neighbours()
                    .forEach {
                        if (path.none { d -> d == it }) { q.add(it to path.plus(listOf(it))) }
                        if (discovered.none { d -> d == it }) { discovered.add(it) }
                    }
            }

            return discovered.mapNotNull { input[it] }.count { it == 9 } to count
        }

        val bfsResult = input.filterValues { it == 0 }.keys.map { bfs(it) }

        part1() { bfsResult.sumOf { it.first } }
        part2() { bfsResult.sumOf { it.second } }
    }
j
I didn't even try any DFS/BFS, since all step are uniform, just take all zeros, then all adjacent ones, then all adjacent twos etc 🙂 there is an opportunity for DP though, but... meh, too much fuss for too little improvement
e
yeah my whole 
visited
set disappeared after I saw that we were only making 0-1, 1-2, 2-3, etc. steps in both parts
I partition the input into 10 sets (points at height 0, points at height 1, points at height 2, etc.) at the start, and I only have to look at the points in the next height during each pass
same 1
j
I started out writing a very naive implementation, thinking: “Let’s just see if it works for part1, worry about part 2 later”. And surprise, surprise, not only did it work, it made part2 very much a one-liner:
Copy code
val route = "0123456789".toList()   
fun findPaths(cur: Position, routeIndex: Int): Sequence<List<Position>> = when {
    grid[cur] != route[routeIndex] -> emptySequence()
    routeIndex >= route.indices.last -> sequenceOf(listOf(cur))
    else -> Direction.entries.map { cur + it }.asSequence().flatMap { newPos ->
        findPaths(newPos, routeIndex + 1)
    }.map { listOf(cur) + it }
}
d
Blessedly easy after yesterday. I misread and did the part 2 solution for part 1, so when I got to part 2 I just went back in my history. 🤣
same 7
Used dynamic programming from the start, didn’t check whether it’s needed
Quick check says no — runs fine without the caches
I wasn’t going to risk it 🫠
e
the challenge is rather limited in size. each walk goes exactly 10 steps
👍 1
or 9 steps I guess, fencepost error
j
yes, and max 3 new paths from each node (in practice way less)
👍 1
so no matter if I cache or just repeat the calculations, it's around half a second. I guess storing and lookup in hashmap cache has it's own cost that is on par with just repeating steps for such a short paths
I mean, half a millisecond 😆
d
could try a 2d array cache
i didn’t actually check the hit rate either
didn’t matter
e
I do think it's kind of interesting how similar and different my solutions in different languages can be, even when I'm solving them the same way. Haskell vs Kotlin, for example (ignoring other things about how I structured the code)
Copy code
import Data.Monoid
import Data.Set qualified as Set
part1 input = sum $ Set.size <$> bfs Set.singleton (parse input)
part2 input = getSum $ mconcat $ Map.elems $ bfs (const $ Sum 1) (parse input)
Haskell has very generic built-in tools for things like functors, semigroups, and monoids, so e.g. if I 
<>
two `Set`s together, I get their union, and if I 
<>
two `Sum`s together, I get their sum, while
Copy code
val values = // parse
fun part1() = bfs(::setOf, Set<IntPair>::plus).values.sumOf { it.size }
fun part2() = bfs({ 1 }, Int::plus).values.sum()
while Kotlin has no such thing and I have to explicitly refer to each type's 
::plus
, but the syntax prioritizes having things like 
setOf
available without additional imports
👍 2
d
hits: 341 misses: 1517 for part 1
well same for part 2 as you might expect
z
I accidentally implemented part 2 as an error while implementing part 1 🙂
Same here, and in the end my solution goes between part1 or part2 depending on whether the class used for storing points is a 
data
class or not 😄
😁 1
m
Refactored my (overengineered) BFS solution to cover both parts simultaneously in 29 loc (still at https://github.com/MikeEnRegalia/advent-of-code/blob/master/src/main/kotlin/aoc2024/day10.kt)
r
k
Really fun day today. Tidied up a bit: Solution
p
Copy code
Warming up 1 puzzles for 10s each for year 2024 day 10...
	Default warmed up with 35143 iterations
year 2024 day 10 part 1
	 Default took 149.695us 👑: 538
year 2024 day 10 part 2
	 Default took 135.283us 👑: 1110
was happy enough with this solution this morning - but I originally wasted a good 10-15mins fighting the compiler with an FIR lowering exception.
Day10.kt
c
Also solved part 2 by mistake instead of part 1 😂
f
late to the party, but happy with my solution: (runtime: part1 ≈ 883µs, part2 ≈ 600µs)
21 Views
Open in Slack
PreviousNext
Powered by