#!/usr/bin/python2.7

### IMPORTS ###

import math, random, datetime
from string import ascii_uppercase

try:
    import Image
except ImportError:
    from PIL import Image

import pytesseract

### CLASSES ###

#self.pos_list = [(-1,-1),(1,-1),(-1,1),(1,1)]
class WordSearch(object):
    '''
    Base Wordsearch class - all functions for building and solving wordsearches
    '''
    def __init__(self, string="", matrix=None, size=(0,0), words=[], difficulty="EASY"):
        super(WordSearch, self).__init__()
        self.string = string
        self.matrix = matrix
        self.cols = size[0]
        self.rows = size[1]
        self.words = words
        self.difficulty = difficulty
    
    def __str__(self):
        return "Wordsearch object with %d columns and %d rows" % (self.cols, self.rows)
    
    def is_valid(self):
        return self.cols*self.rows==len(self.string)
    
    def get_from_image(self, image):
        ws_string = pytesseract.image_to_string(Image.open(image))
        ws_str_list = ws_string.split('\n')
        self.string=""
        for s in ws_str_list:
            _s = ""
            self.string+=_s.join(s)
        print self.string
        ws_matrix=[]
        for s in ws_str_list:
            if len(s)>0:
                t=list(s)
                ws_matrix.append(t)
        self.matrix = ws_matrix
        self.rows = len(ws_matrix)
        self.cols = len(ws_matrix[0])
        return
     
    def size_valid(self):
        for word in self.word:
            if len(word)>self.cols and len(word)>self.rows:
                return False
        return True
     
        
    def align_select(self, word):
        '''
        Randomly select alignment, direction and position of word. Returns list of
        potential coordinates in wordsearch matrix.
        '''
        width, height = self.cols, self.rows
        if len(word)>width or len(word)>height:
            return    
        
        align = random.choice(['horizontal', 'vertical', 'diagonal'])
        hdir = random.choice(['forward', 'backward'])
        vdir = random.choice(['up','down'])
        if align == 'horizontal':
            vdir = None
            row_range = range(0, height-1)
            if hdir=='forward':
                col_range = range(0, width-(len(word)-1))
            else:
                col_range = range(len(word)-1, width)
        elif align == 'vertical':
            hdir = None
            col_range = range(0, width-1)
            if vdir=='down':
                row_range = range(0, height-(len(word)-1))
            else:
                row_range = range(len(word)-1, height)
        else:
            if vdir=='down':
                row_range = range(0, height-(len(word)-1))
            else:
                row_range = range(len(word)-1, height)
            if hdir=='forward':
                col_range = range(0, width-(len(word)-1))
            else:
                col_range = range(len(word)-1, width)
                
        start_row = random.choice(row_range)
        start_col = random.choice(col_range)
        
        if align=='horizontal':
            if hdir=='forward':
                pos=(0,1)
            else:
                pos=(0,-1)
        elif align=='vertical':
            if vdir=='down':
                pos=(1,0)
            else:
                pos=(-1,0)
        else:
            if vdir=='down' and hdir=='forward':
                pos=(1,1)
            elif vdir=='up' and hdir=='backward':
                pos=(-1,-1)
            elif vdir=='down' and hdir=='backward':
                pos=(1,-1)
            elif vdir=='up' and hdir=='forward':
                pos=(-1,1)
        '''
        print '\nWord: ' + word
        print 'Alignment: ' + align
        print 'HDir: ' + str(hdir)
        print 'VDir: ' + str(vdir)
        print 'Start: ' + str((start_row,start_col))
        print 'Direction: ' + str(pos)
        '''
        
        cursor=(start_row,start_col)
        pos_buffer = [cursor]
        for i in range(len(word)-1):
            cursor=tuple(map(sum,zip(cursor,pos)))
            pos_buffer.append(cursor)
        return pos_buffer

    def create(self):
        '''
        Randomly builds square word search of length/height size using the words in
        word_list. Alignment/direction/position of each word randomly selected. If
        word cannot be placed into matrix due to presense of previous word, random 
        selection made again
        '''
        width, height = self.cols, self.rows
        ws = []
        for unused in range(height):
            ws.append([])
        for _row in ws:
            for unused in range(width):
                _row.append(' ')
        total_spaces=width*height
        total_letter_count=0
        used_letters={}
        all_letters=ascii_uppercase
        for letter in all_letters:
            used_letters[letter]=0
        for word in self.words:
            word=word.upper()
            for letter in word:
                used_letters[letter]+=1
                total_letter_count+=1
            
            complete=False
            failed=0
            while complete!=True:
                if failed>=100:
                    print "Cannot be done"
                    return
                clash=False
                alignment = self.align_select(word)
                #print alignment
                i=0
                for row,col in alignment:
                    if ws[row][col]!=' ':
                        if ws[row][col]!=word[i]:
                            clash=True
                        #print 'Clash: ' + str((row,col))
                    i+=1
                if clash==False:
                    j=0
                    for row,col in alignment:
                        ws[row][col]=word[j]
                        j+=1
                    complete=True
                    break
                else:
                    failed+=1
        for row in ws:
            print row
        print '\n'

        empty_spaces = total_spaces - total_letter_count
        letter_choice_list = []
        if self.difficulty.upper()=='EASY':
            for _letter in all_letters:
                letter_choice_list.append(_letter)
        elif self.difficulty.upper()=='HARD':
            #print used_letters
            #print total_letter_count
            for letter in used_letters:
                #print letter + ' : ' + str(used_letters[letter])
                frequency = (float(used_letters[letter])/float(total_letter_count))*100
                #print frequency
                for i in range(int(frequency)):
                    letter_choice_list.append(letter)
        else:
            for _letter in all_letters:
                letter_choice_list.append(_letter)
        for j in range(height):
            for k in range(width):
                if ws[j][k]==' ':
                    ws[j][k]=random.choice(letter_choice_list)
        self.string=""
        for row in ws:
            print row
            for letter in row:
                self.string+=letter
        self.matrix = ws
        return
        
    def surrounding_letters(self, pos):
        '''
        Takes a wordsearch (ws), represented as a square matrix of letters, and a 
        position (pos)(row, column) starting from 0, as inputs.
        Returns 2 lists:
            i.  the row of 3 letters above and below letter at position pos. if
                positioned at edge of matrix, 2 letters returned from each row.
            ii. the corresponding positions of those letters based on the original
                letter at pos
        '''
        ws = self.matrix
        row,column=pos
        letter = ws[row][column]
        pos_list = [(-1,-1),(1,-1),(-1,1),(1,1)]
        final_pos_list = pos_list
        result=[]

        if column==0:
            if row==0:
                result.append(ws[row+1][column+1])
                final_pos_list = [(1,1)]
            elif row>=len(ws)-1:
                result.append(ws[row-1][column+1])
                final_pos_list=[(-1,1)]
            else:
                result.append(ws[row-1][column+1])
                result.append(ws[row+1][column+1])
                final_pos_list = pos_list[2:]
        elif column+1==len(ws[row]):
            if row==0:
                result.append(ws[row+1][column-1])
                final_pos_list = [(1,-1)]
            elif row>=len(ws)-1:
                result.append(ws[row-1][column-1])
                final_pos_list=[(-1,-1)]
            else:
                result.append(ws[row-1][column-1])
                result.append(ws[row+1][column-1])
                final_pos_list = pos_list[:2]
        else:
            if row==0:
                result.append(ws[row+1][column-1])
                result.append(ws[row+1][column+1])
                final_pos_list = [(1,-1),(1,1)]
            elif row>=len(ws)-1:
                result.append(ws[row-1][column-1])
                result.append(ws[row-1][column+1])
                final_pos_list=[(-1,-1),(-1,1)]
            else:
                result.append(ws[row-1][column-1])
                result.append(ws[row+1][column-1])
                result.append(ws[row-1][column+1])
                result.append(ws[row+1][column+1])
        return result, final_pos_list

    def get_columns(self):
        '''
        Returns the columns of a wordsearch matrix as individual strings
        '''
        ws = self.matrix
        result = []
        for unused in range(len(ws)):
            result.append([])
        for i in range(len(ws)):
            for row in ws:
                result[i].append(row[i])
        return result

    def find_word(self, _word):
        '''
        Locates a word in a given wordsearch (ws). Wordsearch must be square matrix 
        and word must have at least 3 letters. Returns position of word in matrix 
        as a list of coordinates (tuples). If word not in wordsearch, returns None
        '''
        ws = self.matrix
        coordinates = []
        print '\n'
        word=_word.replace(' ','').upper()
        print word
        first = word[0]
        second = word[1]
        third = word[2]
        for row in ws:
            #assert len(row)==len(ws)
            row_num = ws.index(row)
            #print "row " + str(row_num)
            row_string = ''.join(row).upper()
            if word in row_string: 
                print "Horizontal (Forwards): Row " + str(row_num)
                #print row_string
                #print row_string.find(word)
                for _col in range(row_string.find(word), row_string.find(word)+len(word)):
                    coordinates.append((row_num, _col))
                return coordinates
            elif word in row_string[::-1]:
                print "Horizontal (Backwards): Row " + str(row_num)
                for _col in range(row_string.find(word[::-1]), row_string.find(word[::-1])+len(word)):
                    coordinates.append((row_num, _col))
                coordinates.reverse()
                return coordinates
        columns = self.get_columns()
        for column in columns:
            col_num = columns.index(column)
            col_string = ''.join(column).upper()
            if word in col_string: 
                print "Vertical (Down): Column " + str(col_num)
                for _row in range(col_string.find(word), col_string.find(word)+len(word)):
                    coordinates.append((_row, col_num))
                return coordinates
            elif word in col_string[::-1]:
                print "Vertical (Up): Column " + str(col_num)
                for _row in range(col_string.find(word[::-1]), col_string.find(word[::-1])+len(word)):
                    coordinates.append((_row, col_num))
                coordinates.reverse()	
                return coordinates
        for row in ws:
            row_num=ws.index(row)
            x=-1
            for letter in row:
                x+=1
                col_num = x
                cursor = (row_num,col_num)
                y=-1
                if letter==first:
                    start_cursor=cursor
                    coordinates.append(start_cursor)
                    #print ("First: ", start_cursor)
                    surrounding, positions = self.surrounding_letters(cursor)
                    #print surrounding
                    for surrounding_letter in surrounding:
                        y+=1
                        if surrounding_letter==second:
                            direction = (vertical, horizontal) = positions[y]
                            direction_back = (-vertical,-horizontal)
                            #print direction
                            cursor=tuple(map(sum,zip(cursor,direction)))
                            coordinates.append(cursor)
                            #print ("Second: ", cursor)
                            rest_of_word=''
                            for z in range(len(word)-2):
                                cursor=tuple(map(sum,zip(cursor,direction)))
                                coordinates.append(cursor)
                                r,c = cursor
                                rest_of_word+=ws[r][c]
                            if rest_of_word == word[2:]:
                                print "Diagonal: Starts at %s" % str(start_cursor)
                                return coordinates
                            else:
                                coordinates=coordinates[:2]
                        else:
                            coordinates=[start_cursor]
                    if len(coordinates)==1:
                        coordinates=[] 
                else:
                    coordinates=[]
        print "Not Found"
        return None 

class WordSearchBuilder(WordSearch):
    '''
    Wordsearch builder class for creating wordsearch puuzzles
    '''
    def __init__(self, difficulty="EASY"):
        super(WordSearchBuilder, self).__init__()
        self.difficulty = difficulty
    
    def __str__(self):
        return "Wordsearch Builder object with %s difficulty" % self.difficulty.lower()
        
#ws_build = WordSearchSolver()
#print ws_build

class WordSearchSolver(WordSearch):
    '''
    Wordseach solver class for solving wordsearch puzzles
    '''
    def __init__(self):
        super(WordSearchSolver, self).__init__()
    
    def __str__(self):
        return "Wordsearch Solver object"

#ws_solve = WordSearchSolver()
#print ws_solve



