nandemo on Retiring a Great Interview Problem

Comment on Retiring a Great Interview Problem

Just for fun I decided to rewrite his first version in Haskell. This is probably not idiomatic, though.

  segment_string :: String -> Set String -> Maybe String
  segment_string [] _ = Nothing
  segment_string str dict =
    if str `member` dict
    then Just str
    else let pairs = zip (inits str) (tails str)
             pairInDict (x, y) = x `member` dict && y `member` dict in
         do (x, y) <- find pairInDict pairs
   　        Just (x ++ " " ++ y)

shangaslammi 15y

Here's my Haskell attempt (both naive recursive backtrack and dynamic programming version):

    type Dict = Set String

    hasWord :: Dict -> String -> Bool
    hasWord = flip Set.member

    fmtWords :: [[String]] -> Maybe String
    fmtWords = fmap (intercalate " ") . listToMaybe 

    splitWordsSimple :: Dict -> String -> Maybe String
    splitWordsSimple dct = fmtWords . go where
        go [] = return []
        go s = do
            (i,t) <- zip (inits s) (tails s)
            guard $ hasWord dct i
            (i:) <$> go t

    splitWordsDP :: Dict -> String -> Maybe String
    splitWordsDP dct s = fmtWords $ a ! 0 where
        a = listArray (0, len) $ map f [0..len-1] ++ [[[]]]
        len = length s
        f i = do
            l <- [1..len-i]
            let w = take l $ drop i s
            guard $ hasWord dct w
            (w:) <$> a ! (i+l)

ottbot 15y

http://www.codinghorror.com/blog/2007/02/fizzbuzz-the-progra...

nandemo 15y

So what? This problem (the full version) is more complex than FizzBuzz. Besides, I'm not pasting code here to prove that I can program, but to show how the solution looks like in Haskell.

eru 15y

Yes, doesn't strike me as idiomatic. But I can't come up with a better version on the spot.

zohebv 15y

How about this, this will compute more than pairs

let dict = Data.Set.fromList["apple", "pie", "bread", "applepie", "piebread"]

let fn q = concat.Data.List.map (\(x,y) -> if (member x dict) then if y == "" then [[x]] else Data.List.map (x:) (fn y) else [] ) $ tail $ zip (inits q) (tails q)

fn "applepiebread" [["apple","pie","bread"],["apple","piebread"],["applepie","bread"]]

</code></pre>

Comments