A ladder graph models a word-ladder problem with valid words as vertices and permitted one-step transformations as edges. Finding a word ladder becomes finding a path through the graph, preferably the shortest one. section 5.1.1
Two paths from cat to dog
A longer path is cat → hat → heat → heal → held → dole → does → dogs → dog. A shorter path is cat → cats → tags → goat → got → dog. section 5.1.1
Build the graph incrementally:
- Read a dictionary, keep lowercase letters, and remove duplicate entries. section 5.4
- Generate candidate words by adding, removing, or modifying letters, then use dictionary permutations to find valid results. section 5.4
- Associate every dictionary word with its valid neighboring words and pass those nodes and edges to a graph builder. section 5.4
Figure 5.2 A ladder graph for a selection of English words
Use the graph illustration to inspect how words become connected through permitted transformations. section 5.1.1
Listing 5.10 An IO action that reads a dictionary from a file path
module Ladder
( Dictionary,
readDictionary,
)
where
import qualified Data.List as L
import qualified Graph as G
import qualified PermutationMap as PM
type Dictionary = [String]
readDictionary :: FilePath -> IO Dictionary
readDictionary filepath = do
dictionaryContent <- readFile filepath #1
let
lines = L.lines dictionaryContent #2
words = L.map (L.filter (`L.elem` ['a' .. 'z'])) lines #3
return (L.nub words) #4
Use the dictionary-reading listing to see the IO action that parses, filters, and deduplicates word entries. section 5.4
Listing 5.11 The function to build a ladder graph from a dictionary
mkLadderGraph :: Dictionary -> G.DiGraph String
mkLadderGraph dict = G.buildDiGraph nodes #1
where
map = PM.createPermutationMap dict #2
nodes =
L.map (\w -> (w, computeCandidates map w)) dict #3
Use the graph-building listing to see dictionary words paired with computed candidates before graph construction. section 5.4
