Word ladder: Difference between revisions
m
→{{header|Wren}}: Minor tidy
(+algol68) |
m (→{{header|Wren}}: Minor tidy) |
||
(2 intermediate revisions by 2 users not shown) | |||
Line 23:
{{trans|Nim}}
<
V result = 0B
L(i) 0 .< word1.len
Line 74:
print(‘No path from "’start‘" to "’target‘".’)
E
print(path.join(‘ -> ’))</
{{out}}
Line 90:
=={{header|ALGOL 68}}==
With ''a68g'' use option <code>--storage 2</code>, otherwise it runs out of memory.
<
real program starts after it.
#
Line 268:
print(newline)
FI
OD</
{{out}}
<pre>boy->bay->ban->man
Line 292:
=={{header|C++}}==
This borrows heavily from [[#Wren|Wren]] and a bit from [[#Raku|Raku]].
<
#include <fstream>
#include <iostream>
Line 383:
word_ladder(words, "bubble", "tickle");
return EXIT_SUCCESS;
}</
{{out}}
Line 398:
=={{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)
Line 407:
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"))
</syntaxhighlight>
{{out}}
<pre>
Line 418:
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"))
</syntaxhighlight>
{{out}}
<pre>
Line 429:
=={{header|Go}}==
{{trans|Wren}}
<
import (
Line 517:
wordLadder(words, pair[0], pair[1])
}
}</
{{out}}
Line 531:
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)
Line 577:
showChain $ wordLadder dict "john" "jane"
showChain $ wordLadder dict "alien" "drool"
showChain $ wordLadder dict "child" "adult"</
<pre>λ> lines <$> readFile "unixdict.txt" >>= print . wordLadders "boy" "man"
Line 598:
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 = []
Line 629:
where g (b, r) a = (\x -> (x, x:r)) <$> f b a
findM p = msum . map (\x -> if p x then pure x else mzero)</
===Using A*-search===
See [[A*_search_algorithm#Haskell]]
<
import qualified Data.Map as M
Line 646:
g = Graph $ \w -> M.fromList [ (x, 1)
| x <- short_dict
, distance w x == 1 ]</
<pre>λ> main
Line 655:
No chain</pre>
Works much faster when compiled.
=={{header|J}}==
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.
<syntaxhighlight lang="j">extend=: {{
j=. {:y
l=. <:{:$m
<y,"1 0 I.l=m+/ .="1 j{m
}}
wlad=: {{
l=. #x assert. l=#y
words=. >(#~ l=#@>) cutLF fread 'unixdict.txt'
ix=. ,:words i.x assert. ix<#words
iy=. ,:words i.y assert. iy<#words
while. -. 1 e. ix e.&, iy do.
if. 0 e. ix,&# iy do. EMPTY return. end.
ix=. ; words extend"1 ix
if. -. 1 e. ix e.&, iy do.
iy=. ; words extend"1 iy
end.
end.
iy=. |."1 iy
r=. ix,&,iy
for_jk.(ix,&#iy)#:I.,ix +./@e."1/ iy do.
ixj=. ({.jk){ix
iyk=. ({:jk){iy
for_c. ixj ([-.-.) iyk do.
path=. (ixj{.~ixj i.c) , iyk}.~ iyk i.c
if. path <&# r do. r=. path end.
end.
end.
}.,' ',.r{words
}}</syntaxhighlight>
Task examples:<syntaxhighlight lang="j"> 'boy' wlad 'man'
boy bay ban man
'girl' wlad 'lady'
girl gill gall gale gaze laze lazy lady
'john' wlad 'jane'
john cohn conn cone cane jane
'child' wlad 'adult'
'cat' wlad 'dog'
cat cot cog dog
'lead' wlad 'gold'
lead load goad gold
'white' wlad 'black'
white whine chine chink clink blink blank black
'bubble' wlad 'tickle'
bubble babble gabble garble gargle gaggle giggle jiggle jingle tingle tinkle tickle</syntaxhighlight>
=={{header|Java}}==
<
import java.nio.file.Files;
import java.nio.file.Path;
Line 750 ⟶ 802:
wordLadder(words, "bubble", "tickle", 12);
}
}</
{{out}}
<pre>boy -> bay -> may -> man
Line 763 ⟶ 815:
===Faster alternative===
{{trans|C++}}
<
import java.util.*;
Line 834 ⟶ 886:
System.out.printf("%s into %s cannot be done.\n", from, to);
}
}</
{{out}}
Line 852 ⟶ 904:
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<
def words: [inputs]; # one way to read the word list
Line 894 ⟶ 946:
words
| pairs as $p
| wordLadder($p[0]; $p[1])</
{{out}}
Line 907 ⟶ 959:
=={{header|Julia}}==
<
function targeted_mutations(str::AbstractString, target::AbstractString)
Line 933 ⟶ 985:
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"]]
Line 943 ⟶ 995:
=={{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];
Line 957 ⟶ 1,009:
sel=Select[Subsets[db,{2}],HammingDistance[#[[1]],#[[2]]]==1&];
g=Graph[db,UndirectedEdge@@@sel];
FindShortestPath[g,"child","adult"]</
{{out}}
<pre>{"boy", "bay", "ban", "man"}
Line 965 ⟶ 1,017:
=={{header|Nim}}==
<
Line 1,020 ⟶ 1,072:
echo &"No path from “{start}” to “{target}”."
else:
echo path.join(" → ")</
{{out}}
Line 1,035 ⟶ 1,087:
===Direct translation===
{{trans|C++}}
<
use warnings;
Line 1,133 ⟶ 1,185:
word_ladder('lead', 'gold');
word_ladder('white', 'black');
word_ladder('bubble', 'tickle');</
{{out}}
<pre>boy -> bay -> ban -> man
Line 1,146 ⟶ 1,198:
===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';
Line 1,196 ⟶ 1,248:
}
word_ladder(split) for 'boy man', 'girl lady', 'john jane', 'child adult';</
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>
Line 1,230 ⟶ 1,282:
<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}}
Line 1,242 ⟶ 1,294:
=={{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 ):
Line 1,289 ⟶ 1,341:
for w in ('boy man','girl lady','john jane','alien drool','child adult'):
print( find_path( cache( build_map,load_dico( dico_url )),*w.split()))</
{{out}}
Line 1,302 ⟶ 1,354:
=={{header|Racket}}==
<
(define *unixdict* (delay (with-input-from-file "../../data/unixdict.txt"
Line 1,342 ⟶ 1,394:
(Word-ladder "john" "jane")
(Word-ladder "alien" "drool")
(Word-ladder "child" "adult"))</
{{out}}
Line 1,393 ⟶ 1,445:
=={{header|Raku}}==
<syntaxhighlight lang="raku"
.classify(*.chars)
.map({ .key => .value.Set });
Line 1,429 ⟶ 1,481:
say word_ladder($from, $to)
// "$from into $to cannot be done";
}</
{{out}}
<pre>
Line 1,446 ⟶ 1,498:
Programming note: this REXX program uses the '''lower''' BIF which Regina has).
<br>If your REXX doesn't support that BIF, here is an equivalent function:
<
return translate(a, @, @u)</
<
parse arg base targ iFID . /*obtain optional arguments from the CL*/
if base=='' | base=="," then base= 'boy' /*Not specified? Then use the default.*/
Line 1,505 ⟶ 1,557:
end /*k*/
end /*i*/
$= $$; return ''</
{{out|output|text= when using the default inputs:}}
<pre>
Line 1,560 ⟶ 1,612:
=={{header|Ruby}}==
{{trans|Raku}}
<
Words = File.open("unixdict.txt").read.split("\n").
Line 1,602 ⟶ 1,654:
puts "#{from} into #{to} cannot be done"
end
end</
{{Out}}
Line 1,612 ⟶ 1,664:
=={{header|Swift}}==
{{trans|Wren}}
<
func oneAway(string1: [Character], string2: [Character]) -> Bool {
Line 1,672 ⟶ 1,724:
} catch {
print(error.localizedDescription)
}</
{{out}}
Line 1,689 ⟶ 1,741:
{{trans|Phix}}
{{libheader|Wren-sort}}
<
import "./sort" for Find
var words = File.read("unixdict.txt").trim().split("\n")
Line 1,729 ⟶ 1,781:
["child", "adult"]
]
for (pair in pairs) wordLadder.call(pair[0], pair[1])</
{{out}}
|