Solving Google Code Jam's "Minimum Scalar Product" in Haskell

Question

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:

http://code.google.com/codejam/contest/32016/dashboard#s=p0

And here's the gist of my current Haskell solution:

{-
- 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] -> 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 <- permutations v1, b <- permutations v2]
          options = map scalar pairs

parseVector :: String -> Int -> [Int]
parseVector line n = map read $ take n $ (words line) :: [Int]

scalar :: ([Int],[Int]) -> Int
scalar (v1,v2) = sum $ zipWith (*) v1 v2

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.

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.

Answer 1

Improving your algorithm is the most important thing. Currently, you permute both lists, giving a total of (n!)^2 options to check. You need only permute one of the lists. That should not only reduce the time complexity but also the space usage drastically. And make sure the minimum gets replaced by the strict minimum (as it should, with optimisations, since you're taking the minimum of a list of Ints, compile with -ddump-rule-firings and check for "minimumInt"). If it isn't, use foldl1' min instead of minimum.

I just checked:

Large dataset

T = 10
100 ≤ n ≤ 800
-100000 ≤ xi, yi ≤ 100000

For that, you need a dramatically better algorithm. 100! is about 9.3 * 10¹⁵⁷, the universe will long have ceased to exist before you have checked a measurable portion of all the permutations of 100 elements. You must construct the solving permutations by looking at the data. To find out what the solutions would look like, investigate some small inputs and what permutations realise the minimum scalar product for those (having a look at the Cauchy-Bun'akovskiy-Schwarz inequality would also not hurt).

Answer 2

The solution I came up with:

{-
- 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] -> String
solve input = show result
    where (l1:l2:l3:_) = input
          n = read l1 :: Int
          v1 = parseVector l2 n
          v2 = parseVector l3 n
          result = scalar (sort v1) (reverse $ sort v2)

parseVector :: String -> Int -> [Integer]
parseVector line n = map read $ take n $ (words line) :: [Integer]

scalar :: [Integer] -> [Integer] -> Integer
scalar v1 v2 = sum $ zipWith (*) v1 v2 :: Integer

This seems to give the right answer and is orders of magnitude faster. The trick I guess is to not take the word "permutation" at face value when reading problems like this.

Answer 3

according to me(my solution work), you really don't need to permute, you really need to sort both list,then you require queue and stack,
so how it work
ex:-
input
1 3 -5
-2 1 4

sort
-5 1 3
-2 1 4

then -2*3+4*-5+1*1=-6

ex2:-
so you see
-ve number multiply with most +ve or least -ve
+ve number multiply with most -ve or least +ve