# Programmer: 22C:16 class
# Date: 4/4/12
# Version 3 
# This program reads a list of 5-letter words from a file called words.dat. It then builds a dictionary
# of these words. Each word is a key in the dictionary. The neighbors of a word w are all those words that
# differ from it in exactly one letter. The value associated with a key w in the dictionary is the list
# of neighbors of that word. The program then reads two 5-letter words: source and target and explores
# the dictionary to find a path (if one exists) between the source and target.

import time

# Two words are neighbors if they differ in exactly on letter.
# This function returns True if a given pair of words are neighbors
def areNeighbors(w1, w2):
    count = 0
    for i in range(len(w1)):
        if w1[i] != w2[i]:
            count = count + 1
    
    return count == 1

# The function reads from the file "words.dat" and inserts the words that are read
# into a list. The words are also inserted into a dictionary as keys, with each key 
# initialized to have [] as its value.
def readWords(wordList, D):
    fin = open("words.dat", "r")

    # Loop to read words from the and to insert them in a list
    # and in a dictionary
    for word in fin:
        newWord = word.strip("\n")
        wordList.append(newWord)
        D[newWord] = []

    fin.close()
    

# Builds the network of words using a dictionary. Two words are connected by an edge in this
# network if they are neighbors of each other, i.e., if they differ from each
# other in exactly one letter.
def buildDictionary(wordList, D):
    numPairs = 0
    # Nested for loop to generate pairs of words
    for i in range(len(wordList)):
        for j in range(i+1, len(wordList)):
            # Check if the two generated words are neighbors
            # if so append word2 to word1's neighbor list and word1 to word2's neighbor list
            if areNeighbors(wordList[i], wordList[j]):
                D[wordList[i]].append(wordList[j])
                D[wordList[j]].append(wordList[i])
    
# Main program
wordList = []
D = {}
readWords(wordList, D)
buildDictionary(wordList, D)

# Compute the largest degree
m = max(map(len, D.values()))

# Initialize the degree distribution
degreeDist = {}
for degree in range(m+1):
    degreeDist[degree] = 0

# Walk through each word in the word network dictionary D
# and increment the frequency of the degrees encountered.
for k in D:
    degree = len(D[k]) # degree is the degree of word k
    degreeDist[degree] = degreeDist[degree] + 1

# Prints the degrees and their frequencies
degreeDistList = degreeDist.items()
degreeDistList.sort()
for item in degreeDistList:
    print item[0], item[1]