Skip to content

Instantly share code, notes, and snippets.

@gigamonkey
Created July 26, 2013 18:20
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save gigamonkey/6091053 to your computer and use it in GitHub Desktop.
Save gigamonkey/6091053 to your computer and use it in GitHub Desktop.
Change counting problem from SICP in Scala
object Change {
val zeros = Stream.continually(0)
def ways(denominations: Seq[Int]) = {
denominations.foldLeft(zeros) { (previous, d) =>
lazy val base: Stream[Int] = zeros.take(d - 1) ++ 1 #:: previous.zip(base).map { x => x._1 + x._2 }
base.drop(d)
}
}
def main(args: Array[String]) {
val nums = args.map(_.toInt)
val amount = nums.head
val denominations = nums.tail
println(ways(denominations)(amount))
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment