qk-10puzzle.rs

use csv;
use std::fs::File;
use itertools::Itertools;

#[derive(Clone, Copy, Debug, PartialEq)]
enum Operator {
    Add,
    Sub, 
    Mult,
    Div
}

#[derive(Clone, Debug, PartialEq)]
enum Ast {
    Op(Operator, Box<Ast>, Box<Ast>),
    Const(f64),
}

impl Ast {
    fn to_string(&self) -> String {
        use Ast::*;
        match self 
        {
            Op(op, lhs, rhs)  => match *op {
                Operator::Add => format!("({} + {})", lhs.to_string(), rhs.to_string()),
                Operator::Sub  => format!("({} - {})", lhs.to_string(), rhs.to_string()),
                Operator::Mult => format!("{} * {}", lhs.to_string(), rhs.to_string()),
                Operator::Div  => format!("{} / {}", lhs.to_string(), rhs.to_string()),
            }
            Const(val) => (*val as i64).to_string()
        }
    }
}

fn solve_recursive(target_value: f64, seq_val_ast: &Vec<(f64, Ast)>) -> Option<Ast>
{
    use Operator::*;
    const EPS: f64 = 1.0e-10;
    if seq_val_ast.len() == 1 {
        if (target_value - seq_val_ast[0].0).abs() < EPS {
            return Some(seq_val_ast[0].1.clone());
        } else {
            return None;
        }
    }

    let operators = vec![Add, Sub, Mult, Div];
    for pair in seq_val_ast.iter().enumerate().permutations(2)
    {
        for op in &operators 
        {
            let (lhs_ind, lhs_val, lhs_ast) = (pair[0].0, pair[0].1.0, pair[0].1.1.clone());
            let (rhs_ind, rhs_val, rhs_ast) = (pair[1].0, pair[1].1.0, pair[1].1.1.clone());
            let val = match op
            {
                Add  => lhs_val + rhs_val,
                Sub  => lhs_val - rhs_val,
                Mult => lhs_val * rhs_val,
                Div  => lhs_val / rhs_val,
            };           
            let ast = Ast::Op(*op, Box::new(lhs_ast), Box::new(rhs_ast));

            let (lhs_ind, rhs_ind) = if lhs_ind > rhs_ind {
                (rhs_ind, lhs_ind)
            } else {
                (lhs_ind, rhs_ind)
            };
            let mut evaled_seq_val_ast = seq_val_ast.clone();
            evaled_seq_val_ast.remove(rhs_ind);
            evaled_seq_val_ast.remove(lhs_ind);
            evaled_seq_val_ast.push((val, ast));

            let solution = solve_recursive(target_value, &evaled_seq_val_ast);
            if solution != None {
                return solution;
            }
        }
    }
    None
}

fn solve(target_value: f64, seq: &Vec<f64>) -> Option<Ast>
{
    let seq_val_ast = seq.iter().map(|val| (*val, Ast::Const(*val))).collect();
    solve_recursive(target_value, &seq_val_ast)
}

#[test]
fn test()
{
    let target_value = 10.;
    let seq = vec![1., 1., 5., 8.];
    let solution = solve(target_value, &seq);
    assert!(solution != None);

     let target_value = 65.0;
    let seq = vec![2.0, 2.0, 2.0, 2.0, 3.0, 3.0, 4.0, 5.0, 5.0, 5.0, 6.0, 9.0];
    let solution = solve(target_value, &seq);
    assert!(solution != None);
}

fn main() {
    let filepath = "test.csv".to_string();
    match File::open(&filepath) {
        Ok(file) => {
            let mut rdr = csv::Reader::from_reader(file);

            let mut ok_cnt = 0;
            let mut total_cnt = 0;
            for line in rdr.records() {
                let line = line.unwrap();
                let index = line.get(0).unwrap().parse::<i64>().unwrap();
                let target_value = line.get(1).unwrap().parse::<f64>().unwrap();
                let seq: Vec<f64> = line.get(2).unwrap().split(',').map(|s| s.parse::<f64>().unwrap()).collect();
                println!("{}: {} {:?}", index, target_value, seq);
                let solution = solve(target_value, &seq);
                if solution != None {
                    println!("{} = {}", solution.unwrap().to_string(), target_value);
                    ok_cnt += 1;
                }
                total_cnt += 1;
            }
            println!("{} / {} = {} %", ok_cnt, total_cnt, (ok_cnt as f64 / total_cnt as f64 * 100.0) as i64);
        }
        Err(e) => {
            panic!("{:?}", e);
        }
    }
}