Problem 5, "Five programming problems every Software Engineer should be able to solve in less than 1 hour"

problem5.rs

// Problem 5 - https://blog.svpino.com/2015/05/07/five-programming-problems-every-software-engineer-should-be-able-to-solve-in-less-than-1-hour
// https://play.rust-lang.org/
 
#[derive(Copy,Clone)]
enum Op {
  Concat = 0,
  Plus,
  Minus
}

impl Op {
  fn from(n: usize) -> Op {
    match n {
      0 => Op::Concat,
      1 => Op::Plus,
      2 => Op::Minus,
      _ => panic!()
    }
  }
}

fn eval(ops: &[Op; 9], target: i64) -> bool {
  let mut val = 0;
  let mut acc = 1;  // digit '1'
  let mut prev = Op::Concat;
  for i in 0..9 {
    let digit = (i as i64) + 2;
    match ops[i] {
      Op::Concat => {
        acc = acc * 10 + digit
      },
      op => {
        match prev {
          Op::Concat => { val = acc },
          Op::Plus => { val += acc },
          Op::Minus => { val -= acc },
        }
        acc = digit;
        prev = op;
      }
    }
  }
  target == val
}

fn dump(ops: &[Op; 9]) {
  let mut s = "1".to_string();
  for n in 0..8 {
    match ops[n] {
      Op::Plus => { s.push('+') },
      Op::Minus => { s.push('-') },
      _ => (),
    }
    s.push((b'2' + n as u8) as char);
  }
  println!("{}", s);
}

fn solve() {
  let mut ops = [Op::Concat; 9];
  ops[8] = Op::Plus;  // sentinel
  for n in 0..(3usize.pow(8)) {
    let mut m = n;
    for i in (0..8).rev() {
      ops[i] = Op::from(m % 3);
      m /= 3;
    }
    if eval(&ops, 100) {
      dump(&ops);
    }
  }
}

fn main() {
  solve();
}