GitHub - agarwala95/Ladder: Ladders is a word game where a player tries to get from one word ("start word") to another ("goal word") in as few steps as possible. In each step, the player must either add one letter to the word from the previous step, or take away one letter, and then rearrange the letters to make a new word.

agarwala95 / Ladder Public

Notifications You must be signed in to change notification settings
Fork 0
Star 0

Ladders is a word game where a player tries to get from one word ("start word") to another ("goal word") in as few steps as possible. In each step, the player must either add one letter to the word from the previous step, or take away one letter, and then rearrange the letters to make a new word.

0 stars 0 forks Branches Tags Activity

Star

Notifications

Branches Tags

Name		Name	Last commit message	Last commit date
Latest commit History 2 Commits
ladders.py		ladders.py
output_1.txt		output_1.txt
output_2.txt		output_2.txt
output_3.txt		output_3.txt
output_4.txt		output_4.txt
readme.txt		readme.txt
requirements.txt		requirements.txt
wordList.txt		wordList.txt

Repository files navigation

Problem 1.1 Ladders

I used Python 3.5.4 for the assignment. My solution is breadth first search. This method searches for the goal word at every level of the tree and then returns the previous nodes till the start word.

To easily traverse through the word file, I have used a hashing function where I denote each word with a hash value. This reduces the time to search
for a word. Also, only those words with the same letters/characters but with different order of characters have the same hash value.
I find the connecting nodes for a word using the function children() function. This connects each word to all words that can be obtained by adding a letter
or subtracting a letter.

I have used the following packages:
string
collections : defaultdict
queue : Queue
sys