title: Using dynamic programming with Scala to solve the Mixture from CodeChef
body: <p>I am trying to solve the following <a href="http://www.codechef.com/problems/MIXTURES" rel="nofollow">codechef problem</a> using scala. The statement of the problem is as follows:</p>
  
  <blockquote>
    <p>Harry Potter has n mixtures in front of him, arranged in a row. Each
    mixture has one of 100 different colors (colors have numbers from 0 to
    99).</p>
    
    <p>He wants to mix all these mixtures together. At each step, he is going
    to take two mixtures that stand next to each other and mix them
    together, and put the resulting mixture in their place.</p>
    
    <p>When mixing two mixtures of colors a and b, the resulting mixture will
    have the color (a+b) mod 100.</p>
    
    <p>Also, there will be some smoke in the process. The amount of smoke
    generated when mixing two mixtures of colors a and b is a*b.</p>
    
    <p>Find out what is the minimum amount of smoke that Harry can get when
    mixing all the mixtures together.</p>
  </blockquote>
  
  <p>The sample answer provided is as follows:</p>
  
  <blockquote>
    <p>Input:</p>
  
  <pre><code>2 
  18 
  19 
  3
  40
  60
  20
  </code></pre>
    
    <p>Output: </p>
  
  <pre><code>342
  2400
  </code></pre>
    
    <p>In the second test case, there are two possibilities:</p>
  
  <pre><code>first mix 40 and 60 (smoke: 2400), getting 0, then mix 0 and 20 (smoke: 0); total amount of smoke is 2400
  first mix 60 and 20 (smoke: 1200), getting 80, then mix 40 and 80 (smoke: 3200); total amount of smoke is 4400
  </code></pre>
    
    <p>The first scenario is the correct approach since it minimizes the
    amount of smoke produced.</p>
  </blockquote>
  
  <p>I understand that this can be solved using dynamic programming but I am having trouble approaching this problem and expressing the algorithm in scala.</p>
  
  <p>Here's how I am thinking about this problem, in some kind of a lookup structure(Array,Map with Tuple(Int,Int) as key) store all the calculated values for mixing two colors</p>
  
  <p>This can be accomplished by the following pseudo-code:</p>
  
  <pre><code>for(colors1&lt;-1 through n)
     for(colors2&lt;-k through n)
        if(color1 != color2)
            //Check if color1,color2 combination exists as (color1,color2) or (color2,color1)    
            Map(color1,color2) = (color1+color2)%100
  </code></pre>
  
  <p>Once all the initial colors have been calculated, now we need to consider the order in which we mix up the colors taking into account the smoke produced. This is where I am having issues. I am hitting a wall trying to formulate the sub-structure that will provide the minimum smoke produced.</p>
  
  <p>It will be great to get some guidance here.</p>
  
  <p>Thanks</p>