https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2021 day 14> :thread:
# advent-of-code
a
d
I love it when the lightbulb comes on and I finally figure it out! 💡
m
https://github.com/mdekaste/AdventOfCode2021/blob/main/src/main/kotlin/year2021/day14/Day14.kt lost a lot of time on part 1 debugging because I accidently did 
joinToString{""}
instead of 
joinToString("")
😄 1
d
Still working on it… had what I thought was a nice dynamic programming solution that gets to step 23 quickly and then OOMs
j
Day 14: we’re officially out of brute force sandbox 🙂
💯 3
😅 1
d
Is there an easier way in Kotlin to increment a map value? I can't do 
map.value += 5
since the value might be null so I ended up doing 
map.value = (map.value ?: 0) + 5
. That seems tedious.
Copy code
rules.forEach { rule ->
    pairs.forEach { pair ->
        if (pair.value > 0 && rule.first == pair.key) {
            newPairs[pair.key] = (newPairs[pair.key] ?: 0) - pair.value
            newPairs[pair.key[0] + rule.second] = (newPairs[pair.key[0] + rule.second] ?: 0) + pair.value
            newPairs[rule.second + pair.key[1]] = (newPairs[rule.second + pair.key[1]] ?: 0) + pair.value
            counts[rule.second[0]] = (counts[rule.second[0]] ?: 0) + pair.value
        }
    }
}
e
https://github.com/ephemient/aoc2021/blob/main/kt/src/commonMain/kotlin/com/github/ephemient/aoc2021/Day14.kt planning to optimize this; I can use a LongArray instead of a Map<Char, Long>
@David Whittaker carrying over from Java, no. could define an extension, or use 
map = .withDefault { 0 }; map[value] = map.getValue(value) + 5
🙏 1
m
d
Figured it out, now need to make my code not garbage
K 2
I went with
Copy code
fun <T> MutableMap<T, Long>.increment(key: T, amount: Long) =
    compute(key) { _, v -> (v ?: 0L) + amount }
K 1
e
groupingBy
shines here. No need to do manual incrementing to count and sum up occurrences.
☝️ 2
d
I need to play with that more. I don't understand 
groupingBy
just yet
e
it basically splits an iterable into a per-key iterations with some nice helpers like 
.eachCount()
d
Copy code
fun <T> Iterable<T>.histogram(): Map<T, Long> = groupingBy { it }.eachCount().mapValues { it.value.toLong() }
e
For this problem, the following extension would have helped to make the code even cleaner: https://youtrack.jetbrains.com/issue/KT-50229
👍 2
m
@elizarov I indeed used a fold in my code because I missed a sumOf function. Would love to see GroupingBy work for nearly all iterable functions 🙂
j
looks like AoC-driven design for stdlib!
K 1
m
How do I make eachCount() work with Longs though?
e
Unlike a typical sport programming competition, AoC has way more “business-like” problems. Often, things that you miss in stdlib for AoC might have occurrent is real-life business logic, too.
🙌 1
n
I created a "CountingMap" because that allowed to elegantly initialize the 2 counts I need for my solution (1 for windowed occurrences, one for chars):
Copy code
class CountingMap<T>(
        l: List<T> = emptyList(),
        private val m: MutableMap<T, Long> = mutableMapOf()
    ) : MutableMap<T, Long> by m {
        init {
            l.forEach { inc(it) }
        }

        fun inc(k: T, amount: Long = 1L) {
            m[k] = (m[k] ?: 0L) + amount
        }
    }
m
IMHO something like these would make nice additions to the stdlib:
Copy code
fun <K> Iterable<K>.frequencies() = mutableMapOf<K, Long>().apply { this@frequencies.forEach { inc(it, 1) } }
fun <K> MutableMap<K, Long>.inc(k: K, n: Long) = set(k, get(k)?.let { it + n } ?: n)
💯 1
e
@Michael Böiers 
.eachCount().mapValues { it.toLong() }
🙌 2
m
^ Missed that, was too obvious 😉
e
@Michael Böiers 
frequencies() == groupingBy { it }.eachCount().mapValues { it.toLong() }
m
this only works if you start out with an non-overflowing int right?
if my sum has an intermediate overflowing step, it breaks
n
I then use e.g. 
val parts = CountingMap(template.windowed(2, partialWindows = false))
m
^ Yes, that thought was what prevented me from considering eachCount
e
For intermediate steps you start with Longs and sum Longs using 
fold
You do 
eachCount
only in the initialization step.
m
I’d still really like a frequencies method. As cool and versatile as groupingBy is, for mere counting it sucks to always have to say 
groupingBy { it }.eachCount()
.
e
groupingB { it }.eachCount()
is really explicit and reads well. But it does happen a from time to time in real-life Kotlin code. It might make sense to have a shorter 
frequencies
in stdlib. However, my quick search still shows that it is needed in puzzles more often that in real-life…
e
Grouping.eachCount()
should rarely overflow an `Int`; collection sizes can't be larger than 
Int
to begin with. but a hypothetical 
Grouping.sumOf()
should have 
Long
overload
👌 1
☝️ 2
m
@elizarov Point taken. Then again developers might find the language more impressive if it lends itself well to these challenges. Methods like frequencies() and permutations() or duplicates() come in handy and are reasonably generic. Reminds me of the random() function in Iterables, which is really cool.
e
See, the reason we’ve added 
random()
was primarily for testing, not for puzzles. The rule of thumb is that in order to be added to stdlib the function must be domain-agnostic (useful across variety of domains). And even that is not enough. It has to be either universally/widely needed or if it is needed occasionally/rarely, then it could because it is otherwise tricky/error-prone to implement (or because it could be non-trivial to implement efficiently).
👍 1
A puzzle-only method does not make any sense in stdlib. If you need it only for puzzles and never use it in real-life code, then you will not know it exists when the time comes to solve a puzzle.
👍 1
e
.permutations() is potentially interesting IMO: it's not entirely trivial to implement in a non-recursive way
m
permutations is also difficult to show an actual use case for, I know I implemented Steinhaus-Johnson-Trotter algorithm with Even's speedup back in the days I programmed in Java, but I can't for the life of me remember why I needed it.
But just like "calculating primes" is not something I want to do myself and I just use BigInteger.nextProbablePrime to generate them. "Why would you need primes?!" well security for one reason
e
that one's maybe not the best example, because I think it turns out building crypto on top of general-purpose BigInteger isn't a great idea; it requires deeper knowledge of how it's being used to avoid information disclosure via timing side-channels etc.
m
Python has permutations in its standard library. It’s not only needed for puzzles, but in scientific/mathematical settings. I understand your reasoning @elizarov - it’s not easy to draw the line, and you want to keep the standard library small. 🙂
k
day 6 dejavu
j
honestly, it’s not good to have too bloated stdlib in kotlin. We already had this issue with JDK having everything inside, from crypto to two ui frameworks. Would be great to have things like permutations, GCD, Chinese Remainder etc and other mathematical algorithms in official kotlin library (along Complex numbers and numerical methods), but only as separate library.
m
kotlinx to the rescue 👀
➕ 2
m
Sure, by all means put it in kotlinx. It’s not exactly much that’s needed either. I have solved a LOT of AoC puzzles this year, and it’s about five functions that keep popping up.
p
https://github.com/tKe/aoc-21/blob/main/kotlin/src/main/kotlin/year2021/Day14.kt took me a while before the 💡 moment. I ended up with my own 
fun <T, K> Grouping<T, K>.eachSum(transform: (T) -> Long): Map<K, Long>
extension. I also needed an extension to merge two maps with conflict handling, but I wasn't sure if I'd missed something in stdlib.
e
not part of kotlin stdlib, but java 8 map has a 
merge()
default method which allows for handling conflicts
👍 1
m
Late to the game but here is mine.
🙌 4
t
In a hurry with this one today, luckily I did most of the thinking for this on Day 6 with lanternfish. • Code • Blog
Looks like I missed a fun conversation about 
groupingBy { ... }.eachCount
. I agree, I only ever use it for puzzles and like it because it’s easy to read. I’d welcome a 
Iterable<T>.permutations()
in the stdlib, but I doubt it would pass the “mostly not used by puzzles only” rule.
e
I've had a few places in real code where permutations() might be used, but usually it only happens with a fixed number of selectors so you may as well just write a nested for loop. unbounded input to permutations() would be a terrible thing in real life
t
Same. I’ve needed it a couple of times for legitimate work, but always just ended up writing something to handle my own types, etc. NBD.
k
I will be ashamed to admit that this 1 took me 3 hours to figure out
t
No shame in that. I spend hours on a problem two years ago because I had inserted a typo into my input file (which is why I never even look at them now). 🙂
10 Views
Open in Slack
PreviousNext
Powered by