My Weblog

Blog about programming and math

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
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 ( 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.

Advertisements

May 19, 2011 - Posted by | Programming

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: