https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2021 day 17> :thread:
# advent-of-code
a
d
Wow I ugly brute-forced this but it worked.
i
Yeah, I spent several minutes trying to figure all these movement equations, and then I was like "Ah screw that, just simulate it and see what hits".
💯 1
j
ok, but how do you know what “deltaY” range to simulate? having 
y=-115..-63
I ended up with 
dy=-115..115
covering all possibilities, but I have no idea (yet) why is it enough :)
d
I’m trying to use 
sequence
or 
generateSequence
but keep getting:
Copy code
File being compiled: problem_17.main.kts
The root cause java.lang.RuntimeException was thrown at: org.jetbrains.kotlin.backend.jvm.codegen.FunctionCodegen.generate(FunctionCodegen.kt:50) (problem_17.main.kts): org.jetbrains.kotlin.backend.common.BackendException: Backend Internal error: Exception during IR lowering
File being compiled: problem_17.main.kts
The root cause java.lang.RuntimeException was thrown at: org.jetbrains.kotlin.backend.jvm.codegen.FunctionCodegen.generate(FunctionCodegen.kt:50)
Weirdly changing 
Vector.next()
from member to extension fixes it
j
I had a ton of fun today with sequence generators and operators overloading!
(and they say you can’t compare apples to oranges. OF COURSE YOU CAN)
🟧 1
🍎 1
m
https://github.com/mdekaste/AdventOfCode2021/blob/main/src/main/kotlin/year2021/day17/Day17.kt not sure if my bounds on velocities to check are correct, but it seems to work for both input and test input. I know that the minimal x should be the solution to 
x² + x - 2 * xMin = 0
rounded up, but ended up with approximating it with 
sqrt(2.0 * xMin).roundToInt()
j
same 2
e
@Dan Fingal-Surma please, file a bug with a code that crashed compiler.
m
haha @Jakub Gwóźdź, I made that same meme for my work colleagues. "Using logic to reasonably conclude bounds on velocities vs Just fucking yeet a shitton of them"
🤣 3
d
Will do — I’ll get a minimum reproducing case
j
Ahhh it turns out that it can be easily proven than with y bounds like 
[y1..y2]
(as long as both are negative) the proper max vertical velocity is 
-y1-1
… anything more and probe overshoots (as it has too much velocity when hitting the surface on way back down)
d
Can confirm that 
for (y in target.min.y..1000) {
--> 
for (y in target.min.y..-target.min.y) {
yields the same answers
ah yes, it crosses the y=0 line at -initialVelocity.y speed if the initial aim was up
Because symmetry
e
It’s an “Advent of Code”, not an “Advent of Math”
🧮 3
d
lol
e
basically, delta-y definitely has to be in [-Y, Y] where Y is the absolute max Y bound. if it's smaller, it'll jump directly from the starting point to below the target; if it's larger, after its rise and return to the origin, it'll fall below the target within a single step
I have somewhat tighter bounds in my Haskell solution but it doesn't seem necessary
(this logic does break if the target straddles the X axis, but I'm excluding that input via regex so it's fine :))
d
t
Even brute forcing is really fast, with using 
generateSequence
it only takes ~400ms. I really enjoyed this one 🙂 reminds me of

https://archive.org/download/win3_BANGBANG/screenshot_00.jpg▾

m
m
@Michael Böiers vx -= vx.sign 👀
🙌 1
Michaels together strong
m
Michaels for the win! I also got rid of the fold, easier to mapToNull to entries and then create the map. 🙂
Boiled it down to 26 readable lines. Would be interesting to see what this would look like in Java - or in Go. Some languages are just more concise than others …
e
Using 
;
in Kotlin is clearly a cheat.
t
I ended up brute forcing it. I’m not great at math and am in a hurry (about to start a two day road trip) so I didn’t spend the time to figure it out. I ended up using a sequence to simulate tracks. • Blog • Code I’ll be late or a day behind with tomorrow’s solution due to travel.
m
@elizarov Cheat in terms of LOC? I understand the reasoning. I’m using the official rules for formatting the code though, and in this case I think it is still very readable. But thank you for making me aware of the rules 😊
e
Franky, I also use 
;
sometimes myself, but I would only use it when I need to show that certain pattern repeats from one row to the next. In general, though, 
;
in Kotlin is discouraged.
👍 1
m
Well, now it’s 27 readable lines without any semicolon 😎
n
anybody else do part 1 in their head 😎
now I gotta break out the code for part 2 lol
l
Compute min/max velocities for x/y, then cartesian product to have all initial velocities that might work, then the answer finds itself. Easy peasy https://github.com/TheSunshinator/Advent-of-Code-2021/blob/main/src/day17/DailySolution.kt
d
@Michael Böiers golang solution without input parsing: https://github.com/dfings/advent-of-code/blob/main/src/2021/problem_17.go
(I'll add input parsing in a bit)
m
Nice! I’m down to 25 LOC (without semicolons) 🙂 Of course you’re probably not going for minimal LOCs, but you could maybe get there …
This is what could give you the edge 🙂 
px, py, vx, vy = px+vx, py+vy, Max(0, vx-1), vy-1
🤣 1
d
I could try... Don't really need the Target struct
m
I also started with a data class for the probe which I then removed because it didn’t add any clarity after all.
Added proper input parsing and tweaked to code to remain at 25 LOC. I wonder whether there’s a clever way to simplify this in Kotlin.
Copy code
Regex("""x=(.+)\.\.(.+), y=(.+)\.\.(.+)""").find(readln())!!.destructured.toList().map(String::toInt)
Down to 23 20 LOC. I’ll leave it at that …
Copy code
fun main() = Regex("""(.+)\.\.(.+)""".let { "x=$it, y=$it" }).find(readln())!!.destructured.toList().map(String::toInt)
    .let { (tLeft, tRight, tBottom, tTop) ->
        (1..tRight).flatMap { vx -> (tBottom..-tBottom).map { vx to it } }.mapNotNull { (vx0, vy0) ->
            var maxY = 0
            var hitTarget = false
            var x = 0
            var y = 0
            var vx = vx0
            var vy = vy0
            while (x <= tRight && y >= tBottom) {
                x += vx
                y += vy
                vx += 0.compareTo(vx)
                vy += -1
                if (y > maxY) maxY = y
                if (x in tLeft..tRight && y in tBottom..tTop) hitTarget = true
            }
            maxY.takeIf { hitTarget }
        }
    }.apply { println(maxOf { it }) }.run { println(size) }
p
e
I've updated my solution to be much more efficient, O(W + H) rather than O(W * H)
p
d
String::toIntOrNull
nice
k
k
3 Views
Open in Slack
PreviousNext
Powered by