d3f2a014c80e938da97a8bfe73086f80.py

"""
Joseph Zhong
9 Nov. 2016
test.py

There are multiple objectives involving SETs of 3 cards
  - Output the maximum number of possible SETs
  - Output the maximum number of disjoint SETs
  - The largest collection of disjoint SETs

Constraints:
  - Code must be readable
  - 5 second per test case run-time
  - Memory (??)

Thoughts on the Problem:
  Immediately, the above objectives are difficult for the following reasons:
    - Constrained Permutations
    - The constraint involves checking 3 objects with 4 features
  The second objective seems much more difficult than the first in the concept
    of maximum is introduced with possibilities
    - Disjoint sets
    - Maximum disjoint set
    - Elements of the maximum disjoint set

Thoughts on Potential Solutions:
  Obj1
    Iterative Solutions
      "Brute Force": n^3 solution to check each possible trio as a set
        With 3 <= n <= 30, worst case this will be <27000 checks to return only
        a handful of possible sets while not taking advantage of memory available
      Optimizations:
        - (?) Immediately move on when first two cards are impossible
          - This actually increased Obj1 runtime from ~75-90ms to ~100-110ms
          - Don't know whether it's worth optimizing feature checking...
        - TODO: Try recursive backtracking method instead
          - This also seems overkill, and annoying to implement without
              utilizing stack memory and I can't immediately think of a
              "dynamic programming" implementation to save feature comparisons
    Obj1 Pseudocode:
      for i...n card, j...(i+1,n), k...(j+1,n):
        check and ++
        Add valid set to a list with card indices
  Obj2
    Maximum Disjoint Set
      - (?) aka disjoint powerset problem
      - There are 2^n subsets in a regular powerset
    Immediately I see a recursive backtracking problem, however the complication
      is that there are three dimensions which paths are chosen. The algorithm
      makes sense, the runtime is the worry.
    Optimizations to try:
      - Dynamic Programming Application? Each SET has a number of matching
          disjoint sets?
      - Something about checking only the cards in each set
        - ...

"""

# regex will help with with easing the manual pattern matching process
import re
import sys
import time
from itertools import chain, combinations


def symbol(thingy):
  """
  Regex matching for "Symbol" type
  :param thingy: The thingy to match against
  :return: The extracted "Symbol" type as a String ("a" | "s" | "h")
  """
  if bool(re.match('@|a|A', thingy)): return 'a'
  elif bool(re.match('\$|s|S', thingy)): return 's'
  elif bool(re.match('#|h|H', thingy)): return 'h'
  else: raise Exception("Invalid Input -- Multiple Symbols detected")

def shade(thingy):
  """
  Regex matching for "Shade" type
  :param thingy: The thingy to match against
  :return: The extracted "Shade" type as a String ("symbol" | "lower" | "upper")
  """
  if bool(re.match('@|\$|#', thingy)): return 'symbol'
  elif bool(re.match('a|s|h', thingy)): return 'lower'
  elif bool(re.match('A|S|H', thingy)): return 'upper'
  else: raise Exception("Invalid Input -- Multiple Shades detected")

def areSame(values):
  return values[1:] == values[:-1]

def areUnique(values):
  return len(values) == len(set(values))

def isSet(test_set):
  """
  A SET is when the cards all are same or all different in any feature categories
  :param test_set: A trio of cards
  :return: A boolean value on whether the trio represents a SET
  """
  features = {
    'color',
    'symbol',
    'shade',
    'number'
  }

  # allows for checking of arbitrary set size
  for key in features:
    if not ((areSame([card[key] for card in test_set]))
        or (areUnique([card[key] for card in test_set]))):
      return False
  return True

def test(cards, n):
  """
  """
  sets = []
  # obj1 output
  for i in range(n - 2): # first card
    for j in range(i + 1, n - 1): # second card
      # if isSet((cards[i], cards[j])): # check if valid already: slowed runtime
      for k in range(j + 1, n): # third card
        if isSet((cards[i], cards[j], cards[k])):
          sets.append(
              { i, j, k }
          )
  print len(sets)

  #
  # obj2 experiments ...
  #
  # experimenting with powerset solution -- too many subsets to check through
  # def powerset(iterable):
  #   s = list(iterable)
  #   return chain.from_iterable(combinations(s, r) for r in range(1, len(s)+1))
  # print list(powerset(sets))

  # def is_disjoint_set(test_sets):
  #   """
  #   :param test_sets: set to check whether is disjoint
  #   :return: Boolean value whether set is disjoint or not
  #   """
  #   for i in range(len(test_sets) - 1):
  #     for j in range(0, len(test_sets)):
  #       if j != i and len(set.intersection(test_sets[i], test_sets[j])) != 0:
  #         return False
  #   return True
  #
  # list_of_disjoint_sets = []
  # def explore(test_sets):
  #   """
  #   Depth first brute force recursive approach
  #     - builds the small disjoint sets first, or O(2^n)
  #     - takes very very long to return
  #   Adds to list_of_disjoint_sets
  #   :param test_sets: list of sets to explore
  #   """
  #   if is_disjoint_set(test_sets):
  #     list_of_disjoint_sets.append(test_sets)
  #   else:
  #     for i in range(len(test_sets)):
  #       explore(test_sets[0:i] + test_sets[i+1:])
  # explore(sets)
  # print list_of_disjoint_sets
  # print 'Number of disjoint sets found: {}'.format(len(list_of_disjoint_sets))

  # def is_disjoint_set(test_sets):
  #   """
  #   :param test_sets: set to check whether is disjoint
  #   :return: Boolean value whether set is disjoint or not
  #   """
  #   for i in range(len(test_sets) - 1):
  #     for j in range(0, len(test_sets)):
  #       if j != i and len(set.intersection(test_sets[i], test_sets[j])) != 0:
  #         return False
  #   return True
  #
  # list_of_disjoint_sets = []
  # def breadth_first_explore(test_sets):
  #   """
  #   Breadth first also brute-force recursive approach
  #     - builds the larger disjoint sets first
  #     - still very slow solution if possibilities set is large
  #   :param test_sets: list of sets to explore
  #   """
  #   q = []
  #   if is_disjoint_set(test_sets):
  #     list_of_disjoint_sets.append(test_sets)
  #     return
  #   else:
  #     for i in range(len(test_sets)):
  #       q.append(test_sets[0:i] + test_sets[i+1:])
  #     while len(q): # queue of test sets is not empty
  #       tmp = q.pop(0)
  #       if is_disjoint_set(tmp):
  #         list_of_disjoint_sets.append(tmp)
  #         return
  #       else:
  #         for index in range(len(tmp)):
  #           q.append(tmp[0:index] + tmp[index+1:])
  # breadth_first_explore(sets)
  # print 'Number of disjoint sets found: {}'.format(len(list_of_disjoint_sets))

  # bad, incomplete iterative solution without backtracking exploration
  # although is it really bad if it misses some solutions, but fast? :P
  # :( ughhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh
  list_of_disjoint_sets = [[s] for s in sets] # [[1, 2, 81]  ... n=41 ]
  def can_add(s, disjoint_set):
    """
    Test whether adding set into the already disjoint_set will still be disjoint
    :param s: set to add
    :param disjoint_set: already disjoint set
    :return: Boolean True if the add is still disjoint, False otherwise
    """
    for d_set in disjoint_set:
      if len(d_set) + len(s) != len(d_set.union(s)):
        return False
    return True
  i = 0
  for s in sets: # input
    for disjoint_set in list_of_disjoint_sets:
      i += 1
      if can_add(s, disjoint_set): # check if s and disjoint_set are disjoint
        list_of_disjoint_sets.append(disjoint_set)
        disjoint_set.append(s)


  # list_of_disjoint_sets = []
  # if len(sets):
  #   cards_used = sets[0]
  #   list_of_disjoint_sets.append(sets[0])
  #   for i in range(1, len(sets)):
  #     for card in sets[i]:
  #       if card in cards_used:
  #         break
  #     cards_used.update(sets[i])
  #     list_of_disjoint_sets.append(sets[i])
  # print 'list %s' % list_of_disjoint_sets

  # <insert dynamic programming attempt here>
  # <insert include/exclude tree attempt here>
  # <insert correct solution here> :(

  # obj2 output
  max_disjoint_set = {}
  for i in range(len(list_of_disjoint_sets)):
    if len(list_of_disjoint_sets[i]) > len(max_disjoint_set):
      max_disjoint_set = list_of_disjoint_sets[i]
  print len(max_disjoint_set)

  # obj3 output
  print ''
  # print max_disjoint_set
  for s in max_disjoint_set:
    for card in s:
      print '{} {}'.format(cards[card]['color'], cards[card]['thingy'])
    print ''

def parse_card(line):
  color, thingy = line.split()
  return {
    'thingy': thingy,
    'color': color,
    'symbol': symbol(thingy),
    'shade': shade(thingy),
    'number': len(thingy)
  }

def parse_in(f_name=None):
  """
  Parse Input from either stdin or a file
  :param f_name:
  :return:
  """
  cards = []
  n = 0
  if f_name is None:
    n = int(raw_input())
    for i in range(n):
      cards.append(parse_card(raw_input()))
  else:
    with open(f_name, 'r') as input_file:
      n = int(input_file.readline())
      for line in input_file:
        cards.append(parse_card(line))
  test(cards, n)

start = time.time()

parse_in('in')
# parse_in('in1')
# parse_in()

# print runtime
# print '%.4f seconds' % (time.time() - start)