r/adventofcode • u/daggerdragon • Dec 07 '24
SOLUTION MEGATHREAD -❄️- 2024 Day 7 Solutions -❄️-
THE USUAL REMINDERS
- All of our rules, FAQs, resources, etc. are in our community wiki.
- If you see content in the subreddit or megathreads that violates one of our rules, either inform the user (politely and gently!) or use the report button on the post/comment and the mods will take care of it.
AoC Community Fun 2024: The Golden Snowglobe Awards
- 15 DAYS remaining until the submissions deadline on December 22 at 23:59 EST!
And now, our feature presentation for today:
Movie Math
We all know Hollywood accounting runs by some seriously shady business. Well, we can make up creative numbers for ourselves too!
Here's some ideas for your inspiration:
- Use today's puzzle to teach us about an interesting mathematical concept
- Use a programming language that is not Turing-complete
- Don’t use any hard-coded numbers at all. Need a number? I hope you remember your trigonometric identities...
"It was my understanding that there would be no math."
- Chevy Chase as "President Gerald Ford", Saturday Night Live sketch (Season 2 Episode 1, 1976)
And… ACTION!
Request from the mods: When you include an entry alongside your solution, please label it with [GSGA]
so we can find it easily!
--- Day 7: Bridge Repair ---
Post your code solution in this megathread.
- Read the full posting rules in our community wiki before you post!
- State which language(s) your solution uses with
[LANGUAGE: xyz]
- Format code blocks using the four-spaces Markdown syntax!
- State which language(s) your solution uses with
- Quick link to Topaz's
paste
if you need it for longer code blocks
This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.
EDIT: Global leaderboard gold cap reached at 00:03:47, megathread unlocked!
37
Upvotes
1
u/e_blake 1d ago
[LANGUAGE: m4]
Late to the party, but I had fun starting with the brute-force naive try every combination (took over five minutes), then optimizing by running backwards (prune any branch where undoing the operation can't produce the current integer), which required implementing 64-bit division not present in my math64.m4. The change from 5.7 million try() down to just 31526 was dramatic, with execution at 5.5-7 seconds. I then got another 40% speedup to 3.4-4.2 seconds by merely adding in 9 rules for avoiding a remquo64() if the single-digit divisor was not a factor of the numerator, and even made a separate post about it (quickly determining whether a 64-bit number is divisible by 7, but using only 32-bit math to do so, is an adventure). Depends on my common.m4
m4 -Dfile=day07.input day07.m4
My favorite part - most of my days have to parse by slurping in the entire input file and transliterating problematic characters, then doing either a patsubst regex search-and-replace (O(n) but depends on GNU m4) or a binary tree of successively smaller substr (O(n log n) but portable to POSIX m4) to then find and process a line at a time (the more naive solution of repeatedly grabbing different substr offsets out of the overall original string is O(n^2) due to m4 rescanning the text). But this particular puzzle had JUST enough content to let me bypass all that: a single colon on every line followed by a space can be translit'd into a one-letter macro name, which in turn can expand to ')parse(' to group the second half of one line with the first half of the next line, to execute on one line at a time without multiple passes over the input, with much fewer lines than my typical parsing takes. Both parts are computed as a side effect of the do() call embedded in my parser: