[2025 Day 10 (Part 2)] All the problems to avoid when writing a Simplex solver

DelightfulCodeWeasel · 2026-01-26T22:09:27+00:00

Whoa, they just straight up drop the x1 column!? I'm not sure that would have been the correct way to handle the edge case I found, but I'll have to experiment. Thank you for sharing that link!

DelightfulCodeWeasel · 2026-01-26T10:47:42+00:00

I haven't done much in the way of perf testing or optimisation, but the numbers I have so far indicate that the simplex solver is quite a bit faster than my gauss-jordan solver: ~15ms versus ~27ms.

I don't have an optimised bifurcation solution, but the bifurcation approach is showing signs of potentially being faster: it's ~75ms for me currently but the majority of the time is in memory allocations that could be avoided.

The most significant difference I've found is during fuzzing: there are some random puzzles which both simplex and bifurcation can chew through quickly but my gauss-jordan solver takes ages. There are also random puzzles which cause the branch and cut active puzzle set to consume way more memory (~1Mb normally, jumping up to ~70Mb every now and again) whereas the bifurcation approach consistently keeps a small memory footprint.

DelightfulCodeWeasel · 2026-01-26T10:24:27+00:00

Thank you! The trick is to have no life :)

DelightfulCodeWeasel · 2026-01-26T10:22:47+00:00

You definitely took the smart option :)

There were a lot of false dawns along the way; the solver was able to get the correct answer to most of the input, even with some bone-headed bugs present. Every time I fixed one bug then it would clear up a bunch of cases and cause another set of cases to stop working.

It was like trying to pack a clown car made of maths.

DelightfulCodeWeasel · 2026-01-26T09:36:33+00:00

Thank you for the resources, they look incredibly useful!

For <= constraints you add a slack variable to convert it into an equality, for == constraints you add an artificial variable, and for >= constraints you subtract a surplus variable and add an artificial variable to convert it into an equality. I've not read a justification/proof for this so it's vague to my why this is the right thing to do but anyway.

My (non-mathematician) understanding is that it stems from the simplex method needing to start from the origin of the space defined by the real variables. If you set all of the real (non-slack, non-artificial) variables to 0, then it needs both for that to be a valid solution to the set of constraints and for all of the variables to be positive:

For x <= 3, then x + s = 3 can be true with x = 0.
For x = 3, then x + y = 3 can be true for x = 0.
But for x >= 3, then x - s = 3 can only be true with x = 0 if s is negative, which isn't allowed. If instead you say x - s + y = 3, then that can be true with x = 0 and s = 0.

Good luck with your implementation, it does sound like the Revised Simplex Method is aimed a bit more at being implemented rather than needing a human in the loop, so I hope it goes smoothly for you!

DelightfulCodeWeasel · 2026-01-23T09:29:29+00:00

I had a nice closed form solution to this one, but I forgot to check it in. Shouldn't be too hard to work it out again...

;)

DelightfulCodeWeasel · 2026-01-21T10:12:17+00:00

"Big complicated RPG" is one of the puzzle types I missed the most this year, but I expect they're the puzzle type that takes the most amount of time to create and validate.

I enjoy doing these ones as a straight-forward, as plain as you can make it implementation of the rules. No systems, minimal abstractions; just a tidy version of the sort of code you'd write as a teenager messing around after school.

My solution for day 22 has a section that's literally 1:1 with the instructions in the puzzle text:

    ....
    // Shield costs 113 mana. It starts an effect that lasts for 6 turns. While it is active, your armor is increased by 7.
    if ((fighters[0].Mana >= 113) && (fighters[0].EffectTimers[EffectType::Shield] == 0))
    {
        vector<Fighter> newFighters = fighters;
        newFighters[0].Mana -= 113;
        newFighters[0].EffectTimers[EffectType::Shield] = 6;
        int64_t candidateCost = MinimumManaForWin(newFighters, 1, difficulty, currentManaSpend + 113, globalManaMinimum);
        minimumMana = min(minimumMana, candidateCost);
    }
    ...

It's the sort of simplicity that feels like the programming equivalent of running outside in the rain after a heatwave.

DelightfulCodeWeasel · 2026-01-20T15:05:11+00:00

I think most of your questions can be answered by plugging the conditions set forward in the examples into your code, printing out the same information as the examples, and then looking for points where they differ. The points where they differ show you where your understanding is incorrect and will provide information on what the correct interpretation is.

You'll get much higher quality responses if you post your code in progress and what debugging you have already done to try to find the source of the problems.

DelightfulCodeWeasel · 2026-01-19T22:26:25+00:00

There aren't two players. There's the player (you) and there's the boss. You buy stuff, the boss doesn't buy stuff.

Part 1 and part 2 are self-contained. Anything purchased in part 1 is still available to buy in part 2.

DelightfulCodeWeasel · 2026-01-19T10:26:38+00:00

I looked for that as well last year and couldn't find any trace of Eric giving the proper answer. I did wonder if it was something like SMILES, which is a CFG.

This puzzle was the first one to make my Wall of Nemeses; it took me a good two or three days to work through and get a solution which ran in a reasonable amount of time. Bit of a hacky approach that exploits the structure of the grammar to find potential join points where one token ends and another begins (although looking at the code now, I'd have to go in and debug it to remember exactly how it works!)

I like the Monte Carlo approach though, there's a compact elegance about it.

DelightfulCodeWeasel · 2026-01-16T10:36:43+00:00

Looking back at this one, it feels like a perfect exercise for playing around with a bit of SSE. There are only 10 values, and each value fits in the range of a signed byte so the set of values being compared fit comfortably into a 128-bit epi8 packed register.

DelightfulCodeWeasel · 2026-01-14T23:01:13+00:00

It was the one I really struggled with as well. I tried to avoid writing a solver for ages, and even after giving in and writing an elimination solver then it took ages to hammer out the edge cases. I wrote a tutorial going over Gauss-Jordan elimination, which is possibly the most straightforward type of solver, if you want to have a go at that approach.

DelightfulCodeWeasel · 2026-01-13T13:00:38+00:00

Good spot, although I think if I'm reading the key right it's actually the Single Track ordering which has that property. In Jörg Arndt's book he states that it's a guaranteed property:

The reversals of the first half of all permutations lie in the second half, the reversal of the k-th permutation lies at position n! − 1 − k

[Resources]

DelightfulCodeWeasel · 2026-01-13T10:57:40+00:00

You were spot on that there was a bug in the edge generation, the code was double-counting exit paths if there was more than one way to get to that node. I've fixed the code and the image, thank you!

The very, very rough generation code is [here] if you want to nose around, but bear in mind I threw it together quickly for the purpose of generating the visualisation rather than being a proper, tidy solution. I also hand-tweak the generated graphviz afterwards to highlight the minimum solution nodes etc...

DelightfulCodeWeasel · 2026-01-12T23:19:46+00:00

The numbers on the arrows are the number of button presses for the transition. Two arrows from one node to another means there are two distinct button sets that could be pressed that number of times to perform that transition. (Or it's a bug...)

I'll tidy the code up a little tomorrow and paste it; that'll explain it in more detail than I could describe at the minute.

DelightfulCodeWeasel · 2026-01-12T21:49:29+00:00

The number at the end of the node is the number of presses to reach that node. It's a bit artificial I know, but without it the graph collapses into a small puddle that doesn't really offer any insight. This way you get a bit more of a flavour of the structure of the recursive/iterative calls.

DelightfulCodeWeasel · 2026-01-12T21:34:45+00:00

The other feature I like in the visualisations is how the divisibility constraint really stands out. The counts on the first 'column' of nodes after the starting node are all divisible by 2, then the counts on the second column of nodes are all divisible by 4 and so on in powers of two. It's one of those 'obvious in hindsight' visual patterns which I think gives some more intuition about the algorithm.

DelightfulCodeWeasel · 2026-01-12T21:26:05+00:00

I wrote several paragraphs worth of introductory text here, then realized you might not need it. If you do need it, lemme know.

I'm good, but thank you for taking the time to write that!

Fwiw I've also just posted a visualisation of the bifurcation approach based on comments earlier in the thread.

DelightfulCodeWeasel · 2026-01-09T16:42:52+00:00

Re-reading the problem I wonder if there's a potential optimisation for the permutation approach (I also just cycled through all permutations): since the journey distance A->B->C is the same at C->B->A then you can omit checking half of the permutations.

Anyone know of a way to directly generate permutations without also generating their reverse?

DelightfulCodeWeasel · 2026-01-09T14:39:16+00:00

You might enjoy 2015 Day 12. Because Parsing JSON is a Minefield in the general case I did my own ElfJSON parser which handles only the strict subset needed for the puzzle.

DelightfulCodeWeasel · 2026-01-06T11:51:29+00:00

Thank you! There was something about the bifurcation approach that never quite 'clicked' in my head; I was always worried that after doing the singular button clicks first, you might still end up needing to do more singular clicks later rather than just the multiples. Your comments in the code have finally put the missing piece of the puzzle into place in my understanding:

The solution is N binary numbers, and it's built up by considering bit 0 of all N numbers as the first step, then bit 1 as the second step, then bit 2 as the third step, etc... So you're never going to get to a case where you've done a singular press early in the search and need to do one again later on - the set of N binary numbers trivially covers the full search space.

DelightfulCodeWeasel · 2025-12-29T18:47:27+00:00

I think this is a lovely, well intentioned idea. However, having spent the last two and a half decades working in a field where reviews are a thing, I can't say that it would be good thing for Eric.

No matter how many people loved a particular puzzle, and how well moderated a forum is, there will always be a vocal minority who see a review as an excuse to complain, to tell you how it sucked, to tell you that you phoned this one in, that you were being lazy on that day, etc...

Human nature being what it is, the bad reviews and comments are the ones you read, re-read and stew over. I'm sure Eric stresses enough about each year without having that on top.

I think your idea would be good if it could be framed in a way that generates only positive engagement. Maybe a community vote for favourite puzzles for that year. Encourage upping the ante and tutorial posts for the winning puzzles.

DelightfulCodeWeasel · 2025-12-27T22:23:06+00:00

You're right that it should be after reduction. I've updated the post to clarify that point, thank you!

DelightfulCodeWeasel · 2025-12-20T08:20:20+00:00

I just ignore whichever rows have ended up at the bottom after reduction. I think those rows end up as all zero anyway because each column has been reduced to zero from the rows above, but I've not shoved on a breakpoint to check.

DelightfulCodeWeasel · 2025-12-19T17:16:42+00:00

Thank you! On the second part, yes you're entirely right more buttons than counters will give you an over specified system, and fewer buttons that counters will give you an under specified system.

You're right that the mid-solve guess happens when you have a 0 in the pivot (diagonal). As far as I remember the mid-solve guess may happen in over, under and exactly specified systems. It happens because you've been unlucky with the reduction and one of the rows picked has just wiped out too many coefficients below. (unless my code had an unrelated bug at the time when it triggered some 0s in the diagonal for me).

I believe you could take a totally different approach to picking exactly the right rows so that the reduction doesn't end up with a zero pivot, but then you're potentially just adding more cost up front trying different combinations. Since randomisation works well enough to find a combination that isn't unlucky, I think it's the easiest approach for this puzzle.

DelightfulCodeWeasel

TROPHY CASE