I'm trying to catch up a bit. Still don't think I'll finish by Christmas (tonight is the 20th for me), but I still want to do what I can. In that spirit - this is my third tonight! I started a few hours ago, just finished days 9 and 10, and I still feel good. I just recovered from that severe cold, so now I'm getting into it again.

Also, regarding the flavor text for today's puzzle: Onsen are pretty great. I've visited one once while in Japan, and it was very relaxing, even though it was a bit awkward visiting as a foreigner. Highly reccomend it, assuming you're okay with nudity.

... hot springs. As in, warmed up coils of metal. Cool.

AUGHHHHH

Bad word play aside, this seems a little bit tricky. Basically testing and checking to see which combinations are valid. Seems a little annoying, but my initial thoughts are thus:

1. Figure out how many in the row are shown as damaged
2. Subtract that from the total number damaged from the springs, for unknown damaged springs N
3. Generate every possible permutation of N springs
4. Check validity of every permutation

1 and 2 are simple enough. 3 might be a little tricky but I can manage something. 4 isn't that bad.

getline(input, line);
auto lineSplit = split(line, " ");

string row = lineSplit[0];
vector<int> runs;
for (auto s: split(lineSplit[1], ","))
{
    runs.push_back(stoi(s));
}

int toFind = reduce(runs.begin(), runs.end());
for (int i = 0; i < row.length(); i++)
{
    switch (row[i])
    {
        case '#': toFind--; break;
    }
}

That's 1 & 2 done. Filling out the switch case should help a bit with 3.

My idea is simply a recursive function: as long as there's still enough slots for a damaged spring to go, it will generate a string with that, as well as one without it for that one slot, then recurse.

vector<string> recurseFillSprings(string base, int toPlace, int missingCount)
{
    // Base 1 - if there's not enough spaces to place the springs, return
    if (toPlace > missingCount) return vector<string>();

    // Base 2 - if no more springs place, fill rest of string and return that
    if (toPlace == 0)
    {
        vector<string> toReturn;
        for (int i = 0; i < base.length(); i++)
        {
            if (base[i] == '?') base[i] = '.';
        }

        toReturn.push_back(base);
        return toReturn;
    }

    int missingIndex = base.find('?');

    // Case - Broken spring
    base[missingIndex] = '#';
    auto brokenStrings = recurseFillSprings(base, toPlace-1, missingCount-1);

    // Case - Working spring
    base[missingIndex] = '.';
    auto workingStrings = recurseFillSprings(base, toPlace, missingCount-1);

    brokenStrings.insert(brokenStrings.end(), workingStrings.begin(), workingStrings.end());
    return brokenStrings;
}

input:
input:
.??..??...?##.

output:
.##..#.....##.
.##...#....##.
.##.......###.
.#...##....##.
.#...#....###.
.#....#...###.
..#..##....##.
..#..#....###.
..#...#...###.
.....##...###.

Seems to be working so far. But that's just the list of possible inputs, step 3 above. I need to whittle that down to just the valid number of outputs.

bool isValid(string row, vector<int> runs)
{
    int i = 0, runIndex = 0, curRun = 0;
    bool inRun = false;

    while (i < row.length())
    {
        if (row[i++] == '#')
        {
            inRun = true;
            curRun++;
            continue;
        }

        // Current run does not match expected run
        if (inRun && curRun != runs[runIndex++]) return false;

        inRun = false;
        curRun = 0;
    }

    return true;
}

input:
.??..??...?##. : 1,1,3

output:
.##..#.....##. - Invalid
.##...#....##. - Invalid
.##.......###. - Invalid
.#...##....##. - Invalid
.#...#....###. - Valid
.#....#...###. - Valid
..#..##....##. - Invalid
..#..#....###. - Valid
..#...#...###. - Valid
.....##...###. - Invalid

That seems to match up pretty well!

Unfortunately it doesn't work. Turns out I wasn't accounting for a run being at the end of a line properly, as well as not checking that all of the runs have been satisfied. Adding an extra at the end, as a good number of valid runs can be pushed up against the edge.

It works, but it still takes a while to run, likely due to a stupidly high amount of string copying and whatnot. It would likely be faster if I did some pre-validation as I'm generating the strings, instead of just doing a ton of memory allocation, but ¯_(ツ)_/¯

I saw this coming, I swear. And still I didn't brace myself.

Now each line is actually five copies of itself.... great. I'm going to have to optimize it, and have an in-progress 'isValid' check. Maybe I can just plop that into my string generation thing, prune out invalid ones early?

bool isValid(string row, vector<int> runs)
{
    // ...
    while (i < row.length())
    {
        // Base-ish case. Unknown up to this point. Assume fine.
        if (row[i] == '?') return true;

        //...
    }
    return true;
}

Just that made the code run significantly faster, adding that check in the middle of the string generation. If an in-progress string isn't valid up to the unknown part, no point continuing! Re-running part 1 full was really quick. But part 2 sample alone is extremely slow.... not surprising considering one row alone has 506250 valid arrangements! It's likely just a ton of mallocs causing this. Especially bad since I haven't started using the heap either, just the stack... so... I'll fix that.

// Dozens of lines going something from
row[i] == '#';
// to
row->at(i) == '#';

Still slow, but not as slow. The sample finishes in reasonable time (under 10 seconds), but the full input just gets bogged down.

I think my main problem is it's recursively returning full vectors of strings, and it's dynamically allocating memory for all of those strings, plus constantly merging them into bigger and bigger vectors one step at a time.

... And I just realized something. Now that I'm validating in the middle of the recursion, I don't need to return the strings! All of the strings that would be returned are valid, so I just need to recurse the valid number!

...

It takes the same amount of time.

Okay, after a long think, I realize that while each string I'm checking is unique, I can memoize the unknown-onwards portion of the it; THAT'S what I'm recomputing over and over. I need to memoize the back half essentially.

I admit, I ended up spending hours and hours on this, mostly finding little edge cases, off-by-one errors, and in the end my code looks fully different. But it is memoized properly! Most of it was just improperly handling substrings.

I need to sleep.