Skip to content

Instantly share code, notes, and snippets.

@kberridge
Created June 10, 2012 01:03
Show Gist options
  • Save kberridge/2903340 to your computer and use it in GitHub Desktop.
Save kberridge/2903340 to your computer and use it in GitHub Desktop.
F# solution to the word ladder problem
let words = System.IO.File.ReadAllLines("four-char-dictionary.txt")
let isWordInDict word =
words |> Seq.exists (fun w -> w = word)
let filterToDict words =
words |> List.filter isWordInDict
let filterNotSeen (seen : Set<string>) words =
words |> List.filter (fun w -> not(seen.Contains(w)))
let findChildren (word : string) = [
let generateCandidates prefix char postfix =
['a'..'z'] |> List.filter (fun i -> i <> char)
|> List.map (fun l -> prefix + l.ToString() + postfix)
yield! generateCandidates "" (word.[0]) (word.[1..])
for i in 1..3 do
yield! generateCandidates (word.[0..(i-1)]) (word.[i]) (word.[(i+1)..])
]
let findValidUniqueChildren seen = findChildren >> filterNotSeen seen >> filterToDict
type node = string List * string // parent List * word
let rec buildNodes (words : string List) (parents : string List) (nodes : node List) =
match words with
| [] -> nodes
| w :: tail -> buildNodes tail parents ((parents, w) :: nodes)
let rec findLadderWorker (searchNodes : node List) (endword : string) (seen : Set<string>) =
let queuechildren word parents searchNodes =
let children = findValidUniqueChildren seen word
let newparents = word :: parents
let childnodes = buildNodes children newparents []
let newSearchNodes = searchNodes @ childnodes
findLadderWorker newSearchNodes endword (seen + (Set.ofList children))
let testnode (node : node) (searchNodes : node List) =
match node with
| parents, word when word = endword -> word :: parents |> List.rev
| parents, word -> queuechildren word parents searchNodes
match searchNodes with
| [] -> []
| node :: others -> testnode node others
let findLadder startword endword =
if startword = endword then
[endword]
else
let children = findValidUniqueChildren Set.empty startword
let seen = Set.ofList (startword :: children)
let startNodes = buildNodes children [startword] []
findLadderWorker startNodes endword seen
let args = System.Environment.GetCommandLineArgs()
if args.Length < 3 then // 3 is a hack to support both fsi and fsc
printfn "You forgot to include start and end word arguments"
else
let startword = args.[(args.Length - 2)]
let endword = args.[(args.Length - 1)]
let ladder = findLadder startword endword
printfn "%A" ladder
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment