Posts Tagged ‘reverse’

Programming Praxis – Reverse Words

March 8, 2011

In today’s Programming Praxis exercise, we’re revisiting the well-known interviewing problem of reversing the words in a string. This time, we have to do the reversal in place and without using any library functions for determining the words. Let’s get started, shall we?

Haskell doesn’t do much in the way of in-place modifications by default. Attempting to modify a string (or indeed the majority of all data structures) will create a copy of it (though part of the new one may refer to same memory occupied by the original). I figured the closest thing to modifying the string in place would be to turn it into a mutable array. It’s not entirely in-place since we still have to convert to and from the array, but it’s the closest we’re going to get.

import Data.Array.IO

We start with a function to switch to characters in a string.

switch :: (MArray a e m, Ix i) => i -> i -> a i e -> m ()
switch i j a = do x <- readArray a i
                  writeArray a i =<< readArray a j
                  writeArray a j x

Next, we make a function to reverse part of a string.

revRange :: Int -> Int -> IOArray Int a -> IO (IOArray Int a)
revRange i j a = mapM_ (\n -> switch n (j+i-n) a) [i..div (i+j) 2] >> return a

The algorithm for reversing the words in a string is the same as in the Scheme version: reverse the entire string, then reverse the individual words.

reverseWords :: String -> IO String
reverseWords xs = do a <- newListArray (0, length xs - 1) xs
                     (s,e) <- getBounds a
                     f 0 e =<< revRange s e a where
    f i e a = if i > e then getElems a else nextSpace i e a >>=
                 \s -> f (s+1) e =<< revRange i (s-1) a
    nextSpace i e a = if i > e then return i else readArray a i >>= \c ->
                      if c == ' ' then return i else nextSpace (i+1) e a

Let’s see if everything is working properly:

main :: IO ()
main = do let a =? b = print . (== b) =<< reverseWords a
          "" =? ""
          " " =? " "
          "  " =? "  "
          "hello" =? "hello"
          "hello " =? " hello"
          " hello" =? "hello "
          "the quick brown fox" =? "fox brown quick the"
          "the quick  brown fox" =? "fox brown  quick the"
          "the quick  brown 42 fox!" =? "fox! 42 brown  quick the"

Yup. Having to do things in place does make the code a lot longer than the original solution though.

Programming Praxis – Google Code Jam Qualification Round Africa 2010

February 15, 2011

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.