How to resolve the algorithm Word ladder step by step in the Java programming language
How to resolve the algorithm Word ladder step by step in the Java programming language
Table of Contents
Problem Statement
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 A john can be made into a jane: john -> cohn -> conn -> cone -> cane -> jane A child can not be turned into an adult. Optional transpositions of your choice.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Word ladder step by step in the Java programming language
First implementation
The first implementation of the WordLadder class reads a dictionary of words from a file, and then provides a method to find the shortest chain of single-character modifications that lead from one word to another. The method uses a breadth-first search to find the shortest path, and prints the path if it is found. The method takes two parameters: a map of word lengths to the set of words of that length, and two strings, the from word and the to word. The method first checks if the from word is in the dictionary, and if it is, it creates a queue of lists of strings, where each list is a path from the from word to the to word. The method then iterates over the queue, removing the first list from the queue and checking if the last word in the list is the to word. If it is, the method prints the list and returns. If it is not, the method iterates over the set of words of the same length as the last word in the list, and checks if any of the words differ from the last word in the list by one character. If a word is found that differs by one character, the method creates a new list that is the same as the old list, but with the new word added to the end, and adds the new list to the queue. The method repeats this process until the queue is empty or the to word is found. If the to word is not found, the method prints an error message.
Second implementation
The second implementation of the WordLadder class also reads a dictionary of words from a file, and then provides a method to find the shortest chain of single-character modifications that lead from one word to another. The method uses a breadth-first search to find the shortest path, and prints the path if it is found. The method takes two parameters: a map of word lengths to the list of words of that length, and two strings, the from word and the to word. The method first checks if the from word is in the dictionary, and if it is, it creates a queue of lists of strings, where each list is a path from the from word to the to word. The method then iterates over the queue, removing the first list from the queue and checking if the last word in the list is the to word. If it is, the method prints the list and returns. If it is not, the method iterates over the list of words of the same length as the last word in the list, and checks if any of the words differ from the last word in the list by one character. If a word is found that differs by one character, the method creates a new list that is the same as the old list, but with the new word added to the end, and adds the new list to the queue. The method repeats this process until the queue is empty or the to word is found. If the to word is not found, the method prints an error message.
Comparison of the two implementations
The two implementations of the WordLadder class are very similar. The main difference is that the first implementation uses a set to store the words of each length, while the second implementation uses a list. The set implementation is more efficient for finding words that differ from a given word by one character, but the list implementation is more efficient for adding new words to the queue. Overall, the two implementations are very similar in terms of performance and functionality.
Source code in the java programming language
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.stream.IntStream;
public class WordLadder {
private static int distance(String s1, String s2) {
assert s1.length() == s2.length();
return (int) IntStream.range(0, s1.length())
.filter(i -> s1.charAt(i) != s2.charAt(i))
.count();
}
private static void wordLadder(Map<Integer, Set<String>> words, String fw, String tw) {
wordLadder(words, fw, tw, 8);
}
private static void wordLadder(Map<Integer, Set<String>> words, String fw, String tw, int limit) {
if (fw.length() != tw.length()) {
throw new IllegalArgumentException("From word and to word must have the same length");
}
Set<String> ws = words.get(fw.length());
if (ws.contains(fw)) {
List<String> primeList = new ArrayList<>();
primeList.add(fw);
PriorityQueue<List<String>> queue = new PriorityQueue<>((chain1, chain2) -> {
int cmp1 = Integer.compare(chain1.size(), chain2.size());
if (cmp1 == 0) {
String last1 = chain1.get(chain1.size() - 1);
int d1 = distance(last1, tw);
String last2 = chain2.get(chain2.size() - 1);
int d2 = distance(last2, tw);
return Integer.compare(d1, d2);
}
return cmp1;
});
queue.add(primeList);
while (queue.size() > 0) {
List<String> curr = queue.remove();
if (curr.size() > limit) {
continue;
}
String last = curr.get(curr.size() - 1);
for (String word : ws) {
if (distance(last, word) == 1) {
if (word.equals(tw)) {
curr.add(word);
System.out.println(String.join(" -> ", curr));
return;
}
if (!curr.contains(word)) {
List<String> cp = new ArrayList<>(curr);
cp.add(word);
queue.add(cp);
}
}
}
}
}
System.err.printf("Cannot turn `%s` into `%s`%n", fw, tw);
}
public static void main(String[] args) throws IOException {
Map<Integer, Set<String>> words = new HashMap<>();
for (String line : Files.readAllLines(Path.of("unixdict.txt"))) {
Set<String> wl = words.computeIfAbsent(line.length(), HashSet::new);
wl.add(line);
}
wordLadder(words, "boy", "man");
wordLadder(words, "girl", "lady");
wordLadder(words, "john", "jane");
wordLadder(words, "child", "adult");
wordLadder(words, "cat", "dog");
wordLadder(words, "lead", "gold");
wordLadder(words, "white", "black");
wordLadder(words, "bubble", "tickle", 12);
}
}
import java.io.*;
import java.util.*;
public class WordLadder {
public static void main(String[] args) {
try {
Map<Integer, List<String>> words = new HashMap<>();
try (BufferedReader reader = new BufferedReader(new FileReader("unixdict.txt"))) {
String line;
while ((line = reader.readLine()) != null)
words.computeIfAbsent(line.length(), k -> new ArrayList<String>()).add(line);
}
wordLadder(words, "boy", "man");
wordLadder(words, "girl", "lady");
wordLadder(words, "john", "jane");
wordLadder(words, "child", "adult");
wordLadder(words, "cat", "dog");
wordLadder(words, "lead", "gold");
wordLadder(words, "white", "black");
wordLadder(words, "bubble", "tickle");
} catch (Exception e) {
e.printStackTrace();
}
}
// Returns true if strings s1 and s2 differ by one character.
private static boolean oneAway(String s1, String s2) {
if (s1.length() != s2.length())
return false;
boolean result = false;
for (int i = 0, n = s1.length(); i != n; ++i) {
if (s1.charAt(i) != s2.charAt(i)) {
if (result)
return false;
result = true;
}
}
return result;
}
// 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.
private static void wordLadder(Map<Integer, List<String>> words, String from, String to) {
List<String> w = words.get(from.length());
if (w != null) {
Deque<String> poss = new ArrayDeque<>(w);
Deque<String> f = new ArrayDeque<String>();
f.add(from);
Deque<Deque<String>> queue = new ArrayDeque<>();
queue.add(f);
while (!queue.isEmpty()) {
Deque<String> curr = queue.poll();
for (Iterator<String> i = poss.iterator(); i.hasNext(); ) {
String str = i.next();
if (!oneAway(str, curr.getLast()))
continue;
if (to.equals(str)) {
curr.add(to);
System.out.println(String.join(" -> ", curr));
return;
}
Deque<String> temp = new ArrayDeque<>(curr);
temp.add(str);
queue.add(temp);
i.remove();
}
}
}
System.out.printf("%s into %s cannot be done.\n", from, to);
}
}
You may also check:How to resolve the algorithm Pernicious numbers step by step in the Swift programming language
You may also check:How to resolve the algorithm Color wheel step by step in the Plain English programming language
You may also check:How to resolve the algorithm Variadic function step by step in the Julia programming language
You may also check:How to resolve the algorithm Element-wise operations step by step in the Rust programming language
You may also check:How to resolve the algorithm A+B step by step in the OpenEdge/Progress programming language