Lewis Carroll invented a word-game or puzzle which he called "doublets" in a book by the same name.  Given two distinct words of the same length, find a chain of words, each with only a single character different from the previous word in the chain, that will lead from the first to the last word.  Additionally, the number of words in the chain should be as small as possible. Solutions are often not unique.  His 6-word solution above to the task of getting from "head" to "tail' can be replaced by an alternate 6-word solution: "head -> heal -> hell -> hall -> hail -> tail".

Your mission will be write a program to find the shortest ladder between two given words (or at least one of the shortest). 

You will be given a list of English words, in the file dictall.txt (you should download this).  You must use this wordlist for this problem. 

First step: test your program by duplicating the results below.  Your program may find different sequences than the ones below, but they must not be longer.

Some hints:

• Since all of the words in the input file are the same length, you only need to process words of that length in the wordlist file.
  
• it would be wise to create a data structure whereby you can look up any particular word, and quickly find all its "neighbors" -- namely those words in the wordlist which are one character different from the one you've just looked up.  You might want to do this as your first task in the program.
  
• at some point in your algorithm, you might want to look up, very quickly, whether a word has already been "processed".  Since this is a yes/no question, perhaps a Python set (or some other hashed datatype) might do the job very fast.
  
• A* search might be very useful here: to find the shortest solution.

(4, ['hate', 'have', 'hove', 'love'])

Challenge problems  -- post answers to the WordLadder Challenge Problems homework slot:

1. See if you can find a really long 4-letter wordladder.  Post the longest one you can find to the comments-to-Teacher, giving its length and the ladder itself, like so:  ['11', 'abbe', 'able', 'ably', 'ally', 'alls', 'ails', 'aids', 'lids', 'lies', 'lied', 'tied'].  You should be able to find ladders longer than 11.
   
2. Same thing for longest 5-letter wordladders
   
3. Same thing for longest 6-letter wordladders
   
4. The wordladders we've constructed were always the shortest paths between two words.  Post the length of the longest path you can find between "head" and "tail" -- don't post all of the words.  But remember: there can be no duplicate words in the chain.

Post your results to the WordLadder Challenges GoogleSpreadsheet

[1551, ['hate', 'hath', 'bath', 'math', 'oath', 'path', 'pith', 'kith', 'with', 'wish', 'dish', 'fish', 'fist', 'gist', 'hist', 'mist', 'wist', 'wast', 'bast', 'cast', 'east', 'fast', 'hast', 'mast', 'past', 'vast', 'vest', 'best', 'fest', 'jest', 'nest', 'pest', 'rest', 'test', 'west', 'weft', 'deft', 'heft', 'haft', 'daft', 'raft', 'waft', 'wait', 'bait', 'gait', 'grit', 'writ', 'whit', 'chit', 'shit', 'skit', 'slit', 'alit', 'flit', 'flat', 'plat', 'slat', 'scat', 'seat', 'beat', 'feat', 'heat', 'meat', 'neat', 'peat', 'teat', 'that', 'chat', 'ghat', 'phat', 'shat', 'what', 'whet', 'when', 'then', 'teen', 'been', 'keen', 'peen', 'seen', 'ween', 'wean', 'bean', 'dean', 'jean', 'mean', 'mead', 'bead', 'dead', 'head', 'read', 'reed', 'deed', 'feed', 'geed', 'heed', 'meed', 'need', 'peed', 'seed', 'teed', 'weed', 'weld', 'geld', 'held', 'meld', 'veld', 'vend', 'bend', 'fend', 'mend', 'pend', 'rend', 'send', 'tend', 'wend', 'wand', 'band', 'hand', 'rand', 'sand', 'said', 'maid', 'paid', 'raid', 'rail', 'bail', 'fail', 'hail', 'jail', 'mail', 'nail', 'pail', 'sail', 'tail', 'wail', 'wall', 'ball', 'call', 'fall', 'gall', 'hall', 'mall', 'pall', 'tall', 'tell', 'bell', 'cell', 'dell', 'fell', 'hell', 'jell', 'sell', 'well', 'yell', 'yelp', 'help', 'kelp', 'keep', 'beep', 'deep', 'jeep', 'peep', 'seep', 'veep', 'weep', 'week', 'geek', 'meek', 'peek', 'reek', 'seek', 'seem', 'deem', 'teem', 'them', 'thew', 'chew', 'phew', 'shew', 'whew', 'whey', 'they', 'trey', 'grey', 'prey', 'pray', 'bray', 'dray', 'fray', 'gray', 'tray', 'troy', 'trod', 'prod', 'plod', 'clod', 'clad', 'glad', 'grad', 'brad', 'bred', 'bled', 'fled', 'pled', 'sled', 'shed', 'sped', 'aped', 'oped', 'owed', 'awed', 'abed', 'aced', 'iced', 'ices', 'aces', 'ages', 'ales', 'oles', 'odes', 'ides', 'ires', 'ares', 'ores', 'ones', 'opes', 'apes', 'awes', 'ewes', 'owes', 'owls', 'awls', 'ails', 'mils', 'nils', 'oils', 'oily', 'wily', 'winy', 'piny', 'tiny', 'ting', 'ding', 'king', 'ping', 'ring', 'sing', 'wing', 'wind', 'bind', 'find', 'hind', 'kind', 'mind', 'rind', 'rink', 'fink', 'kink', 'mink', 'oink', 'pink', 'sink', 'wink', 'wick', 'dick', 'hick', 'kick', 'nick', 'pick', 'rick', 'sick', 'tick', 'tack', 'back', 'hack', 'jack', 'pack', 'rack', 'sack', 'yack', 'yuck', 'buck', 'duck', 'fuck', 'muck', 'puck', 'suck', 'tuck', 'tusk', 'dusk', 'husk', 'musk', 'rusk', 'risk', 'disk', 'desk', 'deck', 'beck', 'heck', 'neck', 'peck', 'peak', 'beak', 'teak', 'weak', 'weal', 'deal', 'heal', 'meal', 'peal', 'real', 'seal', 'teal', 'veal', 'vial', 'dial', 'rial', 'rill', 'bill', 'dill', 'fill', 'gill', 'hill', 'kill', 'mill', 'pill', 'sill', 'till', 'will', 'wild', 'gild', 'mild', 'milk', 'bilk', 'silk', 'sulk', 'bulk', 'hulk', 'hunk', 'bunk', 'dunk', 'funk', 'gunk', 'junk', 'punk', 'sunk', 'sank', 'bank', 'dank', 'hank', 'rank', 'tank', 'yank', 'yang', 'bang', 'dang', 'fang', 'gang', 'hang', 'pang', 'rang', 'sang', 'tang', 'tans', 'bans', 'cans', 'fans', 'mans', 'pans', 'sans', 'vans', 'vats', 'bats', 'cats', 'eats', 'fats', 'hats', 'mats', 'oats', 'pats', 'rats', 'tats', 'tits', 'bits', 'fits', 'hits', 'kits', 'nits', 'pits', 'sits', 'wits', 'zits', 'zips', 'dips', 'hips', 'kips', 'nips', 'pips', 'rips', 'sips', 'tips', 'yips', 'yaps', 'caps', 'gaps', 'haps', 'maps', 'naps', 'paps', 'raps', 'saps', 'taps', 'tabs', 'cabs', 'dabs', 'gabs', 'jabs', 'nabs', 'nibs', 'bibs', 'dibs', 'fibs', 'jibs', 'ribs', 'rubs', 'bubs', 'cubs', 'dubs', 'hubs', 'nubs', 'pubs', 'subs', 'tubs', 'tugs', 'bugs', 'hugs', 'jugs', 'mugs', 'pugs', 'rugs', 'rags', 'bags', 'fags', 'gags', 'hags', 'jags', 'mags', 'nags', 'sags', 'tags', 'wags', 'wigs', 'digs', 'figs', 'gigs', 'jigs', 'pigs', 'rigs', 'rids', 'aids', 'bids', 'kids', 'kiss', 'diss', 'hiss', 'miss', 'piss', 'pass', 'bass', 'mass', 'sass', 'sacs', 'macs', 'mads', 'bads', 'cads', 'dads', 'fads', 'gads', 'pads', 'rads', 'tads', 'wads', 'weds', 'beds', 'feds', 'reds', 'recs', 'secs', 'sics', 'pics', 'tics', 'ties', 'dies', 'hies', 'pies', 'vies', 'vims', 'aims', 'dims', 'hims', 'rims', 'rams', 'cams', 'dams', 'hams', 'jams', 'tams', 'yams', 'yaks', 'oaks', 'oafs', 'oars', 'bars', 'cars', 'ears', 'gars', 'jars', 'mars', 'pars', 'tars', 'wars', 'ways', 'bays', 'cays', 'days', 'fays', 'gays', 'hays', 'jays', 'mays', 'nays', 'pays', 'rays', 'says', 'saws', 'caws', 'haws', 'jaws', 'maws', 'paws', 'raws', 'yaws', 'yews', 'dews', 'hews', 'mews', 'news', 'pews', 'sews', 'seas', 'peas', 'teas', 'yeas', 'yens', 'dens', 'fens', 'hens', 'kens', 'pens', 'tens', 'wens', 'wins', 'bins', 'dins', 'fins', 'gins', 'pins', 'sins', 'tins', 'tuns', 'buns', 'duns', 'funs', 'guns', 'nuns', 'puns', 'runs', 'suns', 'suds', 'buds', 'cuds', 'duds', 'muds', 'mums', 'bums', 'cums', 'gums', 'hums', 'rums', 'sums', 'sues', 'cues', 'dues', 'hues', 'rues', 'ryes', 'ayes', 'byes', 'dyes', 'eyes', 'ekes', 'eked', 'eyed', 'dyed', 'died', 'hied', 'pied', 'tied', 'tier', 'bier', 'pier', 'peer', 'beer', 'deer', 'jeer', 'seer', 'veer', 'weer', 'wear', 'bear', 'dear', 'fear', 'gear', 'hear', 'near', 'pear', 'rear', 'sear', 'tear', 'tsar', 'tzar', 'czar', 'char', 'chap', 'clap', 'flap', 'slap', 'snap', 'swap', 'swop', 'shop', 'chop', 'clop', 'flop', 'glop', 'plop', 'slop', 'stop', 'step', 'stem', 'item', 'idem', 'idea', 'ilea', 'flea', 'flew', 'blew', 'clew', 'slew', 'skew', 'spew', 'stew', 'stow', 'scow', 'show', 'chow', 'crow', 'brow', 'grow', 'prow', 'trow', 'trot', 'toot', 'boot', 'blot', 'clot', 'plot', 'slot', 'shot', 'snot', 'knot', 'knit', 'snit', 'smit', 'emit', 'omit', 'obit', 'obis', 'ibis', 'iris', 'irks', 'arks', 'asks', 'auks', 'yuks', 'yups', 'cups', 'pups', 'peps', 'reps', 'refs', 'rems', 'gems', 'hems', 'hers', 'herb', 'kerb', 'verb', 'very', 'aery', 'airy', 'miry', 'wiry', 'wary', 'nary', 'narc', 'nark', 'bark', 'dark', 'hark', 'mark', 'park', 'perk', 'perm', 'berm', 'germ', 'term', 'team', 'beam', 'ream', 'seam', 'scam', 'sham', 'wham', 'whim', 'shim', 'skim', 'slim', 'swim', 'swam', 'slam', 'clam', 'cram', 'dram', 'gram', 'pram', 'tram', 'trim', 'brim', 'grim', 'prim', 'prom', 'from', 'frog', 'flog', 'clog', 'slog', 'smog', 'smug', 'slug', 'plug', 'plum', 'alum', 'glum', 'slum', 'scum', 'scud', 'spud', 'stud', 'stub', 'snub', 'snob', 'knob', 'know', 'snow', 'slow', 'blow', 'flow', 'glow', 'plow', 'ploy', 'cloy', 'clay', 'flay', 'play', 'slay', 'shay', 'spay', 'stay', 'sway', 'swab', 'scab', 'slab', 'blab', 'flab', 'flub', 'club', 'chub', 'chug', 'thug', 'thud', 'thus', 'taus', 'taut', 'tact', 'fact', 'pact', 'pant', 'cant', 'rant', 'want', 'went', 'bent', 'cent', 'dent', 'gent', 'kent', 'pent', 'rent', 'sent', 'tent', 'tint', 'dint', 'hint', 'mint', 'pint', 'punt', 'aunt', 'bunt', 'cunt', 'hunt', 'runt', 'rust', 'bust', 'dust', 'gust', 'just', 'must', 'mutt', 'butt', 'putt', 'puts', 'cuts', 'guts', 'huts', 'juts', 'nuts', 'outs', 'ruts', 'tuts', 'tots', 'cots', 'dots', 'hots', 'jots', 'jets', 'bets', 'gets', 'nets', 'pets', 'sets', 'vets', 'wets', 'webs', 'wees', 'bees', 'fees', 'gees', 'pees', 'sees', 'tees', 'lees', 'lies', 'libs', 'labs', 'lacs', 'lads', 'lids', 'lips', 'laps', 'lags', 'legs', 'begs', 'kegs', 'keys', 'beys', 'buys', 'burs', 'curs', 'furs', 'firs', 'airs', 'sirs', 'sire', 'dire', 'dirk', 'dirt', 'girt', 'gift', 'rift', 'sift', 'silt', 'gilt', 'hilt', 'jilt', 'kilt', 'milt', 'tilt', 'wilt', 'welt', 'belt', 'felt', 'gelt', 'melt', 'pelt', 'pert', 'part', 'cart', 'dart', 'fart', 'hart', 'kart', 'mart', 'tart', 'wart', 'watt', 'matt', 'malt', 'halt', 'half', 'calf', 'calk', 'balk', 'talk', 'task', 'bask', 'cask', 'mask', 'mash', 'bash', 'cash', 'dash', 'gash', 'hash', 'rash', 'sash', 'wash', 'wasp', 'gasp', 'hasp', 'rasp', 'ramp', 'camp', 'damp', 'tamp', 'temp', 'hemp', 'hump', 'bump', 'dump', 'jump', 'pump', 'rump', 'sump', 'lump', 'lamp', 'limp', 'gimp', 'pimp', 'wimp', 'wisp', 'lisp', 'list', 'last', 'lest', 'lust', 'lush', 'bush', 'gush', 'hush', 'mush', 'push', 'puss', 'buss', 'cuss', 'fuss', 'muss', 'mess', 'mesa', 'mesh', 'mosh', 'bosh', 'gosh', 'josh', 'nosh', 'posh', 'pooh', 'poof', 'prof', 'prop', 'crop', 'drop', 'drip', 'grip', 'trip', 'trap', 'crap', 'crab', 'drab', 'grab', 'grub', 'drub', 'drug', 'drag', 'brag', 'crag', 'craw', 'draw', 'drat', 'brat', 'frat', 'fret', 'feet', 'beet', 'beef', 'reef', 'reel', 'feel', 'fuel', 'duel', 'dual', 'dull', 'bull', 'cull', 'full', 'gull', 'hull', 'mull', 'null', 'pull', 'purl', 'burl', 'curl', 'furl', 'hurl', 'hurt', 'curt', 'curb', 'curd', 'turd', 'turf', 'surf', 'serf', 'sera', 'sere', 'here', 'herd', 'hard', 'bard', 'card', 'ward', 'yard', 'yarn', 'barn', 'darn', 'earn', 'tarn', 'warn', 'wain', 'fain', 'gain', 'main', 'pain', 'rain', 'vain', 'lain', 'lawn', 'dawn', 'fawn', 'pawn', 'sawn', 'yawn', 'yawl', 'bawl', 'bawd', 'bald', 'balm', 'calm', 'palm', 'pals', 'gals', 'gels', 'eels', 'ells', 'alls', 'ills', 'ilks', 'inks', 'inns', 'ions', 'cons', 'dons', 'eons', 'hons', 'sons', 'tons', 'toes', 'does', 'foes', 'goes', 'hoes', 'noes', 'roes', 'woes', 'woks', 'woos', 'boos', 'bios', 'bros', 'bras', 'baas', 'bias', 'boas', 'bobs', 'cobs', 'fobs', 'gobs', 'hobs', 'jobs', 'mobs', 'robs', 'sobs', 'sods', 'bods', 'cods', 'gods', 'hods', 'mods', 'nods', 'pods', 'rods', 'rots', 'mots', 'pots', 'sots', 'sols', 'pols', 'pois', 'phis', 'chis', 'this', 'thin', 'chin', 'shin', 'skin', 'spin', 'span', 'scan', 'swan', 'swag', 'shag', 'slag', 'flag', 'flak', 'flan', 'clan', 'claw', 'flaw', 'flax', 'flex', 'flux', 'flus', 'flue', 'blue', 'blur', 'slur', 'spur', 'spar', 'scar', 'star', 'stab', 'stag', 'stat', 'spat', 'spit', 'suit', 'suet', 'sued', 'cued', 'hued', 'hoed', 'coed', 'toed', 'toad', 'goad', 'road', 'woad', 'wold', 'bold', 'cold', 'fold', 'gold', 'hold', 'mold', 'sold', 'told', 'toll', 'boll', 'doll', 'moll', 'poll', 'roll', 'roil', 'boil', 'coil', 'foil', 'moil', 'soil', 'toil', 'tool', 'cool', 'fool', 'pool', 'wool', 'wood', 'food', 'good', 'hood', 'mood', 'rood', 'roof', 'goof', 'hoof', 'woof', 'wolf', 'golf', 'gulf', 'guff', 'buff', 'cuff', 'duff', 'huff', 'muff', 'puff', 'ruff', 'riff', 'rife', 'fife', 'wife', 'wide', 'aide', 'bide', 'hide', 'ride', 'side', 'tide', 'tike', 'bike', 'dike', 'hike', 'mike', 'pike', 'peke', 'puke', 'duke', 'nuke', 'nude', 'dude', 'rude', 'rube', 'cube', 'tube', 'tuba', 'tuna', 'tune', 'dune', 'dung', 'bung', 'hung', 'rung', 'sung', 'lung', 'ling', 'link', 'lank', 'lack', 'lick', 'luck', 'lurk', 'lark', 'lard', 'laid', 'land', 'lend', 'lead', 'leaf', 'leak', 'lean', 'leap', 'leas', 'leis', 'lens', 'less', 'lass', 'lams', 'lama', 'lamb', 'limb', 'limn', 'lien', 'lion', 'loon', 'boon', 'coon', 'goon', 'moon', 'noon', 'soon', 'sown', 'down', 'gown', 'mown', 'town', 'torn', 'tern', 'turn', 'burn', 'burg', 'burp', 'burr', 'bury', 'fury', 'fumy', 'fume', 'fame', 'came', 'dame', 'game', 'name', 'same', 'tame', 'time', 'dime', 'mime', 'rime', 'rice', 'dice', 'mice', 'mica', 'pica', 'pita', 'vita', 'visa', 'viva', 'diva', 'dive', 'dine', 'fine', 'kine', 'mine', 'nine', 'pine', 'sine', 'tine', 'vine', 'vino', 'wino', 'wine', 'wane', 'bane', 'bate', 'date', 'fate', 'gate', 'mate', 'pate', 'rate', 'sate', 'site', 'bite', 'cite', 'kite', 'mite', 'nite', 'rite', 'wite', 'wile', 'bile', 'file', 'film', 'firm', 'farm', 'harm', 'warm', 'warp', 'carp', 'harp', 'tarp', 'taro', 'tiro', 'tyro', 'typo', 'hypo', 'hype', 'type', 'tape', 'cape', 'gape', 'jape', 'nape', 'rape', 'ripe', 'pipe', 'wipe', 'wire', 'fire', 'hire', 'mire', 'tire', 'tare', 'bare', 'care', 'dare', 'fare', 'hare', 'mare', 'pare', 'rare', 'ware', 'were', 'mere', 'mete', 'mute', 'cute', 'cure', 'pure', 'pyre', 'tyre', 'tyke', 'take', 'bake', 'cake', 'fake', 'hake', 'make', 'rake', 'sake', 'wake', 'wade', 'bade', 'fade', 'jade', 'made', 'mace', 'dace', 'face', 'pace', 'race', 'racy', 'lacy', 'lady', 'lazy', 'hazy', 'haze', 'daze', 'faze', 'gaze', 'maze', 'raze', 'rage', 'raga', 'gaga', 'saga', 'sago', 'sage', 'cage', 'gage', 'page', 'wage', 'wale', 'bale', 'dale', 'gale', 'hale', 'kale', 'male', 'pale', 'sale', 'tale', 'vale', 'vile', 'mile', 'pile', 'rile', 'rule', 'mule', 'muse', 'fuse', 'ruse', 'rise', 'vise', 'vase', 'base', 'case', 'cafe', 'safe', 'sane', 'cane', 'mane', 'pane', 'vane', 'lane', 'line', 'lint', 'lent', 'left', 'lift', 'lilt', 'lily', 'limy', 'limo', 'lime', 'lame', 'lace', 'lice', 'nice', 'vice', 'vibe', 'gibe', 'jibe', 'jive', 'five', 'give', 'hive', 'rive', 'wive', 'wave', 'wavy', 'navy', 'nave', 'cave', 'eave', 'gave', 'have', 'pave', 'rave', 'save', 'lave', 'love']]