CareerCup

Treat it as a graph problem. start node is the start word. adjacent words are words where one of the characters is changed and the result is in the dictionary. Then you can perform a BFS on it to find the shortest path from start to end.

Optimization potential exists:
- dual source BFS
- Accelerate search with a heuristic (A*, guess the remaining distance as the number of characters to change to the end - which is never an overestimation, so you'll find the shortest path)
- Find adjacents: put the dictionary into a Trie where you can navigate the Nodes inside, so you can change characters at single positions (this wins on very large alphabets in practice and loose on reasonable small alphabets due to cache advantages of Hashtable)

Good idea Chris. Here's simple implementation.

JSBin:  jsbin.com/gilemoq/edit?js,console

function Node(word, friends) {
  this.word = word;
  this.friends = friends;
}

function createGraph(start, dict, visited) {
  visited[start] = true;
  
  var friendWords = getFriendsWords(start, dict);
  
  var friends = friendWords.reduce(function(f, fWord) {
    if (!visited[fWord]) {
      f = f.concat( createGraph(fWord, dict, Object.create(visited)) );
    }
    return f;
  }, []);
  
  var node = new Node(start, friends);
  
  return node;
}

function getFriendsWords(word, dict) {
  var result = [];
  for(var i = 0; i < dict.length; ++i) {
    var charDiffCount = getCharDiffCount(word, dict[i]);
    if (charDiffCount === 1) {
      result.push( dict[i] );
    }
  }
  return result;
}

function getCharDiffCount(a, b) {
  var count = Math.abs(a.length - b.length);
  for(var i = 0; i < a.length; ++i) {
    if (a[i] !== b[i] ) ++count;
  }
  return count;
}

function printGraph(node) {
  if (node) {
    console.log(node.word);
    node.friends.forEach(printGraph);
  }
}

function findShortestPath(root, target, path, result) {
  if (!root) {
    return;
  }else if(root.word === target) {
    var currentMinLength = result.minPath ? result.minPath.length : Infinity;
    result.minPath = path.length < currentMinLength ? path.slice() : result.minPath;
  }else {
    var currentPath = [root.word];
    var friends = root.friends;
    for(var i = 0; i < friends.length; ++i) {
      var friend = friends[i];
      path.push( friend.word );
      findShortestPath(friend, target, path, result);
      path.pop();
    }
  }
}

var start = 'SAT';
var end = 'PAN';
var dict = ['RAT', 'PAT'].concat( end );

var root = createGraph(start, dict, {});
var result = {};
findShortestPath(root, end, [], result);
console.log( 'minPath: ' + start + '->' + result.minPath.join('->') );

# python 3.6.x
"""
Assume a word list of length N where every word has width W
for i in [0..W-1]
    - rotate each word in the list by i
    - sort the list of words
    - compare consecutive words in the sorted list
    - assume the pair of words being compared as tuple (u, v)
    - if the distance between u and v =1
        - add (u,v ) as edge to a graph
let Networkx now find a shortest path from any u to any v
note: the distance between words = D when they differ in D char positions
"""
from operator import itemgetter
import networkx as nx

rotate = lambda s, t: s[len(s) - t:len(s)] + s[0:len(s) - t]
apartby1 = lambda s1, s2: 1 == len([i for i in range(len(s1)) if s1[i] != s2[i]])
g = nx.Graph()

dict = ["SAT", "PAN", "RAT", "PAT", "DAM"]
g.add_nodes_from(dict)

for t in range(3):
    tdict = []
    for word in dict:
        tdict.append([word, rotate(word, t)])
    sorted(tdict, key=itemgetter(1))

    for w in tdict:
        for wn in tdict[1:len(tdict)]:
            if apartby1(w[1], wn[1]):
                print(" edge {} -> {}".format(w[0], wn[0]))
                g.add_edge(w[0], wn[0])
try:
    result = nx.shortest_path(g, "SAT", "PAN")
    print("path of len {} found, {}".format(len(result), result))
except:
    print ("no path found")