https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2023 day 9> :thread:
# advent-of-code
a
m
easy problem today :D
Copy code
object Day9 : Challenge() {
    val parsed = input.lines().map { it.split(" ").map(String::toInt) }

    private fun next(list: List<Int>): Int = when (list.all { it == 0 }) {
        true -> 0
        else -> list.last() + list.zipWithNext { a, b -> b - a }.let(::next)
    }

    override fun part1() = parsed.sumOf(::next)
    override fun part2() = parsed.map(List<Int>::reversed).sumOf(::next)
}
👌 2
same 1
👍 1
b
easiest problem yet
💯 2
✅ 1
m
Part 1
Part 2
I lost time trying to think of the hidden catch, but there wasn't one, it was just that easy...
b
mine was essentially the same as @Michael de Kaste
Copy code
fun findNext(list: List<Int>): Int {
        val diffs = list.windowed(2) { (a, b) -> b - a }
        if (diffs.all { it == 0 }) return list.last()
        return list.last() + findNext(diffs)
    }

    part1 {
        lines.map { it.getIntList() }.sumOf { findNext(it) }
    }

    part2 {
        lines.map { it.getIntList().reversed() }.sumOf { findNext(it) }
    }
l
I think I got a pretty solution
🆒 3
👍 2
😍 1
m
apparantly, doing a check for all is a bit slower than just reducing until the lists are empty:
Copy code
private fun next(list: List<Int>): Int = when (list.all { it == 0 }) {
    true -> 0
    else -> list.last() + list.zipWithNext { a, b -> b - a }.let(::next)
}
TimedValue(value=["Day9", 1953784198, 957], duration=1.010900ms)
vs.
Copy code
private fun next(list: List<Int>): Int = list.lastOrNull()
    ?.let { last -> last + list.zipWithNext { a, b -> b - a }.let(::next) }
    ?: 0
TimedValue(value=["Day9", 1953784198, 957], duration=944.6us)
my assumption was that reducing past a collection of 0's was going to be unnecessary, but check for all 0's every single time is heavier than just doing it, haha
j
My input must be with a trick, my code:
Copy code
fun Sequence<Long>.extrapolateValue(): Long {
        val rows = generateSequence(this.toList()) { lastRow ->
            lastRow.windowed(2).map { (a, b) ->
                b - a
            }
        }.takeWhile { it.any { n -> n != 0L } }
        return rows.sumOf { it.last() }
}
And then summing it up, yields the same result as some of the other solutions, but aoc says that is a wrong result, I'm baffeled. Edit: my problem was that number parsing only got positive numbers.
j
the day of the windows
Untitled.kt
Untitled.kt
n
Got a little bit stuck at part 2, took some time to realise that I was reversing the raw input, not the parsed integers
j
Oh man my problem was that my parsing messed up negative numbers
m
smallified my code a bit:
Copy code
fun List<Int>.next(): Int = lastOrNull()?.let { it + zipWithNext { a, b -> b - a }.next() } ?: 0
object Day9 : Challenge() {
    private val parsed = input.lines().map { it.split(" ").map(String::toInt) }
    override fun part1() = parsed.sumOf(List<Int>::next)
    override fun part2() = parsed.map(List<Int>::reversed).sumOf(List<Int>::next)
}
e
j
I’m playing a bit with DeepRecursiveFunction, the jury is still out on this.
DeepRecursiveFunction.patch.diff
v
My attempt at Day 9, implemented in iterative and recursive ways. used 
fold
for the first time. it's fun 🙂 https://github.com/bravura-quark/aoc-kotlin-2023/blob/main/src/Day09.kt
t
It's 
runningFold
for me again (I did everything as in the story - didn't realize it's just possible to sum the last values in part 1):
Copy code
fun List<List<Long>>.extendFromRight() = reversed()
        .runningFold(last()) { prevNumbers, curNumbers -> curNumbers.append(prevNumbers.last()) }
        .reversed()

    fun List<List<Long>>.extendFromLeft() = reversed()
        .runningFold(last()) { prevNumbers, curNumbers -> curNumbers.prepend(prevNumbers.first()) }
        .reversed()
p
a
this must have been my fastest part2 minus part1 time 😛 only need to change one line of 
.sum()
to 
.reduceRight(Int::minus)
edit: and one 
it.last()
to 
it.first()
a
hello fellow adventists! I guess they decided to go easy on us on Friday so it wasn't hard today. https://github.com/andriyo/advent-of-code-kotlin-2023/blob/main/src/Day09.kt At first it looked like Pascal's triangle but it wasn't that so just normal coding without math voodoo As usual, I did it as functional as possible without mutable data structures, recursions. The only thing I'm not happy about is that I needed to do 
mySequence.toList()
at one point in Part 2. Not sure if it's due to fundamental nature of the problem or it's possible to do it fully thru streams without terminating in a collection.
p
a
The only thing I'm not happy about is that I needed to do 
mySequence.toList()
at one point in Part 2
@andriyo yup, that caught me out too. in my case with 
reduceRight
and in your case with 
reversed
maybe that the designers wanted us to be conscious of the fact that reversing a sequence (or doing anything from right to left) requires having the full result, and hence no longer a "sequence" but a collection
a
yeah, it's still not super clear to me: one one hand the Part 2 seems symmetrical and therefore it should be stream-like as Part 1, on the other hand, I have this reversed().fold (aka foldRight()) which spoils the whole thing.. I need to go look at other people code, maybe someone did it without finite list...
it seems all solutions had to look at the end of the list one way or the other.
a
here's mine - freaky that Day 9 can actually be reduced to so few lines and still make sense
m
@Jonathan Kolberg me too, I would have had a first time pass from code to answer if my input Regex just had 
-?
😅 1
p
Oh, I had another idea! For part 2, just invert the input!
🧠 2
K 1
😈 1
a
@Paul Woitaschek holy s**t! yeah, that works brilliantly!
a
@ephemient ) they did the same. pretty neat trick )
🧠 2
n
I was dead tired, kicked my son off my computer wanting 5 minutes to code up part 1 so I could sleep on what was surely going to be a brutal part 2. Or...maybe not.
But see this?
p
My solution was overflowing the int space by 1%
n
Without it I get this. Anyone know what Gods I displeased?
m
sumOf is notoriously weird about typings
👍 2
p
AOC rule number 1: Always long 🙈
a
how does sumOf not have a <Long> override?
p
Copy code
public inline fun <T> Iterable<T>.sumOf(selector: (T) -> Long): Long {
It’s there
Even kotlin itself hast o fight its type system 🤷
😅 2
d
Yay an easy one so I can go off to the gym today 😄
n
But it shouldn't be ambiguous because my lambda returns an Int. But c'est la vie.
p
It does not have 
OverloadResolutionByLambdaReturnType
d
The heart of my puzzle solution is this:
Copy code
private fun getNextValue(history: List<Long>) : Long {
        if (history.distinct().size == 1) {
            return history.first()
        }

        return history.last() + getNextValue(history.zipWithNext { a, b -> b - a })
    }
I decided on using a recursive function that would continue until all of the elements were the same (they do not have to be 0). If the elements are not all the same, we can use 
zipWithNext
to create the derived history (history' if you will) and pass it to the recursive function and get its next value
For part 2 it's the same, but there is a minus instead of a plus and a first() instead of a last() 🙂
AoC 2023 day 9 - Davio.kt
AoC 2023 day 9 - Davio.kt
Since the entire solution is short enough I thought I'd just share it as a snippet this time
n
It does not have 
OverloadResolutionByLambdaReturnType
?
p
The sumOf has, the reduce one not
🙌 1
a
I swear to god I hadn't seen your code before I committed this @ephemient https://github.com/ondrsh/AdventOfCode2023/blob/master/src/main/kotlin/Day9.kt zipWithNext is more elegant anyway
n
carcinization!
d
I guess my only real smart insight today was that I stopped when the numbers where all the same because the next step in that case is always all zeroes 😄
m
I wonder when the wild day will be
d
When I looked at this problem in bed this morning (timezone is only friendly to very early risers), I expected I was going to have to do some fancy polynomial calculation so I stumbled upon Lagrange Interpoliations, a fun little rabbit hole
Since every line represents a polynomial of the Nth degree, there is probably a more mathy way to get the answer directly
e
yes, I did come up with a non-recursive solution using binomial coefficients. I'm debating replacing my existing solution with this; it's faster, but less clear
Day9.kt.cpp
🙌 1
🧮 1
a
yeah, those simple things like 0.toLong() -> 0L, fold(0) { + } -> reduce() - IDE should just detect them it did look like Pascal triangle to me too with all its binomial coeff beauty - thankfully, not much of a math problem today - those tend to be more of "pattern recognition/spotting" (not fun) kind of problems and not algorithmic problem solving (fun kind)
d
I refactored to 
generateSequence
after first solving with a 
MutableList
e
I did end up committing the faster solution after all. the recursive one is still in git history
a
That's genius @ephemient
r
easy one today indeed, my solution basically matches a number of solutions already pasted here. One thing I noted was that for part 2, 
List<Int>.reversed()
appeared to perform better than 
List<Int>.asReversed()
, which I did not expect at first... am I doing so many lookups that the reversed index lookup (which is done by the implementation returned by 
asReversed()
) becomes too expensive to outperform building a new reversed list?
e
@Riccardo Lippolis that doesn't seem to be the case for me… but I'm also only iterating the list, not indexing it
d
I never needed reversed
e
still, the inputs are relatively small, so what you say is potentially possible: the extra indirection through the 
asReversed
wrapper might be more expensive than creating a new simple object
d
But yes that's likely
r
looking at the code of 
ReversedListReadOnly
, there is an extra bounds check, which is performed on every indexed lookup, but when iterating it's only performed when creating the iterator, so that would explain why you don't see the same result indeed. But indeed, too small to actually make a difference anyway 🙂
d
Have not seen 
zipWithNext
j
I thought weekend problems would be harder? I was especially surprised how easy part 2 was.
Copy code
fun calculateNext(list: List<Int>): Int = if (list.all { it == 0 }) 0 else
        list.last() + calculateNext(list.zipWithNext { a, b -> b - a })

    fun part1(input: List<String>): Int = input.map { it.splitToInts() }.sumOf { calculateNext(it) }

    fun part2(input: List<String>): Int =
        input.map { it.splitToInts() }.map { it.reversed() }.sumOf { calculateNext(it) }
m
@ephemient I've been playing with the same formula, and technically you can make it faster by returning quicker after finding that s equals the next number and then adding the difference to the last element.
g
Indeed, the task was easy today. But this year I had a plan to utilize coroutines whenever possible, and today's task was perfect to split into async jobs, here is my solution
e
you could use 
.sumOf { it.await() }
instead of 
.awaitAll().sum()
👍 1
d
x.map { async { block } }.awaitAll()
is just 
x.map { block }
if the code isn’t really async
nono 1
e
it's in the 
Default
dispatcher so it does actually spawn threads
probably performs worse than not forking since the work units are so small though
p
A nice simple day - shame it landed on a weekend and not a work-day.
Day09.kt
Interestingly I did find that 
asReversed
was slower than 
reversed
, and I'm only iterating that first list level, not indexing.
g
@ephemient docs say 
.awaitAll()
is seems to be better, because it's suspended function, can be cancelled and it fails immediately any of waiting job fails. I agree this is not more performant for this task, but I want to try and play with it this year 😉
👍 1
n
Is there any difference between zipWithNext and windowed(2)?
j
Not much. Zip... has a bit better performance
p
Yes - 
zipWithNext
when used with a 
transform
avoids allocating. When used without a 
transform
it will allocate a 
Pair<T, T>
which has property-access for 
first
and 
last
, and 
windowed
will allocate a list with two elements, which has index-access for the 
component1()
and 
component2()
(assuming destructuring). It may reuse the underlying list iirc when provided with a transform.
yes black 1
👍 1
Surprisingly, I'm finding 
windowed(2) { (a, b) -> b - a }
more performant than 
zipWithNext { a, b -> b - a }
😮 3
Copy code
Warmup finished after 10.000029300s with 3183 iterations
year 2023 day 9 part 1
	 Window took 320.367us (1.00x): 1743490457
	 Default took 349.463us (1.09x): 1743490457
	 WindowMap took 804.369us (2.51x): 1743490457
year 2023 day 9 part 2
	 Window took 329.255us (1.00x): 1053
	 Default took 355.929us (1.08x): 1053
	 WindowMap took 817.143us (2.48x): 1053
apparently for this case, 
kotlin.collections.MovingSubList
outperforms a normal list iterator.
Copy code
@AoKSolution
object Day09MutArray : PuzDSL({
    fun IntArray.next() = apply {
        for (i in lastIndex downTo 1)
            for (j in 0..<i)
                this[j] = this[j + 1] - this[j]
    }.sum()

    val parser = lineParser {
        it.split(' ').mapNotNull(String::toIntOrNull).toIntArray()
    }

    part1(parser) { histories -> histories.sumOf { it.next() } }
    part2(parser) { histories ->
        histories.sumOf {
            it.reverse()
            it.next()
        }
    }
})
This seems to be as fast as (if not slightly faster) @ephemient’s maths based solution - which I find interesting 😄 - then again, my "benchmarking" isn't the most precise.
r
Loops go brrr, right?
p
Indeed 😄 basically repeatedly replace the bottom n-1 indices with their deltas until they're all zero, leaving the n'th term remaining as the delta of each level. Then sum the deltas.
a
anything with the loop is probably optimized by CPU branch prediction... Anyway, if the code has good time complexity, it's enough. Optimizing further is actually coupling the code with more implementation details which is not good long term
j
difference at each step
I totally misunderstood the description and assumed the difference at a step is always an absolute value.
p
scratch that - maths still trumps loops.
Copy code
Benchmark               Mode  Cnt     Score     Error  Units
BenchDay09.arrayPart1  thrpt    3  6773.200 ±  47.510  ops/s
BenchDay09.arrayPart2  thrpt    3  6557.496 ± 960.668  ops/s
BenchDay09.mathsPart1  thrpt    3  7589.826 ± 284.387  ops/s
BenchDay09.mathsPart2  thrpt    3  7546.072 ± 765.402  ops/s
e
pretty close, though! and if our inputs were a couple orders of magnitude larger, mine would overflow 
Long
while yours should be still be OK
n
@ephemient that math solution, is it kind of lagrange interpolation?
e
@Nikita Merinov I derived it myself but later checked, it's a special case of https://en.wikipedia.org/wiki/Newton_polynomial
basically worked out by hand that
Copy code
[z] = 1z
            [y, z] = 2z -  1y
         [x, y, z] = 3z -  3y +  1x
      [w, x, y, z] = 4z -  6y +  4x -  1w
   [v, w, x, y, z] = 5z - 10y + 10x -  5w + 1v
[u, v, w, x, y, z] = 6z - 15y + 20x - 15w + 6v - 1u
once you see the pattern, it's pretty easy to prove
😀 2
j
Nice!
n
@ephemient Awesome, thanks.
k
late to the party. Played with recursion:
j
@maiatoday yes exactly the same, I did not change the code at all, just the parsing
e
I changed my solution to use tail recursion. Improves the total time a little.
k
Here's my solution... also played with recursion:
Copy code
private const val PART_ONE_EXPECTED = 114L
private const val PART_TWO_EXPECTED = 2L

private val space = """\s+""".toRegex()

fun main() {
    Logger.debug = true
    fun compute(input: List<String>, partOne: Boolean): Long {
        val op: (Long, Long) -> Long = if (partOne) Long::plus else Long::minus
        val getter: (List<Long>) -> Long = if (partOne) ({ it[it.size - 1] }) else ({ it[0] })

        fun findNextValue(list: List<Long>): Long {
            val intervals = list.windowed(2).map { it[1] - it[0] }
            return op(getter(list), if (intervals.distinctBy { it }.size == 1) intervals[0] else findNextValue(intervals))
        }

        return input.sumOf { findNextValue(it.mapLongs(space)) }
    }

    fun part1(input: List<String>): Long = compute(input, true)
    fun part2(input: List<String>): Long = compute(input, false)

    val input = readLines("Day09")
    val inputTest = readLines("Day09-Test")

    check(part1(inputTest) == PART_ONE_EXPECTED)
    check(part2(inputTest) == PART_TWO_EXPECTED)

    println(part1(input))
    println(part2(input))
}
p
I found tailrec slightly slower in my testing.
c
Suspiciously easy today. Makes me worried for tomorrow.
n
@ephemient After researching the wiki newton interpolation I have to say that yours one is lagrange. With lagrange interpolation you have the same polynomial coefficients for the same number of data points as you demo'ed. E.g. for 3 data points, coefficients are always 1 -3 and 3. So for input data 
[1, 2, 4]
result is 
1 * 1 + (-3) * 2 + 3 * 4 = 7
For input 
[1, 3, 6]
result is 
1 * 1 + (-3) * 3 + 3 * 6 = 10
On the other hand newton's one is more complex - it doesn't give straight coefficients to use and involves calculation of divided differences (it is almost the same what we were doing in the puzzle if following by the problem description), and computations will be different for different data points even if the number of points is the same. E.g. for 
[1,2,4]
result 7 is calculated by 
1 + (2-1) * (3-0) + (4-2 - (2-1))/2 * (3-0) * (3-1)
E.g. for 
[1,3,6]
result 10 is calculated by 
1 + (3-1) * (3-0) + (6-3 - (3-1))/2 * (3-0) * (3-1)
Of course it doesn't change anything, but I had to comment on "lagrange vs newton interpolation" topic 🙂
e
@Nikita Merinov on that page, "Newton forward divided difference formula" is recorded as
Copy code
N(x) = \sum_{i=0}^{k}{s \choose i}i!{h}^{i}[y_0,\ldots,y_i]
simplifying with h=1
I'm not producing a polynomial on 
x
and evaluating, which is what you'd get doing it the Lagrange way, although that's valid too
k
BTW did we just do derivation?
d
Yes, if you keep taking the derivative of a polynomial, its continuous tangent line, you eventually end up with a straight line with a dx / dy that is just a constant. And the derivative of a constant is 0 because it never goes up or down
n
"Newton forward divided difference formula" is recorded as
Copy code
N(x) = \sum_{i=0}^{k}{s \choose i}i!{h}^{i}[y_0,\ldots,y_i]
simplifying with h=1
That was exactly the formula I've used to show calculations for inputs 
[1,2,4]
and 
[1,3,6]
. The last part of that formula - 
[y0,...,yi]
- is the notation of divided differences. So it does not directly use input data (like 1,2,4 or 1,3,6), but their differences and differences of differences etc.
I'm not producing a polynomial on 
x
and evaluating, which is what you'd get doing it the Lagrange way, although that's valid too
There is no need to produce polynomial itself (I'm not even sure how one would do it dynamically, by building expression tree maybe), since we know 
x
we are searching interpolation for. Probably my sentence "polynomial coefficients" was bit misleading. Lagrange interpolation formula looks like (screenshot), and it operates directly on input (in opposite to newton's one). E.g. for the given input 
[1,2,4]
you only need to calculate coefficients 
c1, c2, c3
, so that the final result is 
c1 * 1 + c2 * 2 + c3 * 4
.
e
@Nikita Merinov Lagrange gives you a polynomial which lets you interpolate at any point 
x
. if you were to apply it to this problem, you could simply compute it once and then evaluate it at 
x=lastIndex+1
and 
x=-1
. but that requires more computation and is not what I built
(that is built into 
numpy.polynomial
as 
Polynomial.fit
, if you were in that environment)
a
Untitled.kt
Untitled.kt
n
@ephemient Any polynomial interpolation approach gives you a polynomial - both newton and lagrange - so you can interpolate at any 
x
. Lagrange is not special here, and so newton is not. "Newton forward divided difference formula" is specialized for evenly spaced 
x
- it just means it simplifies calculation a bit - but it still gives you a polynomial, which should work on any 
x
correctly spaced from the last one. But I'm afraid the discussion went in different direction. My very first point was about the formula you have provided - 
[x, y, z] = 3z -  3y +  1x
(and others) and your statement that it is a special case of newton polynomial. My comment was simply that - it's rather special case of lagrange, not newton. As I cannot see how one can easily transform newton formula to computation like 
3z -  3y +  1x
. If I'm wrong, could you please show how that can be done?
t
Part 1
Part 2
20 Views
Open in Slack
PreviousNext
Powered by