import random
import sys

# -------------
# getWords
# -------------

def getWords():

   fileName = "words.txt"
   list     = []

   try:

      f = open(fileName, "r")

   except IOError:

      print("Could not open file: [" + fileName + "]")
      sys.exit()

   content = f.readlines()
   f.close()

   for word in content:
      list.append(word.strip())

   return(list)

# -------------
# Entry
# -------------

class Entry:

   def __init__(self, letter):
      self.mLetter = letter.lower()
      self.mUsed   = False

   def __str__(self):
      return("{{ '{0}', {1} }}".format(self.mLetter, self.mUsed))

# -------------
# showBoard
# -------------

def showBoard(board):

   for i in range(0, len(board)):
      for j in range(0, len(board[i])):
         print(board[i][j], end = " ")
      print()

class RC:

   def __init__(self, row, column):
      self.mRow    = row
      self.mColumn = column

def seek(board, processed, remaining, row, column, theSet):

   #print("{0} {1} {2} {3}".format(processed, remaining, row, column))
   #showBoard(board)

   if remaining == "":
      theSet.add(processed)
      return
 
   list = []

   if row == -1 and column == -1:

      for i in range(0, 4):
         for j in range(0, 4):

            if remaining.startswith(board[i][j].mLetter):
               list.append(RC(i, j))

   else:

      offsets = [ RC(-1, -1), RC(-1, 0), RC(-1, 1),
                  RC( 0, -1),            RC( 0, 1),
                  RC( 1, -1), RC( 1, 0), RC( 1, 1) ]

      for rc in offsets:
         r = row    + rc.mRow
         c = column + rc.mColumn

         if r >= 0 and r <= 3 and c >= 0 and c <= 3 and board[r][c].mUsed == False:

            if remaining.startswith(board[r][c].mLetter):
               list.append(RC(r, c))

   #print("list: " + str(list))

   for location in list:

      entry = board[location.mRow][location.mColumn]

      entry.mUsed = True

      seek(board, processed + entry.mLetter, remaining[len(entry.mLetter):],
         location.mRow, location.mColumn, theSet)

      entry.mUsed = False

# -------------
# findWords
# -------------

def findWords(letters, words):

   k     = 0
   board = []

   for i in range(0, 4):
      row = []
      for j in range(0, 4):
         row.append(Entry(letters[k]))
         k += 1
      board.append(row)

   theSet = set()
   
   for word in words:
      seek(board, "", word, -1, -1, theSet)

   print(str(theSet))

# ---------------------
# Script Begins Here
# ---------------------

words = getWords()

# print(str(words))

dice = [

   [ 'A', 'A', 'E', 'E', 'G', 'N' ],
   [ 'A', 'B', 'B', 'J', 'O', 'O' ],
   [ 'A', 'C', 'H', 'O', 'P', 'S' ],
   [ 'A', 'F', 'F', 'K', 'P', 'S' ],
   [ 'A', 'O', 'O', 'T', 'T', 'W' ],
   [ 'C', 'I', 'M', 'O', 'T', 'U' ],
   [ 'D', 'E', 'I', 'L', 'R', 'X' ],
   [ 'D', 'E', 'L', 'R', 'V', 'Y' ],
   [ 'D', 'I', 'S', 'T', 'T', 'Y' ],
   [ 'E', 'E', 'G', 'H', 'N', 'W' ],
   [ 'E', 'E', 'I', 'N', 'S', 'U' ],
   [ 'E', 'H', 'R', 'T', 'V', 'W' ],
   [ 'E', 'I', 'O', 'S', 'S', 'T' ],
   [ 'E', 'L', 'R', 'T', 'T', 'Y' ],
   [ 'H', 'I', 'M', 'N', 'U', 'Q' ],
   [ 'H', 'L', 'N', 'N', 'R', 'Z' ]

]

# first, we need to randomize the order
# of the rows

random.shuffle(dice)

letters = []

for i in range(0, len(dice)):
   index = random.randrange(len(dice[i]))
   letter = (dice[i][index] if dice[i][index] != 'Q' else 'Qu')
   letters.append(letter)

# print(letters)

k = 0

for i in range(0, 4):

   print("+----+----+----+----+")

   for j in range(0, 4):

      print("| {0:2s} ".format(letters[k]), end = "")
      k += 1

   print("|")

print("+----+----+----+----+\n")

findWords(letters, words)