https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2024 day 1> (spoilers) :thread:
# advent-of-code
a
🎄 1
m
Part 1
Part 2
Looking forward to seeing a shorter way of parsing the list than the two substrings. 😄
n
Both shorter and longer:
Copy code
val (a, b) = input.getIntList().collate(2)
m
sadly you cannot destructure in a class and letting 'parsed' be a Pair<List<Int>, List<Int>> also didn't feel right to me.
Untitled.cpp
n
It really bothers me that you cannot destructure in a class.
k
This is my solution. I tried to go too fast and didn't read that I had to sort, and when I did I added the transpose and forgot the second one, and because kotlin doesn't throw an error when you destructure a list of a 1000 items into only 2 values, unlike python so I submitted a second wrong answer.
n
what do the "log 1" and "log 2" things do? Are they infix functions for logging the value somewhere?
k
yeah, they are supposed to also put the answer in my clipboard, but that didn't seem to work.
I use a lot of util functions to go fast 😛
n
Not a lot of room for people to do things differently. Mine's basically the same as the rest:
m
You need a 
sleep(200)
. If your process finishes immediately after trying to put something into the clipboard, it doesn't apply.
m
I forgot to add my input parsing utils to my current library this year blob nervous
k
I added a feature to my 'log' function in my archive version last year, and I noticed it wasn't in my main project version, so I copied it over, but forgot that I had to readd the copying 😕
m
I like the 
ints()
and 
getIntList()
helpers you all have, I'll have to borrow the idea.
b
i stole them last year...
m
@Neil Banman sad kotlin noises K sad panda
b
arrow has a nice 
unzip
oh, i updated arrow and now it's deprecated 💩
a
I'm so glad Kotlin has an unzip ❤️ for part Two, I used a mutable map with 
.getOrPut()
so that counting does not repeat for each repeated number in the left list; since the repeated number would occur the same number of times in the right list.
same 1
n
My helper functions are
Copy code
fun String.ints() = Regex("""-?\d+""").findAll(this).map { it.value.toInt() }.toList()
fun String.longs() = Regex("""-?\d+""").findAll(this).map { it.value.toLong() }.toList()
j
somehow I forgot about .eachCount() and ended up with
Copy code
private fun List<Long>.frequencies(): Map<Long, Int> =
    buildMap<Long, Int> { this@frequencies.forEach { compute(it) { _, u -> (u ?: 0) + 1 } } }
but anyway, it's a nice warmup challenge, just to get re-acquainted with stdlibs. Could be as well done in a spreadsheet 🙂
p
Nice warmup to get reminded of the 
zip
function 👌
👍 2
j
so... overall is it a O(N*logN) or am I missing something?
a
I used a mutable map with 
.getOrPut()
so that counting does not repeat
I wonder if two 
getEachCount
(not nested) would be better. so then 
sum of x * rightListCount[x] * leftListCount[x]
j
@Anirudh you'd need to go through whole left list anyway first, just to get counts...
ah
but if there is a repetition, you'd save on lookup in right conters
(so yes, it theoretically would help, but there is no repetition on left list in my input)
a
as far as I can see, there's some repetition: 
(35412, 20), (26729, 20), (88579, 19), (89301, 19)
but only about 30 items have any repeats so maybe pre-counting doesn't save much. and with just 1,000 items in the actual input; these optimisations won't save much
j
nah, for thousand items it even works well without any pre-counting, just plain O(N^2), but we aren't here for the easy, so if we gain several processor ticks by counting right column, we might as well count the left one 🙂
⬆️ 1
a
ok, so I re-verified my input: my left side has no repetitions, so pre-counting the left side wouldn't help. and on the right side, we're expecting numbers to repeat (since that's what we're checking).
d
j
but since we have the right list already sorted from the part1, we can make the counting a bit quicker than the groupingBy:
Copy code
private fun List<Long>.frequencies(): Map<Long, Int> = buildList<Pair<Long, Int>> {
    this@frequencies.forEach { l ->
        if (isNotEmpty() && last().first == l) add(l to removeLast().second + 1)
        else add(l to 1)
    }
}.toMap()
d
I just did:
Copy code
val frequencies = secondList.groupBy { it }.mapValues { it.value.size }
m
since we have the right list already sorted from the part1
Well, depending on your approach. I keep my part1 and part2 solutions separate, they have nothing in common. Makes the part 2 solution cleaner since the code doesn't need to solve part 1 anymore. But that results in more code overall, of course, since similarities end up duplicated across the two solutions.
p
A nice start to advent 🙂
Day01.kt
very nice 1
j
same, same. My setup is parsing for part2 from start, but still, I'm looking for all possible optimizations. This is the charm of first AoC days each year, isn't it. Further in the event, the approach would be more like "ah, damn it, whatever works" 🙂
😄 4
oh. and indeed for part 2 we don't have to parse the right column to ints! (although it's probably faster for map lookup)
n
I do this differently in my two langs (Rust and Kotlin). With Kotlin the slowness bothers me so at least when I refactor I usually try to do any shared parsing just once. Every day is in its own class so it's easy to have shared values. In Rust, parsing takes almost no time and sharing values is a pain, so I usually reparse for each part. Today I reparsed for both parts, because like @Michael de Kaste said, you can't destructure in a class, and it makes for really awkward init code in cases like today.
t
Violating Rule #4, but maximizing Rule #2 of the 4 Rules of Simple Design 😬
😅 1
😇 1
k
Copy code
fun main() {
    val s1 = mutableListOf<Int>() // List to store numbers from the first column
    val s2 = mutableListOf<Int>() // List to store numbers from the second column

    fun load(fileName: String) {
        s1.clear()
        s2.clear()
        readInput(fileName).map { line ->
            line.split(Regex("\\s+")) // Split the line by whitespace
                .map(String::toInt) // Convert strings to integers
                .let { (e1, e2) -> s1.add(e1); s2.add(e2) } // Add to respective lists
        }
    }

    fun part1(): Int {
        s1.sort() // Sort the first list
        s2.sort() // Sort the second list
        return (s1 zip s2).sumOf { (a, b) -> (a - b).absoluteValue }
    }


    fun part2(): Int {
        val map = s2.groupingBy { it }.eachCount()
        return s1.sumOf { it * (map[it] ?: 0) }
    }

    // Load input for the test case and verify the results
    load("Day01_test")

    part1().let { result ->
        println("result1 = $result")
        check(result == 11) { "part1 Day01_test" }
    }

    part2().let { result ->
        println("result2 = $result")
        check(result == 31) { "part2 Day01_test" }
    }

    // Load the actual input and solve the puzzle
    load("Day01")

    part1().println()
    part2().println()
}
p
k
@Jakub Gwóźdź The complexity of your solution (part2, pre-sorted by part1 list) is O(n^2), but groupingBy is O(n) because it works with hashMaps! worst case: Imagine I give you two lists that have no elements in common!
j
Challenge accepted. I think, that if the lists are pre-sorted, I can make it in O(N). (will edit this comment with solution in ~10 minutes 🙂 ) EDIT: Yeah, probably can be done more idiomatic, but it's O(N), assuming both 
left
and 
right
are sorted (and left is unique, as in puzzle input)
Copy code
fun part1(left: List<Long>, right: List<Long>): Long = left.asSequence()
    .zip(right.asSequence()) { l, r -> abs(r - l) }
    .sum()

fun part2(left: List<Long>, right: List<Long>): Long = left.fold(0 to 0L) { a, l ->
    var (j, s) = a
    while (j < right.size && right[j] < l) j++
    while (j < right.size && right[j] == l) j++.also { s = s + l }
    j to s
}.second
t
Happy Advent of Code 2024 everybody! Mine looks mostly similar to a lot of the ones here I guess. I'm going to try blogging solutions again this year but I'm somewhat busier this month than in years past so we'll see how it goes. :) • Blog • Code
🎉 1
K 2
advent of code intensifies 1
p
Very cool that you again write a blog post for every puzzle besides solving it.
thank you color 1
p
d
nice, I like 
secondList.groupingBy { it }.eachCount()
better than 
secondList.groupBy { it }.mapValues { it.value.size }
k
I lost a full minute because I destructured something wrong and kotlin doesn't give you an error, unlike python, so I spend a few hours trying to understand how compiler plugins work. After writing some of the worst code I have ever seen: I now get warnings if something looks off.
Screen Recording 2024-12-01 220941.mp4
t
Fun! I got to use 
zipWithNext
which is always a good time. Brute forced the second part because it's day 2 and we can get away with things like that. I lost a bit of time (not that I'm trying for the leaderboard by any stretch) because for the actual input, I was running it against my Day 1 class (yay cut and paste errors) and it was actually giving a result, haha. Wrong result, but still. Kinda funny looking back at it. * Code * Blog
e
m
I’m trying to collect all puzzles in a single desktop app with nice viz. So far, I’ve tackled the first day. What’s your thoughts?
Screen Recording 2024-12-16 at 22.52.40.mov
❤️ 2
j
This is sooo cool!!! ❤️ ❤️ ❤️
29 Views
Open in Slack
PreviousNext
Powered by