45 lines
1.4 KiB
Text
45 lines
1.4 KiB
Text
program word_ladder;
|
|
dict := read_dictionary("unixdict.txt");
|
|
testpairs := [['boy', 'man'], ['girl', 'lady'], ['john', 'jane'], ['child', 'adult']];
|
|
|
|
loop for [fromWord, toWord] in testpairs do
|
|
l := ladder(dict, fromWord, toWord);
|
|
if l = om then
|
|
print(fromWord, '->', toWord, 'impossible');
|
|
else
|
|
print(fromWord, '->', toWord, l);
|
|
end if;
|
|
end loop;
|
|
|
|
proc ladder(dict, fromWord, toWord);
|
|
dict := {word : word in dict | #word = #fromWord};
|
|
ladders := [[fromWord]];
|
|
dict less:= fromWord;
|
|
loop while ladders /= [] do
|
|
l fromb ladders;
|
|
next := {word : word in onediff(dict, l(#l))};
|
|
dict -:= next;
|
|
nextls := [l + [word] : word in next];
|
|
if exists l in nextls | l(#l) = toWord then
|
|
return l;
|
|
end if;
|
|
ladders +:= nextls;
|
|
end loop;
|
|
return om;
|
|
end proc;
|
|
|
|
proc onediff(rw dict, word);
|
|
return {other : other in dict | #other = #word and diffs(word, other) = 1};
|
|
end proc;
|
|
|
|
proc diffs(word1, word2);
|
|
return +/[if word1(i) = word2(i) then 0 else 1 end : i in [1..#word1]];
|
|
end proc;
|
|
|
|
proc read_dictionary(file);
|
|
dictfile := open(file, 'r');
|
|
dict := {getline(dictfile) : until eof(dictfile)};
|
|
close(dictfile);
|
|
return dict;
|
|
end proc;
|
|
end program;
|