https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2021 day 6> :thread:
# advent-of-code
a
d
That was actually pretty fun! I wish I didn't make so many stupid mistakes.
I think what made it fun was that I did the naïve solution for part 1 and then (in classic AoC form), I had to think of a different way to store the data for part 2.
m
j
I went to the “good enough” solution since start, but it took me a bit at part 2 to understand that, well, 
Int
might not make it 🙂
otherwise, I’m quite sure this can be optimized, but meh, I’ll stay with this
🤯 2
m
Still not sure how to code this avoiding ugly 
toLong()
calls, given that 
eachCount()
works on 
Int
only … EDIT: better now, but still not pretty …
k
I think there is an closed solution to the problem, anyway the simulation is only O(n) so it works.
t
I'm traveling tonight so for once I stayed up until midnight for the puzzle. I got part 1 pretty quickly (for me, I was like 1,500 away from the leaderboard, lol) with a naïve approach but part 2 took me a really long time. I eventually ended up realizing I could just keep rotating an Array of fishies per day and adding to day 8. I'll write it up in the morning, I'm so tired (this is waaaaaaaaay past my bedime) 🙂 Originally I did it with a Map until I realized that there were only a few days so I switched to an array. I did have to write my own rotate-in-place function which I might rethink in the morning.
k
I did it with a 
Deque
m
@Jakub Gwóźdź That's very similar to mine with the cache! 😄
d
Great problem. Started out with a solution that didn’t scale to 256. Had to retool after OOMing. https://github.com/dfings/advent-of-code/blob/main/src/2021/problem_6.main.kts Original:
e
@knthmn just like fibonacci, this is probably fastest via matrix exponentiation (or other equivalents to the same), but I didn't bother to set that up
💯 1
k
k
@ephemient I think the only way is to solve the 9th degree characteristic equation of the matrix, and there is no analytic solution for it. So there isn't a closed equation
m
https://github.com/mdekaste/AdventOfCode2021/blob/main/src/main/kotlin/year2021/day6/Day6.kt thought I was being extra smart by rotating, turns out I wasn't the only smart guy ;)
👍 3
e
@knthmn O(log n) preprocessing time to compute the exponentiated matrix, then O(1) runtime
in fact, I implemented that after all: https://github.com/ephemient/aoc2021/commit/a3d3917b108efe2415f0f403fde7ee84de051f16 before:
Copy code
Benchmark         Mode  Cnt      Score       Error  Units
Day6Bench.part1  thrpt    5  98938.375 ± 29221.707  ops/s
Day6Bench.part2  thrpt    5  93935.888 ±  6461.912  ops/s
after:
Copy code
Benchmark         Mode  Cnt       Score      Error  Units
Day6Bench.part1  thrpt    5  120113.506 ± 7501.950  ops/s
Day6Bench.part2  thrpt    5  121375.217 ± 2123.868  ops/s
K 1
f
implemented with a fold - liked the readability without compromising too much on the performance: https://github.com/fmmr/advent/blob/master/src/main/kotlin/no/rodland/advent_2021/Day06.kt
💯 1
p
c
I ran out of time this morning to finish Part 2 to defeat the heap error. I'll have to reup on techniques, anyone have any good resources? I tried to (rushed) implement a fold function (via this great article, https://kousenit.org/2019/11/26/fibonacci-in-kotlin/) but I still missed the mark! Here is my failed attempt: https://github.com/cak/advent-of-code-2021/blob/main/src/Day06.kt I'll revisit tonight.
p
Okay your solutions might be smarter 😁
e
as I mentioned up-thread, this can be solved by pre-computing the matrices, which boils down to
Copy code
fun part1(input: IntArray): Long = input.sumOf(longArrayOf(1421, 1401, 1191, 1154, 1034, 950, 905, 779, 768)::get)
fun part2(input: IntArray): Long = input.sumOf(longArrayOf(6703087164, 6206821033, 5617089148, 5217223242, 4726100874, 4368232009, 3989468462, 3649885552, 3369186778)::get)
in the end
t
I thoroughly enjoy how differently these tasks are handled. Every time I solve a day, I browse a few other repos and ususally every single one uses a different approach. It's also intreseting to see how the solutions differ in readability vs efficiency. Sometimes I deliberatley chose the slower and/or 'less idiomatic' solution because it was more readably to me. Never thought I'd have this much fun and kinda regret that I didn't participate the last few years.
💯 2
p
My solutions have their focus on readability, not performance
They are fast enough to save Santa 🎅 💨
t
@ephemient I am constantly amazed at what you come up with.
👍 1
Solved and written up now. I ended up rotating a LongArray where the indices represent time and the values represent fishies. Probably similar to a lot of solutions here, I'll have to go look now that I've had a bit of sleep and some coffee. 🙂 • Blog • Code Part two of my road trip is today, so I'm off!
n
a not very sophisticated approach:
p
@Nate Ridderman that 1..256.map could be a repeat(256)
💪 1
And that ourLantern.map a ourLantern.forEach
👍 1
And that final like can be .values().sum()
👍 2
g
p
https://github.com/tKe/aoc-21/blob/main/kotlin/src/main/kotlin/year2021/Day06.kt another fold/rotate approach that seems to be common today 🙂
m
Most recent refactor of my solution. There may be more clever solutions, but I like how it stays close to the verbal description of the algorithm. EDIT: one more tweak to use a when expression, even if it is one line longer 😉
Copy code
fun main() = generateSequence(::readLine).single().day06().let { (p1, p2) -> println(p1); println(p2) }

fun String.day06() = split(",").map { it.toInt() }
    .run { LongArray(9) { i -> count { it == i }.toLong() } }
    .run { listOf(grow(80), grow(256)).map { it.sum() } }

private fun LongArray.grow(n: Int) = copyOf().also { l ->
    repeat(n) {
        val spawn = l[0]
        for (i in 0..8) l[i] = when (i) {
            6 -> l[i + 1] + spawn
            8 -> spawn
            else -> l[i + 1]
        }
    }
}
👍 1
t
https://github.com/vandeven/aoc2021/blob/master/src/main/kotlin/Day6.kt easy to understand implementation 🙂 (probally not the most efficient one though)
m
My noobie code cannot finish part 2 because of heap error...any tips appreciated https://github.com/Jaavv/advent-of-code-2021/blob/main/src/Day06.kt
p
@Marc Javier Do you have an idea why your solution doesn't work?
m
way too much objects? 😆
p
Yep. So you need to come up with a solution that doesn't create more objects on each iteration
☝️ 1
Also, write a test for part 2. It give you a hint why your int can't work
v
I’m also facing an OOM for part 2.
Copy code
fun partOneAndTwo(input: List<String>, days: Int): Long {
    val finalList = input.first().split(",").map { it.toInt() }.toMutableList()
    for (day in 1..days) {
        for (i in 0 until finalList.size) {
          val newNumber = finalList[i].dec()
          if (newNumber == -1) {
            finalList[i] = 6
            finalList.add(8)
          } else {
            finalList[i] = newNumber
          }
        }
    }
    return finalList.count().toLong()
  }
Works fine for part 1 and crushes for part 2. Not sure which operation creates extra objects in the heap…
k
your list grows exponentially
finalList.add(8)
7 Views
Open in Slack
PreviousNext
Powered by