Word ladder

Yet another shortest path problem. Given two words of equal length the task is to transpose the first into the second.

Word ladder is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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>

1. include <fstream>
2. include <iostream>
3. include <map>
4. include <string>
5. 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

<lang rexx></lang> output

Swift

Translation of: Wren

<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

Translation of: Phix

Library: Wren-sort

Library: 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>

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.