Ooooooh boy. I started a bit late this year. I forgot that it starts on Midnight of the 1st, which is basically 9pm on November 30th. I thought I had another day, but when I went to get set up today... the 2nd puzzle was about to go live. Whoops!

As a heads up, for anyone that happens to read this, I'm assuming you've already read the puzzle, otherwise, you might get lost as to what I'm talking about! I'll try to assume you've only read the first part, as you need to actually solve it to read the second part.

And a fair warning: While I don't post the whole of my code here, I will likely post what I feel is the important parts, and I do have a link to my github with the full code submission on each day. So if you don't want to spoil solving the problems yourself, you've been warned!

This one seems pretty simple. Simpler than last year even. All I need to do is scan from the left for the first digit, then scan from the right for the second digit. On average only about half of each line needs to be scanned, and in the worst case, the whole word needs to be scanned to find the sigle digit (O(n+1)).

-->3
pqr3stu8vwx
       8<--

A nice little hack with the digits in the string - the digits 0-9 are all in sequence in ASCII, so the fastest way to see if a character is a digit, just compare it with the character literals '0' and '9' - if it's between those two inclusive, it's a digit! And to cast it to an number, just subtract '0'!

int num;
string::iterator it = line.begin();

// Left - 10s digit
while (!isDigit(*it)) it++;
num = *it - '0';
num *= 10;

// Right - 1s Digit
string::reverse_iterator rit = line.rbegin();
while (!isDigit(*rit)) rit++;
num += *rit - '0';

Looks like for part two, it turns out some of the string literals of the digits are embedded into the string. Basically "one", "two", etc. are there, AND they count as digits!

Just need to add a preprocessing step that does a string replace for each of the digits.

... except of course it isn't that easy. Aside from the fact that string manipulation in c++ works far differently than other languages such as c#, almost immediately there's an edge case that I ran in to! My initial approach was to search for every instance of "zero", followed by "one", etc., but in the case of "eightwothree", it was first replacing the "two". But in the example it's flowing left-to-right, meaning it's just taking it in the wrong order. I need to scan for every digit starting with the the first character... ugh.

vector<DigitWord> DigitMap = {
    {"one", "1"},
    {"two", "2"}
    // etc...
};

string undigitString(string s)
{
    string workingString = s;

    for (int i = 0; i < workingString.length(); i++)
    {
        for (DigitWord dw: DigitMap)
        {
            if (workingString.length() - i < dw.word.length()) continue;
            if (workingString.substr(i, dw.word.length()) == dw.word)
            {
                workingString.replace(i, dw.word.length(), dw.digit);
            }
        }
    }

    return workingString;
}

This approach feels a bit more cumbersome, as it's O(m*n) instead of my other approach, which was something like O(m*log(n)), but it works reasonably fast still... except....

Augh! It trips up on eighthree. It returns either 8hree or eigh3 depending on which method I use... but it's meant to be 83. Seems unfair that it two digits can share a single letter like that. Nothing in the writeup texts hints that this can be true. Actually unfair.

A quick edit to my table...

vector<DigitWord> DigitMap = {
    {"zero", "z0ro"},
    {"one", "o1e"},
    {"two", "t2o"},
    // etc...
};

Hacky, but it works!

Toughest Day 1 by far.