Bridge Repair: Advent of Code 2024 (Day 7)

Today, we’ll help some engineers whose operators were taken by elephants. They need to fix a bridge, but to do that, they need these operators to calculate their calibration equations. It’s all about long integers and working on operators to get the result.

Bridge Repair

Check the full story here and you can also find the code in my GitHub.

Processing the data

Our engineers need the equations to make sense of the numbers, but the inputs are a bit… operator-less. So the puzzle input will in the equations without any operators. The code below processes these equations and stores them in a map for easy access and further calculations.

unordered_map<long int, vector<long int>> equations;

void loadData() {
    string line = "";
    ifstream ip("ip.txt");

    if (ip.is_open()) {
        while (getline(ip, line)) {
            int pos = line.find(":");
            long int key = stol(line.substr(0, pos));
            vector<long int> numbers;
            string token;
            istringstream tokenStream(line.substr(pos + 1));
            while (getline(tokenStream, token, ' ')) {
                if (token != "") {
                    numbers.push_back(stol(token));
                }
            }
            equations[key] = numbers;
        }
        ip.close();
    }
}

Here, each key in equations map represents the equation’s value, and the corresponding vector holds all the numbers.

Part 1: Using Addition and Multiplication

The first step involves using two basic operators: addition (+) and multiplication (*). An equation is valid if you can compute its value using these operators on the provided numbers. The operator precedence won’t apply here. You can just evaluate left to right. The goal is to calculate the sum of all valid equation values for getting the star.

My Approach:

• Loop through all the equations
• For each equation, use recursion to check if the target value can be achieved using addition or multiplication on the numbers
• If the equation is valid, add its value to the total sum

Here’s the implementation:

bool solve(long int curr, int currIdx, const long int& expected, const vector<long int>& numbers) {
    if(curr > expected) {
        return false;
    }

    if(currIdx == numbers.size() - 1) {
        return curr == expected;
    }

    if(solve(curr + numbers[currIdx + 1], currIdx + 1, expected, numbers)) {
        return true;
    }

    if(solve(curr * numbers[currIdx + 1], currIdx + 1, expected, numbers)) {
        return true;
    }

    return false;
}

bool canSolve(const long int& value, const vector<long int>& numbers) {
    return solve(numbers[0], 0, value, numbers);
}

The solve function recursively checks if the target value (expected) can be achieved by applying addition or multiplication on the current number (curr) and the next numbers in the vector.

int main() {
    loadData();

    long long int total = 0;
    for (auto const& [key, numbers] : equations) {
        if(canSolve(key, numbers)) {
            total += key;
        }
    }

    cout << "calibration: " << total << endl;

    return 0;
}

By the end of this process, you will get the total calibration value printed, earning you the first star of the day.

Part 2: New Operator

In this part, we introduce a new operator: the concatenation operator (||). This operator combines the digits of its left and right inputs into a single number.

My Approach:

• Convert each number to a string
• Concatenate the strings
• Convert the concatenated string back into a number and check

The updated solve function includes this new operation:

bool solve(long int curr, int currIdx, const long int& expected, const vector<long int>& numbers) {
    // all part 1 code

    if(solve(stol(to_string(curr) + to_string(numbers[currIdx + 1])), currIdx + 1, expected, numbers)) {
        return true;
    }

    return false;
}

By adding this logic to the existing code, the function can now handle the concatenation operator. Running the updated program will calculate the sum of all valid equations, earning you the second star.

Conclusion

Recursion is a powerful tool in problem-solving. Initially, my brute force brain implemented a solution using loops. However, I later realised that recursion could optimise the process significantly and implemented the current solution.

If you enjoyed this challenge, try solving this related problem on LeetCode:

• 1808. Maximize Number of Nice Divisors