Shortest path to transform one word into another

Question

I submitted the following code for a job application, and was rejected. They gave no feedback. Would appreciate any comments on the approach I took, and coding style.

This is the question:

Given two words (start and end) and the dictionary, find the length of the shortest transformation sequence from start to end, such that:

1) Only one letter can be changed at a time

2) Each intermediate word must exist in the given dictionary

3) At each step, exactly one character is replaced with another character

For example:

start = “hit”

end = “cog”

dictionary = [“hit”,”dot”,”dog”,”cog”,”hot”,”log”]

As one of the shortest transformations is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, return its length 4. Note: All words have the same length. All words contain only lowercase alphabetic characters.

My solution:

public class DictionaryDashSolver
{
    TransformationGraph transformationGraph = null;
    HashWordMap hashWordMap;

    /// <summary>
    /// Loads the dictionary of words to be used when calling Solve
    /// </summary>
    /// <param name="dictionary">An array of string</param>
    public void LoadDictionary(string[] dictionary)
    {
        if (dictionary == null)
            throw new Exception ("Supplied dictionary is null");
        dictionary = ConvertToLowerCase (dictionary);
        //create the graph of words to valid word with single character transformations
        this.transformationGraph = new TransformationGraph (dictionary);
        //create a lookup table from hash to word for converting the result from the graph traversal
        this.hashWordMap = new HashWordMap (dictionary);
    }

    /// <summary>
    /// Finds the shortest path between two words, in the dictionary.
    /// Dictionary should be supplied using LoadDictionary.
    /// Returns the list of transformation, including fromWord and toWord
    /// </summary>
    /// <param name="fromWord">Word to transform from </param>
    /// <param name="toWord">Word to transform towards</param>
    public List<string> Solve(string fromWord, string toWord)
    {
        if (this.transformationGraph == null)
        {
            throw new Exception("DictionaryDashSolver has no loaded transformation graph");
        }
        if (this.hashWordMap == null)
        {
            throw new Exception("DictionaryDashSolver has no loaded hash to word map");
        }
        if (string.IsNullOrEmpty(fromWord) || string.IsNullOrEmpty(toWord))
        {
            throw new Exception("Cannot solve for null input words");
        }
        if (fromWord.Length != toWord.Length)
        {
            throw new Exception("fromWord " + fromWord + " and toWord " + toWord + " must have the same number of characters");
        }

        fromWord = fromWord.ToLower ();
        toWord = toWord.ToLower ();
        var hashRoute = FindRoute (fromWord, toWord);
        return ConvertRouteIntoWords(hashRoute);
    }

    string[] ConvertToLowerCase(string[] inputDictionary)
    {
        for (int i = 0; i < inputDictionary.Length; i++)
            if (inputDictionary [i] != null)
                inputDictionary [i] = inputDictionary [i].ToLower ();
        return inputDictionary;
    }

    string[] ReplaceNullWordsWithEmptyString(string[] inputDictionary)
    {
        for (int i = 0; i < inputDictionary.Length; i++)
            if (inputDictionary [i] == null)
                inputDictionary [i] = "";
        return inputDictionary;
    }

    List<int> FindRoute(string fromWord, string toWord)
    {
        var astar = new AStar<int> () {
            GetNeighbours = (a) => this.transformationGraph.GetNeighbours (a),
            Heuristic = (a, b) => GetHammingDistanceForWordHashes (a, b),
            DistanceBetween = (a, b) => GetHammingDistanceForWordHashes (a, b)
        };
        return astar.CalculateRoute (fromWord.GetHashCode (), toWord.GetHashCode ());
    }

    float GetHammingDistanceForWordHashes(int word1Hash, int word2Hash)
    {
        var wordA = this.hashWordMap.HashToWord (word1Hash);
        var wordB = this.hashWordMap.HashToWord (word2Hash);
        if (string.IsNullOrEmpty (wordA) || string.IsNullOrEmpty (wordB))
        {
            return float.MaxValue; // 
        }
        return wordA.GetHammingDistance (wordB); 
    }

    List<string> ConvertRouteIntoWords(List<int> hashRoute)
    {
        if (hashRoute == null)
            return null;
        List<string> newList = new List<string> ();
        hashRoute.ForEach ((i) => newList.Add (this.hashWordMap.HashToWord (i)));
        return newList;
    }
}

public class TransformationGraph
{
    Dictionary<int, List<int>> validTransformations = new Dictionary<int, List<int>> ();

    public TransformationGraph (string[] dictionary)
    {
        this.validTransformations.Clear ();
        LoadWordHashes (dictionary);
        BuildTransformations (dictionary);
    }

    public List<int> GetNeighbours(int node)
    {
        List<int> neighbours = null;
        if (!this.validTransformations.TryGetValue (node, out neighbours))
            neighbours = new List<int> ();
        return neighbours;
    }


    private void LoadWordHashes(string[] dictionary)
    {
        foreach (string word in dictionary)
        {
            if (word != null)
            {
                var hash = word.GetHashCode ();
                this.validTransformations [hash] = null;
            }
        }
    }

    private void BuildTransformations (string[] dictionary)
    {
        foreach (string word in dictionary)
        {
            if (word != null)
                this.validTransformations[word.GetHashCode()] = GetValidTransformationsFromWord (word);
        }
    }

    private List<int> GetValidTransformationsFromWord (string fromWord)
    {
        List<int> transformations = new List<int>(); 
        var stringBuilder = new StringBuilder (fromWord);
        int fromWordHash = fromWord.GetHashCode ();
        for (int characterIndex = 0; characterIndex < fromWord.Length; characterIndex++)
        {
            var existingCharacter = stringBuilder [characterIndex];
            for (char character = 'a'; character <= 'z'; character++)
            {
                stringBuilder [characterIndex] = character;
                var newWord = stringBuilder.ToString ();
                var newWordHash = newWord.GetHashCode();
                if (IsValid (newWordHash) && fromWordHash != newWordHash )
                {
                    transformations.Add (newWordHash);
                }
            }
            stringBuilder [characterIndex] = existingCharacter;
        }
        return transformations;
    }

    private bool IsValid(int wordHash)
    {
        return validTransformations.ContainsKey (wordHash);
    }
}

public class HashWordMap : Dictionary<int,string>
{
    public HashWordMap (string[] dictionary)
    {
        this.Clear ();
        BuildMap (dictionary);
    }

    private void BuildMap(string[] dictionary)
    {
        foreach (string word in dictionary)
        {
            if (word != null)
            {
                var hash = word.GetHashCode ();
                this [hash] = word;
            }
        }
    }

    public string HashToWord(int hash)
    {
        return this.TryGetOrDefault(hash);
    }
}

public class AStar<T>
{
    HashSet<T> closedSet = new HashSet<T> ();
    HashSet<T> openSet = new HashSet<T> ();
    Dictionary<T,T> cameFrom = new Dictionary<T,T> ();
    Dictionary<T,float> gScore = new Dictionary<T,float> ();
    Dictionary<T,float> fScore = new Dictionary<T,float> ();

    public Func<T,List<T>> GetNeighbours { get; set; }

    public Func<T,T, float> DistanceBetween { get; set; }

    public Func<T,T, float> Heuristic { get; set; }

    public Func<T,T, bool> Compare { get; set; } = (x,y) => EqualityComparer<T>.Default.Equals (x, y);

    public List<T> CalculateRoute (T start, T end)
    {
        if (GetNeighbours == null || DistanceBetween == null || Heuristic == null)
            throw new Exception("AStar functions not initialised");

        Clear ();
        openSet.Add (start);
        gScore [start] = 0;
        fScore [start] = Heuristic (start, end);

        while (openSet.Count > 0)
        {
            var current = GetBestOpen ();
            if (Compare (current, end))
                return ReconstructPath (cameFrom, current);
            openSet.Remove (current);
            closedSet.Add (current);
            foreach (var neighbour in GetNeighbours(current))
            {
                if (closedSet.Contains (neighbour))
                    continue;
                var score = gScore.TryGetOrDefault (current, float.MaxValue) + DistanceBetween (current, neighbour);
                if (!openSet.Contains (neighbour))
                    openSet.Add (neighbour);
                if (score >= gScore.TryGetOrDefault (neighbour, float.MaxValue))
                    continue; //not better

                cameFrom [neighbour] = current;
                gScore [neighbour] = score;
                fScore [neighbour] = gScore [neighbour] + Heuristic (neighbour, end);
            }
        }

        return null;
    }

    void Clear ()
    {
        closedSet.Clear ();
        openSet.Clear ();
        cameFrom.Clear ();
        gScore.Clear ();
        fScore.Clear ();
    }

    T GetBestOpen ()
    {
        float minScore = float.MaxValue;
        T minItem = default(T);

        foreach (var item in openSet)
        {
            var score = fScore.TryGetOrDefault (item);
            if (score <= minScore)
            {
                minItem = item;
                minScore = score;
            }
        }

        return minItem;
    }


    List<T> ReconstructPath (Dictionary<T,T> cameFrom, T current)
    {
        var path = new List<T> ();
        path.Add (current);
        while (cameFrom.ContainsKey (current))
        {
            current = cameFrom [current];
            path.Add (current);
        }
        path.Reverse ();
        return path;
    }
}

public static class DotNetExtensions
{
    public static int GetHammingDistance(this string strA, string strB)
    {
        if(strA.Length != strB.Length)
        {
            throw new Exception("Strings must be equal length");
        }

        int dist = 
            strA.ToCharArray()
                .Zip(strB.ToCharArray(), (c1, c2) => new { c1, c2 })
                .Count(m => m.c1 != m.c2);

        return dist;
    }

    public static T1 TryGetOrDefault<T,T1>(this Dictionary<T, T1> fScoreMap, T key, T1 defaultVal = default(T1))
    {
        T1 value;
        if (!fScoreMap.TryGetValue(key, out value))
            value = defaultVal;
        return value;
    }
}

---

Tests:

[TestFixture ()]
public class DictionaryDashSolverTest
{
    Random random = new Random();

    [Test]
    public void BasicTest()
    {
        var mc = new DictionaryDashSolver();
        mc.LoadDictionary(new string[] {"boy", "bot"});
        var result = mc.Solve("boy", "bot");
        Assert.AreEqual(2, result.Count);
        Assert.AreEqual("boy", result[0]);
        Assert.AreEqual("bot", result[1]);
    }

    [Test]
    public void SameWord()
    {
        var mc = new DictionaryDashSolver();
        mc.LoadDictionary(new string[] {"boy", "bag", "bat"});
        var result = mc.Solve ("boy", "boy");
        Assert.AreEqual(1, result.Count);
        Assert.AreEqual("boy", result[0]);
    }

    [Test]
    public void NullWordInInput()
    {
        var mc = new DictionaryDashSolver();
        mc.LoadDictionary(new string[] {"boy", "bag", "bat"});
        Assert.Throws<Exception>( () => mc.Solve (null, "boy"));
    }

    [Test]
    public void NullWordInDictionary()
    {
        var mc = new DictionaryDashSolver();
        mc.LoadDictionary(new string[] {"boy", null, "bat"});
        Assert.DoesNotThrow( () => mc.Solve ("bat", "boy"));
    }

    [Test]
    public void UppercaseInput()
    {
        var mc = new DictionaryDashSolver();
        mc.LoadDictionary(new string[] {"boy", "bot", "bat"});
        var result = mc.Solve ("Boy", "bot");
        Assert.AreEqual(2, result.Count);
        Assert.AreEqual("boy", result[0]);
        Assert.AreEqual("bot", result[1]);
    }

    [Test]
    public void UppercaseDictionary()
    {
        var mc = new DictionaryDashSolver();
        mc.LoadDictionary(new string[] {"Boy", "bot", "bat"});
        var result = mc.Solve ("boy", "bot");
        Assert.AreEqual(2, result.Count);
        Assert.AreEqual("boy", result[0]);
        Assert.AreEqual("bot", result[1]);
    }

    [Test]
    public void InputWordNotInDictionary()
    {
        var mc = new DictionaryDashSolver();
        mc.LoadDictionary(new string[] {"boy", "bot", "bat"});
        Assert.IsNull(mc.Solve ("bog", "bot"));
    }

    [Test]
    public void NumericInDictionary()
    {
        var mc = new DictionaryDashSolver();
        mc.LoadDictionary(new string[] {"coy", "co2", "bo2", "bot", "bat"});
        Assert.IsNull(mc.Solve ("coy", "bat"));
    }

    [Test]
    public void NumericInput()
    {
        var mc = new DictionaryDashSolver();
        mc.LoadDictionary(new string[] {"coy", "cog", "bog", "bot", "bat"});
        Assert.IsNull(mc.Solve ("co2", "bat"));
    }

    [Test]
    public void SymbolInInput()
    {
        var mc = new DictionaryDashSolver();
        mc.LoadDictionary(new string[] {"coy", "cog", "bog", "bot", "bat"});
        Assert.IsNull(mc.Solve ("co@", "bat"));
    }

    [Test]
    public void NumCharactersDifferent()
    {
        var mc = new DictionaryDashSolver();
        mc.LoadDictionary(new string[] {"cope", "cog", "bog", "bot", "bat"});
        Assert.Throws<Exception> (() => mc.Solve ("cope", "bat"));
    }

    [Test]
    public void NullIfNoRoute()
    {
        var mc = new DictionaryDashSolver();
        mc.LoadDictionary(new string[] {"boy", "bag", "bat"});
        Assert.IsNull(mc.Solve ("boy", "bat"));
    }

    [Test]
    public void NullDictionary()
    {
        var mc = new DictionaryDashSolver();
        Assert.Throws<Exception>(() => mc.Solve ("boy", "bat"));
    }


    [Test]
    public void FindShortestPath()
    {
        var mc = new DictionaryDashSolver();
        mc.LoadDictionary(new string[] {"aaa", "baa", "caa", "cca", "ccc", "aac", "acc"});
        var result = mc.Solve ("aaa", "ccc");
        Assert.AreEqual (result.Count, 4); //naive algorithm would take 5 steps, assuming transformation are checked character 0 -> n, a -> z
    }

    [Test]
    public void LargeDictionaryFindOptimalSolution()
    {
        var mc = new DictionaryDashSolver();
        int size = 25000;
        var dict = new string[size + 5];
        int i = 0;
        for (; i < size; i++)
            dict [i] = RandomString (4);
        dict[i++] = "aaaa";
        dict[i++] = "aaaz";
        dict[i++] = "aazz";
        dict[i++] = "azzz";
        dict[i++] = "zzzz";

        mc.LoadDictionary(dict);
        List<string> result = null;
        Assert.DoesNotThrow (() => result = mc.Solve ("aaaa", "zzzz"));
        Assert.IsNotNull (result);
        Assert.AreEqual (5, result.Count);
    }

    public string RandomString(int length)
    {
        const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

        return new string(Enumerable.Repeat(chars, length)
            .Select(s => s[random.Next(s.Length)]).ToArray());
    }
}

Answer 1

Ran out of space in one comment, so figured I'd better write an answer...

Overall, the code is pretty readable and easy to follow. Performance is an obvious concern, however, and there are a few 'dubious' methods in there.

There is one HUGE issue:

Hash codes are not one to one mappings!!! They can't be (the space of strings is bigger than the space of ints), they are not, and this is a MASSIVE PROBLEM FOR YOUR CODE!!!!! DON'T USE THE HASH CODES!!!!!

I won't mention this again. But you can't do this. If you need a string, use a string: it has GetHashCode() implemented so that it can be used efficiently in Dictionaries and HashSets.

Now for everything else:

Misc Style

• I like to mark everything as explicitly private, not a big issue

• You have a lot of 'missing' curly braces: this is an easy way to annoy people and convince them that you write bad code. Personally I omit them now and then for stuff that just returns, continues, or throws, but I would absolutely avoid nesting (e.g. in ConvertToLowerCase)

• I personally dislike having spaces after method names and before indexers, but you have been consistent with it, so no complaint

• There is a curious inconsistency with spaces after commas (e.g. Func<T,List<T>> vs Func<T,T, float> in AStar

Per Member commentary

DictionaryDashSolver.LoadDictionary(string[])

Null check is sane, but converting to lowercase may not be. The spec states that the dictionary will contain only lowercase alphabetic characters: coercing the input to be 'to the spec' is unexpected behaviour, which is bad, and may cause fun problems with some cultures (I don't know much about globalization, but I'm sure it can go wrong somehow!). It would arguably make more sense to throw if supplied with non-lower-case inputs.

I like that you have this method: it suggests that you've thought about preloading the adjacency graph, which you have. However, you haven't documented this, and for a large dictionary and short route length it may impact on performance. Some explanation of this implementation design decision should be recorded.

Have you considered making this a constructor? This has a really important benefit: you can't misuse the class, and it is obvious how to correctly use the class. A nice knock-on effect is that you would no longer need the transformationGraph or hashWordMap checks in Solve (because you can't misuse the class).

I would feel much better passing this method/constructor an IReadOnlyList<string> for reasons that well become apparent below (note that T[] is convertible to IReadOnlyList<T>.

DictionaryDashSolver.Solve(string, string)

The biggest issue with this method is that it doesn't do what has been asked. The spec asks for the length of an optimal route, it doesn't ask for the route itself. While you have indirectly returned this information, it isn't what has been asked for, and it's important to code APIs as they have been agreed. Changing an API (even for the better) is a design decision, not something to do without discussing it with those people that will consume the API. I wouldn't mention this if you had provided an alternative method which does just return the length - and documented it's use - but you have not. Doing stuff that isn't made clear in the spec is becoming something of a theme!

You should also note that the length of a route of length 5 is actually suggested to be 4 in the spec, so the length of the returned array is still an inadequate result.

The null and/or empty checks on the inputs are great, because this is an exposed method, so you should assume the user will get it wrong and tell them when you do. I would, however, separate out the IsNullOrEmpty checks, so that you can return an ArgumentException with the parameter name explicit: the current message is perhaps OK, but you won't do better than an ArgumentException.

Again, however, you are assuming you can just ToLower the inputs, this isn't good, and it absolutely should be documented. (It is good to see inline documentation for exposed methods, but it could do with more detail given the current implementation).

I haven't had a serious look at the tests, but you are testing the important method, so that's good, and they look somewhat comprehensive. Showing the test case you have been given would be a sensible move, and would have highlighted the issues with the return value and associated OBOE.

DictionaryDashSolver.ConvertToLowerCase(string[])

The API for this method is not clear; does it modify the given array? The parameter name and presence of a return value suggest that it does not, and yet it does, and this is undocumented. Even worse, this means you are modifying the input to the API, which is not documented, and could cause problems with the code calling Solve.

DictionaryDashSolver.ReplaceNullWordsWithEmptyString(string[])

What is this?!?!? WHY?!?!?! WHY!!!! JUST THROW!!! Writing 'defensive' and 'overly robust' APIs is a great way to hide API misuse from an unsuspecting user, and cause them hours of misery while they throw nulls at you without realising, and wonder why your API is behaving funnily (even though their code is completely broken). I also suspect that this will still result in a crash, but an even more cryptic one about the lengths of strings (I note that this possibility is not tested).

Again, this is modifying the input array: if you are going to do this, make it obvious: returning suggests you clone, and 'input' suggests it isn't output.

DictionaryDashSolver.ConvertRouteIntoWords(List<int>)

There is a very good reason why ForEach is not in Linq: this method would be much more readable as a Linq Select or traditional foreach.

TransformationGraph.TransformationGraph(string[])

This is a constructor: why are you clearing the list you have just created?

TransformationGraph.GetNeighbours(int)

You are potentially creating a lot of empty Lists: perhaps create one and return it all the time.

Is the output meant to be mutable? If not, better to return an IReadOnlyList<T>.

AStar.CalculateRoute(T, T)

Nice to see a generic implementation of A*. This method ought to have inline documentation since it is clearly meant to be reusable.

If you expect the heuristic and such to change, then consider making them parameters for Solve; otherwise, it might be better to just create one AStar instance for each combination (pass them to the only constructor): again, this prevents misuse and provides a simple and explorable API.

openSet and closedSet are not the most helpful names ever. I go with due and seen (mostly for historical reasons), but I'm sure you can think of something better.

You are currently checking all candidates for openSet against closedSet, but you never check current against it, which you perhaps ought to.

This code is frightening:

var score = gScore.TryGetOrDefault (current, float.MaxValue) + DistanceBetween (current

Why are you defaulting to float.MaxValue? This default should never be used (I believe) and makes no sense anyway. Again, this is defensive coding which doesn't make any sense: just use a clean dictionary lookup: if the code crashes, GOOD: it has told you that the code is wrong in the most helpful way possible by giving you a stack trace, rather than hiding the issue. Similar commentary applies to the string.IsNullOrEmpty checks in GetHammingDistanceForWordHashes, where you basically say "this value makes no sense... return a value that makes no sense", when you should be saying "this value makes no sense... CRASH!!!!". Same again for the null check in ConvertRouteIntoWords.

Why not clear when you exit? Why leave the memory in use?

AStar.Compare

This could be slow: you should cache the comparer.

AStar.GetBestOpen()

You ought probably to be using a Priority Queue (a simple binary heap would perform just fine) to look up the next best entry. Changing this means making significant changes to CalculateRoute. You are lucky that the adjacency graph has no weights, else it could be significantly more fiddly... you are unfortunate that you have written a general purpose AStar, so you do need to worry about this. It is not impossible that you could add an entry to openSet with a score, only to find a better route to that entry before exploring it. This requires you to check this, and update your gScore (not a great name, nor is fScore) and cameFrom tables.

To expand on this: using a priority queue should give you O(log n) lookup (but you do need to be careful about double entries and the like, so it won't be 'simple' to modify your code) rather than O(n) lookup which you currently have. When n=100000, this is a huge difference, and is what makes heuristic search scale well (when a suitable heuristic exists, which you have already identified here).

AStar.ReconstructPath(,)

Again, this could return a IReadOnlyList<T>. It also looks like it is meant to be static.

DotNetExtensions.GetHammingDistance(string, string)

Style: missing space after if.

DotNetExtensions.TryGetOrDefault(,,)

Style: this can be smartened up with C# 7 inline declaration syntax, but if that isn't available, then so be it. Given this is an extension method, it would better to use a more general name for the dictionary (e.g. dictionary) rather than fScoreMap.