Author's note: If you're wondering where the quote came from, I got ChatGPT to generate quotes that describe when brute force no longer works. The other one I quite like is 'Brute force is the last resort of the incompetent', allegedly inspired by Isaac Asimov.
In the previous post, I mentioned how I looked up all the talks by Bryan Cantrill but omitted how his talk on Docker / containers was the one that inspired it. Other notable talks include the golden age of hardware / software co-design and Monktoberfest 2022 (which I highly recommend if you’re a parent).
The other thing that I didn’t mention was attending the ML Applied Projects event. I wanted to get started on 2024 ideas, among them having a local copy of my ChatGPT discussions. During the event I was told these are available to download! I don’t recall seeing this option last year, but I guess that task is done.
The notable event today was the Zig meetup at Bun HQ. It's often refreshing to chat to people in person and comforting to realize if you feel awkward at events like these, others likely feel the same way too. Jarred Sumner went through cool string optimization stuff that Bun does (for example storing details in the 12 bits not needed in an 8-byte address because the system only needs 52 bits), which is easy in Zig because Zig doesn’t have a string type.
Advent of Code Day 5 was the first day my code that works for the example wouldn’t work for the puzzle input. For the first part, the solution involved mapping integers to integers and my lazy implementation generated all the possibilities. The puzzle input made the dictionaries huge (though in my case strangely didn’t OOM), so I converted the dictionaries to be more compact by storing only the values needed to make the translation.
For the second part, we needed to run different ‘seed’ values through multiple integer-to-integer mappings to find the minimum final output. The brute force implementation would have taken a long time. The fix involved two changes (1) finding the minimum contiguous range across all lookups to know how many you can skip (for example, if you know 50 maps to 10 and 55 maps to 15 then you just need to keep track of 10), and (2) fill the gaps in the dictionary so you can do the first change more effectively. The times I measured:
w/ step 1 : not done even after ~4 hoursw/ step 1 : done after ~2 hoursw/ steps 1 + 2: done after ~4 minsAll the things: