Word ladder: Difference between revisions
Content added Content deleted
(J) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 23: | Line 23: | ||
{{trans|Nim}} |
{{trans|Nim}} |
||
< |
<syntaxhighlight lang="11l">F isOneAway(word1, word2) |
||
V result = 0B |
V result = 0B |
||
L(i) 0 .< word1.len |
L(i) 0 .< word1.len |
||
Line 74: | Line 74: | ||
print(‘No path from "’start‘" to "’target‘".’) |
print(‘No path from "’start‘" to "’target‘".’) |
||
E |
E |
||
print(path.join(‘ -> ’))</ |
print(path.join(‘ -> ’))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 90: | Line 90: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
With ''a68g'' use option <code>--storage 2</code>, otherwise it runs out of memory. |
With ''a68g'' use option <code>--storage 2</code>, otherwise it runs out of memory. |
||
< |
<syntaxhighlight lang="algol68"># quick implementation of a stack of INT. |
||
real program starts after it. |
real program starts after it. |
||
# |
# |
||
Line 268: | Line 268: | ||
print(newline) |
print(newline) |
||
FI |
FI |
||
OD</ |
OD</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>boy->bay->ban->man |
<pre>boy->bay->ban->man |
||
Line 292: | Line 292: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
This borrows heavily from [[#Wren|Wren]] and a bit from [[#Raku|Raku]]. |
This borrows heavily from [[#Wren|Wren]] and a bit from [[#Raku|Raku]]. |
||
< |
<syntaxhighlight lang="cpp">#include <algorithm> |
||
#include <fstream> |
#include <fstream> |
||
#include <iostream> |
#include <iostream> |
||
Line 383: | Line 383: | ||
word_ladder(words, "bubble", "tickle"); |
word_ladder(words, "bubble", "tickle"); |
||
return EXIT_SUCCESS; |
return EXIT_SUCCESS; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 398: | Line 398: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Word ladder: Nigel Galloway. June 5th., 2021 |
// 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 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: | 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 |
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")) |
[("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> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 418: | Line 418: | ||
The bad news is evil can not be turned into good, but the good news is god can become man. |
The bad news is evil can not be turned into good, but the good news is god can become man. |
||
< |
<syntaxhighlight lang="fsharp"> |
||
[("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")) |
[("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> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 429: | Line 429: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|Wren}} |
{{trans|Wren}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 517: | Line 517: | ||
wordLadder(words, pair[0], pair[1]) |
wordLadder(words, pair[0], pair[1]) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 531: | 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. |
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. |
||
< |
<syntaxhighlight lang="haskell">import System.IO (readFile) |
||
import Control.Monad (foldM) |
import Control.Monad (foldM) |
||
import Data.List (intercalate) |
import Data.List (intercalate) |
||
Line 577: | Line 577: | ||
showChain $ wordLadder dict "john" "jane" |
showChain $ wordLadder dict "john" "jane" |
||
showChain $ wordLadder dict "alien" "drool" |
showChain $ wordLadder dict "alien" "drool" |
||
showChain $ wordLadder dict "child" "adult"</ |
showChain $ wordLadder dict "child" "adult"</syntaxhighlight> |
||
<pre>λ> lines <$> readFile "unixdict.txt" >>= print . wordLadders "boy" "man" |
<pre>λ> lines <$> readFile "unixdict.txt" >>= print . wordLadders "boy" "man" |
||
Line 598: | 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. |
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. |
||
< |
<syntaxhighlight lang="haskell">wordLadders2 :: String -> String -> [String] -> [[String]] |
||
wordLadders2 start end dict |
wordLadders2 start end dict |
||
| length start /= length end = [] |
| length start /= length end = [] |
||
Line 629: | Line 629: | ||
where g (b, r) a = (\x -> (x, x:r)) <$> f b a |
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)</ |
findM p = msum . map (\x -> if p x then pure x else mzero)</syntaxhighlight> |
||
===Using A*-search=== |
===Using A*-search=== |
||
See [[A*_search_algorithm#Haskell]] |
See [[A*_search_algorithm#Haskell]] |
||
< |
<syntaxhighlight lang="haskell">import AStar (findPath, Graph(..)) |
||
import qualified Data.Map as M |
import qualified Data.Map as M |
||
Line 646: | Line 646: | ||
g = Graph $ \w -> M.fromList [ (x, 1) |
g = Graph $ \w -> M.fromList [ (x, 1) |
||
| x <- short_dict |
| x <- short_dict |
||
, distance w x == 1 ]</ |
, distance w x == 1 ]</syntaxhighlight> |
||
<pre>λ> main |
<pre>λ> main |
||
Line 660: | Line 660: | ||
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. |
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 |
j=. {:y |
||
l=. <:{:$m |
l=. <:{:$m |
||
Line 689: | Line 689: | ||
end. |
end. |
||
}.,' ',.r{words |
}.,' ',.r{words |
||
}}</ |
}}</syntaxhighlight> |
||
Task examples:< |
Task examples:<syntaxhighlight lang="j"> 'boy' wlad 'man' |
||
boy bay ban man |
boy bay ban man |
||
'girl' wlad 'lady' |
'girl' wlad 'lady' |
||
Line 705: | Line 705: | ||
white whine chine chink clink blink blank black |
white whine chine chink clink blink blank black |
||
'bubble' wlad 'tickle' |
'bubble' wlad 'tickle' |
||
bubble babble gabble garble gargle gaggle giggle jiggle jingle tingle tinkle tickle</ |
bubble babble gabble garble gargle gaggle giggle jiggle jingle tingle tinkle tickle</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
< |
<syntaxhighlight lang="java">import java.io.IOException; |
||
import java.nio.file.Files; |
import java.nio.file.Files; |
||
import java.nio.file.Path; |
import java.nio.file.Path; |
||
Line 802: | Line 802: | ||
wordLadder(words, "bubble", "tickle", 12); |
wordLadder(words, "bubble", "tickle", 12); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>boy -> bay -> may -> man |
<pre>boy -> bay -> may -> man |
||
Line 815: | Line 815: | ||
===Faster alternative=== |
===Faster alternative=== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang="java">import java.io.*; |
||
import java.util.*; |
import java.util.*; |
||
Line 886: | Line 886: | ||
System.out.printf("%s into %s cannot be done.\n", from, to); |
System.out.printf("%s into %s cannot be done.\n", from, to); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 904: | Line 904: | ||
{{works with|jq}} |
{{works with|jq}} |
||
'''Works with gojq, the Go implementation of jq''' |
'''Works with gojq, the Go implementation of jq''' |
||
< |
<syntaxhighlight lang="jq">def count(stream): reduce stream as $i (0; .+1); |
||
def words: [inputs]; # one way to read the word list |
def words: [inputs]; # one way to read the word list |
||
Line 946: | Line 946: | ||
words |
words |
||
| pairs as $p |
| pairs as $p |
||
| wordLadder($p[0]; $p[1])</ |
| wordLadder($p[0]; $p[1])</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 959: | Line 959: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">const dict = Set(split(read("unixdict.txt", String), r"\s+")) |
||
function targeted_mutations(str::AbstractString, target::AbstractString) |
function targeted_mutations(str::AbstractString, target::AbstractString) |
||
Line 985: | Line 985: | ||
println("john to jane: ", targeted_mutations("john", "jane")) |
println("john to jane: ", targeted_mutations("john", "jane")) |
||
println("child to adult: ", targeted_mutations("child", "adult")) |
println("child to adult: ", targeted_mutations("child", "adult")) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
boy to man: [["boy", "bay", "may", "man"], ["boy", "bay", "ban", "man"], ["boy", "bon", "ban", "man"]] |
boy to man: [["boy", "bay", "may", "man"], ["boy", "bay", "ban", "man"], ["boy", "bon", "ban", "man"]] |
||
Line 995: | Line 995: | ||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{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.}} |
{{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.}} |
||
< |
<syntaxhighlight lang="mathematica">db=DeleteDuplicates[RemoveDiacritics[ToLowerCase[Select[DictionaryLookup[],StringLength/*EqualTo[3]]]]]; |
||
sel=Select[Subsets[db,{2}],HammingDistance[#[[1]],#[[2]]]==1&]; |
sel=Select[Subsets[db,{2}],HammingDistance[#[[1]],#[[2]]]==1&]; |
||
g=Graph[db,UndirectedEdge@@@sel]; |
g=Graph[db,UndirectedEdge@@@sel]; |
||
Line 1,009: | Line 1,009: | ||
sel=Select[Subsets[db,{2}],HammingDistance[#[[1]],#[[2]]]==1&]; |
sel=Select[Subsets[db,{2}],HammingDistance[#[[1]],#[[2]]]==1&]; |
||
g=Graph[db,UndirectedEdge@@@sel]; |
g=Graph[db,UndirectedEdge@@@sel]; |
||
FindShortestPath[g,"child","adult"]</ |
FindShortestPath[g,"child","adult"]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{"boy", "bay", "ban", "man"} |
<pre>{"boy", "bay", "ban", "man"} |
||
Line 1,017: | Line 1,017: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim">import sets, strformat, strutils |
||
Line 1,072: | Line 1,072: | ||
echo &"No path from “{start}” to “{target}”." |
echo &"No path from “{start}” to “{target}”." |
||
else: |
else: |
||
echo path.join(" → ")</ |
echo path.join(" → ")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,087: | Line 1,087: | ||
===Direct translation=== |
===Direct translation=== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
Line 1,185: | Line 1,185: | ||
word_ladder('lead', 'gold'); |
word_ladder('lead', 'gold'); |
||
word_ladder('white', 'black'); |
word_ladder('white', 'black'); |
||
word_ladder('bubble', 'tickle');</ |
word_ladder('bubble', 'tickle');</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>boy -> bay -> ban -> man |
<pre>boy -> bay -> ban -> man |
||
Line 1,198: | Line 1,198: | ||
===Idiomatic version=== |
===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. |
<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. |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use feature 'say'; |
use feature 'say'; |
||
Line 1,248: | Line 1,248: | ||
} |
} |
||
word_ladder(split) for 'boy man', 'girl lady', 'john jane', 'child adult';</ |
word_ladder(split) for 'boy man', 'girl lady', 'john jane', 'child adult';</syntaxhighlight> |
||
Same style output. |
Same style output. |
||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<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: #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,282: | Line 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;">"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> |
<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> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
<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> |
<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}} |
{{out}} |
||
Line 1,294: | Line 1,294: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
The function ''cache'' is not part of the algorithm but avoid re-download and map re-computing at each re-run. |
The function ''cache'' is not part of the algorithm but avoid re-download and map re-computing at each re-run. |
||
< |
<syntaxhighlight lang="python">import os,sys,zlib,urllib.request |
||
def h ( str,x=9 ): |
def h ( str,x=9 ): |
||
Line 1,341: | Line 1,341: | ||
for w in ('boy man','girl lady','john jane','alien drool','child adult'): |
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()))</ |
print( find_path( cache( build_map,load_dico( dico_url )),*w.split()))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,354: | Line 1,354: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket">#lang racket |
||
(define *unixdict* (delay (with-input-from-file "../../data/unixdict.txt" |
(define *unixdict* (delay (with-input-from-file "../../data/unixdict.txt" |
||
Line 1,394: | Line 1,394: | ||
(Word-ladder "john" "jane") |
(Word-ladder "john" "jane") |
||
(Word-ladder "alien" "drool") |
(Word-ladder "alien" "drool") |
||
(Word-ladder "child" "adult"))</ |
(Word-ladder "child" "adult"))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,445: | Line 1,445: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
<lang |
<syntaxhighlight lang="raku" line>constant %dict = 'unixdict.txt'.IO.lines |
||
.classify(*.chars) |
.classify(*.chars) |
||
.map({ .key => .value.Set }); |
.map({ .key => .value.Set }); |
||
Line 1,481: | Line 1,481: | ||
say word_ladder($from, $to) |
say word_ladder($from, $to) |
||
// "$from into $to cannot be done"; |
// "$from into $to cannot be done"; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,498: | Line 1,498: | ||
Programming note: this REXX program uses the '''lower''' BIF which Regina has). |
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: |
<br>If your REXX doesn't support that BIF, here is an equivalent function: |
||
< |
<syntaxhighlight lang="rexx">lower: procedure; parse arg a; @= 'abcdefghijklmnopqrstuvwxyz'; @u= @; upper @u |
||
return translate(a, @, @u)</ |
return translate(a, @, @u)</syntaxhighlight> |
||
< |
<syntaxhighlight 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*/ |
parse arg base targ iFID . /*obtain optional arguments from the CL*/ |
||
if base=='' | base=="," then base= 'boy' /*Not specified? Then use the default.*/ |
if base=='' | base=="," then base= 'boy' /*Not specified? Then use the default.*/ |
||
Line 1,557: | Line 1,557: | ||
end /*k*/ |
end /*k*/ |
||
end /*i*/ |
end /*i*/ |
||
$= $$; return ''</ |
$= $$; return ''</syntaxhighlight> |
||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
Line 1,612: | Line 1,612: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="ruby">require "set" |
||
Words = File.open("unixdict.txt").read.split("\n"). |
Words = File.open("unixdict.txt").read.split("\n"). |
||
Line 1,654: | Line 1,654: | ||
puts "#{from} into #{to} cannot be done" |
puts "#{from} into #{to} cannot be done" |
||
end |
end |
||
end</ |
end</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 1,664: | Line 1,664: | ||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
{{trans|Wren}} |
{{trans|Wren}} |
||
< |
<syntaxhighlight lang="swift">import Foundation |
||
func oneAway(string1: [Character], string2: [Character]) -> Bool { |
func oneAway(string1: [Character], string2: [Character]) -> Bool { |
||
Line 1,724: | Line 1,724: | ||
} catch { |
} catch { |
||
print(error.localizedDescription) |
print(error.localizedDescription) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,741: | Line 1,741: | ||
{{trans|Phix}} |
{{trans|Phix}} |
||
{{libheader|Wren-sort}} |
{{libheader|Wren-sort}} |
||
< |
<syntaxhighlight lang="ecmascript">import "io" for File |
||
import "/sort" for Find |
import "/sort" for Find |
||
Line 1,781: | Line 1,781: | ||
["child", "adult"] |
["child", "adult"] |
||
] |
] |
||
for (pair in pairs) wordLadder.call(pair[0], pair[1])</ |
for (pair in pairs) wordLadder.call(pair[0], pair[1])</syntaxhighlight> |
||
{{out}} |
{{out}} |