Haskell's Google Jam Minimal Scalar Solution

Question

In preparation for the upcoming Google Code Jam bug, I started working on some issues. Here is one of the practical tasks I tried:

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

And here is 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 provided input example, but dies at a small input on an error from memory. Increasing the maximum heap size does not seem to mean anything, but let it work endlessly.

My main question is how to optimize this so that it really returns a solution other than that it passed the -O flag to ghc, which I already did.

Answer 1

The solution I came across:

 {- - 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 correct answer and is an order of magnitude faster. The trick, I think, is not to take the word "permutation" at face value when reading such problems.

Answer 2

Improving your algorithm is the most important thing. You are currently rearranging both lists, providing a total of (n!)^2 parameters to check. You only need to rearrange one of the lists. This should not only reduce the time complexity, but also significantly reduce the use of space. And make sure that the minimum is replaced with a strict minimum (as with optimization, since you take the minimum of the Int s list, compile with -ddump-rule-firings and check the "minimumInt"). If not, use foldl1' min instead of the minimum.

I just checked:

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

To do this, you need a significantly better algorithm. 100! is about 9.3 * 10 ¹⁵⁷ junior will cease to exist long before you check the measurable part of all permutations of 100 elements. You must build decisive permutations by looking at the data. To find out what the solutions will look like, examine some small inputs and what permutations implement the minimum scalar product for them (if you look at the Cauchy-Bunyakovsky-Schwartz inequality, it will not hurt either).

Answer 3

according to me (my solution work), you really don't need to rearrange, you really need to sort both lists, then you need a queue and a stack,
as it works for example: -
input data
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 multiply the number with the greater + ve or the smallest -ve
+ ve number is multiplied by most -ve or minimum + ve

Answer 4

My main question is how to optimize this so that it really returns a solution other than that it passed the -O flag to ghc, which I already did.

I think you should reconsider your approach. I think this problem is not so much in coding skills as in solving problems. Trying all possible permutations is brute force, and I think that now you have a good feeling why this brute force strategy does not work in this case;). This can actually be done in 3 lines of code when you use stl algorithms (not counting input and output, of course).

In fact, Madan Ram has already given some kind of solution. However, if you are ever given such a problem in an interview, you will also need to know why it works in all cases (not just for a number of examples). Therefore, my advice is to take a pen and a piece of paper and make some examples by hand, then you will learn how to do it.

SPOILER WARNING

It's hard to give a hint without spoiling a lot, but since the solution has already been published ... Try to start simply. Which element in the first vector has the greatest contribution to the scalar product? To which element of the second vector do you need to do this in order to get the least contribution to the scalar product?