Letters and Numbers "Numbers Round" solver in Scala

about.md

A Scala object capable of coming up with the best answer during "Numbers Rounds" of the famous TV game-show Letters and Numbers. Uses Streams and lazy evaluation for a nicely performant solution.

see http://en.wikipedia.org/wiki/Letters_and_Numbers for more

One contestant chooses how many "small" and "large" numbers they would like to make up six randomly chosen numbers. Small numbers are between 1 and 10 inclusive, and large numbers are 25, 50, 75, or 100. All large numbers will be different, so at most four large numbers may be chosen. The contestants have to use arithmetic on some or all of those numbers to get as close as possible to a randomly generated three-digit target number within the thirty second time limit. Fractions are not allowed—only integers may be used at any stage of the calculation.

lan.scala

object LAN {

  abstract class Operation
  case object Add extends Operation
  case object Subtract extends Operation
  case object Multiply extends Operation
  case object Divide extends Operation
  case class Num(val valu: Float) extends Operation

  type Equation = List[Operation]

  object Operation {
    def apply(opStr: String): Operation =
      opStr match {
        case "+" => Add
        case "-" => Subtract
        case "*" => Multiply
        case "/" => Divide
        case x => Num(x.toFloat)
      }
  }
  object Equation {
    def apply(equationStr: String): Equation =
      equationStr.split(" ").toList.map(Operation.apply)
  }

  def calc(equa: Equation): Float =
    equa match {
      case Num(x) :: List() => x
      case Num(x) :: y :: Num(z) :: xs => y match {
        case Add => calc( Num(x + z)::xs )
        case Subtract => calc( Num(x - z)::xs )
        case Multiply => calc( Num(x * z)::xs )
        case Divide => calc( Num(x / z)::xs )
      }
      case _ => 0
    }

  // from http://stackoverflow.com/questions/1070859/listing-combinations-with-repetitions-in-scala
  def mycomb[T](n: Int, l: List[T]): List[List[T]] =
    n match {
      case 0 => List(List())
      case _ => for(el <- l;
                sl <- mycomb(n-1, l dropWhile { _ != el } ))
                yield el :: sl
  }
  def comb[T](n: Int, l: List[T]): List[List[T]] = mycomb(n, l.removeDuplicates)
  def tuple2ToList[T](t: (T,T)): List[T] = List(t._1, t._2)

  // create a stream of all possible versions of the equation
  val ops: Equation = List(Add, Subtract, Multiply, Divide)
  def possibilities(cards: Equation) : Stream[Equation] =
    { for {
        hand <- cards.permutations
        opMix <- comb(cards.length-1, ops)
      } yield (hand,opMix).zipped.toList.map(tuple2ToList[Operation](_)).flatten ++ List(hand.last)
    }.toStream

  // figure out which equation yields the solution closest to a given goal
  def best_equation(equations: Stream[Equation], goal: Float): Equation = {
    def aux(remaining: Stream[Equation], winner: Equation, winning_diff: Float): Equation =
      remaining match {
        case x #:: xs =>
          if ((calc(x) - goal).abs < winning_diff) aux(xs, x, (calc(x) - goal).abs)
          else aux(xs, winner, winning_diff)
        case Stream() => winner
      }
    aux(equations, List(), Float.PositiveInfinity)
  }

  // testing:
  def main(args: Array[String]) = {
    val e = Equation("25 10 50 7 2 4")
    val ppp = possibilities(e)
    val best = best_equation(ppp, 900)
    println(best)
    println(calc(best))
  }

}