four-number.rs

.gitignore

/main

main.rs

use std::cmp::Ordering;
use std::fmt;

#[derive(Clone)]
enum Op {
  Value(i32),
  Add(Box<Op>, Box<Op>),
  Minus(Box<Op>, Box<Op>),
  Mul(Box<Op>, Box<Op>),
  Div(Box<Op>, Box<Op>),
}

impl fmt::Debug for Op {
  fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
    return match self {
      Op::Value(x) => {
        write!(f, "{:?}", x)
      },
      Op::Add(x, y) => {
        write!(f, "({:?} + {:?})", x, y)
      },
      Op::Mul(x, y) => {
        write!(f, "({:?} * {:?})", x, y)
      },
      Op::Minus(x, y) => {
        write!(f, "({:?} - {:?})", x, y)
      },
      Op::Div(x, y) => {
        write!(f, "({:?} / {:?})", x, y)
      },
    }
  }
}

#[derive(Clone)]
struct Fraction {
  numerator: i32,
  denominator: i32,
}

impl Fraction {
  fn new(numerator: i32, denominator: i32) -> Self {
    Self {
      numerator: numerator,
      denominator: denominator,
    }
  }
  fn add(&self, f: Self) -> Self {
    Self {
      numerator: self.numerator * f.denominator + self.denominator * f.numerator,
      denominator: self.denominator * f.denominator,
    }
  }
  fn minus(&self, f: Self) -> Self {
    Self {
      numerator: self.numerator * f.denominator - self.denominator * f.numerator,
      denominator: self.denominator * f.denominator,
    }
  }
  fn mul(&self, f: Self) -> Self {
    Self {
      numerator: self.numerator * f.numerator,
      denominator: self.denominator * f.denominator,
    }
  }
  fn div(&self, f: Self) -> Self {
    Self {
      numerator: self.numerator * f.denominator,
      denominator: self.denominator * f.numerator,
    }
  }
  fn reduce(&self) -> Self {
    let g = self.gcd(self.numerator.abs(), self.denominator.abs());
    if g == 0 { return self.clone(); }
    Self {
      numerator: self.numerator / g,
      denominator: self.denominator / g,
    }
  }
  fn gcd(&self, a: i32, b: i32) -> i32 {
    let u = if a > b { a } else { b };
    let l = if a > b { b } else { a };
    if l == 0 { return u; }
    self.gcd(l, u % l)
  }
}

impl PartialOrd for Fraction {
  fn partial_cmp(&self, f: &Fraction) -> Option<Ordering> {
    Some((self.numerator * f.denominator).cmp(&(self.denominator * f.numerator)))
  }
}

impl PartialEq for Fraction {
  fn eq(&self, f: &Fraction) -> bool {
    let a = self.reduce();
    let b = f.reduce();
    a.numerator == b.numerator && a.denominator == b.denominator
  }
}

impl fmt::Debug for Fraction {
  fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
    if self.denominator == 1 {
      write!(f, "{:?}", self.numerator)
    } else {
      write!(f, "{:?}/{:?}", self.numerator, self.denominator)
    }
  }
}

impl Op {
  fn compile(&self) -> Fraction {
    return match self {
      Op::Value(x)    => { Fraction::new(*x, 1) }, // ?
      Op::Add(x, y)   => { x.compile().add(y.compile()) },
      Op::Mul(x, y)   => { x.compile().mul(y.compile()) },
      Op::Minus(x, y) => { x.compile().minus(y.compile()) },
      Op::Div(x, y)   => { x.compile().div(y.compile()) },
    }
  }
}

fn solve(items: &Vec<i32>, from: usize, to: usize) -> Vec<Op> {
  let len = to - from;
  match len {
    len if len == 1 => {
      return vec![Op::Value(items[from])];
    },
    len if len > 0 => {
      let mut v = Vec::new();
      for k in (from+1)..to {
        let l = solve(items, from, k);
        let r = solve(items, k, to);
        for x in &l {
          for y in &r {
            v.push(Op::Add(Box::new(x.clone()), Box::new(y.clone())));
            v.push(Op::Minus(Box::new(x.clone()), Box::new(y.clone())));
            v.push(Op::Div(Box::new(x.clone()), Box::new(y.clone())));
            v.push(Op::Mul(Box::new(x.clone()), Box::new(y.clone())));            
          }
        }
      }
      return v;
    },
    _ => {
      panic!("something wrong {:?}", len);
    }
  }
}

fn rec(count: i32, ten: &Fraction, mut items: &mut Vec<i32>) {
  if count == 0 {
    for v in &solve(&items, 0, items.len()) {
      let d = v.compile().reduce();
      if d == *ten {
        println!("{:?} = {:?}", d, v);
      }
    }
    return
  }
  for i in 0..10 {
    items.push(i);
    rec(count - 1, ten, items);
    items.pop();
  }
}

fn main() {
  let ten = Fraction::new(10, 1);
  rec(4, &ten, &mut Vec::new())
}