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

Documentation¶

http://word-ladder.readthedocs.io/en/latest/

Installing¶

Clone the repository (Pypi package comming soon)

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

Production¶

$ pip install .

Development¶

$ 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

References¶

https://bradfieldcs.com/algos/graphs/word-ladder/

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

Returns:	The graph memoized instance
Return type:	(`Graph`)

words_has_same_length()¶

Compare length of start and end words

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