https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2021 day 18> :thread:
# advent-of-code
a
e
Brutal. If I were to give such a problem on a traditional programming competition, I’d be hated for the rest of my life by sports programming community. But, frankly, I personally like problems of this kind. They are truly about writing code.
👍 2
j
All about finding the right data structure, and of course I choose wrong one at the beginning 🙂 But it was fun.
e
When performance does not really matter, data structures are not a big deal. Here you can literally do whatever the problem says, copying and replacing all the time.
j
aye, but when I first parsed it into neat tree of Pairs of Pairs etc, I suddenly realised that it’s hard to find the “first regular number to the left of the exploding pair” 🤷
e
You can just flatten regulars from tree to a list, keeping the exploded pair unflattenned, so that you can find its index in the list to see what is to the left and the right of it.
j
ah yes, indeed
k
All of these sea animals are so knowledgeable 😂
n
I initially parsed this into a tree, but then decided to start over again and solved everything using regex. That went pretty well.
😱 1
e.g. finding the last number to the left of the "level 5" is
Copy code
val mb = Regex("""(.+?)(\d+)([^\d]+)""").matchEntire(before)
if (mb == null) {
    append(before)
} else {
    append("${mb.groupValues[1]}${mb.groupValues[2].toInt() + left.toInt()}${mb.groupValues[3]}")
}
(where 
left
is a match from the regex matching the beginning of the level-5)
about 100 lines (with some test samples) and runs both parts in under 1.5 seconds
This could be even nicer if there were a ``replaceFirst(input: CharSequence, transform: (MatchResult) -> CharSequence): String` in 
Regex
. But the 
replaceFirst
only exists for simple replacement strings.
youtrack 4
❤️ 1
Is there a smarter way for part 2 than looping over all the lines nested to test all the combinations?
e
@nkiesel The cleanest I came with:
Copy code
buildList {
    for (i in a.indices) for (j in a.indices) if (i != j)
        add(add(a[i], a[j]).magnitude())
}.maxOrNull()!!
n
is that better than 
a.forEachIndexed { i1, f1 -> a.forEachIndexed { i2, f2 -> ...
? BTW: I created a 
infix operator fun plus(other: Fish) = Fish("[$this,$other]").reduced()
to use 
add((a[i] + a[j]).magnitude())
final Q: I right now compute the sum of fishes using 
input.map { Fish(it) }.reduce { acc, fish -> acc + fish }
. Why can't I use 
input.sumOf { Fish(it) }
?
j
I’m pretty happy with
Copy code
l.flatMap { l1 -> l.map { l2 -> addition(l1, l2) } }
                .maxOf { it.magnitude() }
l
- list of inputs
n
but that would add the same lines as well, no?
true story 1
you would then need
Copy code
val fish = input.mapIndexed { i, f -> i to Fish(f) }.toMap()
return fish.flatMap { (i, f) -> (fish - i).let { g -> g.values.map { f + it } } }.maxOf { it.magnitude() }
k
I got the parsing down if anyone wants to take a look. Haven't finished explosion/splitting yet. Will try again tomorrow (3AM here): https://github.com/Kietyo/advent_of_code_2021_v2/blob/main/src/day18.kt
See 
parseSnailNode
for details
m
e
https://github.com/ephemient/aoc2021/blob/main/kt/src/commonMain/kotlin/com/github/ephemient/aoc2021/Day18.kt I've tried this solution multiple ways - working on a tree, manipulating a stream of tokens, or regex - and I'm not sure which approach I like best. the tree solution I've used here feels overengineered but the other approaches are more annoying to write in Kotlin, so that's what I'll leave it as for now.
also darn, I'm over 1 second of total runtime (all days all parts) in Haskell, Kotlin (JVM), and Python; only Kotlin (GraalVM native-image) and Rust are below, and GraalVM is pretty close to the limit… time to look into some more optimization
m
Needs some refactoring. Should have defined a separate class for the root node without a parent, so that the others have a non-null one 🙂 And I’m not using the sealed class hierarchy quite as well as I could 🙂 https://github.com/MikeEnRegalia/AdventOfCode2021/blob/main/kotlin/src/main/kotlin/Day18.kt
d
I have code that works on most of the test inputs until the second addition of the last example. Gonna have to debug later since that addition has many, many reduction steps.
And of course it’s a pointer tracking bug… forgot to update parent of new leaf nodes on split (using maximally mutable, single Node class)
My terrible code that got me to a solution — may refactor later or may never touch again: https://github.com/dfings/advent-of-code/blob/main/src/2021/problem_18.main.kts
I flatten to an in-order traversed list and seek rather than walking the tree directly
n
Having looked at many of the skillful other solutions, I still like my regex-based approach mostly for it's simplicity and the 1:1 match with the requirements (although I'm sure it is slower because of the repeated regex matching).
e
I just updated all my solutions to operate on a flat list of tokens, it's faster and simpler. (except my python solution, regex runs faster than plain python code apparently)
the lack of 
fun MutableList<T>.splice(IntRange, Iterable<T>)
is annoying though
n
@ephemient: I liked your "sequence" idea for part 2 so I stole it (with credit :-)
m
Managed to refactor my solution - now at 96/82 lines. Pretty happy with it actually. NEVER touching it again 🙂 https://github.com/MikeEnRegalia/AdventOfCode2021/blob/main/kotlin/src/main/kotlin/Day18.kt
Damn - now that I’m looking at it I see that the parent attribute should be in the base interface. The refactoring never stops 😉
d
Mutating the type of node in place was simpler logic
(no need to update the parent)
m
Yes, that’s maybe not as nice from a typing standpoint, but much faster to code. Just build a node that’s fit for all eventualities 🙂
d
Lol yeah, limiting factor is "can I get something that works?"
😎 1
I have these hanging around in my Project Euler repo:
Copy code
infix fun <T, U> Sequence<T>.cartesianProduct(other: Sequence<U>): Sequence<Pair<T, U>> =
  this.flatMap { i -> other.map { j -> i to j } }
  
infix fun <T, U> Iterable<T>.cartesianProduct(other: Iterable<U>): Sequence<Pair<T, U>> =
  this.asSequence() cartesianProduct other.asSequence()
k
j
I did it using tree and thanks to sealed class that Kotlin provide, love it! https://github.com/Jintin/AdventCode2021/blob/main/src/Day18.kt
p
Busy weekend: https://github.com/PaulWoitaschek/Advent-of-Code-2021/blob/main/src/main/kotlin/aoc/day18/Day18.kt At first I had a oop oriented solution with a sealed interface but it turned out way simpler just operating on the strings
p
@Paul Woitaschek looks like we had the same flow 🙂
🙌 1
t
Not a fan of this one. Mostly because I battled a stupid bug that was my fault and I had fallen behind due to travel. But it’s done. • Code • Blog
n
Whew, I’m days behind and this one was the hardest yet for me. @nkiesel here’s how I created the combinations for part two:
Copy code
buildList {
    for (i in 1 until a.size) for (j in 0 until i-1)
        add(Pair(a[i], a[j]))
}
e
you could golf that down to
Copy code
buildList { a.forEachIndexed { i, x -> a.subList(0, i).mapTo(this, x::to) } }
although this particular puzzle needs all 
n * (n - 1)
pairs, not just half of them
n
Excellent point… I overlooked that and got lucky that I found the solution.
4 Views
Open in Slack
PreviousNext
Powered by