Word ladder

Word ladder
You are encouraged to solve this task according to the task description, using any language you may know.

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.

Other tasks related to string operations:

Metrics

• Array length
• String length
• Copy a string
• Empty string  (assignment)

Counting

• Word frequency
• Letter frequency
• Jewels and stones
• I before E except after C
• Bioinformatics/base count
• Count occurrences of a substring
• Count how many vowels and consonants occur in a string

Remove/replace

• XXXX redacted
• Conjugate a Latin verb
• Remove vowels from a string
• String interpolation (included)
• Strip block comments
• Strip comments from a string
• Strip a set of characters from a string
• Strip whitespace from a string -- top and tail
• Strip control codes and extended characters from a string

Anagrams/Derangements/shuffling

• Word wheel
• ABC problem
• Sattolo cycle
• Knuth shuffle
• Ordered words
• Superpermutation minimisation
• Textonyms (using a phone text pad)
• Anagrams
• Anagrams/Deranged anagrams
• Permutations/Derangements

Find/Search/Determine

• ABC words
• Odd words
• Word ladder
• Semordnilap
• Word search
• Wordiff  (game)
• String matching
• Tea cup rim text
• Alternade words
• Changeable words
• State name puzzle
• String comparison
• Unique characters
• Unique characters in each string
• Extract file extension
• Levenshtein distance
• Palindrome detection
• Common list elements
• Longest common suffix
• Longest common prefix
• Compare a list of strings
• Longest common substring
• Find common directory path
• Words from neighbour ones
• Change e letters to i in words
• Non-continuous subsequences
• Longest common subsequence
• Longest palindromic substrings
• Longest increasing subsequence
• Words containing "the" substring
• Sum of the digits of n is substring of n
• Determine if a string is numeric
• Determine if a string is collapsible
• Determine if a string is squeezable
• Determine if a string has all unique characters
• Determine if a string has all the same characters
• Longest substrings without repeating characters
• Find words which contains all the vowels
• Find words which contains most consonants
• Find words which contains more than 3 vowels
• Find words which first and last three letters are equals
• Find words which odd letters are consonants and even letters are vowels or vice_versa

Formatting

• Substring
• Rep-string
• Word wrap
• String case
• Align columns
• Literals/String
• Repeat a string
• Brace expansion
• Brace expansion using ranges
• Reverse a string
• Phrase reversals
• Comma quibbling
• Special characters
• String concatenation
• Substring/Top and tail
• Commatizing numbers
• Reverse words in a string
• Suffixation of decimal numbers
• Long literals, with continuations
• Numerical and alphabetical suffixes
• Abbreviations, easy
• Abbreviations, simple
• Abbreviations, automatic

Song lyrics/poems/Mad Libs/phrases

• Mad Libs
• Magic 8-ball
• 99 Bottles of Beer
• The Name Game (a song)
• The Old lady swallowed a fly
• The Twelve Days of Christmas

Tokenize

• Text between
• Tokenize a string
• Word break problem
• Tokenize a string with escaping
• Split a character string based on change of character

Sequences

• Show ASCII table
• De Bruijn sequences
• Self-referential sequences
• Generate lower case ASCII alphabet

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 let fG n g=n|>List.partition(fun n->2>Seq.fold2(fun z n g->z+if n=g then 0 else 1) 0 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.

To treat the dictionary and input words as caseless,   all words are translated to lowercase.

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 msg , "target word isn't the same length as the base word" call letters /*assign letters, faster than SUBSTR. */

1. = 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;         @.x= 1                /*bump # words with length L; semaphore*/
        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 m;    call look;  if result\==  then leave      /*Found?  Quit.*/
          end   /*f*/

say if f>m then call msg 'no word ladder solution possible for ' base " ──► " targ

              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*/

call show words(rung) exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ msg: say; if arg()==2 then say '***error*** ' arg(2); else say arg(1); say; exit 13 show: say 'a solution: ' base; do j=1 to arg(1); say left(,12) word(rung,j); end; return letters: do m=1 for length(abc); a.m= substr(abc, m, 1); end; return /*──────────────────────────────────────────────────────────────────────────────────────*/ look: procedure expose @. !. a. $ abc base L rung targ search; rungs= word(rung, 1)

     $$=;                                                            rung#= 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 & rung#>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:  4
──────────────────────────────  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:  4
──────────────────────────────  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:  5
──────────────────────────────  base  word is:  child
────────────────────────────── target word is:  adult

no word ladder solution possible for  child  ──►  adult

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.