Programming Praxis – Google Code Jam Qualification Round Africa 2010

In today’s Programming Praxis exercise, our goal is to solve three Google Code Jam assignments. Let’s get started, shall we?

A quick import:

import Data.List

For the store credit exercise, we simply test all unique combinations of two items to see which add up to the correct total and return the first one.

storeCredit :: Num a => a -> [a] -> (Int, Int)
storeCredit c xs = head [ (i, j) | (i, a) <- zip [1..] xs
                        , (j, b) <- drop i $ zip [1..] xs, a + b == c]

Reversing the words in a sentence is trivial: make a list of words, reverse it and assemble them together again.

reverseWords :: String -> String
reverseWords = unwords . reverse . words

The T9 assignment is a bit more complicated. First, we find the correct sequence of digits for each character of the input. Then we add spaces between each consecutive group of identical digits, except between consecutive zeros.

t9 :: String -> String
t9 s = unwords =<< groupBy (\(a:_) (b:_) -> a == b && a > '0') (map f s)
    where f c = maybe "0" id . lookup c . concat $ zipWith zip
                    (words "abc def ghi jkl mno pqrs tuv wxyz")
                    [[replicate n d | n <- [1..]] | d <- ['2'..]]

Some tests to see if we made any mistakes:

main :: IO ()
main = do print $ storeCredit 100 [5,75,25] == (2,3)
          print $ storeCredit 200 [150,24,79,50,88,345,3] == (1,4)
          print $ storeCredit 8 [2,1,9,4,4,56,90,3] == (4,5)
          print $ reverseWords "this is a test" == "test a is this"
          print $ reverseWords "foobar" == "foobar"
          print $ reverseWords "all your base" == "base your all"
          print $ t9 "hi" == "44 444"
          print $ t9 "yes" == "999337777"
          print $ t9 "foo  bar" == "333666 6660022 2777"
          print $ t9 "hello world" == "4433555 555666096667775553"

Nope, looks like everything is working properly.

About these ads

Tags: , , , , , , , , , , , ,

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


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: