Anonymous user
Word ladder: Difference between revisions
→{{header|Nim}}
Line 201:
child to adult: [["This cannot be done."]]
</pre>
=={{header|Nim}}==
<lang Nim>import sets, strformat, strutils
func isOneAway(word1, word2: string): bool =
## Return true if "word1" and "word2" has only one letter of difference.
for i in 0..word1.high:
if word1[i] != word2[i]:
if result: return false # More than one letter of difference.
else: result = true # One letter of difference, for now.
var words: array[1..22, HashSet[string]] # Set of words sorted by length.
for word in "unixdict.txt".lines:
words[word.len].incl word
proc path(start, target: string): seq[string] =
## Return a path from "start" to "target" or an empty list
## if there is no possible path.
let lg = start.len
doAssert target.len == lg, "Source and destination must have same length."
doAssert start in words[lg], "Source must exist in the dictionary."
doAssert target in words[lg], "Destination must exist in the dictionary."
var currPaths = @[@[start]] # Current list of paths found.
var pool = words[lg] # List of possible words to use.
while true:
var newPaths: seq[seq[string]] # Next list of paths.
var added: HashSet[string] # Set of words added during the round.
for candidate in pool:
for path in currPaths:
if candidate.isOneAway(path[^1]):
let newPath = path & candidate
if candidate == target:
# Found a path.
return newPath
else:
# Not the target. Add a new path.
newPaths.add newPath
added.incl candidate
break
if newPaths.len == 0: break # No path.
currPaths = move(newPaths) # Update list of paths.
pool.excl added # Remove added words from pool.
when isMainModule:
for (start, target) in [("boy", "man"), ("girl", "lady"), ("john", "jane"),
("child", "adult"), ("cat", "dog"), ("lead", "gold"),
("white", "black"), ("bubble", "tickle")]:
let path = path(start, target)
if path.len == 0:
echo &"No path from “{start}” to “{target}”."
else:
echo path.join(" → ")</lang>
{{out}}
<pre>boy → bon → ban → man
girl → gill → gall → gale → gaze → laze → lazy → lady
john → cohn → conn → cone → cane → jane
No path from “child” to “adult”.
cat → cot → cog → dog
lead → load → goad → gold
white → whine → chine → chink → clink → clank → blank → black
bubble → babble → gabble → garble → gargle → gaggle → waggle → wangle → tangle → tingle → tinkle → tickle</pre>
=={{header|Phix}}==
| |||