3 ms·
I think the problem is inherently pretty difficult. Also extremely ambiguous. Here's a solution I put together in Haskell: encode :: Char -> [Bool] enc
by oisdk 7y ago
I think the problem is inherently pretty difficult. Also extremely ambiguous. Here's a solution I put together in Haskell:
encode :: Char -> [Bool]
encode 'a' = [False, True]
...
encode 'z' = [True , True , False, False]
data Trie a
= Trie
{ payload :: Maybe a
, false :: Trie a
, true :: Trie a
}
insert :: [Bool] -> a -> Trie a -> Trie a
insert xs v = foldr f b xs
where
b t = t {payload = Just v}
f False k (Trie e f t) = Trie e (k f) t
f True k (Trie e f t) = Trie e f (k t)
table :: Trie Char
table = foldr (uncurry insert) (fix (\t -> Trie Nothing t t)) [ (encode c, c) | c <- ['a'..'z'] ]
newtype Parser a b = Parser { runParser :: [a] -> [(b, [a])] } deriving Functor
instance Applicative (Parser a) where
pure x = Parser (\xs -> [(x,xs)])
(<*>) = ap
instance Monad (Parser a) where
xs >>= f = Parser \s -> do
(x,s') <- runParser xs s
runParser (f x) s'
instance Alternative (Parser a) where
empty = Parser (const [])
xs <|> ys = Parser (\s -> runParser xs s ++ runParser ys s)
instance MonadPlus (Parser a) where
eoi = Parser \case
[] -> [((),[])]
_ -> []
char = Parser \case
(x:xs) -> [(x,xs)]
[] -> []
morse :: Parser Bool String
morse = go table
where
go t = (go . bool (false t) (true t) =<< char)
<|> msum (fmap (\x -> fmap (x:) (go table <|> [] <$ eoi)) (payload t))
decode :: [Bool] -> [String]
decode = map fst . runParser morse
The output is pretty much unusable, though. For the string "me", for instance, there are 4 possible parses:
["g","me","tn","tte"]
For the string "hello", there are 19796.