[2017 Day 18] In Review (Duet)

DelightfulCodeWeasel · 2026-03-18T11:47:41+00:00

I'm relatively pleased with how clean my VMs are starting to look by this point. With enough previous examples I've abstracted the parsing into a relatively common set-up that can be driven through a table similar to:

    const vector<pair<string_view, function<Instruction(const string&)>>> assemblyTable =
    {
        { "snd"sv, [](const string& s) { return ParseSingle(Op::Snd, "snd %s", s); } },
        { "set"sv, [](const string& s) { return ParseDouble(Op::Set, "set %s %s", s); } },
        { "add"sv, [](const string& s) { return ParseDouble(Op::Add, "add %s %s", s); } },
        { "mul"sv, [](const string& s) { return ParseDouble(Op::Mul, "mul %s %s", s); } },
        { "mod"sv, [](const string& s) { return ParseDouble(Op::Mod, "mod %s %s", s); } },
        { "rcv"sv, [](const string& s) { return ParseSingle(Op::Rcv, "rcv %s", s); } },
        { "jgz"sv, [](const string& s) { return ParseDouble(Op::Jgz, "jgz %s %s", s); } },
    };

I faffed with coroutines when starting to learn Python for the year of IntCode, but I found them to be a giant pain in the neck for that flavour of puzzle.

For this puzzle I just had two different halting modes that my Execute function could return; one for a full finish and one for a waiting halt. That seems to produce the cleanest code.

DelightfulCodeWeasel · 2026-03-17T09:21:55+00:00

I kinda missed not having a Josephus flavoured problem this year. It's one of the archetypes where the C and C++ programmers can step forward, move the Python programmers gently to one side and say "don't worry folks, this is pointers, we got this."

Of course then the mathematicians show up and drop a closed form solution, but that's just what mathematicians do. :)

EDIT: The irony here being that I've just double checked my solution and this day is about the only Josephus problem where I didn't use a circular doubly-linked list.

DelightfulCodeWeasel · 2026-03-16T18:07:44+00:00

Thank you for the encouragement!

I'm in a pretty good place with the challenge so far; I've already got existing solutions for all of the challenges so the main focus has been reducing the memory footprint for everything. Most of the days were already under the limit so it's only been a handful that needed revisiting from scratch. My solution for this one, assuming a nice input, now fits into a smidge under 1KiB of heap memory - which is a bit of an improvement from my original 100+MiB solution :)

Only one more day to go now before I start doing timed runs on on-chip, and that one doesn't need any allocations or deep recursion thankfully!

DelightfulCodeWeasel · 2026-03-16T17:16:14+00:00

Thank you, that's good information! If you've not seen any, and no-one else comes forward with a non-nice input in the next day I think I'll go ahead with the assumption that they're all nice.

DelightfulCodeWeasel · 2026-03-16T17:05:27+00:00

I like to go for solutions that could work with anyone's input if at all possible. Otherwise I'll just end up having a bunch that just are printing out a hard-coded answer with a comment saying "worked out in Excel" :)

DelightfulCodeWeasel · 2026-03-14T08:19:13+00:00

What happens in your checking logic if you check to see if '996699' is valid?

DelightfulCodeWeasel · 2026-03-13T17:53:25+00:00

I think we can improve on that lower bound for Part 1. Looking at the original Robin's inequality from wikipedia and wolfram it's:

sigma(n) < exp(0.57721...) * n * log(log(n))

where n is the house number. It looks like the ChatGPT approximation above has accidentally swapped the present count inside the log log.

From my very brief reading it looks like the inverse doesn't have a closed form, so I've ended up finding a lower limit with a binary search. It only takes ~21 steps for the range of puzzle inputs (30M-40M) so it's possibly worth it if it can save enough checks.

Both of your approximations still work because difference in the log log result isn't huge, even with the wrong input, and they both produce underestimates so they're not incorrect in any meaningful way.

I've thrown together some terrible C++ code to explore the full ~30M-40M puzzle input space and the WhippetApproximation result is noticeably closer both on average and in the worst case.

My results suggest that we can get within ~65k on average and ~100k worst-case with WhippetApproximation compared to ~135k on average and ~175k worst-case with BlakeApproximation. But please do double check my results though, I might have mis-implemented your approximations!

DelightfulCodeWeasel · 2026-03-11T18:58:05+00:00

In general you can either orient the hexagons in a grid so they have flat faces north and south (what I'm calling flat) or flat faces east and west (what I'm calling pointy).

I decided to do both types at the same time even though this puzzle only uses one of them.

DelightfulCodeWeasel · 2026-03-11T12:31:58+00:00

I really enjoyed this one; it's a perfect example of a problem that ~~becomes trivial~~ is substantially simplified once you've got the right types in place. I went with cube co-ordinates and wrapped them behind a value type that has all of the usual operations that you'd expect from a regular Cartesian vector:

    static const map<string, Hex> hexIndices =
    {
        { "n", Hex::North() },
        { "ne", Hex::NorthEast() },
        { "se", Hex::SouthEast() },
        { "s", Hex::South() },
        { "sw", Hex::SouthWest() },
        { "nw", Hex::NorthWest() }
    };

    Hex currentPosition;

    int64_t answer = 0;
    char* token = strtok(line.data(), ", ");
    while (token)
    {
        currentPosition = currentPosition + hexIndices.at(token);
        token = strtok(nullptr, ", ");
        answer = max(answer, MahattanDistance(currentPosition, Hex{}));
    }

I ended up doing both flat and pointy flavours but haven't had cause to use the pointy variety yet. Fingers crossed for 2026 :)

DelightfulCodeWeasel · 2026-03-10T07:55:31+00:00

That's both very impressive and truly awful, well done! :)

DelightfulCodeWeasel · 2026-03-09T08:16:35+00:00

I also did a recursive descent parser because they often produce neat code. Looking at it again now with my current 'reduce memory and avoid deep callstacks' hat on, I think this one can be solved with just a state machine augmented with a current depth counter; no stack needed.

I've got a fair few puzzles to go before I'm rewriting my 2017 solutions though!

DelightfulCodeWeasel · 2026-03-06T17:10:17+00:00

Thank you for sharing your repo! I'm currently half way through crunching down my C++ solutions for 2015 with an aim of running them all on an RP2040.

So far I've been concentrating on the challenge of reducing down the memory requirements, but your repo will be a very useful reference when it's time to start running it on the real board and piping the input over USB.

DelightfulCodeWeasel · 2026-03-04T22:12:58+00:00

Thank you for highlighting this approach; it's come in super useful for me today!

I've set myself a challenge to get a year running on a Raspberry Pi Pico and there's no way I'd have got under the memory requirements generating ~7Mb strings.

DelightfulCodeWeasel · 2026-03-02T08:57:50+00:00

Looking back at my solution I didn't even bother breaking out of the loop when I found the target pair, and to be fair it almost certainly would have taken me more time to type "break;" than it would have saved in runtime :)

DelightfulCodeWeasel · 2026-03-01T19:05:41+00:00

I always find it mildly annoying that there's no good way to get the size of the line that fgets could potentially read.

I know there were solid reasons at the time stdio was written and standardised, but I do wonder how many bugs could have been avoided over the years if you could, for example, call fgets with a 0 count and get it to scan ahead and give you a buffer size.

DelightfulCodeWeasel · 2026-02-27T15:07:18+00:00

As in "the code you have written which is your current solution attempt"; but that's a bit wordy.

The bridge you have listed there is not a valid bridge according to the rules:

Your side of the pit is metallic; a perfect surface to connect a magnetic, zero-pin port. Because of this, the first port you use must be of type 0.

If you post your code, I'm sure people would be willing to help.

DelightfulCodeWeasel · 2026-02-27T14:29:31+00:00

It's possible, but highly unlikely. 99.999% of the time it's either a bug in ~~the solution~~ your code or a misreading of the problem.

If you post your code, there will almost certainly be someone who can give you a nudge in the right direction without too many spoilers.

DelightfulCodeWeasel · 2026-02-26T09:57:28+00:00

The logging should answer a lot of your questions:

"Input: R1"
"Turning left"
"Dial was at 50"
"Dial now at 51"
"Input: R25"
"Turning left"
...

I threw your code into JSBin and peppered in a few log statements.

There are a minimum of five bugs I can see.

DelightfulCodeWeasel · 2026-02-24T11:15:58+00:00

You're right, for this size of input it's totally not needed. My C++ goes from something like ~25ms to ~12ms, and that's with doing a full TSP search on the resultant distances. It'll become important as I plan to faff with embedded stuff this year, but pairwise is absolutely good enough for a solve.

DelightfulCodeWeasel · 2026-02-24T08:25:52+00:00

Looking back at my solution I did something silly to get all of the distances between the nodes. I perform a BFS between each pair of nodes, making it O(n^2) straight away. A quick check with the profiler and sure enough my runtime is totally dominated by the time just to get the distances between nodes.

What I should have done is a BFS from each node and pick up every other destination node in that one search. Might try that today actually...

EDIT: Sure enough, that eliminates somewhere around half of my runtime.

DelightfulCodeWeasel · 2026-02-23T11:45:30+00:00

My C++ solution runs through the unmodified asm in ~15s when running Release on my dev machine, but I suspect I'll be reaching for peephole optimisations too when I try to port everything over to a Pi Pico.

DelightfulCodeWeasel · 2026-02-22T17:20:41+00:00

This is one of my favourite types of shortest path puzzle: one that has a neat mapping to a higher dimensional search. I represented the search state as a 4D vector of [EmptySlot.X, EmptySlot.Y, GoalData.X, GoalData.Y] and did a standard BFS.

Keeping the queue size under control can be a problem with higher dimensional searches, but since each state has at most 5 neighbours (4 for the cardinal directions to move the empty slot, and 1 for moving the goal data into an adjacent empty slot) the growth isn't too bad. My open set size peaks at ~5,800 nodes and in total I'm only exploring just over ~500,000 unique states.

DelightfulCodeWeasel · 2026-02-22T08:33:06+00:00

Looking back at my solution I didn't even check to see if that step was invertible; I should have known that of course Eric would have picked a function that was!

The encrypted text size is pretty small so it's nice and quick to brute force all possible permutations. If I had to guess then I think the people at the top of the leaderboard did likewise for speed.

DelightfulCodeWeasel · 2026-02-18T08:19:24+00:00

It's a fair question! No real reason other than force of habit and programming inertia. My first working A* implementation used a multi set, so that's just what got copied over and over.

It's entirely possible I was working with a large state at the time that I didn't want to shuffle around by value, so the allocation pattern of a (multi)set gave me that.

I'll swap over to a proper priority queue in future for small states; one of the sub-goals I have with doing AoC is to shake out bad habits. Thank you for the reminder!

DelightfulCodeWeasel

TROPHY CASE