mixture.scala

/** 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)))