Last active
July 1, 2024 10:22
-
-
Save terakun/208881312835505feae093e2313f9e41 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment