https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2023 day 11> :thread:
# advent-of-code
a
d
Modeled the problem correctly in the first place so part 2 was trivial (modulo an off by one error that took a few mins to track down)
same 1
(the 
e - 1
part was the off by one error, 
e
= expansion factor)
👍 5
☝️ 1
t
nice problem 🙂 But I modeled the part1 in the brute-force way so I had to redo it for part 2 😕 PS. Funny that they didn't provide the exact expected result for test input for problem 2.
d
I started thinking about how to insert characters into the string and decided it was too complicated lol
m
I expected what part 2 is going to be, but my solution was a dead end so this is my worst time so far. Then the actual correct solution solved both...
b
the off by 1 got me too
n
Same here: solved part 1 by adding empty rows/cols, but then part 2 was actually simpler than part 1.
l
Yes, part 2 is the same as part 1 with a configurable expansion rate and Long for the sum
j
For part1 i inserted rows/columns and decided for part 2 that I had to do the column/row insertion virtually, since it only mattered for galaxies
n
Had the same off-by-one error. I'm not the first, and I certainly won't be the last!
💯 1
e
l
Oh I avoided that off-by-one error thanks to reusing code for part 1. The factor is 2 in part 1 and I only added 1 to each coordinate so I immediately use factor - 1 to keep it working
d
For part 1 I just did
Copy code
fun makePoint(x: Int, y: Int) = Point(
    x + colsToExpand.count { x > it }, 
    y + rowsToExpand.count { y > it }
)
so then I did count times 1m which is wrong
➕ 1
m
Part 2 (part 1 just has smaller expansion)
n
I again ran into the Int overflow for part 2. Would be soo great if Kotlin would throw exceptions for Int (or Long) overflows.
❤️ 1
b
i stared at it too long trying to think of a way to easily insert a column of text, eventually gave up and did it virtually which made part 2 easy:
Copy code
val ys = lines.indices.filter { lines[it].all { c -> c == '.' } }
val xs = lines.first().indices.filter { lines.all { line -> line[it] == '.' } }
fun expandedX(x: Long) = x + xs.count { it < x } * (n - 1)
fun expandedY(y: Long) = y + ys.count { it < y } * (n - 1)
buildList {
    lines.forEachIndexed  { row, line ->
        line.forEachIndexed { col, c ->
            if (c == '#')
                add(PointL(expandedX(col.toLong()), expandedY(row.toLong())))
        }
    }
}
Copy code
sequence {
    val seen = mutableSetOf<PointL>()
    galaxies.forEach { p ->
        seen += p
        yieldAll((galaxies - seen).map { p to it })
    }
}.sumOf { (a, b) -> (a mdist b) }
r
off-by-1 error 🙋 , implemented part 1 correctly which made part 2 super easy (saw that one coming) 🙋
e
@Norbert Kiesel I haven't updated this workaround in a while but it should still work (beyond possibly updating ASM for newer Java versions) https://kotlinlang.slack.com/archives/C87V9MQFK/p1672167437730299?thread_ts=1671963784.115849&amp;cid=C87V9MQFK
n
I remember looking at this some time ago. Perhaps something can be done about a compiler plugin once k2 and KSP2 are released.
e
KSP is unrelated, it can only add code'
m
First did zipping and passing on, but I went back to my trusty TreeMap
Copy code
object Day11 : Challenge() {
    private val parsed = input.lines()
        .flatMapIndexed { y: Int, s: String -> s.mapIndexedNotNull { x, c -> (y to x).takeIf { c == '#' } } }

    private fun holes(selector: (Pair<Int, Int>) -> Int) = parsed.asSequence()
        .map(selector)
        .sorted()
        .distinct()
        .zipWithNext { a, b -> b to b - a - 1 }
        .toMap(TreeMap())

    override fun part1() = solve(2)
    override fun part2() = solve(1000000)

    private fun solve(expansionAmount: Int): Long {
        val holesY = holes { it.first }
        val holesX = holes { it.second }

        val newPlaces = parsed.map { (y, x) ->
            val holesBeforeY = holesY.headMap(y, true).values.sum()
            val holesBeforeX = holesX.headMap(x, true).values.sum()
            y + holesBeforeY * (expansionAmount - 1) to x + holesBeforeX * (expansionAmount - 1)
        }

        return newPlaces.flatMap { (y1, x1) -> newPlaces.map { (y2, x2) -> abs(y2 - y1) + abs(x2 - x1) } }
            .sumOf { it.toLong() } / 2
    }
}
e
I’ve also got bitten by an int overflow on part 2. Unfortunately, it is quite expensive to do overflow-checked arithmetics on JVM, so it cannot be a default behavior. Adding support for 
CheckedInt
as a library is an option, but it would be, inevitable, somewhat cumbersome to use, as it is not a default.
👍 3
d
Once I saw 1M I immediately did find/replace Int to Long 😂
same 2
e
I’ve actually thought about overflow, but my mental arithmetics was wrong. I did keep a total in long, but when counting contribution from each row and column I’ve multiplied the scaling factor by the number of times the paths cross this row/column. Somehow, I thought that the second multiple is not going to exceed 1000 (because I already saw around ~500 galaxies in my input), so 1M times 1000 would still fit into an int. In reality, the second multiple is an order of magnitude of a square of a number of galaxies and reaches to ~50k, overflowing int when multiplied by a scaling factor.
d
j
I noticed the off-by-one error, but was to lazy to fix it in the solution part, I just changed my calling code to
Copy code
part2(input, 999_999).println()
think smart 4
😂 1
➕ 2
j
For me going with 
Long
was not much of an issue (I expected that as soon as I looked at input data), but the ugliness came with indexing operator 
[]
, which enforces 
Int
so I had to cast back like 
rows[r.toInt()] to cols[c.toInt()]
Untitled.pas
e
@Dan Fingal-Surma the existence of 
checkedAdd
isn't an issue, it exists in standard Java as 
Math.addExact
. that doesn't solve how to make that ergonomic (so you can write code using the normal 
+
etc. operators)
with my javaagent poc, it can
Copy code
@CheckedArithmetic(mode = CheckedArithmetic.Mode.CHECKED)
fun thisWillThrow(): Int {
    for (x in listOf(1)) return x + Int.MAX_VALUE
}

@CheckedArithmetic(mode = CheckedArithmetic.Mode.UNCHECKED)
fun thisWillWrap(): Int {
    for (x in listOf(1)) return x + Int.MAX_VALUE
}
but because of the layer it's working at, it can't apply to specific blocks or expressions within a function, it potentially breaks things that are inlined (like unsigned integers), and it can't apply to Kotlin lambdas. that's something the compiler could do properly, though
k
Yeah, I have been using my `Sint`s for a while now (safe integer) they are longs but also have additional overflow detection. Their biggest downside is that you can't do 
value == 0
, I need to use an extension property to get it to work 
value == 0.s
m
Couldn't you implement 
equals
on your 
Sint
that works with normal integers?
e
not legally
k
well that would work with 
value == 0
but not with 
0 == value
, but I also made them inline classes, so I can't override equals
e
I ended up rewriting my solution to split by axis, since manhattan distance and the cosmic expansion are both independent. this means I can get it to O(N^2 + M^2) instead of O((NM)^2), where the input is sized NxM
k
huh O(N² + M²) is the same as O((n+m)²)
e
indeed, but it is not O(N²M²)
a
I got lucky with part1 for this one, so I didn't have to do anything for part except scaling factor. there was off by one thingy but it's not my first rodeo so I just enumerated +/-1 in all places to lockpick a winning combo. https://github.com/andriyo/advent-of-code-kotlin-2023/blob/main/src/Day11.kt non-mutable everything but it wasn't hard. Again, those Long shenanigans so I had to 
reduce
instead of 
sum
Also used TreeMap for faster lookup, so there is a binary search somewhere
e
sum
works fine on 
Long
👍 1
a
oh you right - must be somewhere earleir I had to convert so I replaced sum() just to be safe
there was somehting that didn't work with 
Long
.. 
count()
?
k
count
always returns an int. But you also can't have lists that are longer than the max integer
a
I did a sequence...
p
e
even if you did have sequences longer than 
Int.MAX_VALUE
it would take a long time to 
count()
that high…
🥁 1
a
> I noticed the off-by-one error, but was to lazy to fix it in the solution part, I just changed my calling code to >
Copy code
part2(input, 999_999).println()
@Jaap Beetstra I did exactly the same 😂 just to test part1 with part2's math, I did 
Day11(testInput).partTwo(1)
and it's not an off-by-one when the multiplier is 1 🤔 I suppose "double" means factor = 2, or add = 1. so if we made the corresponding change to both parts, then 1_000_000 would be correct
a
@ephemient it only takes one extra +1 to ruin a perfectly good Int ) here it is where I used it https://github.com/andriyo/advent-of-code-kotlin-2023/blob/main/src/Day08.kt not saying it's unavoidable but the fact is that count() returns Int, and it's possible imagine a situation where it might not be enough )..
e
that one doesn't make sense… none of the loops are that long so 
.count().minus(1).toLong()
would have worked fine
a
that particular example is remains of the code that was brute forcing Part 2 ) before LCM optimizations - and i'm not saying it's unavoidable there of course, jus an example, there might be other cases where it's needed to count more than Int.MAX
p
j
With the obvious (now) protip that for manhattan metric you can calculate x and y distances separately, the code again allows kotlin’s stdlib to shine. ZipWithNext+RunningFold go brrrr
Untitled.kt
k
Had an 'off by 1' error on part 2 that made me waste a bit of time. I had to re-factor my code from part 1 to part 2 as filling `List`s just would not work when expanding the galaxy by > 10
e
Can someone please explains what kind off-by-one errors are you making here? I’m genuinely puzzled.
m
to expand space from 1 tile to 2, you need to "add" (2 - 1) rows to expand space from 1 tile to 1000000, you need to add (1000000 - 1) rows
k
Each empty line becomes 1 million empty lines, a lot of people by accident add 1 million lines which gives you 1 million and one instead
👍 2
👍🏻 1
c
I just added 1 and 999999
e
I see. I just have an array of row and column factors (1 or 2 in part 1), so there is no chance for such a mistake in principle.
m
A nice and easy one today, and I fortunately picked the efficient approach from the start 🙂 https://github.com/MikeEnRegalia/advent-of-code/blob/master/src/main/kotlin/aoc2023/day11.kt
^^ very nice and generic solution. 😎
t
That was a nice simple one compared to yesterday for me. I didn't have any off-by-one issues and knocked this out pretty quickly. A rare instance of correctly predicting part 2. 🙂 The one thing missing is a built-in "permute this list" function. Not difficult to write one, but it feels like something that should be in the standard lib. • Blog • Code
e
permute in what way, do you mean transpose (which I can see being useful)?
n
Permute this list: agreed. However, this is a more restricted permutation. I have a permutation method in my utils, but that only creates full permutations instead of only pairs. So will look into changing that to accept a "length of returned permuted lists" parameter
e
oh I see your code is taking the cartesian product. I would not call that a permute
m
Neat puzzle. Part 2 only required me to extract the expansion factor as an parameter. First solution:
d
Yeah rather than an array of factors for every row column I just maintain a list of row / column indexes that need to be expanded, and for any give x or y count how many expanded rows / columns are less that that value in order to calculate the projected coordinates. If you then multiply that count by 1M you get 1 too many inserted rows/columns.
Yes this is unordered Cartesian product
b
it's not permutation, is combinations of length 2
d
I'm trying to understand how processing rows and columns separately improves runtime
n
Yeah. And python has stdlib implementation for both
d
e
Dan: there's fewer pairs to consider
d
You don't have to consider the Cartesian product each time?
t
Fair enough, I named it poorly
e
if your galaxies are at X coordinates [1, 1, 3, 3], you don't have to do all [(1, 1), (1, 3), (1, 3), (1, 3), (1, 3), (3, 3)] pairs. you can just do a single (1, 3) pair and then adjust the result
there's no duplicates if you're looking at (x, y) simultaneously, but on one axis at a time…
(there's also a linear-time solution, which I haven't coded up yet but I have plans for)
d
I see you multiply by count that has the same x or y?
e
yes
r
Not that, it was needed, but https://github.com/shiguruikai/combinatoricskt came handy. 😂
e
you can see the 
a * b
multiplication in my current solution (subject to change when I optimize later though)
t
Thanks for pointing out my naming issue - fixed (mostly).
n
image.png
x
I'm catching up late, but day 11 was pretty easy compared to day 10 https://twitter.com/IsuruKusumal/status/1735292380440563764
n
Then Day 12 hits like a ton of bricks... 😭
true story 2
🫠 2
23 Views
Open in Slack
PreviousNext
Powered by