After reading @raganwald's article "Carnac the Magnificent" (http://raganwald.com/2015/05/08/carnac-the-magnificent.html) I was interested to see how well I could do with a naïve solution in Scala using streams. I tried to write a bunch of comments to make it clear how it works. Notably, it doesn't using anything like `eval()` which is one reaso…

carnac.scala

package carnac

// the right approach to this problem is to use dynamic programming.
// i was curious about trying to come up with a readable, minimal
// example solution that worked. i feel ok about this.

object Carnac {

  // represents a mathematical operation, either addition or subtraction.
  sealed abstract class Sym(val f: (Int, Int) => Int, val s: String)
  case object Plus extends Sym(_ + _, "+")
  case object Minus extends Sym(_ - _, "-")

  // p is the implicit instruction between any two numbers.
  // None means concatenate the numbers, Some(sym) uses that sym.
  type P = Option[Sym]

  val Last = 9

  // x is the next number in the sequence
  // ps is a stack of the previous p values we applied
  // total is the running sum so far
  // sym is the last operation we saw (applied to the future value)
  // curr is a working total for the future value
  //
  // returns a stream of all solutions as stacks of p values.
  def run(x: Int, ps: List[P], total: Int, sym: Sym, curr: Int): Stream[List[P]] =
    if (x <= Last) {
      // try concatenation, addition, and subtraction
      run(x + 1, None :: ps, total, sym, curr * 10 + x) #:::
      run(x + 1, Some(Plus) :: ps, sym.f(total, curr), Plus, x) #:::
      run(x + 1, Some(Minus) :: ps, sym.f(total, curr), Minus, x)
    } else if (sym.f(total, curr) == 100) {
      Stream(ps)
    } else {
      Stream.Empty
    }

  // display a stack of p values within the number sequence
  def show(ps: List[P], x: Int = Last, s: String = ""): String =
    ps match {
      case o :: t => show(t, x - 1, o.fold("")(_.s) + x + s)
      case Nil => x + s
    }

  // run our program!
  def main(args: Array[String]): Unit =
    // we call run as if we had seen (0+1...), so x = 2.
    // however, ps = Nil, since we don't want this "virtual" plus.
    run(2, Nil, total = 0, sym = Plus, curr = 1).foreach { p =>
      println(show(p))
    }
}