# -----------------------------------------------------------------------------------------
# Oak Valley Coding Club 2019-2020
# Solution for 2020 ACSL Programming Problem #3 – Junior Division
# Author :  Rithvik Madiraju
# Language: Python 3.x
# -----------------------------------------------------------------------------------------


import ovcc_grader_strings
# 4 group neighbors lookup table
four_group_neighbors = {
  1: [[0, 0], [0, 1], [0, 2], [0, 3]],
  2: [[1, 0], [1, 1], [1, 2], [1, 3]],
  3: [[0, 0], [0, 1], [1, 0], [1, 1]],
  4: [[0, 1], [0, 2], [1, 1], [1, 2]],
  5: [[0, 2], [0, 3], [1, 2], [1, 3]]
}
# 4 group neighbors with wrapping LUT
four_group_neighbors_w = {
  6: [[0, 0], [1, 0], [0, 3], [1, 3]]
}
# 2 group neighbors LUT
two_group_neighbors = {
  7: [[0, 0], [0, 1]], 
  8: [[0, 1], [0, 2]], 
  9: [[0, 2], [0, 3]], 
  10: [[1, 0], [1, 1]], 
  11: [[1, 1], [1, 2]], 
  12: [[1, 2], [1, 3]], 
  13: [[0, 0], [1, 0]], 
  14: [[0, 1], [1, 1]], 
  15: [[0, 2], [1, 2]], 
  16: [[0, 3], [1, 3]] 
}
# 2 group neighbors with wrapping LUT
two_group_neighbors_w = {
  17: [[0, 0], [0, 3]],
  18: [[1, 0], [1, 3]]
}
# Single terms LUT
single_term = {
  19: [[0,0]], 
  20: [[0,1]], 
  21: [[0,2]], 
  22: [[0,3]], 
  23: [[1,0]], 
  24: [[1,1]], 
  25: [[1,2]], 
  26: [[1,3]]
}
# Min term look up table
min_term = {
  1  : "B",
  2  : "~B",
  3  : "A",
  4  : "C",
  5  : "~A",
  6  : "~C",
  7  : "AB",
  8  : "BC",
  9  : "~AB",
 10  : "A~B",
 11  : "~BC",
 12  : "~A~B",
 13  : "A~C",
 14  : "AC",
 15  : "~AC",
 16  : "~A~C",
 17 : "B~C",
 18 : "~B~C",
 19: "AB~C",
 20: "ABC",
 21: "~ABC",
 22: "~AB~C",
 23: "A~B~C",
 24: "A~BC",
 25: "~A~BC",
 26: "~A~B~C"
}
# Utility function to test bit w/ an offset in to the val
def test_bit(val, offset):
    mask = 1 << (offset)
    return(val & mask)
# Split characters in a word
def split(word): 
    return list(word)
# Reset the found pattern 
def reset (a2d, table, key):
  value = table[key]
  for item in value:
      i = item[0]
      j = item[1]
      a2d[i][j] = 0 
# Process the 2d array for patterns listed in the supplied table
def process(array_2d, table):
  list = []
  for (k, v) in sorted (table.items()):
    match = True
    for entry in v:
      x = entry[0]
      y = entry[1]
      if array_2d[x][y] != 1: 
        match = False
        break
    if (match):
      reset(array_2d, table, k)  
      list.append(min_term[k])
  str = ""
  j = 0
  for i in range(len(list)): 
    if (list[i]!="" and j!=0):
      str = str + "+" + list[i]
    if (list[i]!="" and j==0):
        str = str + list[i]
        j = j + 1
  return str
# Find groups of 4 
def find_groups_of_4(array_2d):
  return process(array_2d, four_group_neighbors)
# Find groups of 4  w/ wraparound
def find_groups_of_4_withwrap(array_2d):
  return process(array_2d, four_group_neighbors_w)
# Find groups of 2
def find_groups_of_2(array_2d):
  return process(array_2d, two_group_neighbors)
# Find groups of 2 w/ wraparound
def find_groups_of_2_withwrap(array_2d):
  return process(array_2d, two_group_neighbors_w)
# Find single terms
def find_single_terms(array_2d):
  return process(array_2d, single_term)
# Boolean expresion minimization function
def minimize(v2d):
  list = []
  list.append(find_groups_of_4(v2d))
  list.append(find_groups_of_4_withwrap(v2d))
  list.append(find_groups_of_2(v2d))
  list.append(find_groups_of_2_withwrap(v2d))
  list.append(find_single_terms(v2d))
  str = ""
  j = 0
  for i in range(len(list)): 
    if (list[i]!="" and j!=0):
      str = str + "+" + list[i]
    if (list[i]!="" and j==0):
      str = str + list[i]
      j = j + 1
  # Special case of empty min string
  if (str == ""):
    str = "0"
  return str
# Create the veitch 2D table 
def veitch_2d(str):
  s = split(str)
  rows, cols = (2, 4)
  arr_2d = [[0 for i in range(cols)] for j in range(rows)]
  for index in range (0, cols):
    arr_2d_index = cols - index - 1
    if test_bit(int (s[0], 16), index)!=0:
      arr_2d[0][arr_2d_index] = 1
    if test_bit(int (s[1], 16), index)!=0:
      arr_2d[1][arr_2d_index] = 1
  return arr_2d

# Test driver minimizing veitch table taken from input.txt
words = ovcc_grader_strings.readinput()
ovcc_grader_strings.clearoutput()
for word in words:
    vd = veitch_2d(word[0])
    #print(word[0] + ":" + minimize(vd))
    ovcc_grader_strings.writeoutput(minimize(vd))

# Test driver for exhaustive testing of the Veitch Table 
# Runs through all possible veitch table combos
#for counter in range (0, 256):
#    str="{0:02X}".format(counter)
#    vd = veitch_2d(str)
#    print(str + ":" + minimize(vd))
#    minimize(vd)