ArithmeticSolver.md

Arithmetic solver for http://blog.plover.com/math/17-puzzle.html

sealed trait Op extends Product with Serializable
case object Add extends Op { override def toString() = "+" }
case object Min extends Op { override def toString() = "-" }
case object Mul extends Op { override def toString() = "*" }
case object Div extends Op { override def toString() = "/" }

sealed trait Arithmetic extends Product with Serializable { def value: Int }
final case class Number(value: Int) extends Arithmetic { override def toString() = value.toString }
final case class Combine(lhr: Arithmetic, op: Op, rhr: Arithmetic) extends Arithmetic {
  lazy val value =
    (lhr, op, rhr) match {
      case (Number(x), Add, y) => x + y.value
      case (x, Add, Number(y)) => x.value + y
      case (x, Add, y) => x.value + y.value
      case (Number(x), Min, y) => x - y.value
      case (x, Min, Number(y)) => x.value - y
      case (x, Min, y) => x.value - y.value
      case (Number(x), Mul, y) => x * y.value
      case (x, Mul, Number(y)) => x.value * y
      case (x, Mul, y) => x.value * y.value
      case (Number(x), Div, y) => x / y.value
      case (x, Div, Number(y)) => x.value / y
      case (x, Div, y) => x.value / y.value
    }
  override def toString() = s"($lhr $op $rhr)"
}

object Solver extends  App {
  def split(ls: List[Int]): Stream[(List[Int], List[Int])] = {
    val stream = ls.toStream
    val sl = stream.scanLeft(List.empty[Int])((xs, x) => xs :+ x)
    val rl = stream.scanRight(List.empty[Int])((x, xs) => x :: xs)
    sl.zip(rl).filter { case (left, right) => right.nonEmpty && right.nonEmpty }
  }

  def combine(ls: List[Int]): Stream[Arithmetic] = {
    def combineTwo(left: Arithmetic, right: Arithmetic): Stream[Arithmetic] =
      if (right.value == 0 || left.value % right.value != 0) Stream(Combine(left, Add, right), Combine(left, Min, right), Combine(left, Mul, right))
      else Stream(Combine(left, Add, right), Combine(left, Min, right), Combine(left, Mul, right), Combine(left, Div, right))

    ls match {
      case Nil => Stream.empty
      case x :: Nil => Stream(Number(x))
      case xs =>
        for {
          (left, right) <- split(xs)
          leftA <- combine(left)
          rightA <- combine(right)
          combined <- combineTwo(leftA, rightA)
        } yield combined
    }
  }

  def solve(ls: List[Int], goal: Int): Stream[Arithmetic] = {
    def go(left: Arithmetic, right: List[Int], goal: Int): Stream[Arithmetic] = {
      if (left.value == 0)
        if (goal == 0)
          solve(right, 0).flatMap(right => Stream(Combine(left, Add, right), Combine(left, Min, right))) ++
          combine(right).flatMap(right => if (right.value == 0) Stream(Combine(left, Mul, right)) else Stream(Combine(left, Mul, right), Combine(left, Div, right)))
        else
          solve(right, goal - left.value).flatMap(right => Stream(Combine(left, Add, right))) ++ solve(right, left.value - goal).flatMap(right => Stream(Combine(left, Min, right)))
      else
        if (goal == 0)
          solve(right, 0).flatMap(right => Stream(Combine(left, Mul, right)))
        else
          solve(right, goal - left.value).flatMap(right => Stream(Combine(left, Add, right))) ++
            solve(right, left.value - goal).flatMap(right => Stream(Combine(left, Min, right))) ++
              (if (goal % left.value == 0) solve(right, goal / left.value).flatMap(right => Stream(Combine(left, Mul, right))) else Stream.empty) ++
                (if (left.value % goal == 0) solve(right, left.value / goal).flatMap(right => Stream(Combine(left, Div, right))) else Stream.empty)
    }

    ls match {
      case Nil => Stream.empty
      case x :: Nil => if (x == goal) Stream(Number(x)) else Stream.empty
      case xs =>
        for {
          (left, right) <- split(xs)
          lc <- combine(left)
          c <- go(lc, right, goal)
        } yield c
    }
  }

  def solve2(ls: List[Int], goal: Int): Stream[Arithmetic] =
    ls.permutations.toStream.flatMap(solve(_, goal))
}