'''
September 2017 Puzzle

Place the letters A, B, and C in the 4x4 grid below so that each
of the following "words" can be found in a row (read left to right)
or column (read top to bottom). 

ACAA     BACA     BACC     BBAB

BBAC     CBBA     CBCA     CBBC 
'''

from __future__ import print_function   #so this will work with Py 2.7
import itertools as it

def makeVertical(ps):
  '''
  Receive a list of 4 strings representing the horizontal words
  of a possible solution (ps) and return what would be the
  vertical words with these 4 words in each row.
  '''
  
  vertList = []

  for column in range(4):
    verticalWord = ps[0][column] + ps[1][column] + ps[2][column] + ps[3][column]
    vertList.append(verticalWord)

  return vertList



################
#Main
################
if __name__ == '__main__':

  allWords = ['acaa', 'baca', 'bacc', 'bbab', 'bbac', 'cbba', 'cbca', 'cbbc']
  
  #Create a list of all the possibilities for the 4 horizontal words that
  # can be made with the above 8 possibilities
  solList = it.permutations(allWords, 4)

  #Check each one to see if the vertical words make up the remaining allWords
  for horizontalWords in solList:
    verticalSet = set(allWords) - set(horizontalWords)
    verticalWords = makeVertical(horizontalWords)
    
    if set(verticalWords).issubset(verticalSet):
      print(horizontalWords[0])
      print(horizontalWords[1])
      print(horizontalWords[2])
      print(horizontalWords[3])
      print()