The idea originaes from the CodeKata19, find a word chain for two words of a wordlist

example 1 turning lead into gold:

lead
load
goad
gold

example 2 turning code into ruby:

code
rode
robe
rube
ruby

Note

it would be also valid if you had found this chain even though it is not an optimal solution (because it’s depth 6 not 5). It should only demonstrate that the start/end-letter is not always identical to the start/destiny word

code
rode
rods
robs
rubs
ruby

can you inspect my code on principals of CleanCode OOP and maybe some hints on performance/algorithm?

Main class

public static void main( String[] args )
{
    WordChainBuilder wordChainBuilder = new WordChainBuilder("src/main/resources/words.txt");
    List<String> goldChain = wordChainBuilder.build("gold", "lead");
    System.out.println("chain: "+goldChain);

    List<String> rubyChain = wordChainBuilder.build("ruby", "code");
    System.out.println("chain: "+rubyChain);
}

Node class

class Node {

    private Node predecessor;
    private final String word;

    Node(String word) {
        this.word= word;
    }

    String getWord() {
        return word;
    }

    void setPredecessor(Node node){
        predecessor = node;
    }

    Node getPredecessor() {
        return predecessor;
    }
}

WordChainBuilder class

class WordChainBuilder {

    private final String wordListFilename;

    WordChainBuilder(String wordListFilename) {
        this.wordListFilename = wordListFilename;
    }

    List<String> build(String startWord, String destinyWord) {
        if (startWord == null || destinyWord == null || 
            startWord.length() != destinyWord.length()) {
            throw new IllegalArgumentException();
        }

        List<String> words = readAllWordsWithLength(startWord.length());

        List<Node> currentDepth = new ArrayList<>();
        currentDepth.add(new Node(startWord));

        while (!currentDepth.isEmpty()) {
            List<Node> nextDepth = new ArrayList<>();
            for (Node node : currentDepth) {
                List<Node> derivedNodes = findDerivedNodes(node, words);

                Node destinyNode = findDestinyNode(derivedNodes, destinyWord);
                if (destinyNode != null){
                    return buildChain(destinyNode);
                }
                nextDepth.addAll(derivedNodes);
            }
            removeWordsAlreadyUsed(words, nextDepth);
            currentDepth = nextDepth;
        }
        return Collections.emptyList();
    }

    private void removeWordsAlreadyUsed(List<String> words, List<Node> nodes) {        
        words.removeAll(nodes.stream().map(Node::getWord).
            collect(Collectors.toList()));
    }

    private Node findDestinyNode(List<Node> nodes, String destinyWord) {
        return nodes.stream().filter(node -> node.getWord().equals(destinyWord)).findAny().orElse(null);
        }

    private List<Node> findDerivedNodes(Node node, List<String> words) {
        List<Node> derivedNodes = new ArrayList<>();
        for (String derivedWord : findDerivedWords(node.getWord(), words)) {
            Node derivedNode = new Node(derivedWord);
            derivedNode.setPredecessor(node);
            derivedNodes.add(derivedNode);
        }
        return derivedNodes;
    }

    private List<String> buildChain(Node node) {
        List<String> chain = new ArrayList<>();
        while (node.getPredecessor() != null) {
            chain.add(node.getWord());
            node = node.getPredecessor();
        }
        chain.add(node.getWord());
        Collections.reverse(chain);
        return chain;
   }

    private List<String> findDerivedWords(String word, List<String> candidates) {
        return candidates.stream().filter(w -> derivesByOne(word, w)).collect(Collectors.toList());
        }

    private static boolean derivesByOne(String word, String candidate) {
        int difference = 0;
        for (int i = 0; i < word.length(); i++) {
            if (word.charAt(i) != candidate.charAt(i)) {
                difference = difference + 1;
                if (difference > 1){
                    return false;
                }
            }
        }
        return difference == 1;
    }

    private List<String> readAllWordsWithLength(final int length) {
        try (Stream<String> lines = Files.lines(Paths.get(wordListFilename), Charset.defaultCharset())) {
            return lines.filter(line -> line.length() == length).collect(Collectors.toList());
        } catch (IOException e) {
            e.printStackTrace();
        }
        return Collections.emptyList();
    }
}

again i’m totally lost in finding proper objects or any idea on how to better split my code into seperate concerns 🙁 help!

thanks for the help so far, i opened a followup question on that topic…

Responsibilities

A class should have only one responsibility. Robert C. Martin describes it with “There should never be more than one reason for a class to change”.

The class WordChainBuilder has more than one responsibilities. An indicator for this is that it has many private methods. I saw a video (I will provide a reference to it) in which Sandi Metz said she generally avoids private methods.

I think you can not always avoid private methods, but if you have too many, your class definitely has more than one responsibility.

Responsibilities of WordChainBuilder:

• build the word chain
• read from the file system
• do operations on list
• do operations on strings

Type Embedded in Name

Avoid placing types in method names; it’s not only redundant, but it forces you to change the name if the type changes.

Because of the multiple responsibilities, there are several hidden abstractions in a class. So you have to name your variables and methods somehow.

Some type embedded names are:

• startWord & destinyWord
• findDerivedNodes & findDestinyNode
• findDerivedWords
• destinyNode & derivedNodes

Primitive Obsession

Primitive Obsession is using primitive data types to represent domain ideas. For example, we use a String to represent a message […]

I see some variables with the name startWord, destinyWord and words, a method derivesByOne that interacts with to words, but I can’t find a data type Word.

We can created it and copy/paste the method derivesByOne into it. After that we can rename the variable names startWord and destinyWord to start and destiny to avoid the code small Type Embedded in Name.

class Word {

    private String value;

    public Word(String word) {/*..*/}

    public boolean isDerivedByOne() {/*..*/}

   // equals & hashcode
}

First Class Collection

The First Class Collection [FCC] is an idea of the Object Calisthenics.

Any class that contains a collection should contain no other member variables. Each collection gets wrapped in its own class, so now behaviors related to the collection have a home.

With an FCC you can extract the methods findDerivedNodes andfindDestinyNode into their own class. Normally a collection of Nodess is a graph – so the new class might have the nameGraph or NodeCollection. In addition, the removeWordsAlreadyUsed andfindDerivedWords methods can be in their own class called Dictionary orWordCollection.

Law Of Demeter

Only talk to your immediate friends.” E.g. one never calls a method on an object you got from another call

The line node.getWord().equals(destinyWord) doesn’t follow the Law of Demeter. Note should have a method contains and than the line can be replaced with node.contains(destinyWord)

Null Object Pattern And New Methods

Because you return in the default case in findDestinyNode a null you have to check on two places if a Node is null (node.getPredecessor() != null)
and destinyNode != null)

We can get ride of the checks by using the Null Object Pattern. For this you have to return in findDestinyNode as default a null object EmptyNode which we have to implement. This object shares the same interface with Node so they implement the same methods.

When we create for destinyNode != null a method isEmpty, the “normal Node” will return false and the EmptyNode true. For node.getPredecessor() != null we can write a method hasPredecessor where the “normal Node” returns true and the EmptyNode false.

Better Data Structure

The method buildChain uses anArrayList to add all predecessors. Since they are appended to the end of the list, it is reversed with Collections.reverse (chain).

The time performance of this method is something like $O(n²)$, where the first $n$ is the number of predecessor and the second $n$ the time complexity of Collections.reverse

The interface List provides a method add(index, element) which we can use. If we add all elements to the first position we don’t have to reverse it. But ArrayList has $O(n)$ for adding 1 element to the first index. Instead of the ArrayList we can use a LinkedList which has for the same operation $O(1)$ and the hole method would have a time complexity of $O(n)$

private List<String> buildChain(Node node) {
    List<String> chain = new LinkedList<>();
    while (node.getPredecessor() != null) {
        chain.add(0, node.getWord());
        node = node.getPredecessor();
    }
    chain.add(node.getWord());
    return chain;
}