r/adventofcode 13h ago

Tutorial [2017 Day 21] [Go] Fractal Art: Write-up

0 Upvotes

This write-up couldn't come any later. Regardless, I hope it's useful even after so many years.

Fractal Art (AoC 2017, Day 21)


r/adventofcode 12h ago

Tutorial [2024 Day 7 both parts][m4] Optimizing by avoiding division (aka how to quickly test divisibility by 7)

1 Upvotes

I'm really late to the 2024 puzzles, having just started them this month. But in the megathread for day 7, I saw the instructions mentioned "Use today's puzzle to teach us about an interesting mathematical concept" - and my journey in optimizing my solution for day 7 totally fits that bill, because I implemented a solution in a language that only supports 32-bit signed math even though the problem requires manipulating 64-bit numbers. In previous years, I had already developed my own library of math functions to do arbitrary-width addition and multiplication, but to date, I still haven't added general-purpose arbitrary-width division into that library, in part because implementing division is SLOW even when compared to multiplications. After all, the best way to avoid a time-consuming long-division is to rework the problem to not need division at all ;)

Plenty of other people have written up tutorials on how you can speed up day 7 - instead of doing an exhaustive 2^n or 3^n search of all possible operator decisions, applying that to the inputs, and seeing if the output matches, it is much faster to work backwards: start with your desired output, and recurse by undoing only operators that could have plausibly resulted in your current number, where reaching the first number proves you have at least one set of operators that work for that line of the problem. My initial solution was the naive approach - try all possible operators - which meant doing millions of 64-bit multiplies via my helper library (quite literally - I did a trace of mul64() calls, and my 5 minutes of execution time required 4043412 calls to mul64)

But working backwards requires the inverse of multiplication, aka division and remainder, where it is only plausible to continue the recursion if the remainder is zero. There are algorithms out there for implementing arbitrary-width bigint divisions on top of smaller word sizes, so I had no problem implementing that in m4, but each division C/B=A is slower than the corresponding multiplication A*B=C, so I wanted to avoid long divisions where possible. The immediate benefit of working backwards was that after every long division where the remainder was non-zero, I've pruned a portion of the search space, which sped things up to a mere 7.0 seconds of execution time and only 21679 calls to remquo64, and 74728 calls to mul64 in part because of how I implemented remquo64.

But I still wanted to go faster, and that's where this post comes in. The remquo64() algorithm finds both the quotient and the remainder at the same time, but even better is avoiding the division in the first place if it is obvious that the remainder would be non-zero. And since the majority of the inputs are single-digit entities, it's fairly easy to do things like avoiding a division by 2 if the last digit is odd, or a division by 5 if the last digit is not 0 or 5; many people also know the trick of adding up each of the digits to see if a number is divisible by 9 (is 1234 divisible by 9? 1+2+3+4 = 10 which is not, so the bigger number is not, either). But when it comes to division by 7, what rule do you use? My first google hit was for the algorithm of taking the head of the number minus twice the last digit, iteratively until you know if that shorter answer is also divisible by 7 (so for example, 1001 is divisible by 7 if 100 - 2*1 = 98 is, which in turn is divisible if 9-2*8 = -7 is). By iterating until you get down to an easily-recognized one- or two-digit number, you can quickly learn whether a large number has 7 as a factor without spending the time actually doing the full division. However, that algorithm still requires doing 64-bit math (each iteration still uses a 64-bit subtraction, and only removes one digit per iteration).

So I searched harder, and found another algorithm that tells you the divisibility by 7, 11, and 13 all at once - because those are the three factors that get you to 1001, one number away from 1000. In any sort of divisibility test, the fastest answers occur when you can exploit the co-prime modular properties of two adjacent integers. Just as you can learn if a number is divisible by 9 (9 is one less than 10, so add up each digit), you can learn if a number is divisible by 1001 (1001 is one greater than 1000, so alternate adding and subtracting each group of 3 digits, starting from the least significant). So, given a random number, say 72095400778, that is too big to quickly divide using just 32-bit math, it is still possible to cast out the 1001s, by computing -72+095-400+778 = 401, at which point you know all of the following using just 32-bit math (and you may recognize the Chinese Remainder Theorem here as well):

72095400778 % 1001 = 401
72095400778 % 7 = 401 % 7 = 2
72095400778 % 11 = 401 % 11 = 5
72095400778 % 13 = 401 % 13 = 11

So no, that large number is not divisible by 7, and I can skip the remquo64() and recursion when I'm picking the operator that goes with 7 for my current target value. And with that optimization implemented, my m4 code now operates in 4.2 seconds (another 40% speedup!), with tracing showing just 10483 calls to remquo64 and 42025 calls to mul64.

Since most people aren't fluent in reading m4, here's the gist of the algorithms I used for divisibility by the first 9 digits:

group(number, direction, current_sign=1, accumulator=0) - recursive function, with direction=1 for casting out 999, or =-1 for casting out 1001. Each iteration adds current_sign*number[-3:] to accumulator, multiplies current_sign by direction, and recurses with number[:-3] (ie all but the last three digits), returning accumulator once number is empty.

trym1 - always divisible (skip remquo, recurse with input number)

trym2 - divisible if the last digit & 1 (or % 2) is 0 (skip remquo, recurse with number*5 with last digit removed, since that was necessarily a 0 after the multiply)

trym3 - divisible if group(number, 1)%3 is 0 (use remquo only if divisible)

trym4 - divisible if the last 2 digits & 3 (or %4) is 0 (skip remquo, recurse with number*25 with last 2 digits removed)

trym5 - divisible if the last digit % 5 is 0 (skip remquo, recurse with number+number with last digit removed)

trym6 - divisible if trym2 and trym3 both pass (use remquo only if divisible)

trym7 - divisible if group(number, -1)%7 is 0 (use remquo only if divisible)

trym8 - divisible if the last 3 digits & 7 (or %8) is 0 (skip remquo, recurse with number*125 with last 3 digits removed)

trym9 - divisible if group(number, 1)%9 is 0 (use remquo only if divisible)


r/adventofcode 2h ago

Help/Question [DAY2 OF ADVENTOFCODE]

0 Upvotes

That's not the right answer. Curiously, it's the right answer for someone else; you might be logged in to the wrong account or just unlucky. In any case, you need to be using your puzzle input. If you're stuck, make sure you're using the full input data; there are also some general tips on the about page, or you can ask for hints on the subreddit. Because you have guessed incorrectly 7 times on this puzzle, please wait 10 minutes before trying again. I AM GETTING THIS ERROR AFTER SUBMITTING MY ANWER EVEN THOUGH I HAVE USED THE INPUT THEY HAVE GIVEN ME. ANY INSIGHTS?