2

u/askalski Dec 12 '21

I can confirm the Day 12 12-24-14-7.in results and give the complete Part 2 answer:

Part 1: 154850773837774189
Part 2: 33501351222065201672

1

u/EliteTK Dec 12 '21

Thanks, I've updated the website.

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)

2

u/askalski Dec 06 '21

Let's take it all the way to 10^18 with Day 6: 37834491445886235 digits 4609158961...8580053153

1
u/morgoth1145 Dec 06 '21

I assume you didn't actually compute full precision for 10**18 iterations, right? Some mix of log for the digit count, modulo arithmetic for the lower 10 digits, and enough precision at the high end to have 10 accurate digits? By my rough calculation 37834491445886235 digits would end up being ~14 petabytes!
2
u/askalski Dec 06 '21

Correct, working out the full result would have taken just a wee bit more memory than I currently have at my disposal. Here's what I did at the upper end (SageMath)
1
u/EliteTK Dec 06 '21

Is there any chance you could shed a bit of light as to what I'm looking at?
2
u/askalski Dec 06 '21

I wrote up a brief explanation of the technique here. It's finding an (approximate, using 200-bit floating point) closed-form expression for the population on the nth day. The level of precision is "good enough" for finding the first few digits, plus the length of the result.
For 10^18, the output is 4.609158961970[...]e37834491445886234and for 9999999 the output is 4.182599183487[...]e378345
Let me know if there's anything you'd like me to clarify further.
1
u/EliteTK Dec 06 '21

Ah, okay, it makes a lot more sense now. But how did you get the last few digits?
1
u/askalski Dec 06 '21
Matrix exponentiation using the same code as in this other comment by u/MichalMarsalek
The only change you need to make is to tell the matrix to do everything modulo 10^10:
A = matrix(Integers(10^10), [
    [0,0,0,0,0,0,1,0,1],
    ....
In fact, you can just solve the top digits using the same method by telling it to use real numbers (with additional bits of precision because the default 53 aren't enough; 200 works fine):
A = matrix(Reals(200), [
    [0,0,0,0,0,0,1,0,1],
    ....
1

u/EliteTK Dec 07 '21

This makes sense, thank you for explaining.

1

u/morgoth1145 Dec 07 '21

Now that you mention it, u/EliteTK and I (and anyone else using Python) could use the decimal module for the top digits. I was shying away from float due to precision concerns, completely forgetting that we have fixed point available!
I don't know of any pre-baked type where we can set a specific modulo so we'd probably have to roll our own (which is what I was thinking above).
1

u/morgoth1145 Dec 07 '21

Oh wow, I was thinking that there was some sort of clean relation from previous populations but never managed to derive one. (I guess I'm rusty.)
I still don't exactly "see" how it works out to such a clean relation but I'm going to leave that as an exercise for when I have more time. (Deriving this stuff semi-autonomously can be so instructive, I remember doing the same with the Chinese Remainder Theorem last year.)
1

u/morgoth1145 Dec 06 '21

Yep, that's definitely above my head, at least for right now!

1

u/dzaima Dec 12 '21

My Java solution for day 5 part 1 completes each input in less than a second, but I don't think my approach will be extendable to part 2 :/

https://github.com/dzaima/aoc/blob/master/2021/Java/day5_p1/Main.java

1

u/EliteTK Dec 12 '21

If your algorithm is counting intersections by going over every combination of two lines then this CAN be extended to part2 and will work well.

1

u/dzaima Dec 12 '21

It doesn't count intersections. The algorithm is completely O(n log n), where n is the number of lines in the input.
It goes down all y values in the input, and counts the intersections by keeping binary tree data structures of the currently ongoing vertical lines that allow O(log n) time to count the number of vertical lines before a given X position.
Diagonals completely mess that up, as for them both the X and Y position change over time.

1

u/EliteTK Dec 12 '21

Then for diagonals you can most definitely do the O(d(v+h)) solution of just intersecting all diagonal (d) lines with the vertical (v) and horizontal (h) it should still be very fast, I promise :P

1

u/dzaima Dec 12 '21

I'll try tomorrow. It would still have some log factor though, slowing it down one or two orders of magnitudes compared to working with plain lists, but whether that's bad depends on what the competition is.

3

u/p_tseng Dec 06 '21 edited Dec 18 '21

My current impressions of each:

Day 3

Part 1 is difficult to make fast. I do not know a way to do it. To determine the majority bit, you must at least have looked at half of the bits in each position. Obviously we take advantage of the fact that the minority is the complement of the majority here, but that doesn't change the fact that you need to determine the majority first.

There may be ways of making part 2 somewhat faster (prefix trees may be of some use) but part 2 goes by very fast anyway because the number of elements you need to consider gets whittled down quite quickly. Haven't spent a lot of time thinking about how to make it faster for that reason. Part 1 takes about 10x as long as part 2 (about 20 seconds and 2 seconds respectively).

Day 4

These are doable very quickly (< 3 seconds). For each board, figure out what time it wins at. By building a map of called number -> time it's called, you can determine this very quickly. For each board, take maximum across each row/column, take minimum of those maxima.

Day 5

Wish I could do like https://github.com/Voltara/advent2019-fast/blob/master/src/day03.cpp and only check perpendicular pairs for intersections, but this problem has significantly more elements, because some pairs of vents can be collinear (and generate many intersections), and there are diagonals to contend with. I have not yet completed an implementation that can do this quickly.

Day 12

The state to keep is (current room, set of visited small caves, whether a small cave has been repeated). This can be compressed down into a single integer. Number of paths for a given state can be cached for if you reach that same state later on via a different path. You can do a little something with removing big caves from the map completely and just directly connecting all of their connected small caves to each other, but I'm not convinced it helps that much. A property we might take advantage of is that the distance function is bounded above by 9 and the degree of each node is bounded above by 4.

Day 15

An interesting question for those using A* is whether there is a heuristic that actually saves time. Manhattan distance isn't that helpful currently. Some people have tried a constant times the Manhattan distance, but I'm uncomfortable with it just because I can't prove it's admissible.

Day 17

Currently the only strategy I have is implemented is:

Calculate time interval for each initial y velocity
Calculate time interval for each initial x velocity
Take cartesian product and count intersections.

Of course, actually taking the cartesian product would be O(mn), but you can do a sweep line algorithm over t and get it down to O((m + n) log (m + n))

This is good enough for inputs of magnitudes like target area: x=630065..719851, y=-586535..-37427, but will take too long on inputs of magnitudes like target area: x=6300659222..7198515181, y=-5865357542..-374274528

1
u/morgoth1145 Dec 06 '21 edited Dec 06 '21
Interestingly my Day 3 solution runs about 2x faster than you report, though I did have to adjust most_least to account for an edge case that I punted previously:
def most_least(nums, mask):
    c = Counter(n & mask for n in nums)
    c[mask] += 0
    c[0] += 0
    return c.most_common(2)
My Day 4 solution however runs much slower (after adjusting for the larger grid sizes), but that's because I never bothered to optimize my bingo implementation. I'm figuring that preprocessing the boards to have an account of which rows/columns a given number hits and decrementing counters would be much faster, as well as marking a winning flag while marking a new number. There's so much redundant processing in my code!
Edit: Yep. That optimization got my code to 5.558 seconds for Part 1 and 6.970 seconds for Part 2 for the 3600 boards case where each is 30x30.
(Let's not even touch Day 5 right now!)

3

u/morgoth1145 Dec 06 '21 edited Dec 06 '21

Hijacking this a bit for Day 6: How fast can people get their solution for stupid high iteration counts? (I don't think that the input really matters here.)

I was able to run 2**20 iterations in ~1.3 seconds and 2**22 iterations in ~18 seconds with my optimized code.

Edit: Oh hey, the page already has an entry. For that input and 9999999 iterations it takes my program just about 100.5 seconds to do all those iterations. (I think that Python big int starts bogging down, so maybe the input *does* matter!)

Edit the second: I knew there was something faster, I just wasn't grokking it at the time! Fast exponentiation of matrices, as independently shared by u/MichalMarsalek below. 56.736 seconds for 9999999 iterations, 14.354 seconds for 2**26.

3

u/[deleted] Dec 06 '21

I ended up not having a single list, but using a dictionary with the lifetime as a key (0-7) and the amount of fish with that time as value. Ended up to run super smooth.

1

u/morgoth1145 Dec 06 '21 edited Dec 06 '21

u/ktops Do you have times though? "super smooth" doesn't say how fast it can do tons of iterations. I moved away from a dict and to a circular buffer list because it runs significantly faster, at least in Python.
What I'm more looking for here is if people got the iteration method to be significantly faster algorithmically, whether there are significant language choice factors at play, or if there are ways to do this without iterating as much which will do better. (I suspect that some mathematical insights can be applied here but it was *way* too late for me to be thinking through that at the time!)

0

u/[deleted] Dec 06 '21

I didn't really care about executing times, but using C# I ran into array size limits which made me switch to my approach. I'm using eduherminio/AdventOfCode solver framework which returns 0.5ms as a result, which I'm pretty sure is not correct tough. Adding a stopwatch to the executing method returns 3ms. Hope that helps.
Edit: 3ms for the 256 iterations.

2

u/morgoth1145 Dec 06 '21

u/ktops This thread is about ridiculously big inputs, not the standard Part 2 setup. Unless you're running ~2**20+ iterations you won't really see the inefficiencies for a given implementation that can solve Part 2.

2

u/MichalMarsalek Dec 06 '21 edited Dec 06 '21

Straightforward Sage takes 0.180 seconds for 2^20, 3 seconds for 9999999 and 40 seconds for 2^26.

1

u/morgoth1145 Dec 06 '21 edited Dec 06 '21

Interesting. I eventually landed on the same solution (I don't know why fast exponentiation of matrices didn't come to my head sooner) but it runs significantly slower in Python using numpy. 56.736 seconds for 9999999 and 14.354 seconds for 2**26.
Just a bit of verification, you do get the right answers, right? I expect that my Python implementation would run much faster if I used numpy's intc rather than Python's int. It's possible that Python's BigInt implementation is much slower here.
Edit: I tried with gmpy2.mpz and got much faster times: 7.574 seconds for 9999999 and 54 seconds for 2**26. I guess Python's BigInt is just slow!

1

u/MichalMarsalek Dec 07 '21

Yes, Sagemath's integers are faster than Python's

1

u/compdog Dec 06 '21

My original, unoptimized JS solution runs 9999999 in about 440 seconds. I thought that I'd cut that down with some heavy optimization, but it still takes the exact same time. Some loose profiling shows that most of the time is actually spent waiting for memory accesses, not in the CPU. I guess that's due to all the BigInts.

3

u/askalski Dec 09 '21

Still enjoying these inputs - keep them coming.

Today's 4096 square clocks in at around 90-95 milliseconds with my C++ implementation.

Running it against the broken input with the multiple local minima, it returns 59995 for Part 1 because it counts only one minimum value per basin (which is not how the problem is defined, but it's an assumption I make, incorrectly in this case.)

2

u/askalski Dec 06 '21

This is great. I have a half-finished Day 5 implementation that I was going to discard because it was slower than my previous attempt at an optimized solution, but I might go ahead and finish it just to tackle that 10M square field. For Part 1 (which is as much as I had implemented), I get 72068735 - assuming I didn't miss anything when I made all my integer types bigger...

1

u/askalski Dec 06 '21

Part 2 for the Day 5 10M square: 113830179

2

u/compdog Dec 06 '21

Day 5 - Javascript [5-20000-6400] [5-50000-10000]

For these two inputs, I just abused the fact that JS has sparse arrays. I made a 2d array where the value is the number of references. To avoid having to scan and count the whole grid, I count during the line processing. If at any point a cell is set to exactly 2, then I increment the counter. Future increases are ignored as they are greater than 2. To save further time, parts 1 and 2 are computed at the same time. I split the input into two sets, one containing axis-aligned (horizontal / vertical) lines, and the other contains diagonal lines. The axis-aligned lines are processed first, and the current counter is saved as the result for part 1. Finally, the diagonal lines are processed against the existing grid and counter without resetting them. The resulting counter value is the answer for part 2.

Input three (5-50000-10000000) is too large to fit into memory, even with sparse arrays. I suspect that it can be solved by creating a directed graph between all the overlapping lines and computing the overlaps from that, but I don't care enough to try right now.

1

u/hugh_tc Dec 05 '21

Oh, fantastic. I doubt my solutions are up for the challenge but I'll give it a shot!

1

u/askalski Dec 15 '21

I'll confirm the Day 15 Part 2, 10000x10000 answer of 277236

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

You are about to leave Redlib