https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2022 day 1> :thread:
# advent-of-code
a
🎄 7
⭐ 11
k
aaah
24/15 wtf. I'm literally dying
m
When you work on a linux for work, but a windows from home, and the line feed character messed you up for a bit blob nervous
d
@Michael de Kaste isBlank() for the win!
n
That extra \r is so worthless. I just strip it out of the input in my template.
d
I messed up because I forgot to zero-out my group sum and entered the wrong number so had to wait the 1 minute - ugh!
m
Like discussed last year, really missing a 'chunkedByPredicate' feature 👀
d
yeah i spent the first part trying to see if such a chunking fn existed
n
Nice, @Kroppeb. That's crazy fast for a compiled language. And here I was using a laptop from 2011. It probably only took a few extra seconds but it felt like an eternity...
m
Feels like it could be shorter, but here is mine.
d
m
Copy code
object Day1 : Challenge() {
    val parsed = input.split(lineSeparator() + lineSeparator())
        .map { it.lines().sumOf(Integer::parseInt) }
        .sortedDescending()
    override fun part1() = parsed.first()
    override fun part2() = parsed.take(3).sum()
}
d
Is split your own extension fn?
m
I think 
input
is the entire file here.
d
Ah, input string
nice
m
yeah my Challenge abstract class reads in the input file as a bare string
m
The fact my template already provides input as lines was probably a detriment here!
m
Yeah I used to do that years before, but now I'm content with just a string
because sometimes they do comma seperated values, sometimes they do lines
d
oh 
sortedDescending()
then you can 
take
instead of 
takeLast
n
yeah, just have a String.lines() utility function and deploy as needed
m
I went for 
sorted()
and 
takeLast(3)
because it's shorter than 
sortedDescending()
and 
take(3)
. 😄
m
let's grab the helper function for future tasks and see what I've reused from last year advent 🐕
a
Mine is more of the same, was watching TV and realized oh shit, it’s already 01:00 😅
Gotta get on AOC!
b
We wanted to take a functional approach, but without using the String fun `split`:
Copy code
lines
        .mapIndexedNotNull { index, entry ->
            index.takeIf { index == 0 || entry.isEmpty() || index == lines.lastIndex }
        }
        .windowed(2)
        .maxOf { (from, to) ->
            lines.subList(from, to)
                .filter(String::isNotEmpty)
                .sumOf(String::toInt)
        }
        .also(::println)
d
For part 1, I just used fold over a sequence of lines as some sort of sneaky map, I started with an accumulator of 0 and every line I increased it by the value I read until I reached a blank line and then just set the acc to 0 again 😄 And of course once I had that blank line I just needed to compare the current acc to the current max and update the max if bigger
m
Copy code
fun main() = day01(String(System.`in`.readAllBytes())).toList().forEach(::println)

fun day01(input: String) = input.split("\n\n")
    .map { it.split("\n").map(String::toInt).sum() }
    .sortedDescending()
    .let { it.first() to it.take(3).sum() }
@Marcin Wisniowski I also fell into the trap of an inflexible template. Will modify it to use a string, plus one line to parse it into a list of strings in the solution, which I can remove if not needed, or change the separator (e.g. to comma).
j
@babel nice. I tend to avoid calling 
subList
in a loop as it feels O(n) to me, but it depends on what type of list your 
lines
are 😉
d
Copy code
var maxElfCalories = 0

        getInputAsSequence().fold(0) { acc, line ->
            if (line.isBlank()) {
                maxElfCalories = maxOf(acc, maxElfCalories)
                0
            } else {
                acc + line.toInt()
            }
        }.call { println(maxElfCalories) }
Formatting does a bit weird with copy-pasting, but you get the idea; 
call
is an extension function I made as a companion to the let, apply etc. family, it takes a block which returns Unit and returns Unit itself, so it's a simple consumer if you will
m
@Davio You are using the fold() method as a means to loop over the list with a running variable. It would communicate the intent better to use an explicit loop and variable, like in my very ineffective initial solution:
Copy code
fun day01(lines: List<String>): Pair<Int, Int> {
    var sum = 0
    var maxSum = Int.MIN_VALUE
    val maxSums = mutableListOf<Int>()
    for (line in lines) {
        if (line == "") {
            maxSums += sum
            maxSum = max(maxSum, sum)
            sum = 0
        } else sum += line.toInt()

    }
    return maxSum to maxSums.sortedDescending().let { it[0] + it[1] + it[2] }
}
d
Yes, but my eyes hurt when I see an old for-loop, so I try to sneakily create for loops without for loops 😄
But with these kinds of puzzles, where you are reading a 'tape' (for lack of a better analogy) where line breaks denote end of groups, I just usually do it with a sequence and then building the group as I go and ending the group when I encounter the blank line
m
Sure, but the fold makes it much more difficult to understand. What makes this an anti-pattern: 1. Modifying surrounding variables from within the fold lambda 2. Not using the return value of the fold()
d
Oh that's totally right, but as I'm the only one reading it, I don't mind much 😄
m
As a rule of thumb, whenever you are modifying the outside scope from within a forEach/reduce/fold/etc. lambda, you should probably use a traditional loop, because you are really writing imperative code. Which is fine! If you look at the implementations of most functional extension functions in the Kotlin standard library, it is all imperative, and for good reason.
d
Yes, it feels like cheating a bit, because Java wouldn't let you do this from within a lambda block :D
m
^^ Well, even if you are the only one reading your code, in a productive setting you might have to read and understand it again after several days/weeks/months/years, so you are better off writing readable code either way. It even applies to AoC, provided you want to share your solutions.
d
I guess that depends on your own modus operandi, in AoC I like to try and come up with clever solutions, however unreadable, just as a mental exercise so I don't mind it personally to go for something a tad less straightforward, but to each his own
Note that my actual code that I write for my current project where I am employed looks nothing like my AoC code 😄
m
In Java, you would have a 'collect' function where you would define your collection and the apply function. both reduce and fold don't really work the same way, which leaves us with a void. I usually fill this with a buildList{ ... } surrounding the code and a foreach with the apply function
d
Maybe we need a sequence generator to yield these kinds of running groups? That would be a fun and useful helper function
m
@Davio Fair enough! I’ve been writing code for so long that I’ve abandoned the idea of writing “clever” code. Like Venkat Subramaniam put it (paraphrased): “If I find myself writing clever code, I look at it, enjoy the feeling, and then refactor it to something simpler”.
d
@Michael Böiers yeah for me AoC is a personal playground where I can go wild and do different stuff than implement REST controllers with CRUD stuff, so I guess that's why I like to go overboard and just have fun with it
But when it comes to production code or shared code or code that you look at in one year and go "which idiot wrote this code?" only to realize it was yourself, then I totally agree with you 🙂
m
@Davio Something like this could be useful:
Copy code
fun <T> List<T>.chunked(separator: (T) -> Boolean): List<List<T>>
And then you would just
Copy code
list.chunked { it.isBlank() }
d
I would also write it as a sequence generator, because with long lists that could be helpful
m
@Davio I use AoC to practice the skill of solving coding challenges fast and efficiently. Also to play around and try different things, for sure, but usually that comes after I’ve solved a particular challenge.
j
Copy code
fun part1() = parse().takeLast(1).sum().let(::println)

fun part2() = parse().takeLast(3).sum().let(::println)

fun parse() = FileReader("1.in")
    .readLines()
    .joinToString("-")
    .split("--")
    .map { elf ->
        elf
            .split("-")
            .map(String::toLong)
            .sum()
    }
    .sorted()
No intention to mess with newline chars, so I hacked it up like this.
d
@Michael Böiers as promised, here is an example implementation of a 
chunked with predicate
function:
Copy code
fun <T> Sequence<T>.chunked(predicate: (T) -> Boolean): Sequence<List<T>> {
    val iterator = this.iterator()
    val buffer = mutableListOf<T>()

    return sequence {
        while (iterator.hasNext()) {
            val element = iterator.next()
            if (predicate.invoke(element)) {
                yield(buffer.toList())
                buffer.clear()
            } else {
                buffer.add(element)
            }
        }
        if (buffer.isNotEmpty()) {
            yield(buffer.toList())
        }
    }
}
If you don't want to use sequences, you can rewrite it to use simple lists instead
Using this new 
chunked
function, the solution for part 1 simplifies to:
Copy code
getInputAsSequence()
   .chunked { it.isBlank() }
   .map { it.sumOf(String::toInt) }
   .max()
m
^^ nice! Good that you resisted the temptation to implement it with a fold 😉
If that function ever becomes part of the standard library it should probably be called split, since it works similarly to the String.split() function.
d
Yeah I thought about that too, and chuncked is usually used with a size, not a predicate
j
@Joey Haas I also have a tendency to generalize and make part 1 just a special case of part 2. However in doing so, the solution for part 1 is then unnecessarily complex. In your example the 
sorted()
in 
parse()
makes it O(n*log(n)). I personally think that it would be better if 
parse()
returned just the collection without the sorting and then in 
part1
you can just call 
max
(keeping it O(n)) and applied 
sortedDescending().take(3).sum()
only in 
part2
m
^ I think that performance optimisation is a minor aspect of AoC. I know that some focus on it, but most are trying to solve the puzzles as fast as possible. From that angle, it is good to implement any part 1 in a generic way that is not too optimised, since that increases the likelihood that part 2 can be solved by the same code, with minor tweaks.
k
@Jan Durovec sublist is O(1) iirc
d
To help with part 2, I added these guys to my ever growing personal std lib 😄
Copy code
fun <T : Comparable<T>> List<T>.top(n: Int): List<T> = this.sortedDescending().take(n)
fun <T : Comparable<T>> List<T>.bottom(n: Int): List<T> = this.sorted().take(n)
fun <T : Comparable<T>> Sequence<T>.top(n: Int): Sequence<T> = this.sortedDescending().take(n)
fun <T : Comparable<T>> Sequence<T>.bottom(n: Int): Sequence<T> = this.sorted().take(n)
j
@Kroppeb only on 
ArrayList
or random access list. On 
LinkedList
etc it must be O(n) as there's no other way to iterate to nth element
d
Which turns part 2 into:
Copy code
getInputAsSequence()
            .split { it.isBlank() }
            .map { it.sumOf(String::toInt) }
            .top(3)
k
@Jan Durovec yeah, I never use linked lists
m
@Davio there is no top function in the standard library 😉
d
It is in my personal std lib 🙂
m
@Davio I know, that makes you code snippet meaningless for those who have no access to your personal library 🙂
k
I think ruby has a max(n) that I'm probably gonna add to my util library
d
Yeah, I listed the ones I added though 😉
Even though you might not have that function in your library, I think you can still understand what the code does
m
I actually wonder what top(3) does. Is it sortedDescending().take(3)? Then it lacks the adding …
d
It does, what do you mean it lacks?
Oh you're right, I forgot to add the sum back
There:
Copy code
getInputAsSequence()
            .split { it.isBlank() }
            .map { it.sumOf(String::toInt) }
            .top(3)
            .sum()
m
nitpicky: but I would do 
.split(String::isBlank)
to stay in line with the line below it 😛
d
Yeah, I could, I just did that to not have to specify something else than 
it
😄
m
I don’t think that top(3) is a big improvement over sortedDescending().take(3) in terms of readability. It’s just another function to learn. And that function is quite unflexible. One of the paradigms in Kotlin is to be explicit, and the top(n) function is hiding away simple things that the caller could do themselves, and tweak them if necessary. It is similar to sum() vs. sumOf {}.
d
I disagree, Kotlin already has many extension functions which could be written as a combination of 2 other functions, so I think it is in Kotlin's spirit to just add more simple and straightforward ones like these
m
For example? I don’t think Kotlin has many rendundant functions in the library. If so, I think these are regarded as regrettable mistakes.
k
In my case it is. I lost probably a second thinking about I best get the top 3. If I knew I had a function for that, no tinkering needed I would have immediately used it. Now this is in context of AOC, idk if I'd add it to the stdlib
m
The split() function here is a good example for an interesting candidate, since it cannot easily be implemented with composing other functions.
k
If I were to add top to the actual stdlib, I'd use a more efficient algorithm like O(n log(k)) at most
m
How to get the largest elements in a list of ints … who wouldn’t immediately think about sorting?
d
I feel this is a personal preference kind of thing 🙂 so I agree with all points and consider this a matter of taste. Maintaining a standard library is an impossible balance to maintain. Make it too bare bones end you get leftpad debacles, make it too stuffed and it might get too bloated. I'm no expert on where the perfect balance is, but we can at least appreciate Kotlin is extensible enough that you can easily add new functions to your personal library.
Any function in the standard library which transforms a collection into a single result can be replaced by fold 😉 😛
x
i suck at folding
Copy code
fun summed(input: List<String>) = input
    .fold(listOf(listOf(0))) { acc, i ->
      if(i.isEmpty()) return@fold acc + listOf(listOf(0))
      val updated = acc.last().plus(i.toInt())
      acc.dropLast(1)  + listOf(updated)
    }
    .map { it.sum() }

fun part1(input: List<String>): Int = summed(input).max()

fun part2(input: List<String>): Int =  summed(input).sortedDescending().take(3).sum()
p
k
m
@xxfast I think you should consider using mutable structures as the accumulator. Immutability is a great concept, but the accumulator in a fold/reduce is meant to be mutated.
@xxfast Like so:
Copy code
fun main() = day01Fold(String(System.`in`.readAllBytes())).forEach(::println)

fun day01Fold(input: String) = input.split("\n")
    .fold(mutableListOf(0)) { acc, line ->
        if (line.isBlank()) acc += 0 else acc[acc.lastIndex] = acc[acc.lastIndex] + line.toInt()
        acc
    }
    .sortedDescending()
    .let { listOf(it.first(), it.take(3).sum()) }
d
This could also be a fun exercise (and a way to completely overengineer this problem) to design your own data structure which contains at max n items with an initializer function (to set everything to 0) and a predicate for inserting items (that the inserted item must be larger than at least one of the items)
Then, while reading the lines / iterating through the groups (which can be done lazily), you would only have to maintain a list of 3 items instead of keeping all the results in the list
m
Something like this could be valuable to have performance-wise. It could be added as an optional parameter to sorted(Descending), something like 
list.sortedDescending(take = 3)
.
d
Okay, absolutely, definitely, certainly, don't try this at home, unless you are as enthusiastic, obsessed and fanatic as I am, but here's an example:
Copy code
fun getResultPart2() {
        val fixedSizeList = FixedSizeList(3, { 0 }) { newElement ->
            this.mapIndexed { index, element -> Pair(index, element) }
                .filter { newElement > it.second }
                .minByOrNull { it.second }
                ?.first ?: -1
        }

        getInputAsSequence()
            .split(String::isBlank)
            .map { it.sumOf(String::toInt) }
            .forEach { fixedSizeList.add(it) }

        println(fixedSizeList.sum())
    }

    private class FixedSizeList<T>(
        private val maxSize: Int,
        private val initializer: () -> T,
        private val additionIndexBlock: FixedSizeList<T>.(T) -> Int
    ) : ArrayList<T>(maxSize) {

        init {
            repeat(maxSize) {
                add(initializer.invoke())
            }
        }

        override fun add(element: T): Boolean {
            if (size < maxSize) {
                return super.add(element)
            }

            val indexOfElementToOverwrite = additionIndexBlock.invoke(this, element)
            return if (indexOfElementToOverwrite > -1) {
                this[indexOfElementToOverwrite] = element
                true
            } else {
                false
            }
        }
    }
So here's a data structure (based on list) which keeps at max N items with a lambda with receiver to find the index of the item to replace, the 
add
function returns a Boolean to let the user know if their addition changed the list or not, this is totally not used or needed in this example, but it's fun that it exists
So in the end, our list will always have exactly 3 items which saves some very costly RAM of course 🤑
t
Late to the party, but I’m happy with my solution: • Blog • Code
k
Here it's my solution, a bit late though 🙂, I basically solved the issue with an imperative solution, and then added a functional one (that under the hood uses similar concepts but makes the solution to look a bit cleaner and elegant as some may say) https://github.com/quebin31/advent-of-code-22/blob/main/src/main/kotlin/com/quebin31/aoc/days/Day1.kt
p
@Davio not generic but this works nicely for ints
Copy code
@JvmInline value class MaxIntArray(val values: IntArray) {
    constructor(size: Int) : this(IntArray(size))
    operator fun plusAssign(v: Int) {
        if(values.size == 1) { values[0] = maxOf(values[0], v) }
        else values.indices.lastOrNull { v > values[it] }?.let { idx ->
            repeat(idx) { values[it] = values[it + 1] }
            values[idx] = v
        }
    }
}

fun List<String>.topElves(n: Int): Int {
    val q = MaxIntArray(n)
    var sum = 0
    map(String::toIntOrNull).forEach {
        if (it == null) q += sum
        sum += it ?: -sum
    }
    return q.values.sum()
}
m
@todd.ginsberg I like how we have the exact same solution 😉
t
Oh wow! Well, great minds and all that. 🙂
m
Here’s another attempt, this time focused on clear intent and performance. WDYT? 🙂
Copy code
fun day01SortedSet(input: String): List<Int> {
    val top = TreeSet<Int>(reverseOrder())
    for (elf in input.split("\n\n")) {
        top += elf.lines().sumOf(String::toInt)
        if (top.size > 3) top -= top.last()
    }
    return listOf(top.first(), top.sum())
}
k
Cool @Michael Böiers, I also used a 
TreeSet
for my solution
p
A little risky to use TreeSet as it would fail for situations with two elves carrying the same amount of calories 😉
e
once I get my benchmarking suite set up again, I'm gonna try implementing quickselect, which should be O(N) instead of O(n log n)
k
@phldavies you're right, I guess I got lucky this time around 😆
Thanks for the heads up @phldavies, I have fixed my extension functions and my solution that was using 
TreeSet
to use a List instead, now I'm actively looking for the place where the element should be inserted so it keeps the list sorted and of course avoids the issue with duplicated values. • Code
d
Love seeing all of these different approaches and learning from you all. Looking forward to the next 24 days!
m
@phldavies Here’s a corrected version. @Kevin Del Castillo solved it by wrapping the Int with a class. 🙂
Copy code
fun day01SortedSet(input: String): List<Int> {
    class Food(val calories: Int)
    val top = TreeSet(compareByDescending(Food::calories))
    for (elf in input.split("\n\n")) {
        top += Food(elf.lines().sumOf(String::toInt))
        if (top.size > 3) top -= top.last()
    }
    return listOf(top.first().calories, top.sumOf { it.calories })
}
e
https://github.com/ephemient/aoc2022/commit/58fc100ef7ee3b8d2495fbf4ce4fab3f2caf0cf9 in my project's benchmark, 
.quickSelectDescending(2)
came out about 30% faster than 
.sorted().takeLast(3)
. it's a lot more code though
@Michael Böiers I don't think wrapping it in a class helps. if the comparator returns 0, 
TreeSet
treats the objects as identical and only keeps one, even if the objects aren't 
equal()
Copy code
TreeSet(Comparator<Any> { _, _ -> 0 }).apply { addAll(listOf(1, 2, 3)) }.size == 1
k
I'm not sure to what you mean by wrapping Int with a class @Michael Böiers
n
@Michael Böiers If you want to save that 10ms by using a pre-sorted collection that allows duplicates, you can do it with a priority queue. Accessing all but the first element of a pq is destructive of course! But part1 only requires a peek and you have no use for it after part2. Note screenshot code relies on unseen extension functions to pretty it up.
Specifically these:
d
I realized we can do this with a simple fold and running sum without any lists, will work it out soon 😄
d
Yeah it is for sure doable in a single iteration without much state
m
@ephemient Yes, I haven’t used TreeSets (or TreeMaps, for that matter) in a long while, thanks for reminding me.
@Kevin Del Castillo @ephemient I’ve since come up with a new approach that does not rely on any special classes and still avoids sorting everything:
Copy code
fun day01MinMax(input: String): List<Int> {
    val top = mutableListOf<Int>()
    for (elf in input.split("\n\n")) {
        top += elf.lines().sumOf(String::toInt)
        if (top.size > 3) top -= top.min()
    }
    return listOf(top.max(), top.sum())
}
d
Copy code
println(
    lines.fold(0 to 0) { acc, value ->
        if (value.isBlank()) {
            0 to maxOf(acc.first, acc.second)
        } else {
            acc.first + value.toInt() to acc.second
        }
    }.second
)
@Michael Böiers you can use a PQ, avoids reallocating the array list every time you modify it not from the tail:
Copy code
val top = java.util.PriorityQueue<Int>()
for (elf in input.split("\n\n")) {
    top += elf.lines().sumOf(String::toInt)
    if (top.size > 3) top.poll()
}
return listOf(top.max(), top.sum())
m
@Dan Fingal-Surma Sure. But then I would depend on a special class, and the benefit is not that great for a list with at most four items.
d
For me it's more that the list gets potentially reallocated on every iteration, irrespective of it's size. You can just call sortDescending and removeLast to avoid that. Underlying array won't ever get reallocated
Obv more verbose than -= min
d
My very naive, but I think quite performant code:
Copy code
getInputAsSequence()
            .split(String::isBlank)
            .map { it.sumOf(String::toInt) }
            .fold(intArrayOf(0, 0, 0)) { acc, element ->
                if (element > acc[0]) {
                    if (element > acc[1]) {
                        acc[0] = acc[1]
                        if (element > acc[2]) {
                            acc[1] = acc[2]
                            acc[2] = element
                        } else {
                            acc[1] = element
                        }
                    } else {
                        acc[0] = element
                    }
                }
                println(acc.joinToString())
                acc
            }.sum()
            .call { println(it) }
So basically instead of a dedicated data structure such as a sorted set or sorted list, we can use an array which means we have to do the comparisons for insertion ourselves
So in this case, as we are looping through all the calorie totals, we are only carrying an array of 3 elements and only insert an element if it needs to be inserted (larger than the smallest value)
We can probably generalize the 'insert at index N and push everything else left 1 place' part, but I will leave that as en exercise for the reader, on with day 2 😄
Okay, because you asked:
Copy code
getInputAsSequence()
            .split(String::isBlank)
            .map { it.sumOf(String::toInt) }
            .fold(intArrayOf(0, 0, 0)) { acc, element ->
                val indexToInsert = acc.indexOfLast { element > it }
                if (indexToInsert > -1) {
                    (0 until indexToInsert).forEach { index ->
                        acc[index] = acc[index + 1]
                    }
                    acc[indexToInsert] = element
                }
                acc
            }.sum()
            .call { println(it) }
p
@Davio nice! Looks like a folded version of the MaxIntArray approach https://kotlinlang.slack.com/archives/C87V9MQFK/p1669908877682639?thread_ts=1669870849.812499&amp;cid=C87V9MQFK I should have looked for 
indexOfLast
🙂
b
Hi everyone! Can you help me why get I "Exception in thread "main" java.lang.NumberFormatException: For input string: "" ? I wrote the code based on the solution video, but I still get an error. Here is some pictures:
k
It seems to be related to how Windows handles newlines which is 
\r\n
if I recall correctly, but I'm not 100% sure if that's the correct order or the other way around because I don't use that crappy OS for anything but gaming 😝
m
You probably have some extra white space in the input. Are you on Windows?
b
Yes I am on Windows and really the windows handles newlines with \r\n. I rewrote the delimiters to \r\n. But I got the same error.
m
Remove the conversion to Int and just print out the parsed result. Does it look like expected?
b
I'm sorry, but I'm at the very beginning step. How can I it make?
k
You want to replace each 
\n
with 
\r\n
, not only one of those because you want to separate lines when there's a blank one, so you should be instead using 
\r\n\r\n
b
Ahhhh okee I got it I got it. Stupid mistake. All right thank you very much. With \r\n\r\n it works.
e
or if you download the input from the website, instead of copy-paste it, it will have 
\n
-only line endings
25 Views
Open in Slack
PreviousNext
Powered by