# My Weblog

## 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

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

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

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.