Word ladder: Difference between revisions
m C++ bug fix |
Added Swift solution |
||
Line 271:
(john cohn conn cone cane jane)
child into adult cannot be done</pre>
=={{header|Swift}}==
{{trans|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>
{{out}}
<pre>
man -> ban -> bay -> boy
girl -> gill -> gall -> gale -> gaze -> laze -> lazy -> lady
john -> cohn -> conn -> cone -> cane -> jane
child into adult cannot be done.
</pre>
=={{header|Wren}}==
|
Revision as of 13:29, 6 June 2021
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.
C++
This borrows heavily from Wren and a bit from Raku. <lang cpp>#include <algorithm>
- include <fstream>
- include <iostream>
- include <map>
- include <string>
- 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 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
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
Swift
<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
<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.