Skip to content

Instantly share code, notes, and snippets.

Last active Aug 29, 2015
What would you like to do?
After reading @raganwald's article "Carnac the Magnificent" ( 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…
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) {
} else {
// 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 =>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment