#!/usr/bin/python
# vim:fileencoding=utf-8

from collections import defaultdict


class RuleOrganizer(object):

    def __init__(self, field_lengths):
        self.field_lengths = field_lengths
        self.rules_by_field = defaultdict(list)

    def cross_fields(self, other_field, other_letter, own_field, own_letter):
        if other_field > own_field:
            other_field, own_field = own_field, other_field
            other_letter, own_letter = own_letter, other_letter
        crossing = {'other_field': other_field,
                        'other_letter': other_letter,
                        'own_letter': own_letter}
        newrule = (self.field_lengths[own_field], crossing)
        self.rules_by_field[own_field].append(newrule)


class Vertex(object):
    def __init__(self, depth, parent, CWR):
        self.depth = depth
        self.parent = parent
        self.CWR = CWR
        self.children = []


def create_vocabulary(filename):
    with open(filename, 'r') as f:
        vocabulary = f.read().split()
    return vocabulary


def solve_CWR(vertex, indexed_vocab_dict, rules):
    if vertex.depth == len(rules):
        return
    rule = rules[vertex.depth+1]
    vocabulary = set()
    length, crossing = rule[0]
    indexed_vocab = indexed_vocab_dict[length]
    for length, crossing in rule:
        index = crossing['own_letter']
        letter = vertex.CWR[crossing['other_field']][crossing['other_letter']]
        if vocabulary:
            vocabulary.intersection_update(indexed_vocab[index][letter])
        else:
            vocabulary = set(indexed_vocab[index][letter])

    for word in vocabulary:
        CWR = vertex.CWR[:]
        CWR.append(word)
        newchild = Vertex(vertex.depth+1, vertex, CWR)
        vertex.children.append(newchild)
        solve_CWR(newchild, indexed_vocab_dict, rules)


def print_solutions(vertex):
    if vertex.depth == 3:
        print vertex.CWR
        return
    for child in vertex.children:
        print_solutions(child)


def count_solutions(vertex, c, depth):
    if vertex.depth == depth:
        return c+1
    for child in vertex.children:
        c = count_solutions(child, c, depth)
    return c


def index_vocabulary(vocabulary):
    indexed_vocab = []
    for word in vocabulary:
        for i, letter in enumerate(word):
            try:
                d = indexed_vocab[i]
                d[letter].append(word)
            except IndexError:
                d = defaultdict(list)
                d[letter].append(word)
                indexed_vocab.append(d)
    return indexed_vocab

if __name__ == '__main__':
    import random
    from time import time

    vocabulary = create_vocabulary('./threes.txt')
    rind = (random.randint(0, len(vocabulary)-1) for i in xrange(500))
    vocabulary = [vocabulary[i] for i in rind]
    indexed_vocab = index_vocabulary(vocabulary)
    indexed_vocab_dict = {3: indexed_vocab}

    rules = RuleOrganizer([3, 3, 3, 3])
    rules.cross_fields(other_field=0, other_letter=2, own_field=1, own_letter=0)
    rules.cross_fields(other_field=1, other_letter=2, own_field=2, own_letter=2)
    rules.cross_fields(other_field=3, other_letter=2, own_field=2, own_letter=0)
    rules.cross_fields(other_field=0, other_letter=0, own_field=3, own_letter=0)

    CWR = [vocabulary[random.randint(0, len(vocabulary)-1)]]
    root = Vertex(0, None, CWR)
    t0 = time()
    solve_CWR(root, indexed_vocab_dict, rules.rules_by_field)
    t1 = time()
    #print_solutions(root)
    c = count_solutions(root, 0, 3)
    print t1-t0, c