Contdown's number game solver for all freaks who like me watched too much British panel shows.

rachel-riley.scala

sealed trait Tree {
  def eval: Option[Int] 
}

case class Leaf(n: Int) extends Tree {
  override def toString = n.toString
  def eval = Some(n)
}

case class Node(op: String, l: Tree, r: Tree) extends Tree {
  override def toString = "("+l+" "+op+" "+r+")"
  def eval = 
    for {
      el <- l.eval
      er <- r.eval
      res <- op match {
        case "+" => Some(el + er)
        case "-" => Some(el - er)
        case "*" => Some(el * er)
        case "/" if er != 0 && el % er == 0 => Some(el / er)
        case _ => None
      }
    } yield res
}

def gen(ns: Seq[Int], depth: Int): Iterator[(Tree, Seq[Int])] = {
  if (ns.isEmpty || depth <= 0) return Iterator()

  (for (n <- ns.iterator) yield (Leaf(n), ns diff Seq(n))) ++
  (for {
    (left, lns) <- gen(ns, depth - 1)
    (right, rns) <- gen(lns, depth - 1)
    op <- Iterator("+", "-", "*", "/") 
  } yield (Node(op, left, right), rns))
}

def solutions(numbers: Seq[Int], target: Int): Iterator[Tree] =
  gen(numbers, numbers.size) map (_._1) filter (_.eval == Some(target))

// Hello Rachel, can I have two big ones and four little ones
solutions(Seq(25, 50, 5, 7, 3, 6), 650) foreach println