
# def add(x, y):
#     return(x + y)
# We don't need this anymore. We just had it to test the unittest TestCase.

from string import ascii_uppercase
from random import choice

# Functions are like machines. Something goes in and something comes out. In this example, cols and rows go in and a dictionary comes out.
def make_grid(columns, rows):
    return {(c, r) : choice(ascii_uppercase) 
                        for r in range(rows) 
                            for c in range(columns)} # This is a nested loop.

# In this example, a postion, a tupple goes in and a list comes out.
def potential_neighbours(position):
    c, r = position
    return [(c-1, r-1), (c, r-1),  (c+1, r-1), 
            (c-1, r),              (c+1, r), 
            (c-1, r+1), (c, r+1),  (c+1, r+1)] # This list data structure is just for visual purposes to see the potential neighbours of a tupple, which is why there is a space in the middle.  # "set" as a data structure will also work here.

# Take in a path, wander through the grid...do we have a word? Return that word.            
def path_to_word(path, grid):
    word = ""
    for position in path: # Loop through path, data type list.
        word += grid[position] # Match position in path list to position in grid dictionary and create string. 
    return word # Return string of letters.
    
# Look up that word in our reference file.    
def load_word_list(filename):
    with open(filename) as f: # We use variable filename instead of "words.txt" so that we can use this function again to call any filname, see below.
        text = f.read().upper().split("\n") # .upper() pulls in the file name in upper case - see above ascii is uppercase means the letters in the grid are uppercase.
    return text    
    
# words = load_word_list("words.txt")

# Real neighbours that are on the grid. This is a pre-calculation that stores all real neighbours in a dictionary as a look up. If you had to run a function to do this calculation ever time there has an entry there would be a performance lag, so the calculation is done up front.
def get_real_neighbours(grid): 
    real_neighbours = {}
    
    for position in grid:
        pn = potential_neighbours(position) # Look up all 8 potentional neighbours generated by the potential_neighbours function.
        
        # on_the_grid = []
        # for p in pn:
        #     if p in grid:
        #         on_the_grid.append(p)
            
        # With list comprehension, it is also written as;
        on_the_grid = [ p for p in pn if p in grid] # ... see if those potential neighbours are on the grid.
        
        real_neighbours[position] = on_the_grid
        
    return real_neighbours    

# This is the search function.
def search(grid, dictionary):
    neighbours = get_real_neighbours(grid)
    paths = []
    
    def do_search(path):
        word = path_to_word(path, grid)
        if word in dictionary:
            paths.append(path)
        for next_pos in neighbours[path[-1]]:
            if next_pos not in path:
                do_search(path + [next_pos])
    
    for position in grid:
        do_search([position])
        
    words = []
    for path in paths:
        words.append(path_to_word(path, grid))
    return set(words)    
    
# This is the display results function (i.e. "Found 4 words").
def display_words(words):
    for word in words:
        print(word)
    print("Found %s words" % len(words))
    
# Main function. 3 by 3 takes about 4 secs to load. 4 by 4 takes a good bit more time. Not advisable to go beyond that.
def main():
    grid = make_grid(3, 3)
    word_list = load_word_list("words.txt")
    words = search(grid, word_list)
    display_words(words)

main() 

# Type python3 -m cProfile boggle.py into the terminal. 