advent2024

The Equation Solver - Exploring Recursive Solutions

This document provides an educational walkthrough of an equation solver program designed to tackle a specific puzzle challenge. The program solves mathematical equations where a target value must be constructed using a set of coefficient values combined with different operations.

1. Solution Intuition: Understanding the Problem

The problem presents equations in the format result: coeff1 coeff2 coeff3... where we need to find valid ways to combine coefficients to achieve the result value. The solution approach uses recursive backtracking to explore different operation combinations.

The operations available are:

Multiplication: a * b
Addition: a + b
Concatenation: e.g., a = 5, b = 7 → 57 (introduced in part 2)

Our strategy will be to recursively try each operation with each coefficient, exploring all possible paths until we find a valid solution that matches the target result.

2. Data Structure: Representing Equations

The first building block is a structure to represent an equation:

#[derive(Debug)]
pub(crate) struct Equation {
    result: u64,
    coeff: Rc<[u64]>
}

This structure stores:

result: The target value we need to achieve
coeff: The coefficients available for operations, stored as a reference-counted array for efficient memory management

Using Rc<[u64]> is a design choice allowing for shared ownership of the coefficients without unnecessary copying during recursive calls.

3. Parser: Converting Text to Data

We need to parse input strings like "190: 10 19" into Equation structures. The program uses the nom parsing library for robust, declarative parsing:

fn parse_equation(s: &str) -> IResult<&str, Equation> {
    map(
        separated_pair(
            u64,
            tuple(( space0, tag(":") )),
            tuple(( space0, separated_list1(space1,u64) ))
        ),
        |(result, (_, coeff))| Equation { result, coeff: coeff.into() }
    )(s)
}

This parser:

Captures a number before the colon as the result
Allows flexible spacing around the separator
Parses all remaining numbers as coefficients
Converts the parsed data into an Equation struct

Implementing the FromStr trait enables convenient parsing with Rust’s .parse() method:

impl FromStr for Equation {
    type Err = String;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        match parse_equation(s) {
            Ok(e) => Ok(e.1),
            Err(e) => Err(e.to_string()),
        }
    }
}

4. Core Algorithm: Recursive Solver

The heart of the solution is the recursive solver function which explores all possible ways to combine coefficients:

fn solve(total: u64, coeff: &[u64], cop: bool) -> Option<u64> {
    fn ct(a:u64, b:u64) -> u64 { format!("{}{}",a,b).parse::<u64>().unwrap() }

    let idx = coeff.len() - 1;

    if idx == 0 { return Some(coeff[idx]) }

    let res_1 = Self::solve(total / coeff[idx], &coeff[..idx], cop).map(|s| s * coeff[idx]);
    let res_2 = if total >= coeff[0] {
        Self::solve(total - coeff[idx], &coeff[..idx], cop).map(|s| s + coeff[idx])
    } else { None };
    let res_3 = if cop && total >= coeff[0] {
        Self::solve((total - coeff[idx])/10u64.pow(coeff[idx].ilog10()+1), &coeff[..idx], cop)
            .map(|s| ct(s, coeff[idx]))
    } else { None };

    match (res_1 == Some(total), res_2 == Some(total), res_3 == Some(total)) {
        (true, _, _) => res_1,
        (_, true, _) => res_2,
        (_, _, true) => res_3,
        _ => None,
    }
}

The algorithm works by:

Base Case: When reaching the last coefficient, return it directly
Recursive Exploration: Try three different operations with the current coefficient:
- Multiplication: Divide the target by the coefficient and recursively solve
- Addition: Subtract the coefficient from the target and recursively solve
- Concatenation (when cop is true): Handle digit concatenation as a special operation
Solution Selection: Once operations are tried, return the first valid solution that exactly matches the target value

The approach effectively creates a decision tree where each level tries all operations with the next coefficient.

5. Efficiency Optimizations

The solution includes several optimizations:

Early Pruning: Only attempt addition/concatenation if total ≥ first coefficient

let res_2 = if total >= coeff[0] {
    Self::solve(total - coeff[idx], &coeff[..idx], cop).map(|s| s + coeff[idx])
} else { None };

Short-circuit Evaluation: Return as soon as a valid solution is found

match (res_1 == Some(total), res_2 == Some(total), res_3 == Some(total)) {
    (true, _, _) => res_1,
    (_, true, _) => res_2,
    (_, _, true) => res_3,
    _ => None,
}

Memory Efficiency: Using slices of the coefficient array rather than creating new arrays in each recursive call
```
Self::solve(total / coeff[idx], &coeff[..idx], cop)
```

6. Public Interface: Simplified Usage

The Equation struct provides a clean public interface through the solver method:

pub(crate) fn solver(&self, cop: bool) -> Option<u64> {
    Self::solve(self.result, &self.coeff, cop)
}

This design:

Encapsulates implementation details
Allows toggling concatenation operations via the cop parameter
Maintains a consistent interface regardless of internal algorithm changes

7. Main Program: Processing Input and Solving

The main program ties everything together:

fn main() {
    let input = std::fs::read_to_string("src/bin/day7/input.txt").expect("msg");
    let equations = input.lines()
        .map(|line| line.parse::<Equation>().unwrap())
        .collect::<Vec<_>>();

    let t = Instant::now();
    let sum = equations.iter()
        .filter_map(|eq| eq.solver(false))
        .sum::<u64>();
    println!("Part 1: total calibration result is {sum} - {:?}", t.elapsed());

    let t = Instant::now();
    let sum = equations.iter()
        .filter_map(|eq| eq.solver(true))
        .sum::<u64>();
    println!("Part 2: total calibration result with CompOp is {sum} - {:?}", t.elapsed());
}

The program:

Reads the input file and parses each line into an Equation
Solves each equation without concatenation for Part 1
Solves each equation with concatenation for Part 2
Measures and displays performance timing for each part

8. Testing: Ensuring Correctness

The implementation includes unit tests for the parser to validate it handles various input formats:

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn parse_input() {
        assert!("190: 10 19".parse::<Equation>().is_ok());
        assert!("3267: 81 40 27".parse::<Equation>().is_ok());
        assert!("83:17 5".parse::<Equation>().is_ok());
        assert!("83 :17 5".parse::<Equation>().is_ok());
        assert!("83   :    17     5".parse::<Equation>().is_ok());
        assert!("83 : ".parse::<Equation>().is_err());
        assert!("363816188802: 5 601 3 603 2 2 93 6 3 5".parse::<Equation>().is_ok());
    }
}

This testing ensures the parser is robust against different spacing patterns and input variations.

Conclusion

This equation solver demonstrates several advanced programming concepts:

Recursive Backtracking: Exploring a solution space by trying different operations
Functional Programming: Using map/filter operations on collections
Parser Combinators: Leveraging nom for declarative, maintainable parsing
Memory Optimization: Using reference counting and slices to minimize copying
Error Handling: Proper propagation of parsing errors

The program effectively solves a challenging problem by breaking it down into manageable components, each with clear responsibilities and interfaces. The recursive approach elegantly handles the combinatorial complexity of trying different operations to reach the target result.

This site is open source. Improve this page.