Word ladder: Difference between revisions

{{trans|Nim}}

 

V result = 0B

L(i) 0 .< word1.len

print(‘No path from "’start‘" to "’target‘".’)

E

 

{{out}}

=={{header|ALGOL 68}}==

With ''a68g'' use option <code>--storage 2</code>, otherwise it runs out of memory.

real program starts after it.

#

print(newline)

FI

{{out}}

<pre>boy->bay->ban->man

=={{header|C++}}==

This borrows heavily from [[#Wren|Wren]] and a bit from [[#Raku|Raku]].

#include <fstream>

#include <iostream>

word_ladder(words, "bubble", "tickle");

return EXIT_SUCCESS;

 

{{out}}

 

=={{header|F_Sharp|F#}}==

// 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 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"))

{{out}}

<pre>

The bad news is evil can not be turned into good, but the good news is god can become man.

 

[("evil","good");("god","man")]|>List.iter(fun(n,g)->printfn "%s" (match wL n g with Some n->n|>String.concat " -> " |_->n+" into "+g+" can't be done"))

{{out}}

<pre>

=={{header|Go}}==

{{trans|Wren}}

 

import (

wordLadder(words, pair[0], pair[1])

}

 

{{out}}

The function first expands a ball around the starting word in the space of possible words, until the ball surface touches the goal (if ever). After that it performs depth-first path-finding from the goal back to the center.

 

import Control.Monad (foldM)

import Data.List (intercalate)

showChain $ wordLadder dict "john" "jane"

showChain $ wordLadder dict "alien" "drool"

 

<pre>λ> lines <$> readFile "unixdict.txt" >>= print . wordLadders "boy" "man"

Performs searching from both ends. This solution is much faster for cases with no chains, and for for short chains. In case of long chains looses its' efficiency.

 

wordLadders2 start end dict

| length start /= length end = []

where g (b, r) a = (\x -> (x, x:r)) <$> f b a

 

 

===Using A*-search===

See [[A*_search_algorithm#Haskell]]

 

import qualified Data.Map as M

 

g = Graph $ \w -> M.fromList [ (x, 1)

| x <- short_dict

 

<pre>λ> main

Here we use a double ended breadth first search (starting from each end). This tends to give us several options where they meet in the middle, so we pick a shortest example from those.

 

j=. {:y

l=. <:{:$m

end.

}.,' ',.r{words

 

boy bay ban man

'girl' wlad 'lady'

white whine chine chink clink blink blank black

'bubble' wlad 'tickle'

 

 

=={{header|Java}}==

import java.nio.file.Files;

import java.nio.file.Path;

wordLadder(words, "bubble", "tickle", 12);

}

{{out}}

<pre>boy -> bay -> may -> man

===Faster alternative===

{{trans|C++}}

import java.util.*;

 

System.out.printf("%s into %s cannot be done.\n", from, to);

}

 

{{out}}

{{works with|jq}}

'''Works with gojq, the Go implementation of jq'''

 

def words: [inputs]; # one way to read the word list

words

| pairs as $p

 

{{out}}

 

=={{header|Julia}}==

 

function targeted_mutations(str::AbstractString, target::AbstractString)

println("john to jane: ", targeted_mutations("john", "jane"))

println("child to adult: ", targeted_mutations("child", "adult"))

<pre>

boy to man: [["boy", "bay", "may", "man"], ["boy", "bay", "ban", "man"], ["boy", "bon", "ban", "man"]]

=={{header|Mathematica}} / {{header|Wolfram Language}}==

{{incorrect|Mathmatica|The requirement is to find the shortest path other examples do John to Jane with 4 intermediate words. Also an impossible example is required: child to adult.}}

sel=Select[Subsets[db,{2}],HammingDistance[#[[1]],#[[2]]]==1&];

g=Graph[db,UndirectedEdge@@@sel];

sel=Select[Subsets[db,{2}],HammingDistance[#[[1]],#[[2]]]==1&];

g=Graph[db,UndirectedEdge@@@sel];

{{out}}

<pre>{"boy", "bay", "ban", "man"}

 

=={{header|Nim}}==

 

 

echo &"No path from “{start}” to “{target}”."

else:

 

{{out}}

===Direct translation===

{{trans|C++}}

use warnings;

 

word_ladder('lead', 'gold');

word_ladder('white', 'black');

{{out}}

<pre>boy -> bay -> ban -> man

===Idiomatic version===

<b>Exactly</b> the same algorithm, written in a more Perl-ish style. Is this better, or worse? Maybe both. Interestingly, runs 1/3-rd faster.

use warnings;

use feature 'say';

}

 

Same style output.

 

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #004080;">sequence</span> <span style="color: #000000;">words</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">unix_dict</span><span style="color: #0000FF;">()</span>

<span style="color: #000000;">word_ladder</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"john"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"jane"</span><span style="color: #0000FF;">)</span>

<span style="color: #000000;">word_ladder</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"child"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"adult"</span><span style="color: #0000FF;">)</span>

<small>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.</small>

{{out}}

=={{header|Python}}==

The function ''cache'' is not part of the algorithm but avoid re-download and map re-computing at each re-run.

 

def h ( str,x=9 ):

 

for w in ('boy man','girl lady','john jane','alien drool','child adult'):

 

{{out}}

=={{header|Racket}}==

 

 

(define *unixdict* (delay (with-input-from-file "../../data/unixdict.txt"

(Word-ladder "john" "jane")

(Word-ladder "alien" "drool")

 

{{out}}

 

=={{header|Raku}}==

.classify(*.chars)

.map({ .key => .value.Set });

say word_ladder($from, $to)

// "$from into $to cannot be done";

{{out}}

<pre>

Programming note: &nbsp; &nbsp; this REXX program uses the &nbsp; '''lower''' &nbsp; BIF &nbsp; which Regina has).

<br>If your REXX doesn't support that BIF, &nbsp; here is an equivalent function:

parse arg base targ iFID . /*obtain optional arguments from the CL*/

if base=='' | base=="," then base= 'boy' /*Not specified? Then use the default.*/

end /*k*/

end /*i*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

=={{header|Ruby}}==

{{trans|Raku}}

 

Words = File.open("unixdict.txt").read.split("\n").

puts "#{from} into #{to} cannot be done"

end

 

{{Out}}

=={{header|Swift}}==

{{trans|Wren}}

 

func oneAway(string1: [Character], string2: [Character]) -> Bool {

} catch {

print(error.localizedDescription)

 

{{out}}

{{trans|Phix}}

{{libheader|Wren-sort}}

import "/sort" for Find

 

["child", "adult"]

]

 

{{out}}