Skip to content

Instantly share code, notes, and snippets.

@ziggystar
Created April 27, 2012 14:25
Show Gist options
  • Save ziggystar/2509688 to your computer and use it in GitHub Desktop.
Save ziggystar/2509688 to your computer and use it in GitHub Desktop.
/** Find the minimum amount of smoke (second) and resulting color (first)
by splitting the sequence at every possible position,
given `lookup` contains the best mix for subsequence. */
def minSmokeMixtureSingle(s: Seq[Int], lookup: Map[Seq[Int],(Int,Int)]): (Int,Int) =
if(s.size == 1)
(s(0),0)
else if(s.size == 2)
mix(s(0),s(1))
else {
val splits = (1 to (s.size - 1)).map(s.splitAt)
val mixes = splits.map{ case (s1,s2) =>
val (c1,sm1) = lookup(s1)
val (c2,sm2) = lookup(s2)
val (newColor,newSmoke) = mix(c1,c2)
(newColor, newSmoke + sm1 + sm2)
}
mixes.minBy(_._2)
}
def mix(m1: Int, m2: Int): (Int,Int) = ((m1+m2) % 100, m1*m2)
def minSmokeMixture(s: Seq[Int]) = {
//create the mixture sequences with increasing length
val windows = for(windowSize <- 1 to s.size;
window <- s.sliding(windowSize) ) yield window
//go over the sequences and compute the lookup-table
val lookup = windows.foldLeft(Map.empty[Seq[Int],(Int,Int)]){case (lu,seq) => lu + (seq -> minSmokeMixtureSingle(seq,lu))}
//simply lookup the result
lookup(s)
}
println(minSmokeMixture(Seq(18, 19)))
println(minSmokeMixture(Seq(40, 60, 20)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment