## SPOJ Perfect Cubes

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

import Data.List import Control.Monad 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 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.

Advertisements

No comments yet.

Advertisements

## Leave a Reply