Word ladder: Difference between revisions
julia example |
m →{{header|Julia}}: allow multiple solutions |
||
Line 38: | Line 38: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
<lang julia>dict = Dict(word => length(word) for word in split(read("unixdict.txt", String), r"\s+")) |
<lang julia>const dict = Dict(word => length(word) for word in split(read("unixdict.txt", String), r"\s+")) |
||
function targeted_mutations(s::AbstractString, target::AbstractString) |
function targeted_mutations(s::AbstractString, target::AbstractString) |
||
Line 51: | Line 51: | ||
push!(newworking, [arr; w]) |
push!(newworking, [arr; w]) |
||
end |
end |
||
⚫ | |||
end |
end |
||
end |
end |
||
isempty(newworking) && return [["This cannot be done."]] |
isempty(newworking) && return [["This cannot be done."]] |
||
for arr in newworking |
|||
⚫ | |||
end |
|||
working = newworking |
working = newworking |
||
end |
end |
||
Line 66: | Line 68: | ||
</lang>{{out}} |
</lang>{{out}} |
||
<pre> |
<pre> |
||
boy to man: [["boy", "bay", "may", "man"]] |
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"]] |
girl to lady: [["girl", "gill", "gall", "gale", "gaze", "laze", "lazy", "lady"]] |
||
john to jane: [["john", "cohn", "conn", "cone", "cane", "jane"]] |
john to jane: [["john", "cohn", "conn", "cone", "cane", "jane"]] |
Revision as of 04:31, 6 June 2021
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 = Dict(word => length(word) for word in split(read("unixdict.txt", String), r"\s+"))
function targeted_mutations(s::AbstractString, target::AbstractString)
working, tried = s, Set{String}() while all(a -> a[end] != target, working) newworking = Vector{Vector{String}}() for arr in working s = arr[end] for j in 1:length(s), c in 'a':'z' w = s[1:j-1] * c * s[j+1:end] if haskey(dict, w) && w != s && !(w in tried) push!(newworking, [arr; w]) end end end isempty(newworking) && return "This cannot be done." for arr in newworking push!(tried, arr[end]) end 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.