Word ladder: Difference between revisions
m (→{{header|Phix}}: added a comment about an initial filter.) |
(Added Wren) |
||
Line 73: | Line 73: | ||
john->cohn->conn->cone->cane->jane |
john->cohn->conn->cone->cane->jane |
||
child into adult cannot be done |
child into adult cannot be done |
||
</pre> |
|||
=={{header|Wren}}== |
|||
{{trans|Phix}} |
|||
{{libheader|Wren-sort}} |
|||
{{libheader|Wren-seq}} |
|||
<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> |
|||
{{out}} |
|||
<pre> |
|||
boy -> bay -> ban -> man |
|||
girl -> gill -> gall -> gale -> gaze -> laze -> lazy -> lady |
|||
john -> cohn -> conn -> cone -> cane -> jane |
|||
child into adult cannot be done. |
|||
</pre> |
</pre> |
Revision as of 19:11, 5 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
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
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.