Skip to content

Instantly share code, notes, and snippets.

@mdunsmuir
Last active August 29, 2015 14:13
Show Gist options
  • Save mdunsmuir/8143854d7239454583d0 to your computer and use it in GitHub Desktop.
Save mdunsmuir/8143854d7239454583d0 to your computer and use it in GitHub Desktop.
given an input 'dictionary' (a list of words) and a string, determine whether the string is an arbitrary concatenation of the words in the dictionary
import System.Environment
import Control.Applicative
import Data.Maybe
import Data.List
import qualified Data.Text as T
import qualified Data.Text.IO as I
import qualified Trie as T
getDictionaryConcatenation :: Ord a => [a] -> T.Trie a -> Maybe [[a]]
getDictionaryConcatenation [] t = Just []
getDictionaryConcatenation xs t
| null pairs = Nothing
| otherwise = (\(p, (Just ss)) -> Just (p : ss)) $ head pairs
where
prefixes = T.prefixesFor xs t
suffixes = map (fromJust . flip stripPrefix xs) prefixes
concats = map (flip getDictionaryConcatenation t) suffixes
pairs = sortBy (\(_, Just a) (_, Just b) -> length a `compare` length b) $
filter (isJust . snd) $ zip prefixes concats
loadDictionary :: IO (T.Trie Char)
loadDictionary = do
words <- T.lines <$> T.toLower <$> I.readFile "/usr/share/dict/words"
let dict = T.fromList $ map T.unpack words
putStrLn "loaded dictionary"
return dict
main = do
args <- getArgs
if length args /= 1
then putStrLn "you must give a string"
else do
dict <- loadDictionary
putStrLn $ show $ getDictionaryConcatenation (head args) dict
class Trie
Insertion = Struct.new(:pos, :str) do
def finished?
pos == str.length
end
def current_char
char_at(pos)
end
def char_at(index)
str.each_char.to_a[index]
end
def incr
obj = self.clone
obj.pos += 1
obj
end
end
def initialize
@nexts = Hash.new
@word = nil
end
def add(word)
ins = Insertion.new(0, word)
_add(ins)
end
def match_prefixes_for(str)
ins = Insertion.new(0, str)
_match_prefixes_for(ins).compact
end
protected
def _add(ins)
if ins.finished?
@word = ins.str
else
@nexts[ins.current_char] ||= Trie.new
@nexts[ins.current_char]._add(ins.incr)
end
end
def _match_prefixes_for(ins)
words = [@word]
if !ins.finished? && child = @nexts[ins.current_char]
words += child._match_prefixes_for(ins.incr)
end
words
end
end
def string_is_dict_combo(dict, str)
trie = Trie.new
dict.each { |word| trie.add(word) }
func = lambda do |str|
matched_words = trie.match_prefixes_for(str)
matched_words.each do |word|
if word == str # we finished with the input
return true
elsif word.length < str.length
result = func[str[word.length..-1]]
return true if result
end
end
return false
end
func[str]
end
puts string_is_dict_combo(["foo", "bar", "baro", "baz"], "bazbarobarfootbaz")
module Trie (
Trie,
empty,
fromList,
insert,
prefixesFor
) where
import Data.Maybe
import Data.List (foldr)
import qualified Data.Map as M
data Trie a = Trie (Maybe [a]) (M.Map a (Trie a))
| Leaf
deriving Show
-- create a new, empty Trie
empty :: Ord a => Trie a
empty = Trie Nothing M.empty
-- create a new Trie from a list
fromList :: Ord a => [[a]] -> Trie a
fromList xs = foldr (\x t -> insert x t) empty xs
-- insert a list into a Trie
insert :: Ord a => [a] -> Trie a -> Trie a
insert xs t = insert' xs xs t
insert' [] xs' (Trie _ m) = Trie (Just xs') m
insert' (x:xs) xs' (Trie s m) = Trie s m'
where
next = M.findWithDefault (Trie Nothing M.empty) x m
m' = M.insert x (insert' xs xs' next) m
-- return all the prefixes of the given list that are present in the Trie
prefixesFor :: Ord a => [a] -> Trie a -> [[a]]
prefixesFor xs t = map fromJust $ filter isJust $ prefixesFor' xs t
prefixesFor' _ Leaf = []
prefixesFor' [] (Trie s _) = [s]
prefixesFor' (x:xs) (Trie s m) = s : prefixesFor' xs (M.findWithDefault Leaf x m)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment