description of game

word-ladder-game

from Vertex import Vertex
from Graph import Graph

def main():
    wordList = ["foul", "foil", "fool", "fail", "fall", "pall",
                "poll", "pole", "pool", "cool", "pope", "pale",
                "sale", "page", "sage"]
    

We will be given a list of words and and two words from the same list.

we have to find shortest path from source to destination

We get all matching words like this :

{
'oul': ['foul'],
'f_ul': ['foul'],
'fo_l': ['foul', 'foil', 'fool'],
'fou': ['foul'], 'oil': ['foil'],
'f_il': ['foil', 'fail'],
'foi': ['foil'],
'ool': ['fool', 'pool', 'cool'],
'f_ol': ['fool'],
'foo': ['fool'],
'ail': ['fail'],
'fa_l': ['fail', 'fall'],
'fai': ['fail'],
'all': ['fall', 'pall'],
'f_ll': ['fall'],
'fal': ['fall'],
'p_ll': ['pall', 'poll'],
'pa_l': ['pall'],
'pal_': ['pall', 'pale'],
'oll': ['poll'],
'po_l': ['poll', 'pool'],
'pol': ['poll', 'pole'],
'ole': ['pole'],
'p_le': ['pole', 'pale'],
'po_e': ['pole', 'pope'],
'p_ol': ['pool'],
'poo': ['pool'],
'c_ol': ['cool'],
'co_l': ['cool'],
'coo_': ['cool'],
'ope': ['pope'],
'p_pe': ['pope'],
'pop': ['pope'],
'ale': ['pale', 'sale'],
'pa_e': ['pale', 'page'],
's_le': ['sale'],
'sa_e': ['sale', 'sage'],
'sal': ['sale'],
'age': ['page', 'sage'],
'p_ge': ['page'],
'pag': ['page'],
's_ge': ['sage'],
'sag_': ['sage']
}

From the above one we get all the words that are differed by only one letter. Then travel through the values and build edges with each of them.

That's it Graph is built.

Finally after graph is built the output graph looks like this :

foul {'foil': 0, 'fool': 0}
foil {'foul': 0, 'fool': 0, 'fail': 0}
fool {'foul': 0, 'foil': 0, 'pool': 0, 'cool': 0}
fail {'foil': 0, 'fall': 0}
pool {'fool': 0, 'cool': 0, 'poll': 0}
cool {'fool': 0, 'pool': 0}
fall {'fail': 0, 'pall': 0}
pall {'fall': 0, 'poll': 0, 'pale': 0}
poll {'pall': 0, 'pool': 0, 'pole': 0}
pale {'pall': 0, 'pole': 0, 'sale': 0, 'page': 0}
pole {'poll': 0, 'pale': 0, 'pope': 0}
pope {'pole': 0}
sale {'pale': 0, 'sage': 0}
page {'pale': 0, 'sage': 0}
sage {'sale': 0, 'page': 0}