Fork me on GitHub

🧵Day 17 Solutions Thread: post your solution here

Miķelis Vindavs05:12:17

Classic AoC where part1 makes you feel like you should find a formula to solve it in constant time, but then part2 says “nope, it’s brute force after all simple_smile

😅 2
Miķelis Vindavs06:12:19

the y search space can be reduced to (range (dec y1) (- y1))


I hard coded one my bounds experimentally. I am sure I could figure out a more correct solution, but on AoC when you get the answer, it's time to sleep.


Thanks. I assumed something like that would be correct, but I wasn't sure.


@U89SBUQ4T that certainly speeds up my brute-force.

Miķelis Vindavs10:12:14

very nice parsing 👍:skin-tone-2:


thanks, although today we can avoid parsing, just store numbers in a map


I like your part1 😅


Closed form for part1, brute force for part 2 (but part1 gave me confidence about the bounds in the y direction):


the insight for part 1 (and for narrowing down the y space) is that after reaching as high as it can, the bullet will fall down to exactly zero height, and the next step must be within the target. if we want to reach as high as we can, the next step after reaching zero height will be at the bottom of the target. (this is assuming that the target is below 0, which is kind of implied in the problem description but I didn't assume in my code; I think I could have assumed that x is always positive too)


I've cleaned up my code with the assumption (again, kind of implied in the description) that the target is in the bottom right quadrant. it's shorter and prettier now

Antonio Bibiano20:12:23

Was happy to find a solution for part1 but then got super lazy about finishing part 2 :(


after some refactoring I ended up with one function which covers both cases and is short (`reductions` is huge helper here). But it was long process...


@U65FN6WL9 seems to work, however there are gaps in initial x velocities when target is missed. For example for x between 195 and 238 (my case) velocities between 81 and 97 miss the target.


I got a closed form solution (so no boundary checking necessary). 0.1ms, 7ms. writeup:

🙌 3
karol21:12:06 prior to any refactoring. I had a formula to find possible x-velocities but then for y velocities used the dumbest thing that works i.e minimum velocity is the lowest y of target and upper bound is 1000 which is less than ideal. Will try to optimize it later but I must admit solving AoC while having a flu is much harder than without one 😄

kevinc04:12:21 I got way, way too clever on my first try. I'd rather have to improve a slow naive solution than debug a fast, complex, wrong solution.


@U1EP3BZ3Q what "seems to work" but doesn't? I didn't do anything clever about x velocities; I just try all the ones that could possibly work


and even some that couldn't, but no big harm in that since my brute force code runs almost instantly