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.

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

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.