Word ladder

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.

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>

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

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.