My Weblog

SPOJ Perfect Cubes

Perfect Cubes is killed by Haskell :). Take two lists and in first list , calculate $( a^3 - b^3 , a , b )$ for all a from 2 to 100 and b from 2 to ( a -1 ) . Second list calculate $( c^3 + d^3 , c , d)$ for all c from 2 to 100 and d from ( c+1 ) to 100. Find the potential match between each list.

```import Data.List

m_1 , m_2 :: [( Integer , Integer , Integer )]
m_1 = sort [ ( a^3 - b^3 , a , b ) | a <- [2..100] , b <- [2..( a - 1 )] ]
m_2 = sort [ ( c^3 + d^3 , c , d ) | c <- [2..100] , d <- [( c + 1 )..100] ]

solve ::  [( Integer , Integer , Integer )] ->  [( Integer , Integer , Integer )] -> [(Integer , Integer , Integer , Integer )]
solve [] [] = []
solve _ []  = []
solve [] _  = []
solve t_1@( ( v_1 , a , b  ) : xs ) t_2@( ( v_2 , c , d ) :ys ) =
case compare v_1 v_2 of
LT -> solve xs t_2
GT -> solve t_1 ys
EQ -> tmpSolve  ( v_1 , a , b ) t_2 ++ solve xs t_2

tmpSolve :: ( Integer , Integer , Integer ) ->  [( Integer , Integer , Integer )] ->  [( Integer , Integer , Integer , Integer)]
tmpSolve _ [] = []
tmpSolve t@(v_1 , a, b) ((v_2 , c , d) : ys ) =
case v_1 == v_2 of
False -> []
True  -> if and [ b < c , c < d , d < a ] then [(a , b , c , d)] ++ tmpSolve t ys else tmpSolve t ys

format :: ( Integer , Integer , Integer , Integer ) -> String
format (a , b, c, d ) = "Cube = " ++ show a ++", Triple = (" ++ show b ++"," ++ show c ++ "," ++ show d ++")"

main = do
let lst =  map format. sort. solve m_1 \$ m_2
forM_ lst putStrLn
```

Sort both list and take first element of tuple from first list $( a^3 - b^3 )$ and find the potential match in second list . If match then check the condition ( b < c , c < d , d < a) otherwise move to next element.