https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2023 day 6> :thread:
# advent-of-code
a
m
Nice break from all the harder ones we had
🙌 7
m
Part 1
Part 2
b
@Marcin Wisniowski Did you hold down the button the entire time?
😂 4
😃 1
Please make sure you let go of the button so the boat gets to move.
m
Part 2 was actually easier, because only one run. 😄
Yes, I held the button the entire time specifically to go against the narrator!
b
..<time
😄
m
That's one character more though, longer solution... 😄
🙌 1
🧠 2
n
Yeah, much simpler than yesterday. Only point was to use Long instead of Int for part 2.
m
To be fair, I bet the intend was to solve it smart, and when I looked at the input, I was amazed how fast loops go from 0 until 35696887 in my case
👍 1
n
yeah, also thought we might have to optimize more (e.g. jump ahead in 50%, then 25%...). But fast enough to not bother.
m
in any case, as expected, my solution is similar to @Marcin Wisniowski
Copy code
object Day6 : Challenge() {
    override fun part1() = input.lines()
        .map { it.split(" ").mapNotNull { it.toIntOrNull() } }
        .let { (a, b) -> a.zip(b) }
        .fold(1L) { acc, (time, distance) -> acc * (0..time).count { i -> (time - i) * i > distance } }

    override fun part2(): Any? {
        val (time, distance) = input.lines().map { it.substringAfter(":").replace(" ", "").toLong() }
        return (0..time).count { i -> (time - i) * i > distance }
    }
}
t
After yesterday's puzzle (where brute-forcing part 2 took very long), I decided to go smarter today (searching for first beating strategy from start and first from end). As it turns out, it wasn't profitable this time 😉
n
I always first create a class (or multiple classes) to capture the parsed data, so my code is always longer (but IMHO a little bit easier to read). So for today, I have a
Copy code
class Race(private val time: Long, private val distance: Long) {
        fun better() = (1..<time).count { (time - it) * it > distance }
    }
d
Blessed relief
e
It can be easily solved using brute force 😕
d
Didn’t bother to solve the quadratic
j
Oh man today was pretty easy, but I overslept, so I got pretty bad ranking sad panda https://github.com/bulldog98/advent-of-code/blob/main/advent2023/src/main/kotlin/year2023/Day06.kt
d
when the inner part of your loop is a few nanos you can get a lot of reps in
60808676 for me
0.06 seconds * nanos inside loop 🙂
j
Copy code
aoc2023.day6.part2() took 5m 1.039336083s and resulted with: 33875953
I have no shame 😆 (now that I have time, I’ll do it properly)
d
you certainly have to compute the distance travelled via formula, you can’t simulate it 🤣
or maybe you can??
(1..<time).count { velocity -> distance < velocity * (time - velocity) }
j
HUH. Almost all of that time was spent on console output, actually:
Copy code
aoc2023.day6.part2() took 35.238708ms and resulted with: 33875953
e
You can solve the equation and get the minimum and maximum "velocity" instantly.
j
@Dan Fingal-Surma almost. Unfortunately you can’t 
count
on LongRange
d
code compiles fine for me
Copy code
fun countWinners(time: Long, distance: Long) =
    (1..time).count { velocity -> distance < velocity * (time - velocity) }.toLong()
j
My code using quadratic formula: runs in 3.9μs (~1000 times faster than the brute force solution)
🙌 2
d
I didn’t want math homework 😅
j
I actually got out pen and paper for that part 😄
🧠 1
➕ 1
same 2
j
@Dan Fingal-Surma yeah the code compiles but returns Int, so, depending on the input file, you could fall into overflow
d
Ah, yeah my big time was < int32max
(I imagine all were)
j
Why doesn't 
LongRange.count{}
return a long?
d
Iterable<T>.count(): Long
j
.count() is on Iterable<T>
Copy code
public inline fun <T> Iterable<T>.count(predicate: (T) -> Boolean): Int {
    if (this is Collection && isEmpty()) return 0
    var count = 0
    for (element in this) if (predicate(element)) checkCountOverflow(++count)
    return count
}
_Collections.kt
d
checkCountOverflow
, which is nice
j
yes it is
m
my 'cleanup' for today:
Copy code
object Day6 : Challenge() {
    override fun part1() = input.lines()
        .map { it.split(" ").mapNotNull { it.toLongOrNull() } }
        .let { (a, b) -> a.zip(b) }
        .fold(1L) { acc, (time, distance) -> acc * solve(time, distance) }

    override fun part2(): Any? {
        val (time, distance) = input.lines().map { it.substringAfter(":").replace(" ", "").toLong() }
        return solve(time, distance)
    }

    private fun solve(time: Long, distance: Long): Long {
        fun solveQuadratic(a: Double, b: Double, c: Double): Long {
            val determinant = b * b - 4.0 * a * c
            val root1 = (-b + sqrt(determinant)) / (2 * a)
            val root2 = (-b - sqrt(determinant)) / (2 * a)
            return ceil(root2).toLong() - ceil(root1).toLong()
        }
        return solveQuadratic(-1.0, time.toDouble(), -distance.toDouble())
    }
}
y
Screenshot 2023-12-06 at 09.04.40.png
m
its a good thing I didnt start doing this version when I inititially started, I had to basically recheck with my actual answer on how to round the roots. My first thought was to round down the max and round up the min, but apparantly, you need to round them both up and I can't get my brain to understand why.
same 1
s
Tried to strike a balance between conciseness and readability
j
@Michael de Kaste because let's say times 3..7 are winning, then you have 7 - 3 + 1 = 5 winning times. So it's more like, you need to round one up and one down, but add 1 at the end. Adding the 1 at the end is equivalent to rounding both up.
j
I don’t know yet how to solve it “computionally” and still stay in integer (or long) numbers. I hate going into floats. Best I can do is binary search for roots, but that’s only O(log(n)), not O(1)
m
@Johannes Gätjen A yes, the extra 1! that makes total sense now 🙂 thanks
👍 1
p
j
My part 2 takes about 337ms, so far the easiest. I can go to bed now!!! advent of code intensifies
y
Lol mine takes 8ms
e
With the cuadratic equation both take 0ms
y
How zero if you need to parse the input 🌚
Mine with quadratic is 8ms
🙌 1
j
Please share here, it would be great to see your approach.
y
m
don't get too hung up on times, my quadratic solution solves in 0.5ms. It depends on the processor and how the input is parsed and all that
j
still naive but a bit less
Copy code
fun calc(t: Long, d: Long): Long {
    var i = 0L
    while ((t - i) * i < d) i++
    return t - i - i + 1
}
resulted in
Copy code
Input(time=47     70     75     66, distance=282   1079   1147   1062)
aoc2023.day6.part1() took 1.270708ms and resulted with: 281600
aoc2023.day6.part2() took 5.151250ms and resulted with: 33875953
But I have this itch I can’t scratch: I know it’s not the PROPER solution, even if blazingly fast 🙂
r
glad it was an easy one today! my calculation method:
Copy code
fun countWaysToWin(t: Long, d: Long) =
    (d / t..t - (d / t)).count { x -> (t - x) * x > d }
of course far from optimal like the quadratic solution, but at least I somewhat narrow the search space compared to iterating from 
0
to 
t
😅
a
fortunately, my part 1 method works for part 2, not iterative. find shortest & longest only, then get the diff + 1 now I need to un-copy-paste. aka refactor
e
https://github.com/ephemient/aoc2023/blob/main/kt/aoc2023-lib/src/commonMain/kotlin/com/github/ephemient/aoc2023/Day6.kt I did the quadratic formula approach right away, but got the math wrong a couple times, oops
j
wasn’t that hard to write integer sqrt after all 🙂 https://github.com/jakubgwozdz/advent-of-code-2023/commit/259f25f
p
Kinda sad it was over so quickly.
Day06.kt
w
Isn’t the idea to find the roots of quadratic equation, e.g. using any of these methods (it’s a shame it can be brute forced): https://encyclopedia.pub/entry/29233
p
Most likely, but loops go brrrr.
😀 3
w
answer = abs(root1 - root2) + 1
If you know one x which gives a valid distance you can do two binary searches, one up and one down to find the roots
Something like the following:
Copy code
// Part 2
    val totalTime = timeValues.joinToString(separator = "").toLong()
    val totalDistance = distValues.joinToString(separator = "").toLong()
    val initialEstimate = totalTime / 2
    require(distTravelled(totalTime, initialEstimate) > totalDistance)
    val lowerBound = binarySearch(0, initialEstimate, inverted = true) {
        distTravelled(totalTime, it) > totalDistance
    } ?: error("No value found")

    val upperBound = binarySearch(initialEstimate, totalTime, inverted = false) {
        distTravelled(totalTime, it) > totalDistance
    } ?: error("No value found")

    // Answer
    println(upperBound - lowerBound + 1)
a
wondering if anyone else went for this or mostly doing 
.count { }
? > fortunately, my part 1 method works for part 2, not iterative. find shortest & longest only, then get the diff + 1 still slightly brute-forcey for the edge-cases but not over the whole range:
Copy code
private fun isPressTimeWin(pressTime: Long, time: Long, distance: Long): Boolean =
    (time - pressTime) * pressTime > distance

private fun numberOfWins(time: Long, distance: Long): Long {
    val shortest = (1L..<time).first { isPressTimeWin(it, time, distance) }
    val longest = (time - 1L downTo 1).first { isPressTimeWin(it, time, distance) }
    return longest - shortest + 1
}
the only potential gotcha is the 
> distance
vs 
>= distance
check. since a tie for first place is also a win - but not in AoC puzzles 😱
p
j
@Werner Altewischer you can even limit it to one binary search, it’ll be symetric after all
d
This day made me feel a lot smarter than yesterday 😓 I just brute-forced it, but it's semi-obvious that there is a symmetry to how many wins you can get, it is like an inverse parabola (meaning it is some form of y = -x2) that you have to find the range for where y > some value and there are 2 x-values where it intersects with the line y = distance
Since the time you hold the button is also the speed, the distance you travel given a button holding time B is actually with total time T: (T - B) * B = TB - B2 and that's where the quadratic thingy pops up, in the B-squared
Okay, some math here (don't be scared): the formula for the distance, let's call it y to get into familiar territory and let's call the time you hold the button x, is 
y = tx - x2
Rearranged that gives us
Copy code
y = -x2 + tx
And remember, t is just a constant If we take the first example of part 1 and solve for y = 9, the distance we need to beat, we use the quadratic formula (https://en.wikipedia.org/wiki/Quadratic_formula) to get x1 and x2 of this range. In this case we want to solve 
ax2 + bx + c= 0
for 
a = -1, b = t (total time) and c = - distance
This gives us x1 ~ 1.7 and x2 ~ 5.3 Obviously we can't hold the button fractions of a millisecond so we have to round up at the lower end and down at the top end, so we get 2 and 5. This is our range and there are 4 numbers in that range, 2, 3, 4 and 5 and this gives us the total number of wins
🙌 1
w
Copy code
// Part 2
        val totalTime = timeValues.joinToString(separator = "").toLong()
        val totalDistance = distValues.joinToString(separator = "").toLong()

        // x * (totalTime - x) - totalDistance = 0
        // -x^2 - totalTime * x  - totalDistance = 0
        // a = -1, b = -totalTime, c = -totalDistance
        val (root1, root2) = solveEquation(-1, -totalTime, -totalDistance)

        val upperBound = floor(max(root1, root2)).toLong()
        val lowerBound = ceil(min(root1, root2)).toLong()

        // Part 2
        println(upperBound - lowerBound + 1)
Copy code
private fun solveEquation(a: Long, b: Long, c: Long): List<Double> {
    val d = b * b - 4 * a * c
    return if (d >= 0L) {
        val denominator = 2.0 * a
        if (d == 0L) {
            listOf(-b / denominator)
        } else {
            listOf((-b + sqrt(d.toDouble())) / denominator, (-b - sqrt(d.toDouble())) / denominator)
        }
    } else {
        emptyList()
    }
}
high school algebra indeed
d
Just one correction for my methodology, it solves for ties as well, so you can do 
b = - (distance + 1)
or another way to make sure you solve for the distance + 1 mm to make sure you beat it
After refactoring, the heart of my solution looks like this:
Copy code
private fun getNumberOfWins(timeInMs: Int, distanceInMm: Long): Int {
        val c = -(distanceInMm + 1)
        val d = (timeInMs.toLong() * timeInMs - 4 * -1 * c).toDouble()
        val root = sqrt(d)
        val x1 = ceil((-timeInMs + root) / -2).toLong()
        val x2 = ((-timeInMs - root) / -2).toLong()
        return (x2 - x1).toInt() + 1
    }
So I inlined -1 as 
a
, timeInMs as 
b
and 
- (distanceInMm + 1)
as 
c
PS: This might have been discussed before, but I try not to look at too many other solutions in these threads to not spoil it for myself, so apologies if this is some kind of deja-vu for some of you
k
How about this approach:
Copy code
val min = (1..time).first { (time - it) * it > distance }
val max = time - (2..time).first { ((distance) / it) < (time - it) }
max - min + 1 //<-- answer of each race
d
That would certainly work too although in your case it might be more useful for the max to go from (time..2) instead of (2..time)? But I also observed another symmetry here, since the formula always goes through 
(0, 0)
it means that the 
max
value is always the same as 
time - min
, so let's look at the first example: the min is at x = 2, so the max is at x = 7 - 2 = 5. This means that we only have to calculate the first value, 
x1
or the 
min
or what you want to call it, and simply do 
x2 = time - x1
k
yes! max doesn't need to be calculated again. (time - min) is the value. THX. @Davio
🎉 1
d
After adding some extension functions such as 
squared
, 
sqrt
and 
roundUp
, it now looks like this:
Copy code
private fun getNumberOfWins(timeInMs: Long, distanceInMm: Long): Long {
    val discriminant = timeInMs.squared + 4 * (-distanceInMm - 1)
    val min = ((-timeInMs + discriminant.sqrt) / -2).roundUp()
    return (timeInMs - 2 * min) + 1
}
I combined some of the calculation parts which makes it less readable, or less explicit, but at the core it's the same thing
k
r
I found something to do with 
zip
today
e
FYI you can directly
Copy code
aList.zip(bList) { f(a, b) }
instead of
Copy code
aList.zip(bList).map { (a, b) -> f(a, b) }
✅ 1
j
rather
Copy code
aList.zip(bList) { a, b -> f(a, b) }
? or
Copy code
aList.zip(bList, ::f)
?
👍 1
d
Well, you should never let a chance to name a thing go to waste 😄 In any case, I decided it was time for another extension function, so for part 1 I can now do:
Copy code
return times.zip(distances).multiplicationOf { (t, d) -> getNumberOfWins(t, d) }
It's like 
sumOf
, but for multiplication
e
I just did (effectively) 
times.zip(distances, ::wins).fold(1, Long::times)
p
I tend to use 
.fold(1, Long::times)
or similar in lieu of 
.product()
or 
.productOf {...}
same 1
keep being tempted to throws some extension methods in for those, but never get around to it
j
and even 
.reduce(Long::times)
🙂
🤣 1
p
when I remember 😄
d
I usually also don't do it, but I had the time and thought okay let's do it. And while I added it I discovered I already had another function to split a list into groups, to help parse inputs that are groups of lines split by empty lines, oh well that would have been useful earlier..
j
Kill em all lambdas
Copy code
data class Input(val time: String, val distance: String)

fun String.longs() = split(" ").filterNot(String::isBlank).map(String::toLong)
fun Input.zipLongs() = time.longs().zip(distance.longs(), ::calc)
fun calc(t: Long, d: Long): Long = t - 2 * lastNotBetter(t, d) - 1
fun lastNotBetter(t: Long, d: Long) = (t - (t * t - 4 * d).isqrt(ceil = true)) / 2

fun part1(input: Input) = input
    .zipLongs()
    .reduce(Long::times)

fun Input.fixForPart2() = Input(time.filterNot(Char::isWhitespace), distance.filterNot(Char::isWhitespace))
fun part2(input: Input) = input
    .fixForPart2()
    .zipLongs()
    .reduce(Long::times)
There is so much you can do with references in kotlin!
e
or write the lambdas in a way that doesn't look like lambdas blob wink
Copy code
foo.let(fun(foo: Foo) = bar)
yes black 2
c
Ridiculously simple today. Part 2 runs instantly despite being pretty sure there's a cleverer way of doing it. I've spotted the output is a mirror so there'll be a quick mathsy way of solving it but when it runs so quickly anyway why bother. Didn't even have to bother parsing the input. Why wasn't this the day 1 puzzle? 😂
Copy code
private val input = listOf(55 to 401, 99 to 1485, 97 to 2274, 93 to 1405)
private val input2 = 55999793L to 401148522741405

fun main() {
    println(part1())
    println(part2())
}

private fun part1() = input
    .map {
        (1..<it.first).count { holdTime -> holdTime * (it.first - holdTime) > it.second }
    }.product()

private fun part2() = input2
    .let {
        (1..<it.first).count { holdTime -> holdTime * (it.first - holdTime) > it.second }
    }
j
Because you can't have the boat race unless you've first been launched on the trebuchet
blob think smart 3
👍 1
t
I am not great at math so I solved part 2 by coming at the problem from both ends and subtracting, then rewrote part 1 to use that method as well. • Blog • Code
K 1
n
What about a binary search to find the boundaries?
j
That’s what I expected myself to do had the bruteforce been too slow. The optimum is at half the time so binary search between 0 and half would get you one boundary, and due to the symettry you can easily calculate the other boundary from the one you find. I wonder if it would perform faster than the quadratic formula approach. I don’t think it’s true that sqrt runs in constant time
n
I also think that once we found the start, it should point us to the end as well because it looks to me the curve is symmetrical. Of course, given how fast a simple brute force solution works, this is lots of over-engineering.
d
Yes once you find the first winning time, the other end should be at reflection point by t/2
x + 2(t/2-x) = t - x -> t - 2x + 1 winners Better to do that after the simple thing works so you can check for errors 😃
j
Yes and happy of it.
🧠 1
😁 2
🤣 1
d
You could indeed binary search for the first intersect if you wanted
n
@Davio That handling of roots works for my puzzle input, and presumably yours, but I'm not sure if it works if the roots fall squarely upon the given distance (pardon the pun). I think it would fail because we want to count all the values that exceed the distance, not just meet the distance. Instead of ceil(x) I think you want floor(x) + 1. That gives the same number for 8.3 (9), but a different number for 8.0 (9 instead of 8 ) then. And then for the other root you want ceil(x) - 1, which gives the same number for 8.3 (8), but a different number for 8.0 (7 instead of 8 ). h/t (per usual) to @ephemient
k
can't we aim for distance + 1 ?
🙌 1
e
A bit late but this is my soln
t
I'm a bit behind with my solutions (curse you day 5 part 2!), but here is my solution for day 6. I've gone with an analytical solution. I'm also happy with these timings. (Pre-parsed input and no printing.)
nvm... these results were with input-parsing.
k
Part 2, using the quadratic formula:
19 Views
Open in Slack
PreviousNext
Powered by