Anonymous user
Word ladder: Difference between revisions
→{{header|Haskell}}: added A* solution
SqrtNegInf (talk | contribs) m (→Idiomatic version: tidy) |
(→{{header|Haskell}}: added A* solution) |
||
Line 267:
child into adult cannot be done.
</pre>
=={{header|Haskell}}==
Uses solution of the task [[A*_search_algorithm#Haskell]].
<lang haskell>import System.IO (readFile)
import Data.List (intercalate, elemIndices)
import AStar (findPath, Graph(..))
import Data.Map (fromList)
distance :: String -> String -> Int
distance s1 s2 = length $ filter not $ zipWith (==) s1 s2
wordLadder :: [String] -> String -> String -> [String]
wordLadder dict start end = findPath g distance start end
where
short_dict = filter ((length start ==) . length) dict
g = Graph $ \w -> fromList [ (x, 1)
| x <- short_dict
, distance w x == 1 ]
showChain [] = putStrLn "No chain"
showChain ch = putStrLn $ intercalate " -> " ch
main = do
dict <- lines <$> readFile "unixdict.txt"
showChain $ wordLadder dict "boy" "man"
showChain $ wordLadder dict "girl" "lady"
showChain $ wordLadder dict "john" "jane"
showChain $ wordLadder dict "alien" "drool"
showChain $ wordLadder dict "child" "adult"</lang>
<pre>*Main> main
boy -> bay -> ban -> man
girl -> gird -> bird -> bard -> lard -> lark -> lack -> lacy -> lady
john -> cohn -> conn -> cone -> cane -> jane
alien -> alden -> alder -> alter -> aster -> ester -> eater -> bater -> bator -> baton -> baron -> boron -> moron -> moran -> moral -> morel -> monel -> money -> monty -> month -> mouth -> south -> sooth -> sloth -> slosh -> slash -> flash -> flask -> flank -> blank -> bland -> blend -> bleed -> breed -> bread -> tread -> triad -> trial -> trill -> drill -> droll -> drool
No chain</pre>
Works much faster when compiled.
=={{header|Java}}==
| |||