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.
C++
This borrows heavily from Wren and a bit from Raku. <lang cpp>#include <algorithm>
- include <fstream>
- include <iostream>
- include <map>
- include <string>
- include <vector>
using word_map = std::map<size_t, std::vector<std::string>>;
// Returns true if strings s1 and s2 differ by one character. bool one_away(const std::string& s1, const std::string& s2) {
if (s1.size() != s2.size()) return false; int sum = 0; for (size_t i = 0, n = s1.size(); i != n; ++i) { if (s1[i] != s2[i]) { if (++sum > 1) return false; } } return sum == 1;
}
// Join a sequence of strings into a single string using the given separator. template <typename iterator_type, typename separator_type> std::string join(iterator_type begin, iterator_type end,
separator_type separator) { std::string result; if (begin != end) { result += *begin++; for (; begin != end; ++begin) { result += separator; result += *begin; } } return result;
}
// Return true if v contains e. template <typename vector_type, typename element_type> bool contains(const vector_type& v, const element_type& e) {
return std::find(v.begin(), v.end(), e) != v.end();
}
// If possible, print the shortest chain of single-character modifications that // leads from "from" to "to", with each intermediate step being a valid word. // This is an application of breadth-first search. bool word_ladder(const word_map& words, const std::string& from,
const std::string& to) { auto w = words.find(from.size()); if (w != words.end()) { auto poss = w->second; std::vector<std::vector<std::string>> queueTemplate:From; while (!queue.empty()) { auto curr = queue.front(); queue.erase(queue.begin()); std::vector<std::string> next; for (const std::string& str : poss) { if (one_away(str, curr.back())) next.push_back(str); } if (contains(next, to)) { curr.push_back(to); std::cout << join(curr.begin(), curr.end(), " -> ") << '\n'; return true; } poss.erase(std::remove_if(poss.begin(), poss.end(), [&next](const std::string& str) { return contains(next, str); }), poss.end()); for (const auto& str : next) { std::vector<std::string> temp(curr); temp.push_back(str); queue.push_back(std::move(temp)); } } } std::cout << from << " into " << to << " cannot be done.\n"; return false;
}
int main() {
word_map words; std::ifstream in("unixdict.txt"); if (!in) { std::cerr << "Cannot open file unixdict.txt.\n"; return EXIT_FAILURE; } std::string word; while (getline(in, word)) words[word.size()].push_back(word); word_ladder(words, "boy", "man"); word_ladder(words, "girl", "lady"); word_ladder(words, "john", "jane"); word_ladder(words, "child", "adult"); word_ladder(words, "cat", "dog"); word_ladder(words, "lead", "gold"); word_ladder(words, "white", "black"); word_ladder(words, "bubble", "tickle"); return EXIT_SUCCESS;
}</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. cat -> cot -> cog -> dog lead -> load -> goad -> gold white -> whine -> chine -> chink -> clink -> blink -> blank -> black bubble -> babble -> gabble -> garble -> gargle -> gaggle -> giggle -> jiggle -> jingle -> tingle -> tinkle -> tickle
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
REXX
This REXX entry does a little more error checking.
It also assumes that the dictionary file is in mixed case as well as the words entered on the CL.
Programming note: this REXX program uses the lower BIF which Regina has).
If your REXX doesn't support that BIF, here is an equivalent function:
<lang rexx>lower: procedure; parse arg a; @= 'abcdefghijklmnopqrstuvwxyz'; @u= @; upper @u
return translate(a, @, @u)</lang>
<lang rexx>/*REXX program finds words (within an identified dict.) to solve a word ladder puzzle.*/ parse arg base targ iFID . /*obtain optional arguments from the CL*/ if base== | base=="," then base= 'boy' /*Not specified? Then use the default.*/ if targ== | targ=="," then targ= 'man' /* " " " " " " */ if iFID== | iFID=="," then iFID='unixdict.txt' /* " " " " " " */ abc= 'abcdefghijklmnopqrstuvwxyz' /*the lowercase (Latin) alphabet. */ abcU= abc; upper abcU /* " uppercase " " */ base= lower(base); targ= lower(targ) /*lowercase the BASE and also the TARG.*/
L= length(base) /*length of the BASE (in characters). */
if L<2 then call err 'base word is too small or missing' /*oops, too small*/ if length(targ)\==L then call err "target word isn't the same length as the base word" call letters /*assign letters, faster than SUBSTR. */
- = 0 /*# of words whose length matches BASE.*/
@.= /*default value of any dictionary word.*/
do recs=0 while lines(iFID)\==0 /*read each word in the file (word=X).*/ x= lower(strip( linein( iFID) ) ) /*pick off a word from the input line. */ if length(x)\==L then iterate /*Word not correct length? Then skip. */ #= # + 1 /*bump number of words with length L. */ @.x= 1 /*store the word in a semaphore array. */ end /*recs*/ /* [↑] semaphore name is uppercased. */
!.= 0 say copies('─', 30) recs "words in the dictionary file: " iFID say copies('─', 30) # "words in the dictionary file of length: " L say copies('─', 30) ' base word is: ' base say copies('─', 30) 'target word is: ' targ rung= targ $= base
do f=1 for abcs; call look; if result\== then leave /*Found? Quit.*/ end /*f*/
say if f>abcs then do; say 'no word ladder solution possible for ' base " ──► " targ; exit 13
end
do f-2; $= base; !.= 0 /*process all the rungs that were found*/ do forever; call look; if result\== then leave /*Found? Quit.*/ end /*forever*/ end /*f-2*/
_= words(rung) call show exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ err: say; say '***error***' arg(1); say; exit 13 show: say 'a solution: ' base; do j=1 for _; say left(, 12) word(rung, j); end; return letters: do abcs=1 for length(abc); a.abcs= substr(abc, abcs, 1); end; return /*──────────────────────────────────────────────────────────────────────────────────────*/ look: procedure expose @. !. a. $ abc rung base L targ search; rungs= word(rung, 1)
$$=; rungw= words(rungs) do i=1 for words($); y= word($, i); !.y= 1 do k=1 for L do n=1 for 26; z= overlay(a.n, y, k) /*change a letter*/ if @.z== then iterate /*Is this not a word? Then skip it. */ if !.z then iterate /* " " a repeat? " " " */ if z==rungs then rung= y rung /*prepend a word to the rung list. */ if z==rungs & rungw>1 then return z /*short─circuit. */ if z==targ then return z $$= $$ z /*append a possible ladder word to $$*/ end /*n*/ end /*k*/ end /*i*/ $= $$; return </lang>
- output when using the default inputs:
────────────────────────────── 25104 words in the dictionary file: unixdict.txt ────────────────────────────── 796 words in the dictionary file of length: 3 ────────────────────────────── base word is: boy ────────────────────────────── target word is: man a solution: boy bay may man
- output when using the inputs of: girl lady
────────────────────────────── 25104 words in the dictionary file: unixdict.txt ────────────────────────────── 2187 words in the dictionary file of length: 3 ────────────────────────────── base word is: girl ────────────────────────────── target word is: lady a solution: girl gill gall gale gaze laze lazy lady
- output when using the inputs of: john jane
────────────────────────────── 25104 words in the dictionary file: unixdict.txt ────────────────────────────── 2187 words in the dictionary file of length: 3 ────────────────────────────── base word is: john ────────────────────────────── target word is: jane a solution: john cohn conn cone cane jane
- output when using the inputs of: child adult
────────────────────────────── 25104 words in the dictionary file: unixdict.txt ────────────────────────────── 3161 words in the dictionary file of length: 3 ────────────────────────────── base word is: child ────────────────────────────── target word is: adult no word ladder solution possible for child ──► adult
Swift
<lang swift>import Foundation
func oneAway(string1: String, string2: String) -> Bool {
if string1.count != string2.count { return false } var sum = 0 for (c1, c2) in zip(string1, string2) { if c1 != c2 { sum += 1 if sum > 1 { return false } } } return sum == 1
}
func wordLadder(words: [String], from: String, to: String) {
var poss = words.filter{$0.count == from.count} var queue: String = from while !queue.isEmpty { var curr = queue[0] let last = curr[curr.count - 1] queue.removeFirst() let next = poss.filter{oneAway(string1: $0, string2: last)} if next.contains(to) { curr.append(to) print(curr.joined(separator: " -> ")) return } poss.removeAll(where: {next.contains($0)}) for str in next { var temp = curr temp.append(str) queue.append(temp) } } print("\(from) into \(to) cannot be done.")
}
do {
let words = try String(contentsOfFile: "unixdict.txt", encoding: String.Encoding.ascii) .components(separatedBy: "\n") .filter{!$0.isEmpty} wordLadder(words: words, from: "man", to: "boy") wordLadder(words: words, from: "girl", to: "lady") wordLadder(words: words, from: "john", to: "jane") wordLadder(words: words, from: "child", to: "adult")
} catch {
print(error.localizedDescription)
}</lang>
- Output:
man -> ban -> bay -> boy 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.