Word Ladder

Word Ladder

Find path from one word to another, changing one letter each step, and each intermediate word must be in the dictionary, the dictionary is a text file with words separated by a line break like the one found in /usr/share/dict/words

Prerequisites

  • Python 3.4 and Linux
  • List of words separated by newlines
  • Virtual environment is recommended

Installing

From PyPi

$ pip install word-ladder

Manually

Clone the repository (Pypi package comming soon)

$ git clone git@github.com:snebel29/word_ladder.git
$ cd word_ladder
$ pip install .

to install development dependencies as well

$ pip install -e .[dev]

Getting started

The word_ladder packges commes with both, a command line tool and a module that can be used to find word ladder paths

Command line tool

Once installed you can use the command line interface

$ word_ladder -h

Python module

You can import and use the module directly as well

>>> from word_ladder import WordLadder
>>> wl = WordLadder('tests/word_lists/linux_english_words')
>>> wl.find_path('fear', 'sail')
['fear', 'hear', 'heir', 'hair', 'hail', 'sail']
>>> wl.find_path('Abe', 'sail')
['Abe', 'be', 'bed', 'bid', 'aid', 'said', 'sail']
>>> wl.find_path('Am', 'sail')
['Am', 'am', 'aim', 'ail', 'sail']

Running the tests

You will have to use nose to run the tests

$ nosetests

Contributing

Clone development branch then create pull requests against it

word_ladder CLI

Installing this package provides a command line interface which one is better describer with its CLI help

$ word_ladder -h

will output

Word ladder

Usage:
  word_ladder from <from> using <dict_file> [-a]
  word_ladder from <from> to <to> using <dict_file> [-a]
  word_ladder -h | --help
  word_ladder -v | --version

Subcommands:
  from              The initial word
  to                The word to stop [Optional]

Options:
  -a, --all-paths    Print all paths
  -h, --help         Show this screen
  -v, --version      Show version

Examples:
  word_ladder from word1 using /english.dict
  word_ladder from word1 using /english.dict --all-paths
  word_ladder from word1 to word2 using /english.dict -a

word_ladder package

Submodules

word_ladder.errors module

exception word_ladder.errors.WordsNotDefined

Bases: Exception

word_ladder.word_ladder module

class word_ladder.word_ladder.Graph(words)

Bases: object

Represents an un-weigthed graph structure with connected words

Parameters:words (iterable) – Words to build the graph with
build(all_lengths=True)

Build the graph

Parameters:all_lengths (bool, optional) – Define if the graph should connect words with different lengths
Returns:dict with the graph structure
class word_ladder.word_ladder.WordLadder(dictionary, start=None, end=None)

Bases: object

Represents a word ladder

Parameters:
  • dictionary (list or str) – Feed with words
  • start (str, optional) – The starting word, Defaults to None
  • end (str, optional) – The ending word, Defaults to None
find_path(start=None, end=None, all_paths=False)

Find the word ladder path

Parameters:
  • start (str, optional) – The starting word, Defaults to None
  • end (str, optional) – The ending word, Defaults to None
  • all_lengths (bool, optional) – Define if the graph should connect words with different lengths
Raises:

WordsNotDefined – If any of the words is None
Returns:

With the word’s path or None
Return type:

(list)
graph

Holds an instance of Graph with the dictionary words

Note

when setting words an internal hash value is created for caching purpose, so we don’t process the grah again if there is a serialzed version of the graph object

Returns:The graph memoized instance
Return type:(Graph)
tmp = ‘/tmp’
words

Holds the list of words

Returns:(list) The list of words
words_has_same_length()

Compare length of start and end words

Returns:(bool or None) True, False or None)