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, called "dictall.txt" (you should download this).  You must use this wordlist for this problem.  While you are developing the program, place this wordlist file in the parent directory/folder of the one containing your Python code, so that you can open the file using the Python statement:  f=open('dictall.txt','r'). When your program is eventually tested on the homework server, the dictall.txt file will be in the parent directory of the one in which your program will be placed for testing.

On the command-line your program will be called with 2 arguments: an inputfilename and an outputfilename.  The input file will be a text file containing a set of lines.  Each line will have two words separated by a comma.  Every word in the input file will be contained in the dictall.txt file, and all of them with have the same length.  For each line, create the shortest wordladder (if possible) between the two words, and write the ladder: sequence of words with commas to separate them, to the output file.  So, as an example:

If there is no ladder between the two words, just write the two input words, as in the line "head,ache" below.

Of course, the program tester will have a larger set of word pairs (possibly all longer or all shorter than 4 letters) and more difficult ones.  Nevertheless, you'll have no more than 3 seconds of CPU time (plenty if your program is efficient).

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.

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.

[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']]