title: Solving Google Code Jam's "Minimum Scalar Product" in Haskell
body: <p>In preparation for the upcoming Google Code Jam, I've started working on some problems. Here's one of the practice problems I've tried:</p>
  
  <p><a href="http://code.google.com/codejam/contest/32016/dashboard#s=p0" rel="nofollow noreferrer">http://code.google.com/codejam/contest/32016/dashboard#s=p0</a></p>
  
  <p>And here's the gist of my current Haskell solution:</p>
  
  <pre><code>{-
  - Problem URL: http://code.google.com/codejam/contest/32016/dashboard#s=p0
  -
  - solve takes as input a list of strings for a particular case
  - and returns a string representation of its solution.
  -}
  
  import Data.List    
  
  solve :: [String] -&gt; String
  solve input = show $ minimum options
      where (l1:l2:l3:_) = input
            n = read l1 :: Int
            v1 = parseVector l2 n
            v2 = parseVector l3 n
            pairs = [(a,b) | a &lt;- permutations v1, b &lt;- permutations v2]
            options = map scalar pairs
  
  parseVector :: String -&gt; Int -&gt; [Int]
  parseVector line n = map read $ take n $ (words line) :: [Int]
  
  scalar :: ([Int],[Int]) -&gt; Int
  scalar (v1,v2) = sum $ zipWith (*) v1 v2
  </code></pre>
  
  <p>This works with the sample input provided, but dies on the small input to an out of memory error. Increasing the max heap size appears to do nothing but let it run indefinitely.</p>
  
  <p>My main question is how to go about optimizing this so that it will actually return a solution, other than passing in the -O flag to ghc, which I've already done.</p>