#!/usr/bin/env python3
from collections import deque

def masks(w):
    '''Return a generator that iterates through all of the masked verions of the word where
    each letter is replaces with a *. E.g. 'few' -> ['*ew', 'f*w', 'fe*']

    '''
    for i in range(len(w)):
        w2 = w[:i] + '*' + w[i+1:]
        yield w2

def valid(w):
    '''Return whether or not the word seems valid (no punctuation, first letter isn't caps)'''
    return all([ 'a' <= c <= 'z' for c in w.strip()])

def preproccess(wordfile):
    '''Given a filename that contains one word per line, return a dictionary which contains each 'mask' as a key
    and every possible word that mask represents as a value. E.g. 'he*d' -> ['head', 'held', 'herd']. TODO:
    prune this to remove single-entry keys which aren't helpufl.
    '''
    words = {}
    with open(wordfile, 'r') as infile:
        raw = [w.strip() for w in infile.readlines() if valid(w)]
        for w in raw:
            for w2 in masks(w):
                if w2 not in words:
                    words[w2] = []
                words[w2].append(w)
    return words

def search(start, goal, wordfile):
    '''Find a shortest path from goal to start using the given wordfile. Each step in the path involves swapping
    exactly one letter and creating another word from the list
    '''
    words = preproccess(wordfile)
    print('loadded wrods, searching...')
    q = deque([goal])  # BFS queue, start at the start and work backwards.
    bp = {}  # "back-pointers" to keep track of the parent node to reconstruct the path at the end.
    bp[goal] = None
    num = 0
    done = False
    while q and not done:
        w = q.popleft()
        num += 1
        for e in masks(w):
            if e not in words:
                print(f"ERROR bad key {e}")
                continue
            for w2 in words[e]:
                if w2 in bp or w2 == w:
                    continue
                bp[w2] = w
                if w2 == start:
                    done = True
                    break
                q.append(w2)
            if done:
                break

    if start in bp:
        print(f"found solution in {num} expansions of BFS:\n")
        curr = start
        while curr != goal:
            print(curr,'  ')
            curr = bp[curr]
        print(goal, '  ')
    else:
        print(f"no solution in {num}")

def combine(infiles, outfile):
    '''Utility function to open multiple word lists (infiles array) and store the intersection of valid words in the outfile'''
    s = None
    for f in infiles:
        with open(f, 'r') as infile:
            words = set([w.strip() for w in infile.readlines() if valid(w)])
            if s:
                s = s.intersection(words)
            else:
                s = words

    with open(outfile, 'w') as out:
        for w in s:
            out.write(w + "\n")

if __name__ == "__main__":
    import argparse
    parser = argparse.ArgumentParser(description="Solve Lewis Carroll's Doublet Puzzles")
    parser.add_argument('wordfile', metavar = 'filename.txt', help='filename holding all words seperated by a newline')
    parser.add_argument('start', metavar = 'FROM')
    parser.add_argument('goal', metavar = 'TO')
    args = parser.parse_args()

    search(args.start, args.goal, args.wordfile)