Skip to content

Instantly share code, notes, and snippets.

@binshi
Created May 18, 2017 10:44
Show Gist options
  • Save binshi/5593cf0a3baf95c2dd91b6aaa12135bf to your computer and use it in GitHub Desktop.
Save binshi/5593cf0a3baf95c2dd91b6aaa12135bf to your computer and use it in GitHub Desktop.
Compute to 100: Given the digits 123456789, build an expression by inserting "+" or "-" anywhere BETWEEN the digits so that it results to 100. Your answer should return all possible combinations. Example: 1 + 23 - 4 + 5 + 6 + 78 - 9 = 100
import scala.collection.mutable.ListBuffer
object Main {
val digits = 123456789
val digitsSplit = digits.toString.map(_.asDigit)
val sum = 100
def attachPrefix(prefix:ListBuffer[String], paths:ListBuffer[ListBuffer[String]]) = {
paths.filter(_.nonEmpty).map(p => prefix ++ p)
}
def findPaths(sum:Int, prevNo:Int, index:Int): ListBuffer[ListBuffer[String]] = {
val prevDigit = Math.abs(prevNo%10)
if (index >= digitsSplit.length) {
if(sum == prevNo) ListBuffer(ListBuffer(prevDigit.toString)) else ListBuffer()
} else {
val currDigit = digitsSplit(index)
val attachNo = if(prevNo >= 0) {10*prevNo + currDigit}
else {10*prevNo - currDigit}
val plusOptions = findPaths(sum-prevNo, currDigit, index+1)
val minusOptions = findPaths(sum-prevNo, -currDigit, index+1)
val joinOptions = findPaths(sum, attachNo, index+1)
val options = ListBuffer[ListBuffer[String]]()
options++=attachPrefix(ListBuffer(prevDigit.toString, "+"), plusOptions)
options++=attachPrefix(ListBuffer(prevDigit.toString, "-"), minusOptions)
options++=attachPrefix(ListBuffer(prevDigit.toString, "&"), joinOptions)
options
}
}
def main(args: Array[String]): Unit = {
findPaths(sum, digitsSplit(0), 1).foreach{s =>
println(s.mkString("").replace("&", ""))
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment