?? Day 7 of Advent of Code: Tackling the Bridge Repair Problem ???

Have you ever had a simple task assigned to you, only to realize it’s not as straightforward as it seems? Well, today’s challenge was just that! ??

The Problem Overview:

Question Link : https://adventofcode.com/2024/day/7

We were given equations in the form of numbers, with the task of inserting different operators (+, *, and even a new one || for concatenation) to see if they can match a target value. So, for example:

190: 10 19 
3267: 81 40 27 
192: 17 8 14        

Our goal was simple: find which equations can be solved using the available operators and then sum up all the valid results. Sounds easy, right? ??

Challenges We Had to Consider:

1. Operator Combinations: The main challenge here was dealing with all possible operator combinations between the numbers.
2. Left-to-Right Evaluation: We had to follow strict left-to-right evaluation rules, ignoring traditional operator precedence.
3. Concatenation (||): A new twist in the problem where you could concatenate numbers together (e.g., 15 || 6 = 156), which added complexity.

Classroom vs. Real Test - The Input:

In class, they teach you to focus on basic arithmetic operations and how to evaluate expressions. But when the real test comes, you're faced with an input file like this:

5354536482085: 5 3 120 4 8 6 77 3 54 1 7
23317289089: 9 420 97 26 49 4 5 88
450512522712: 1 5 528 39 1 2 1 632 8 9        

You realize that the classroom problems were nothing like the 900 equations to evaluate here! ??

Approaches and Why We Shifted to Optimization:

At first, went with a brute-force approach — try all combinations of operators for each equation and check if they match the target. But soon, I realized that as the number of numbers in each equation increases, the number of possible combinations grows exponentially. ??

Exponential Growth:

For example, if we use that approach there is exponential growth in possible combinations

• For n numbers, there are 2^(n-1) operator combinations (+ or *).
• Example: For 7 numbers: 2^(7-1) = 64 combinations.For 10 numbers: 2^(10-1) = 512 combinations.For 20 numbers: Over a million combinations!
• With large inputs like 5354536482085: 5 3 120 4 8 6 77 3 54 1 7, brute force is infeasible because of the massive number of configurations to evaluate.

So we shifted to optimized approaches:

1. Short-circuiting: We stopped further calculations if intermediate results exceeded the target value.
2. Memoization: Storing results of already calculated subproblems helped avoid recomputing.
3. Efficient operator handling: We focused on calculating only valid combinations, cutting down unnecessary calculations.

The Big Takeaway:

The problems themselves aren’t that difficult. It’s the optimization that makes the real difference! In theory, you need to check combinations of operators, but when dealing with large inputs, it’s all about finding ways to make it computationally feasible. ?

Steps to Solve

1. Parse the Input
2. Extend Operator Handling
3. Iterative Evaluation
4. Prune Invalid Paths
5. Check Validity
6. Calculate the Total Calibration Result

Final Thoughts:

What seems like a simple task in class quickly becomes a computationally heavy problem when applied to a large dataset. The key is not just solving the problem but optimizing the solution for scalability.

Excited for what’s next! ????

#AdventOfCode #ProblemSolving #Optimization #CodingChallenge #Python #LearningByDoing #Programming #TechSolutions #Algorithms #CodingJourney