My Weblog

Blog about programming and math

Google code jam qualification round 2011

I solved 3 problem out of 4. I was not able to get the problem A.With 80 points , i got a prime number ( 2221 ) rank in the list :P. The Magicka problem was based on simulation. Just simulate the process . I wrote Haskell solution for this problem after the contest.

import Data.List as L
import Data.Map as M 

rInt::String -> Int
rInt = read 

checkFun::[String] -> String ->String -> Bool 
checkFun xs [] s = False
checkFun xs ( y:ys ) s = if or [ elem ( [y] ++ s ) xs ,  elem ( s ++ [y] ) xs ]  then True else checkFun xs ys s 

solve ::  [ String ] -> String 
solve xs = 
 let 
    c = rInt . head $ xs 
    t_1 = take c . tail $ xs 
    tmp_1 = drop c . tail $ xs 
    d = rInt . head $ tmp_1 
    t_2 = ( take d . tail $ tmp_1 ) ++ ( L.map reverse ( take d . tail $ tmp_1 ) ) -- i got the list in both order 
    tmp_2 = drop d . tail $ tmp_1 
    s = concat.tail $  tmp_2 
    t_l = L.map ( take 2 ) t_1
    t_r = L.map ( drop 2 ) t_1	
    m = M.fromList $ zip ( t_l ++ ( L.map reverse t_l ) ) ( t_r ++ t_r )
  in  solveHelp [ head s ] ( tail s ) m t_2   
        

solveHelp:: String -> String -> Map String String -> [String] -> String
solveHelp xs [] _ _ = xs 
solveHelp xs [y] m t_2 = 
   case M.lookup ( [ L.last xs ] ++ [ y ] ) m of 
   	Just c -> L.init xs ++ c 
        _      ->  case M.lookup ( [ y ] ++ [ L.last xs ] ) m of
		     Just c ->  L.init xs ++ c 
		     _      ->  case checkFun t_2 xs [ y ] of 
			          True ->  []
				  _    ->  xs ++ [ y ] 	         
solveHelp xs (y_1:ys) m t_2 = 
   case  M.lookup ( [ L.last xs ] ++ [  y_1 ] ) m  of 
	Just c ->  solveHelp ( L.init xs ++ c ) ys m t_2
	_      ->  case M.lookup ( [ y_1 ] ++ [ L.last xs ] ) m  of 
		     Just c -> solveHelp ( L.init  xs ++ c ) ys m t_2
		     _      -> 	case  checkFun t_2 xs [ y_1 ]  of 
			          True ->  solveHelp [ head ys ] ( tail ys )  m t_2 
				  _    ->  solveHelp (  xs ++ [y_1] ) ys  m t_2 




format :: String -> String 
format [] = "[]"
format [x] = "[" ++  [x] ++ "]"
format ( x:xs ) = "[" ++ [x] ++ helpFormat xs ++ "]"  where 
		   helpFormat [] = ""
		   helpFormat ( x:xs ) = ", " ++ [x] ++ helpFormat xs 

main::IO()
main = interact $ unlines . zipWith (++) ["Case #" ++ show i ++ ": " |i<-[1..]] .L.map format . L.map (solve . words) . tail . lines

I really liked Candy problem. First i solved it for small cases using brute force method which was not good enough for large test case. I noticed the sum was xor property and one of my friend told me the property of xoring the sequence of N numbers. If you xor N numbers and if it is zero then xor of any N-1 numbers will be equal to excluded one number.

import Data.List
import Data.Bits 

part::[ Int ] -> String 
part xs = 
   let 
	( x:xs' )  = sort xs 
	t = foldr xor x xs'
   in if t /= 0 then "NO" else show ( sum xs' )

rInt::String->Int
rInt = read

main = interact $ unlines.zipWith (++) ["Case #" ++ ( show i ) ++ ": " | i<-[1..] ]. map part.(map.map) rInt.filter (\x -> length x /= 1) . map  words  . lines 

Gorosort problem was totally my intuition . I was not sure about the correctness of algorithm but i remembered a online judge problem , probably http://acm.timus.ru/ , regarding the cycles in permutation.I worked with few test cases and it worked. Just count how may cycles are in the permutation.

import Data.List

rInt :: String -> Integer
rInt = read 

solve :: [ Integer ] -> Double
solve xs =  fromIntegral . length . filter (\x -> x == True ) .  zipWith ( /= ) [1..] $  xs

removeOdd :: [String] -> [ String ]
removeOdd (_:x:xs) = x : removeOdd xs
removeOdd _ = []

main  = interact $ unlines.zipWith (++) ["Case #" ++ ( show i ) ++ ": " | i<-[1..] ]. map ( show . solve ) .( map . map ) rInt . map  words  . removeOdd . tail . lines

You can get the analysis of all the problems on code jam home. To get the solution of problem in different languages , check go-hero.

Advertisements

May 9, 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: