Solve the NYTimes Digits Puzzle by Brute Force

nytimes-digits-solver.rs

#[derive(Copy,Clone,Debug)]
enum Operator {ADD, SUB, MUL, DIV}

#[derive(Copy,Clone,Debug)]
struct Operation {
    lhs: usize,
    rhs: usize,
    operator: Operator,
}

impl Operator {
    fn apply(&self, lhs: usize, rhs: usize) -> Option<usize> {
        match self {
            Operator::ADD => lhs.checked_add(rhs),
            Operator::SUB => lhs.checked_sub(rhs),
            Operator::MUL => lhs.checked_mul(rhs),
            Operator::DIV => lhs.checked_div(rhs).filter(|_| lhs % rhs == 0)
        }
    }
}
                
impl Operation {
    fn result(&self) -> Option<usize> {
        self.operator.apply(self.lhs, self.rhs)
    }
}

impl std::fmt::Display for Operator {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.write_str(match self {
            Operator::ADD => "+",
            Operator::SUB => "-",
            Operator::MUL => "*",
            Operator::DIV => "/",
        })
    }
}

impl std::fmt::Display for Operation {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.write_fmt(format_args!("{:3} {} {:3} = {}", self.lhs, self.operator, self.rhs, 
            match self.result() { Some(e) => e.to_string(), None => "NaN".to_string() }))
    }
}

fn solve(target: usize, options: Vec<usize>) -> Option<Vec<Operation>> {

    let mut best_solution: Option<Vec<Operation>> = None;

    for operator in [
        Operator::ADD,
        Operator::SUB,
        Operator::MUL,
        Operator::DIV,
    ] {
        let n = options.len();
        for j in 1..n {
            let rhs = options[j];
            for i in 0..j {
                let lhs = options[i];
                let operation = Operation{lhs, rhs, operator};
                if let Some(result) = operation.result() {
                    if result == target {
                        return Some(vec![operation]);
                    }
                    let mut new_options = Vec::with_capacity(n - 1);
                    new_options.push(result);
                    for k in 0..n {
                        if k == i || k == j { continue; }
                        new_options.push(options[k]);
                    }
                    if let Some(mut solution) = solve(target, new_options) {
                        if let Some(previous_solution) = &best_solution {
                            if solution.len() + 1 >= previous_solution.len() {
                                continue;
                            }
                        }
                        solution.push(operation);
                        best_solution = Some(solution);
                    }
                }
            }
        }
    }

    best_solution
}

fn usage(error: &str) {
    let mut exe = "solver".to_string();
    if let Ok(me) = std::env::current_exe() {
        if let Some(_name) = me.file_name() {
            if let Some(name) = _name.to_str() {
                exe = name.to_string();
            }
        }
    }
    println!(concat!(
        "usage: {} <target> <option1> <option2> ...\n",
        "error: {}"), exe, error);
}

fn main() {
    let args: Result<Vec<usize>,_> = std::env::args()
        .into_iter().skip(1).map(|x| x.parse()).collect();
    match args {
        Err(_) => usage("all arguments must be integers"),
        Ok(mut numbers) => {
            numbers.reverse();
            match numbers.pop() {
                None => usage("no arguments specified"),
                Some(target) => {
                    if let Some(solution) = solve(target, numbers) {
                        for operation in solution.iter().rev() {
                            println!("{}", operation);
                        }
                    } else {
                        println!("no solution was found.");
                    }
                }
            }
        }
    }
}