Scala solver for Mark Dominus' arithmetic puzzle (http://blog.plover.com/math/17-puzzle.html).

mark.scala

package mark

import spire.math.{ Rational => Q }

object Solver2 {

  case class Op(name: String, run: (Q, Q) => Option[Q])

  val ops: List[Op] = List(
    Op("+", (x, y) => Some(x + y)),
    Op("-", (x, y) => Some(x - y)),
    Op("*", (x, y) => Some(x * y)),
    Op("/", (x, y) => if (y.isZero) None else Some(x / y)))

  def eval(ws: List[Option[Q]], os: List[Op], stack: List[(String, Q)]): Option[(String, Q)] =
    (ws, os, stack) match {
      case (None :: ws, o :: os, (xs, x) :: (ys, y) :: zs) =>
        o.run(x, y).flatMap(z => eval(ws, os, (s"($xs ${o.name} $ys)", z) :: zs))
      case (Some(x) :: ws, os, st) => eval(ws, os, (x.toString, x) :: st)
      case (Nil, Nil, x :: Nil) => Some(x)
      case _ => None
    }

  val threeOps = for { x <- ops; y <- ops; z <- ops } yield List(x, y, z)

  def solve(a: Q, b: Q, c: Q, d: Q, goal: Q): String =
    List(Some(a), Some(b), Some(c), Some(d), None, None, None)
      .permutations.flatMap(ws => threeOps.map(os => (ws, os)))
      .flatMap { case (ws, os) => eval(ws, os, Nil) }
      .filter { case (_, x) => x == goal }
      .map(_._1).take(1).mkString

  def main(args: Array[String]): Unit =
    println(solve(Q(6), Q(6), Q(5), Q(2), Q(17)))
}

The idea is to generate RPN programs (a la Forth) and then evaluate them to see if any successfully finish and return 17.

We use two stacks instead of one because it ends up being easier to generate permutations of 6,6,5,2,op,op,op with the understanding that "op" could be any of +,-,*, or /. We are definitely generating too many programs but I was going for brevity + correctness here.