#!/usr/bin/env python

# Generate a word search grid from hell
# usage: wordgrid.py w h word
# The resulting word grid of w x h letters will be made up from the letters in
# word but will never actually contain the word neither forward nor backwards
# No warranty and all that noise


import sys
import random

def _checkForWord(grid, word, w, h, x, y):
    l = len(word) - 1
    forward, backward = False, False
    # forward
    if x >= l and all(grid[y][x-l+o] == word[o] for o in range(l)):
        forward = True
    elif y >= l and all(grid[y-l+o][x] == word[o] for o in range(l)):
        forward = True
    elif x >= l and y >= l and all(grid[y-l+o][x-l+o] == word[o] for o in range(l)):
        forward = True
    elif x < w-l and y >= l and all(grid[y-l+o][x+l-o] == word[o] for o in range(l)):
        forward = True
    
    # backward
    if x >= l and all(grid[y][x-o] == word[o] for o in range(1, l+1)):
        backward = True
    elif y >= l and all(grid[y-o][x] == word[o] for o in range(1, l+1)):
        backward = True
    elif x >= l and y >= l and all(grid[y-o][x-o] == word[o] for o in range(1, l+1)):
        backward = True
    elif x < w-l and  y >= l and all(grid[y-o][x+o] == word[o] for o in range(1,l+1)):
        backward = True
    
    return forward, backward


def generate(w, h, word):
    word = word.upper()
    letters = set(word)
    letter = list(letters - set(word[-1]))
    etters = list(letters - set(word[0]))
    etter = list(letters - set(word[0]) - set(word[-1]))
    letters = list(letters)
    
    grid = list()
    
    for y in range(h):
        line = list()
        grid.append(line)
        for x in range(w):
            check = _checkForWord(grid, word, w, h, x, y)
            if check[0] and check[1]:
                line.append(random.choice(etter))
            elif check[0]:
                line.append(random.choice(letter))
            elif check[1]:
                line.append(random.choice(etters))
            else:
                line.append(random.choice(letters))
    return grid    

def printgrid(grid):
    for line in grid:
        print(" ".join(line))
        
if __name__ == "__main__":
    if len(sys.argv) != 4:
        print("Usage: wordgrid.py w h word")
        print("The grid will be made up of the letters in word, but word will never appear in it")
        sys.exit(1)
    
    w = int(sys.argv[1])
    h = int(sys.argv[2])

    word = sys.argv[3]
    if len(word) < 3:
        print("The word must have at least three letters")
        sys.exit(1)
    
    print("Find %s!" % word)
    printgrid(generate(w,h,word))