https://adventofcode.com/2015/day/24

This is one that's easy to solve, but hard to solve quickly... in-fact when looking at my original Ruby solution, it was measurable in minutes as to how long it'd take to find an answer (not complete) for each part. I'm not entirely convinced my current method is quite there yet, but it's at least a few orders of magnitude faster.

Part 1

Basic algorithm is:

1. Find all the ways to combine the weights such that they're equal to exactly 1/3 of the total weight.
2. For each of these ways, store them as a mask in order to easily disallow overlapping solutions.
3. Sort each of these possible masks by: a. Number of Items b. Quantum Entanglement
4. Starting from the "best" solutions, find the first set of non-overlapping solutions that produces the total weight, because it's sorted, the first member of this set will be the right answer.

It's actually step #1 that takes all the time in Part 1.

Part 2

There's actually no change here, and since this is very much a Big O problem where the target weight is the biggest factor in how long step #1 of the basic algorithm takes, this part actually completes far quicker than Part 1, since the smaller the target weight, the less ways of achieving that weight are viable...

Python vs C++ vs C

Python

Probably my slowest solution to date... some solution types really don't gel well with interpretted languages.

C++

I'm not mad Python, I'm just disappointed. Same algorithm/approach in C++, and it's a near instant solve.

C

Comparable to the C++ solution, and many orders of magnitude faster than the Python. This does finally highlight one of the more annoying aspects of C. Because in this solution, it's non trivial to pre-calculate the total number of permutations to expect, we have to keep growing a RAM buffer to store this. This is what std::vector does under the hood for us in C++, but in C, we have to do it by hand. The approach is basically:

IF we're about to overflow the RAM buffer
  Create a new RAM buffer twice the size of the old one
  Copy the old RAM buffer to the new RAM buffer
  Remove the old RAM buffer
END

As you can imagine, the better our starting guess of the RAM buffer size, the less times we have to perform the copy... But that could be at the expense of vastly over allocating the memory (for example, it is possible to pre-compute the total number of permutations, but this will include unbalanced too).

Also, one "gotcha" in the C code is around QSORT. Take the following code...

    if (left->nQuantumEntanglement > right->nQuantumEntanglement)
    {
        return 1;
    }
    else if (left->nQuantumEntanglement == right->nQuantumEntanglement)
    {
        return 0;
    }
    else
    {
        return -1;
    }

You might rightly think that could be (since QSort just cares about comparisons being positive, negative or equal to understand how to shuffle the deck):

    return left->nQuantumEntanglement - right->nQuantumEntanglement;

Problem is, this is all unsigned arithmetic. Meaning negative is an impossible outcome (it just becomes large positive). You could cast to a signed type, but can we guarentee the result would over/underflow the int type (since int is one of those loosely defined types whose size varies depending on compiler/processor etc). Easier to just avoid that whole can of worms... I may or may not have spent a disporportionate amount of time debugging that fact...