Word ladder
Yet another shortest path problem. Given two words of equal length the task is to transpose the first into the second.
Only one letter may be changed at a time and the change must result in a word in unixdict, the minimum number of intermediate words should be used.
Demonstrate the following:
A boy can be made into a man: boy -> bay -> ban -> man
With a little more difficulty a girl can be made into a lady: girl -> gill -> gall -> gale -> gaze -> laze -> lazy -> lady
For the wokes, john can be made into jane: john -> cohn -> conn -> cone -> cane -> jane
A child can not be turned into an adult.
Optional transpositions of your choice.
F#
<lang fsharp> // Word ladder: Nigel Galloway. June 5th., 2021 open System.Text.RegularExpressions let fN g=List.init(String.length g)(fun n->let g=g.ToCharArray() in g.[n]<-'.'; g|>System.String)|>String.concat "|" let fG n g=let g=fN g in n|>List.partition(fun n->Regex.IsMatch(n,g)) let wL n g=let dict=seq{use n=System.IO.File.OpenText("unixdict.txt") in while not n.EndOfStream do yield n.ReadLine()}|>Seq.filter(Seq.length>>(=)(Seq.length n))|>List.ofSeq|>List.except [n]
let (|Done|_|) n=n|>List.tryFind((=)g)
let rec wL n g l=match n with h::t->let i,e=fG l (List.head h) in match i with Done i->Some((i::h)|>List.rev) |_->wL t ((i|>List.map(fun i->i::h))@g) e
|_->match g with []->None |_->wL g [] l
let i,e=fG dict n in match i with Done i->Some([n;g]) |_->wL(i|>List.map(fun g->[g;n])) [] e
[("boy","man");("girl","lady");("john","jane");("child","adult")]|>List.iter(fun(n,g)->printfn "%s" (match wL n g with Some n->n|>String.concat " -> " |_->n+" into "+g+" can't be done")) </lang>
- Output:
boy -> bay -> ban -> man girl -> gill -> gall -> gale -> gaze -> laze -> lazy -> lady john -> cohn -> conn -> cone -> cane -> jane child into adult can't be done
Julia
<lang julia>const dict = Set(split(read("unixdict.txt", String), r"\s+"))
function targeted_mutations(str::AbstractString, target::AbstractString)
working, tried = str, Set{String}() while all(a -> a[end] != target, working) newworking = Vector{Vector{String}}() for arr in working s = arr[end] push!(tried, s) for j in 1:length(s), c in 'a':'z' w = s[1:j-1] * c * s[j+1:end] if w in dict && !(w in tried) push!(newworking, [arr; w]) end end end isempty(newworking) && return "This cannot be done." working = newworking end return filter(a -> a[end] == target, working)
end
println("boy to man: ", targeted_mutations("boy", "man")) println("girl to lady: ", targeted_mutations("girl", "lady")) println("john to jane: ", targeted_mutations("john", "jane")) println("child to adult: ", targeted_mutations("child", "adult"))
</lang>
- Output:
boy to man: [["boy", "bay", "may", "man"], ["boy", "bay", "ban", "man"], ["boy", "bon", "ban", "man"]] girl to lady: [["girl", "gill", "gall", "gale", "gaze", "laze", "lazy", "lady"]] john to jane: [["john", "cohn", "conn", "cone", "cane", "jane"]] child to adult: [["This cannot be done."]]
Phix
sequence words = get_text("demo/unixdict.txt",GT_LF_STRIPPED) function right_length(string word, integer l) return length(word)=l end function function one_away(string a, b) return sum(sq_ne(a,b))=1 end function procedure word_ladder(string a, b) sequence poss = filter(words,right_length,length(a)), todo = {{a}}, curr -- aka todo[1], word chain starting from a while length(todo) do {curr,todo} = {todo[1],todo[2..$]} sequence next = filter(poss,one_away,curr[$]) if find(b,next) then printf(1,"%s\n",{join(append(curr,b),"->")}) return end if poss = filter(poss,"out",next) todo &= apply(true,append,{{curr},next}) end while printf(1,"%s into %s cannot be done\n",{a,b}) end procedure word_ladder("boy","man") word_ladder("girl","lady") word_ladder("john","jane") word_ladder("child","adult")
Aside: an initial poss = filter(poss,"out",{a}) might be prudent, but would only prevent a single next:={} step, at about the same cost as the initial filter anyway.
- Output:
boy->bay->ban->man girl->gill->gall->gale->gaze->laze->lazy->lady john->cohn->conn->cone->cane->jane child into adult cannot be done
Raku
<lang perl6>constant %dict = 'unixdict.txt'.IO.lines
.classify(*.chars)
.map({ .key => .value.Set });
sub word_ladder ( Str $from, Str $to ) {
die if $from.chars != $to.chars;
my $sized_dict = %dict{$from.chars};
my @workqueue = (($from,),);
my $used = ($from => True).SetHash;
while @workqueue {
my @new_q;
for @workqueue -> @words {
my $last_word = @words.tail;
my @new_tails = gather for 'a' .. 'z' -> $replacement_letter {
for ^$last_word.chars -> $i {
my $new_word = $last_word;
$new_word.substr-rw($i, 1) = $replacement_letter;
next unless $new_word ∈ $sized_dict
and not $new_word ∈ $used;
take $new_word;
$used{$new_word} = True;
return |@words, $new_word if $new_word eq $to;
}
}
push @new_q, ( |@words, $_ ) for @new_tails;
}
@workqueue = @new_q;
}
} for <boy man>, <girl lady>, <john jane>, <child adult> -> ($from, $to) {
say word_ladder($from, $to)
// "$from into $to cannot be done";
}</lang>
- Output:
(boy bay may man) (girl gill gall gale gaze laze lazy lady) (john cohn conn cone cane jane) child into adult cannot be done
Wren
<lang ecmascript>import "io" for File import "/sort" for Find import "/seq" for Lst
var words = File.read("unixdict.txt").trim().split("\n")
var oneAway = Fn.new { |a, b|
var sum = 0 for (i in 0...a.count) if (a[i] != b[i]) sum = sum + 1 return sum == 1
}
var wordLadder = Fn.new { |a, b|
var l = a.count
var poss = words.where { |w| w.count == l }.toList
var todo = a
while (todo.count > 0) {
var curr = todo[0]
todo = todo[1..-1]
var next = poss.where { |w| oneAway.call(w, curr[-1]) }.toList
if (Find.first(next, b) != -1) {
curr.add(b)
System.print(Lst.flatten(curr).join(" -> "))
return
}
poss = poss.where { |p| !next.contains(p) }.toList
for (i in 0...next.count) {
var temp = [curr]
temp.add(next[i])
todo.add(temp)
}
}
System.print("%(a) into %(b) cannot be done.")
}
var pairs = [
["boy", "man"], ["girl", "lady"], ["john", "jane"], ["child", "adult"]
] for (pair in pairs) wordLadder.call(pair[0], pair[1])</lang>
- Output:
boy -> bay -> ban -> man girl -> gill -> gall -> gale -> gaze -> laze -> lazy -> lady john -> cohn -> conn -> cone -> cane -> jane child into adult cannot be done.