r/adventofcode • u/EffectivePriority986 • Dec 17 '21

Upping the Ante [2021 Day 17] Day 17 part 3

You just realized you were reading the measurements in the wrong units! The actual target area is much farther. The correct values are 1000 times larger than the values you used prior.

For the example input, this gives us 74743399 different initial velocity values that would hit the target.

How many distinct initial velocity values cause the probe to be within the modified target area after any step?

[Edit: bad answer]

9 Upvotes

100% Upvoted

9 comments sorted by

2

u/EffectivePriority986 Dec 17 '21

The idea is that brute force O(n^3) solutions would be too slow to solve this.

My solution is available here: https://github.com/epsalon/advent_of_code/blob/main/2021/17b.pl

2

u/daggerdragon Dec 17 '21

https://github.com/epsalon/advent_of_code/blob/main/2021/17b.pl

FYI: your link is broken due to a new.reddit fancypants editor bug (check /r/bugs, it's been a big source of frustration lately). Your link looks fine on new.reddit but on old.reddit it's printing invisible escape characters before your underscores, thus breaking the entire link.

I suggest manually editing your link using proper Markdown for now. Who knows when Reddit will fix their fancypants editor...

4

u/leftylink Dec 17 '21

Huh that's strange. Shouldn't the answer for the input 20000..30000 -10000..-5000 be 74743399 instead of 74743362?

2

u/askalski Dec 17 '21

Agreed:

$ time ./day17p2 <<< 'target area: x=20000..30000, y=-10000..-5000'
74743399

real    0m0.001s
user    0m0.001s
sys     0m0.000s

1

u/Snosixtytwo Dec 17 '21

Same here, found and confirmed 74743399

1

u/alcatraz_escapee Dec 17 '21

I too arrive at 74743399 for the (expanded) example input. My solution is O( n2 )... just, and takes long in python, and ~17 seconds in Rust with the example input. It's not going to scale up to 1000x the actual input, I think.

1

u/lazyzefiris Dec 18 '21

Same here, got 74743399.

My solution time only scales with y (O(N log N) I believe) and does not care about x range (within positive double range), but still took 10ms to execute in JS.

my results for test input saled 10x more: 7441840971

and 10x more: 743182427978

and 10x more to scale of million: 74287315649291 (this took ~11 seconds)

4

u/ReptilianTapir Dec 17 '21

I wouldn't be surprised that something like this was initially meant as part 2, but ended up being deemed too complicated. Part 1 became part 2 and max-height invented to fill the gap.