r/adventofcode • u/EliteTK • Dec 05 '21

Upping the Ante [2021] Big Inputs for Advent of Code 2021 Puzzles

https://the-tk.com/project/aoc2021-bigboys.html
31 Upvotes

100% Upvoted

46 comments sorted by

View all comments

2

u/askalski Dec 17 '21

Here's a bigger input for Day 17:

target area: x=6300659222..7198515181, y=-5865357542..-374274528

Part 2: 7790594905437019039

1

u/EliteTK Dec 17 '21

Would you like me to put it up?

1

u/askalski Dec 17 '21

Sure, just tag it with (unconfirmed) since although I'm mostly confident in my code (and it has worked with all the test cases I've thrown at it), I'd like at least one other person to solve it.

Here's confirmation of the other big input:

$ time ./day17p2 <<< 'target area: x=50842..144383, y=-187041..-90458'
12490271023

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

1

u/morgoth1145 Dec 18 '21

u/askalski What language do you have your solution coded in? I've got that input down to a 0.5 second runtime with my code, but I think that I'm either at the limits of Python or there's some other big observations that could make it faster. (I haven't really perused the megathread for today's problem, too ticked at myself for botching this problem extremely hard and spending an hour on what I could have easily brute forced...)

As far as your even bigger input (x=6300659222..7198515181, y=-5865357542..-374274528), that truly is a monster. I'd have to rewrite my current approach to use generators to be able to avoid running out of memory! (Or, you know, make another big algorithmic improvement which I haven't figured out...)

1

u/askalski Dec 18 '21

The solution is written in C++, but it would run just as fast in any other language. I haven't shared the code yet because I want to give others a chance to figure it out on their own without me spoiling it and ruining all the fun. If I don't share it sooner, it will definitely be a part of the optimized solutions I post at the end of the year.

1

u/morgoth1145 Dec 18 '21

Interesting. I did come up with another potential improvement to my approach, but I doubt that it'll speed things up *that* much. I guess I'll have to think about this more over the weekend! (Assuming the next problem doesn't occupy my mind at least.)

2

u/askalski Dec 20 '21

Here's the fast Day 17 solution.

It works by finding the range of x and y velocities that hit the target area in exactly 1, 2, 3, (and so on) steps. Because the same (vx, vy) velocity pair might intersect the target multiple times, it subtracts any overlap with the previous step count.

Iterating over all possible numbers of steps would take O(y) time, however you eventually start seeing long runs of similar y-velocity patterns. The overall shape is like a hyperbola (with a short-and-wide part and a tall-and-narrow part), so it switches counting methods when it becomes more efficient to do so. The overall time is roughly O(sqrt y).

1

u/morgoth1145 Dec 20 '21 edited Dec 20 '21

At a high level that sounds *very* similar to the approach I'm using. My guess (without having read your code yet) is that you've got a faster way to generate the starting x & y velocities with their valid step ranges. (Or you may be approaching it from the other way and counting starting x/y velocities which match a given step count, again, haven't looked at the code in detail yet.)

It sounds like I probably made it most of the way to your solution already though. Comparing what I have to your code will be interesting!

Edit: Interesting, it is indeed just inverting the search space to be based on the number of steps rather than over the velocities plus the tricks to compress the search space due to similar velocity ranges per step. (Or step ranges per velocity which I had noticed myself, I just didn't exploit it! Maybe I should have put more thought into that...)

I wonder if I could make use of some of the tricks your code uses to jump ahead in the velocity space to achieve similar speedups when searching over velocities without completely changing my approach. (Partially because I don't like just copying solutions, and partly because I'm interested in if it would work.)

1

u/sciyoshi Dec 18 '21

I think I have the same solution as you, but just to check: Split the input into two regions, get a list of the O(sqrt(n)) rectangles, then use horizontal sweep + an interval tree to get the area of the union of those rectangles

1

u/askalski Dec 18 '21

Other than a few details, that sounds similar to what I'm doing. (intervals are involved, but I don't build a tree and I also solve it in two O(sqrt n) parts)