DictionaryProblem.java

package puzzles;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DictionaryProblem {
    private final static String[] DICTIONARY = {
            "concentricity"
            ,"sharewort"
            ,"tunnland"
            ,"emphysema"
            ,"Pliohippus"
            ,"tomatillo"
            ,"trewsman"
            ,"mulattoism"
            ,"muta"
            ,"begohm"
            ,"leisured"
            ,"scalenohedral"
            ,"devotionist"
            ,"allanitic"
            ,"appentice"
            ,"therapeutical"
            ,"dechemicalize"
            ,"agamic"
            ,"layship"
            ,"caroome"
            ,"vanjarrah"
            ,"frizziness"
            ,"guidebookish"
            ,"expedite"
            ,"strolld"
            ,"clubfisted"
            ,"task"
            ,"sanctiloquent"
            ,"rapturous"
            ,"ye"
            ,"genear"
            ,"wartweed"
            ,"outwind"
            ,"collyba"
            ,"doghead"
            ,"rotascope"
            ,"isogonally"
            ,"cankeredness"
            ,"staringly"
            ,"nemophilist"
            ,"bootyless"
            ,"postflexion"
            ,"xenogenous"
            ,"whereafter"
            ,"freezer"
            ,"atreptic"
            ,"nonavoidance"
            ,"quat"
            ,"indiscriminateness"
            ,"hacksilber"
            ,"countersnarl"
            ,"canonist"
            ,"bromohydrate"
            ,"amplectant"
            ,"impressibleness"
            ,"muckle"
            ,"tricoccous"
            ,"dogwood"
            ,"facetious"
            ,"bushveld"
            ,"liken"
            ,"hugeously"
            ,"Schizaeaceae"
            ,"melodiousness"
            ,"kipperer"
            ,"chantress"
            ,"prudentialness"
            ,"cacoepistic"
            ,"projective"
            ,"cumidin"
            ,"preferableness"
            ,"pseudomorphose"
            ,"halurgist"
            ,"impassiveness"
            ,"kitthoge"
            ,"impar"
            ,"townet"
            ,"ancistrocladaceous"
            ,"nationalness"
            ,"wardmaid"
            ,"jubilist"
            ,"misally"
            ,"unsinkable"
            ,"artichoke"
            ,"assumingness"
            ,"yawner"
            ,"surmount"
            ,"untie"
            ,"Mpondo"
            ,"mesoarial"
            ,"miscurvature"
            ,"urethylan"
            ,"weakfish"
            ,"playwork"
            ,"unfulminated"
            ,"Rosminianism"
            ,"groundneedle"
            ,"beachless"
            ,"bimillenary"
            ,"predictiveness"
            ,"head"
            ,"heal"
            ,"teal"
            ,"tell"
            ,"tall"
            ,"tail"
            ,"door"
            ,"boor"
            ,"book"
            ,"look"
            ,"lock"
            ,"bank"
            ,"bonk"
            ,"loon"
            ,"loan"
            ,"wheat"
            ,"cheat"
            ,"cheap"
            ,"cheep"
            ,"creep"
            ,"creed"
            ,"breed"
            ,"bread"
    };

    public static void main(String[] args) {
        String word = "door";
        String destination = "lock";
        List<String> chain = new ArrayList<>();

        if (find(null, word, destination, chain)) {
            System.out.println(chain);
        } else {
            System.out.printf("Word links not found from %s -> %s%n", word, destination);
        }
    }

    private static boolean find(String previous, String word, String destination, List<String> chain) {
        if ((word == null || word.trim().length() == 0) ||
                (destination == null || destination.trim().length() == 0) ||
                (chain == null)) {

            throw new IllegalArgumentException("Invalid parameters!");
        }

        System.out.printf("Adding %s to the chain...%n", word);
        chain.add(word);

        if (word.equals(destination)) {
            return true;
        }

        Set<String> nextMatches = getNextMatches(previous, word);

        if (nextMatches.isEmpty()) {
            return false;
        }

        for (String nextMatch : nextMatches) {
            if (find(word, nextMatch, destination, chain)) {
                return true;
            } else {
                System.out.printf("Removing %s from the chain...%n", chain.get(chain.size() - 1));
                chain.remove(chain.size() - 1);
            }
        }

        return false;
    }

    private static Set<String> getNextMatches(String previous, String word) {
        Set<String> nextMatches = new HashSet<>();

        for (String dictionaryWord : DICTIONARY) {
            if (previous != null && dictionaryWord.equals(previous)) {
                continue;
            }

            if (differsByOne(dictionaryWord, word)) {
                nextMatches.add(dictionaryWord);
            }
        }

        return nextMatches;
    }

    private static boolean differsByOne(String dictionaryWord, String word) {
        if (dictionaryWord.length() != word.length()) {
            return false;
        }

        int differences = 0;

        for (int i=0; i<word.length(); i++) {
            if (dictionaryWord.charAt(i) != word.charAt(i)) {
                differences++;
            }
        }

        return (differences == 1);
    }
}

Clojure Solution

(def dict [
              "book"
              "dook"
              "nook"
              "look"
              "lock"
              "took"
            ])

(defn sdiff [w1 w2]
  (apply + (map (fn [[a b & c]] (if (= a b) 0 1))
        (map vector w1 w2))))

(defn diff-by-one [word goal] (= 1 (sdiff word goal)))

(defn neighboors [word dict remove]
   (let [wsize (count word)]
     (filter (fn [w] (and
                       (= wsize (count w))
                       (diff-by-one word w)
                       (not-any? (partial = w) remove))) dict)))

(defrecord Doublets [path])

(defn solutions [ word goal visited]
  (let [visited (conj visited word)]
    (if (= word goal) (Doublets. visited)
                      (for [r (neighboors word dict visited)
                            :let [r (solutions r goal visited)]] r ))))
(defn solution [word goal]
  (flatten (solutions word goal [])))

(solution "book" "dook")
=>
(#user.Doublets{:path ["book" "dook"]}
 #user.Doublets{:path ["book" "nook" "dook"]}
 #user.Doublets{:path ["book" "nook" "look" "dook"]}
 #user.Doublets{:path ["book" "nook" "look" "took" "dook"]}
 #user.Doublets{:path ["book" "nook" "took" "dook"]}
 #user.Doublets{:path ["book" "nook" "took" "look" "dook"]}
 #user.Doublets{:path ["book" "look" "dook"]}
 #user.Doublets{:path ["book" "look" "nook" "dook"]}
 #user.Doublets{:path ["book" "look" "nook" "took" "dook"]}
 #user.Doublets{:path ["book" "look" "took" "dook"]}
 #user.Doublets{:path ["book" "look" "took" "nook" "dook"]}
 #user.Doublets{:path ["book" "took" "dook"]}
 #user.Doublets{:path ["book" "took" "nook" "dook"]}
 #user.Doublets{:path ["book" "took" "nook" "look" "dook"]}
 #user.Doublets{:path ["book" "took" "look" "dook"]}
 #user.Doublets{:path ["book" "took" "look" "nook" "dook"]})

PUZZLE

The puzzle is to take two words of the same length and find a way of linking the
first word to the second word by only changing one letter at a time. At the end of the transformation,
there will be a collections of words that show the beginning word being changed
into the ending word, one letter at a time. All the word links must be in Lewis Carroll's own words:

... it is de rigueur that the links should be English words, such as might be used in good society.

Also the word links should be words that are found in the dictionary. No proper nouns.

Here are some examples.

The Doublet of DOOR to LOCK is:

door
boor
book
look
lock

The Doublet of BANK to LOAN is:

bank
bonk
book
look
loon
loan

The Doublet of WHEAT into BREAD is:

wheat
cheat
cheap
cheep
creep
creed
breed
bread

A sample dictionary has been included with a few words to get things going. After you solve the kata, you might want to try a bigger dictionary to discover more exciting doublets

Dictionary

[ "concentricity"
  "sharewort"
  "tunnland"
  "emphysema"
  "Pliohippus"
  "tomatillo"
  "trewsman"
  "mulattoism"
  "muta"
  "begohm"
  "leisured"
  "scalenohedral"
  "devotionist"
  "allanitic"
  "appentice"
  "therapeutical"
  "dechemicalize"
  "agamic"
  "layship"
  "caroome"
  "vanjarrah"
  "frizziness"
  "guidebookish"
  "expedite"
  "strolld"
  "clubfisted"
  "task"
  "sanctiloquent"
  "rapturous"
  "ye"
  "genear"
  "wartweed"
  "outwind"
  "collyba"
  "doghead"
  "rotascope"
  "isogonally"
  "cankeredness"
  "staringly"
  "nemophilist"
  "bootyless"
  "postflexion"
  "xenogenous"
  "whereafter"
  "freezer"
  "atreptic"
  "nonavoidance"
  "quat"
  "indiscriminateness"
  "hacksilber"
  "countersnarl"
  "canonist"
  "bromohydrate"
  "amplectant"
  "impressibleness"
  "muckle"
  "tricoccous"
  "dogwood"
  "facetious"
  "bushveld"
  "liken"
  "hugeously"
  "Schizaeaceae"
  "melodiousness"
  "kipperer"
  "chantress"
  "prudentialness"
  "cacoepistic"
  "projective"
  "cumidin"
  "preferableness"
  "pseudomorphose"
  "halurgist"
  "impassiveness"
  "kitthoge"
  "impar"
  "townet"
  "ancistrocladaceous"
  "nationalness"
  "wardmaid"
  "jubilist"
  "misally"
  "unsinkable"
  "artichoke"
  "assumingness"
  "yawner"
  "surmount"
  "untie"
  "Mpondo"
  "mesoarial"
  "miscurvature"
  "urethylan"
  "weakfish"
  "playwork"
  "unfulminated"
  "Rosminianism"
  "groundneedle"
  "beachless"
  "bimillenary"
  "predictiveness"
  "head"
  "heal"
  "teal"
  "tell"
  "tall"
  "tail"
  "door"
  "boor"
  "book"
  "look"
  "lock"
  "bank"
  "bonk"
  "loon"
  "loan"
  "wheat"
  "cheat"
  "cheap"
  "cheep"
  "creep"
  "creed"
  "breed"
  "bread"
]