Oh boy. "Ignore the last two lines of the input for now". Oh boy. I guess I get a preview of part 2.

Otherwise, it seems pretty simple. A 3d array, 101 length for each dimension. Turn on or off according to a procedure. Even better, some of this input looks similar to one from last week, so I can probably steal code from that.

// Initialize the core
bool core[SIZE][SIZE][SIZE] = {};

for (auto step: steps) {
    // Ignore steps that are out of range
    if (step.xRange.first < -50 || step.xRange.first > 50) continue;

    for (int x = step.xRange.first; x <= step.xRange.second; x++)
    for (int y = step.yRange.first; y <= step.yRange.second; y++)
    for (int z = step.zRange.first; z <= step.zRange.second; z++)
        core[LENGTH+x][LENGTH+y][LENGTH+z] = step.on;

    printf("Light count: %d\n", countOn(core));
}

Deceptively easy. Though looking at the input for part 2... I already know how it's going to get worse. And I don't think I'll easily be able to process that size of a cube the naieve way.

It looks like now the cube has a range of, roughly, 250,000 cubed. Even in the most efficiently packed way, that's still 1,000s of TB. I can't use this same solution.

The basic thought I have is this: Store the cuboid sections individually. As cuboids are added to the list, if they intersect any in the existing list, then both are split up into sections based on the intersection. This means each intersection could result in a single cuboid split into up to 23 new cuboids, if I'm doing my math correctly. Both cuboids would be split up this way. Any overlapping sections from the existing cuboid are deleted. Finally, if the new cuboids are meant to be turned on, they are added to the list of cuboids.

I can absolutely see this getting very messy very quick, but I'm not tooooooo concerned.

~

class Cuboid {
    public:
    p xRange, yRange, zRange;

    Cuboid(){}
    Cuboid(p x, p y, p z) { xRange = x; yRange = y; zRange = z; }

    bool intersects(Cuboid c) {
        return xRange.first < c.xRange.second
            && xRange.second > c.xRange.first
            && yRange.first < c.yRange.second
            && yRange.second > c.yRange.first
            && zRange.first < c.zRange.second;
    }

    vector<Cuboid> split(Cuboid c) {
        vector<Cuboid> newCubes;

        vector<int> newX = getIntersectPoints(xRange, c.xRange);
        vector<int> newY = getIntersectPoints(yRange, c.yRange);
        vector<int> newZ = getIntersectPoints(zRange, c.zRange);

        newX.erase(unique(newX.begin(), newX.end()), newX.end());
        newY.erase(unique(newY.begin(), newY.end()), newY.end());
        newZ.erase(unique(newZ.begin(), newZ.end()), newZ.end());

        vector<p> newXp, newYp, newZp;
        newXp.push_back(p(newX[0], newX[1]));
        for (int i = 1; i < newX.size()-1; i++)
            newXp.push_back(p(newX[i]+1,newX[i+1]));

        newYp.push_back(p(newY[0], newY[1]));
        for (int i = 1; i < newY.size()-1; i++)
            newYp.push_back(p(newY[i]+1,newY[i+1]));

        newZp.push_back(p(newZ[0], newZ[1]));
        for (int i = 1; i < newZ.size()-1; i++)
            newZp.push_back(p(newZ[i]+1,newZ[i+1]));

        for (auto x: newXp)
        for (auto y: newYp)
        for (auto z: newZp)
            newCubes.push_back(Cuboid(x, y, z));

        return newCubes;
    }
};

for (auto s: steps) {
    printf("[Step %2.1d] Currently [%4.1d] cubes\n", ++numSteps, core.size());
    vector<Cuboid> nextCore;

    // For each existing cube...
    for (auto c: core) {
        // 1: Split cube based on intersection with the new cube
        vector<Cuboid> split = c.split(s.cuboid);

        // 2: Only add those that don't intersect with it
        for (auto n: split) 
            if (!s.cuboid.intersects(n))
                nextCore.push_back(n);
    }

    if (s.on) nextCore.push_back(s.cuboid);

    core = nextCore;
}

So I can confirm, more or less, that this IS working. However, after a few minutes, this is what ends up happening...

==================================================================
============== Beginning procedure with [60] cubes ===============
==================================================================

[Step  1] Currently [   0] cubes
[Step  2] Currently [   1] cubes
[Step  3] Currently [  12] cubes
[Step  4] Currently [  79] cubes
[Step  5] Currently [ 101] cubes
[Step  6] Currently [ 808] cubes
[Step  7] Currently [3033] cubes 
[Step  8] Currently [22247] cubes
[Step  9] Currently [26867] cubes
[Step 10] Currently [179568] cubes
[Step 11] Currently [333815] cubes
[Step 12] Currently [2670521] cubes
[Step 13] Currently [12017349] cubes
[Step 14] Currently [38722591] cubes

Each successive step runs VERY slow. This isn't good, the cubes are propogating far too fast.

A way to reduce cubes might be to merge cubes after the intersect step. I know that several of the new cubes from the split step are very likely to be touching with exactly matching faces. Maybe a loop to merge as many cubes as possible? I do immediately just split every cube up as much as possible, and honestly in the average case there should only really be two new cubes.

~

Okay. I added some neat merging logic. I like it, but it would only be a good optimization for something like scene rendering, not this. The end result of this so far is....

==================================================================
============== Beginning procedure with [60] cubes ===============
==================================================================

[Step  1] Currently [   0] cubes
[Step  2] Currently [   1] cubes
[Step  3] Currently [   6] cubes
[Step  4] Currently [  43] cubes
[Step  5] Currently [  53] cubes
[Step  6] Currently [ 424] cubes
[Step  7] Currently [1653] cubes
[Step  8] Currently [9970] cubes
[Step  9] Currently [13067] cubes
[Step 10] Currently [88828] cubes
[Step 11] Currently [171118] cubes
[Step 12] Currently [1368945] cubes
[Step 13] Currently [6160257] cubes
[Step 14] Currently [19849739] cubes
[Step 15] Currently [53389095] cubes

About half as many cubes on average. But not enough. I'm scrapping that code, it's not useful.

~

Okay, a better optimization: Only bother with cubes it could reasonably intersect with! Even more, I only really care about an ON cube and all of the intersections with every OFF cube that comes after it. That's it. My reasoning is

• Any OFF cubes that intersect are just subtracted from that cube's total volume
• Any later ON cubes that intersect with it will have the final output counted from them

Basically, I'm calculating which cube is responsible for which FINAL light output.

A complication is that I'll need to also keep track of intersecting OFF cubes, but I can do that already I think. So, here's the plan now

1. Take the next ON cube, record count of cubes turned on
2. Intersect it with all following cubes, record the intersect cube
3. Subtract intersect volume from count
4. Intersect all cube segments with all other segments, adding the intersection volume back¹

Each full step will return just the number of cubes turned on by that particular cube. The first step will now take the longest, but it shouldn't take too long. If there's no intersection (which most cases will be), then there won't be a problem. BUT just to check my assumptions, I'm going to just get a count of each cube's intersection with subsequent cubes, no other information.

Cube [ 1] intersects with [10] following cubes
Cube [ 2] intersects with [ 9] following cubes
Cube [ 3] intersects with [ 8] following cubes
Cube [ 4] intersects with [ 7] following cubes
...
Cube [59] intersects with [ 0] following cubes
Cube [60] intersects with [ 0] following cubes

Total estimated intersections: 442
Estimated maximum nested intersections: 3095

I can live with just about 3500 intersections and sub-intersections². Shouldn't take too much time at all.

~

Okay, this is interesting. I've two cubes that, very obviously don't intersect on one axis. I've got a bug in my code. Ahahaha, it was so simple too. Z-range misses half the check. A quick fix and it works.

Hmm. I wonder if my original code for this, even if brute-forcing it, would still work. I'm going to try that before going down this path further.

It runs faster, absolutely. Just not in enough of a way to matter. Which makes sense, it would have just intersected the non-intersecting cubes in a way that just one new cube would result. It just saves having to go through that logic. Back to the optimized code!

~

[ 0] ON Cube | [ 6] Intersections | Final Contribution: [          100776]
[ 1] ON Cube | [ 5] Intersections | Final Contribution: [           64089]
[ 2] ON Cube | [ 4] Intersections | Final Contribution: [           90070]
[ 3] ON Cube | [ 3] Intersections | Final Contribution: [           55930]
...
[53] ON Cube | [ 2] Intersections | Final Contribution: [  34861774621075]
[54] OFF cube; skipping
[55] OFF cube; skipping
[56] OFF cube; skipping
[57] OFF cube; skipping
[58] ON Cube | [ 0] Intersections | Final Contribution: [ 533781640216869]
[59] OFF cube; skipping
============ TOTAL COUNT: [ 11967606201448200] cubes =============

Okay, that finished really quick. With a final count of 11967606201448200 cubes. That's... a lot. Too many. A whole digit too many. Okay, there's a problem with either my code or my logic. Testing on the very VERY first input, for the initialization, the number is still off by roughly the same order of magnitude. Looks like I have a bug somewhere in my code, but at least so far it's promising. I can run it really quick so I can iterate faster.

~

[ 0] ON Cube | [15] Intersections | Initial volue [ 131652] | Final Contribution: [1070722]

Yep. That's a difference of 10x, on the first cube. That's a huge difference. Particularly considering this is just the first sample cut down to the ignition area.

Okay, maybe I'm trying to be a bit too tricky with all of this. It was a neat idea, finding intersections of intersections. Hmm. Maybe back to my first idea, but keeping it constrained? That should still work and keep things down.

Nope. Didn't work. And at this point I have no idea what's going wrong.

~

New-new idea. Pre-slicing all of the cubes in the space. The input has 60 cubes, which means (60x2)^3 = 1,728,000 subdivisions. All of the initial cubes will fill a number of these pre-sliced cubes exactly. All I need to do is mark each of these pre-sliced cubes on an off. Or keep track of which ones have been turned on. I can probably do a map of some sort for this? String hashing?

~

Ugh okay, so I just make an index for each slice. Index was too much. I can unpack the indexes to locations when I'm done.

It's far later than I intended to deal with this, but I took so long on this, and I just wanted to get it done tonight... I nerdsniped myself hard. It's 3am, and I'm tired. But it's done. And this is the most amount of 'dead' code I've left in a solution. 2/3 is just neat class structures I thought I might need later.

I'm leaving it all in for now, but just know, basically all of my structures are not actually necessary.