https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2024 day 5> (spoilers) :thread:
# advent-of-code
a
j
Part 1 was pretty straight forward, I struggeled a bit with computing the ordering for part 2, but building a comperator out of the pair of orderings is a working solution. Other trick is to get the middle of a list (always odd length) just use 
list.size/2
as index https://github.com/bulldog98/advent-of-code/blob/main/advent2024/src/main/kotlin/year2024/Day05.kt
m
Part 1
Part 2
y
Comparators today are very handy!
👍 3
m
Good idea with using comparators, maybe I shouldn't have done it by hand!
y
@Marcin Wisniowski I first thought of writing loop in a loop and the realized that it's basically bubble sort, so why not just use the builtin one 🙂
m
I guess my advantage is that I can change the outer loop to 
for (i in 0..(new.size / 2)) {
and avoid the useless sorting of the second half of the list. 😄
Part 2 cleanup
y
m
Had some struggles this morning getting my input parsing to work, my splitOnEmptyLine was configured incorrectly and I also thought the assignment was way harder then it ended up being (I thought keyOrdering could also be 1 -> 2 and 2 -> 3 meaning 1 -> 3 implicitly)
Day_5_Michael.cpp
r
Just showing my helper functions here, the solving part is straightforward (parse input, parse rules to a map, use sumOf with the helper functions) The interesting bit is that in part 2, I counted the number of pages from the current update for every page in the update and then used a comparator from those counters
Untitled.kt
🤔 1
b
probably slow, but my first thought was to use recursion to sort the pages
Untitled
if i was more familiar with comparators that would have been better
odd little ide bug?
j
Both parts basically the same: build comparator, sort each update. If sorted is the same as original - it's filtered for part 1, if sorted is different -> taken for part 2
Untitled.cpp
👍 1
@bj0 no bug, you need to specifically make it 
buildMap<String, MutableSet<String>>
, otherwise it's immutable soon after it leaves the lambda in getOrPut
b
it compiles and runs just fine...
j
oh?
so probably a bug 🙂 or K1/K2 discrepancies
m
buildMap type inferencing has been a bit awkward since the start, I've had this happen many times.
l
I use a comparator but i couldn't find a 
isSortedWith(comparator)
function so I wrote it myself as extension but I feel like I might have missed something. What do you think ?
m
Sadly, there is no 'IsSorted' in the stdlib, best scenario is to actually sort and then compare
🙏 1
l
I did sort and compare at first but then I tried is that way to avoid sorting the full list
Copy code
fun <T> List<T>.isSortedWith(comparator: Comparator<T>): Boolean {
    return asSequence().zipWithNext().all { comparator.compare(it.first, it.second) <= 0 }
}
p
That went quicker than expected. My instinct was to write a comparator that uses the list of rules, and then compare the sorted list with the original. Glad that instinct bore out for part2 as I had a 69sec delta time for star 2 🤩
Day05.kt
a
finally wrote a SAM in AoC. since my 
beforePages
was already defined for part 1, my part 2 comparator was:
Copy code
private val pageComparator = Comparator<Int> { a, b ->
    when {
        b in beforePages[a].orEmpty() -> -1
        a in beforePages[b].orEmpty() -> 1
        else -> 0
    }
}
the IDE/compiler should have a hint for looking up a Map where values are Sets. so this:
Copy code
beforePages.getOrDefault(page, emptySet())
can be replaced with:
Copy code
beforePages[page].orEmpty()
e
Managed to reduce the code size a bit. First I've created two maps (the onLeft and onRight) and used both. That solved the first part. For second part, I've figured out the comparator then refactored first part as well. Later figured only the onLeft map should be enough. Happy with the final result:
Copy code
solve("Print Queue") {
        val (rules, queue) = text
            .split("\n\n")
            .let { it[0].split("\n") to it[1].split("\n") }
            .let { (f, s) -> f.map { it.ints() }.groupBy({ it[0] }) { it[1] } to s.map { it.ints() } }

        val comparator = Comparator<Int> { l, r -> rules[l]?.let { if (r in it) -1 else 1 } ?: 0 }

        part1() {
            queue
                .filter { it == it.sortedWith(comparator) }
                .sumOf { it.middle() }
        }

        part2() {
            queue
                .filter { it != it.sortedWith(comparator) }
                .map { it.sortedWith(comparator) }
                .sumOf { it.middle() }
        }
    }
d
Interesting problem! I ended up implementing my own sort because I wasn’t sure whether the comparator approach would work, as we didn’t have a strict ordering. https://github.com/dfings/advent-of-code/blob/main/src/2024/problem_5.main.kts
Comparator’s documentation very clearly states 
imposes a _total ordering_
p
I switched my comparator to using a Map and implemented a 
Comparator<T>.isSorted
fun.
Copy code
Warming up 2 puzzles for 5s each for year 2024 day 5...
	Default warmed up with 635 iterations
	Map warmed up with 9540 iterations
year 2024 day 5 part 1
	 Map took 219.608us (1.00x): 4790
	 Default took 3.561533ms (16.22x): 4790
year 2024 day 5 part 2
	 Map took 345.216us (1.00x): 6319
	 Default took 3.397258ms (9.84x): 6319
slightly improved performance
Day05Map.kt
d
I used forward/reverse mappings for the rules as they were needed in different cases and I worried about the time complexity of scanning the entire rule set for violations.
p
I wasn't sure if the rules were reflective but afair 
compare(a, b) === -compare(b, a)
is a requirement of a comparator
d
I was worried about 
compare(a, b) == 0
, 
compare(a, c) == 0
, but 
compare(b, c) == 1
. In general it warns about returning 0 inconsistent with equals.
m
iirc you'll get a runtime exception if the reflectiveness property of a comparator breaks
a
similar to ⬆️ , my concern with using Comparators in AoC is that lists aren't "complete". so if 4 & 5 are in Pages but neither are in Rules, then 4 < 5 and 5 < 4 4 == 5 (edited the brainfart) ie unmentioned pages can have any order so what if it ends up in the middle? but it seems to work out for today's inputs; or Mr. Wastl thought of that already and decided not to create such situations
d
I think the Comparator returns 0 for (4, 5)
✅ 1
a
yes, you're right. 4 == 5 but then what happens to sort order? 3, 4, 5 and 3, 5, 4 are both "sorted" but the middle is different (in Python, it would keep the input order for two things which are equal, which can become a WAT when reversed) it's not guaranteed that 
reversed(sorted(lst)) == sorted(lst, reverse=True)
p
j
If only I had read the task properly (again) and noticed that only rules with both sides in the "update" should be applied, I wouldn't need to spend over an hour debugging why I have a loop in ordering rules 🤦 I finally ended up with https://github.com/jandurovec/adventofcode-in-kotlin/blob/main/src/aoc2024/Day05.kt but I'd still like to find out if there is some more elegant (i.e. not so "procedural") way of pre-computing the "higher" map for Comparator to use.
d
If the sort algorithm is stable, order of equivalent elements will be unchanged
👍 1
a
okay, good to know thank you color I haven't tested that much in Kotlin
m
I did it the lazy way without using comparators. Simply swap the two elements of a failing rule and loop until all rules are valid. I wasn't sure if this would work or get stuck in an infinite loop but it does work (at least for my input). Not the fastest solution though, part 2 takes ~130ms.
r
I built a graph using pages and rules, and did a topological sort on part 2
j
after all, whole .groupBy or similar to build maps for ordering was unnecessary. Turns out it's enough to just parse ordering to a Set<Pair<Long,Long>> and Bob is your uncle, the comparator looks like this:
Copy code
val ordering = lines.takeWhile(String::isNotBlank).map { it.split("|").let { (a, b) -> a.toLong() to b.toLong() } }.toSet()

fun <T> comparator(ordering: Set<Pair<T, T>>) = Comparator<T> { o1, o2 ->
    when {
        (o1 to o2) in ordering -> -1
        (o2 to o1) in ordering -> 1
        else -> 0
    }
}
p
@Jakub Gwóźdź I would guess creating one or two Pair instance would cost more than the groupBy approach
j
it's linear, no memory cost, and can be always refactored to 
p = o1.shl(4)+o2
if creating a pair be a major problem 🙂
p
It does lead to using the classic data structure for AoC: the BitSet:
Copy code
Warming up 3 puzzles for 5s each for year 2024 day 5...
	BitSet warmed up with 13237 iterations
	Default warmed up with 617 iterations
	Map warmed up with 10242 iterations
year 2024 day 5 part 1
	 BitSet took 168.2us 👑: 4790
	 Map took 207.94us (1.24x): 4790
	 Default took 4.067499ms (24.18x): 4790
year 2024 day 5 part 2
	 BitSet took 189.803us 👑: 6319
	 Map took 280.196us (1.48x): 6319
	 Default took 4.067117ms (21.43x): 6319
with comparator:
Copy code
infix fun Int.merge(other: Int): Int = or(other shl 7)
fun BitSet.asComparator(): Comparator<Int> = Comparator { o1, o2 ->
    when {
        get(o1 merge o2) -> -1
        get(o2 merge o1) -> 1
        else -> 0
    }
}

val comparator = BitSet().apply {
    for (rule in rules) {
        rule.splitInts('|')
            .also { (a, b) -> set(a merge  b) }
    }
}.asComparator()
s
This is probably not performant at all, but I was lazy
Copy code
class Day05 {

    fun part1(input: String) = solve(input, true)

    fun part2(input: String) = solve(input, false)

    fun solve(input: String, correct: Boolean): Long {
        val (ordering, updates) = input.split("\n\n")
        val order = ordering.lines().toSet()
        return updates.lines()
            .map { it.split(",") }
            .map { it to it.sortedWith { o1, o2 -> if ("$o1|$o2" in order) -1 else if ("$o2|$o1" in order) 1 else 0 } }
            .filter { (it.first == it.second) == correct }
            .sumOf { it.second[it.second.size / 2].toLong() }
    }
}
e
I got a solution onto the leaderboard pretty fast, but it took me a lot more thinking to convince myself about correctness
p
@Sergei Petunin your solution tends to get ~330us per invocation per part in my "benchmark" sonic
s
Thanks, not so bad as I expected!
u
https://github.com/rceuls/advent-of-code-kotlin/blob/main/src/Day05.kt my solution. Nothing fancy, but it works 🙂. Spent most of my time parsing the actual description, and then lost 30 minutes reading the wrong variable (line instead of this) on line 31 😓
n
This one was not straightforward for my particular brain. I made all kinds of terrible assumptions. Then I decided to sleep on it, came up with an approach while lying in bed, and coded it up from scratch in 15 minutes this morning.
👍 3
c
For Part2, since we can have only one solution, I browse the rules to find the last item until the first item of an incorrectly-ordered update : Executed in : 36.78ms (IO included)
Copy code
val rules = file.readLines()
    .filter { it.contains("|") }
    .map { it.split("|") }
    .map { it[0].toLong() to it[1].toLong() }
    .groupBy({ it.first }, { it.second })

//
//Then for each incorrectly-ordered updates
//

var importantRule = rules
    .filter { rule -> update.any { rule.key == it } }
    .mapValues { it.value.filter { value -> update.any { value == it } } }
    .filter { it.value.isNotEmpty() }

val newUpdate = mutableListOf<Long>()
newUpdate.add(0, update.first { it !in importantRule.keys })

while (true) {
    importantRule = importantRule.filter { it.key != newUpdate.first() }
        .mapValues { it.value.filter { it != newUpdate.first() } }
    newUpdate.add(0, importantRule.filter { it.value.isEmpty() }.keys.first())
    if (newUpdate.size == update.size) break
}
b
Bit late but here's my solution for B. I make a Map<Int, List<Int>> which contains a list of numbers that are illegal if encountered after the key. I keep a set of illegal numbers alongside the earliest index that caused it to be added. So if a number in the set is encountered we need to move it to it's corresponding index. While iterating over the list, I check if the number is in the set, if not I add all illegal numbers for the current number to the set, if the illegal number is already in the set it wont be added. this makes it so that only the oldest indices are stored. If the current number X is in the set, I swap it to its place Xi. Because I'm editing the array it's iterating over some bookkeeping has to be done: • All indices in the set need to be incremented if they are greater than Xi • For all the illegal numbers of X, if they are in the set already their index needs to be updated if its greater than Xi • The remaining illegal numbers need to be added
Untitled.kt
Code is a bit rough but didn't have time today to clean it
I actually now realise this isn't a perfect solution but it did give me the correct solution 😅 Edit: the case I'm thinking about that may not be handled correctly is a case where a number Y at index Yi is moved to index Xi, and some number between Xi and Yi is now illegal because of Y. I'll try it out tomorrow (as it is 2am here)
37 Views
Open in Slack
PreviousNext
Powered by