I think I'm getting sick again. Tomorrow's New Years Eve and I may have to spend it at home while my friends all have fun. Eugh.

This seems like a massive parsing headache more than an actually difficult problem.. then again I assume that part 2 is going to add even more of a headache. Let's see.

struct Rule {
    char category, comparison;
    int target;
    string destination;
};

// Parse rules
getline(input, line);
while (line != "")
{
    auto i = line.find("{");
    string label = line.substr(0, i);
    auto ruleStrings = split(line.substr(i+1, line.length() - i - 2), ",");

    vector<Rule> rules;
    for (auto rule: ruleStrings)
    {
        auto parts = split(rule, ":");
        
        if (parts.size() == 1) {
            rules.push_back(Rule{'a', '>', -1, rule});
        } else {
            rules.push_back(Rule{ parts[0][0], parts[0][1], stoi(parts[0].substr(2)), parts[1] });
        }
    }

    getline(input, line);
}

I figure I could simplify the "always passes" rules by simply giving it a condition that will always be true. The input has no negative numbers, so the rule a>-1 will always pass.

while (true)
{
    if (step == "A")
    {
        sum += x + m + a + s;
        break;
    }

    if (step == "R") break;

    for (Rule rule : workflows[step])
    {
        int checkVal;
        switch (rule.category)
        {
            case 'x': checkVal = x; break;
            case 'm': checkVal = m; break;
            case 'a': checkVal = a; break;
            case 's': checkVal = s; break;
        }

        bool passing = false;
        switch (rule.comparison)
        {
            case '>': passing = checkVal > rule.target; break;
            case '<': passing = checkVal < rule.target; break;
        }

        if (passing)
        {
            step = rule.destination;
            break;
        }
    }
}

Trivial once it's all parsed out.

Okay, now this is interesting. Rather than moving through all of the parts individually, just check to see what the ranges for the acceptable parts would be.

The way I'm thinking of doing this is to start with one set of ranges (x=1-4000, m=1-4000, a=1-4000, s=1-4000) and go through the first rule in each step. As it passes through each rule, if any within that range could pass, it would split. For example, for the first rule in the example (s<1351:px), it would result in two ranges that it would keep checking:

• px -> (x=1-4000, m=1-4000, a=1-4000, s=1-1350)
• qqz -> (x=1-4000, m=1-4000, a =1-4000, s=1351-4000)

It would keep splitting the ranges along those lines through the workflows, If a set ever ended up at R, it would just throw it out; if it ended up at A, it would multiply the remaining ranges.

    uint64_t sum = 0;
    while (!parts.empty())
    {
        auto part = parts.front(); parts.pop();

        // Check for valid ranges
        if (part.x.second < part.x.first || part.m.second < part.m.first || part.a.second < part.a.first || part.s.second < part.s.first)
        {
            continue;
        }

        if (part.workflow == "R") continue;
        if (part.workflow == "A")
        {
            sum += SumParts(part);
            continue;
        }

        for (Rule rule : workflows[part.workflow])
        {
            if (rule.target < 0)
            {
                part.workflow = rule.destination;
                parts.push(part);
                break;
            }

            PartSet left = PartSet(part);
            PartSet right = PartSet(part);

            switch (rule.comparison)
            {
                case '<':
                    switch (rule.category)
                    {
                        case 'x': left.x.second = rule.target - 1; right.x.first = rule.target; break;
                        // Copy for other cases...
                    }
                    left.workflow = rule.destination;
                    parts.push(left);
                    part = right;
                    break;

                case '>':
                    // Similar to above case
            }
        }
    }

It ran nearly instantly!

EDIT: About an hour after finishing this, I realized I could have implemented the values as a map<char, int> and just avoided the switch cases, just labeled based on which char it was. Augh. Would have been a lot less typing and copy/pasting.

At least it was fun having XMAS everywhere in my code.