Palantir.py

'''
Problem:
The Magic Box (Programming)
It is well known at Palantir that Director of Engineering Khan is a very skilled engineer.  What is much
less well known is that he is also a skilled ninja, wizard, and genie.  Khan has used his impressive
wizarding power to create a magic box locked with an M by N grid of two wizarding symbols that look
suspiciously like the letters "P" and "T", the initials of Khan's favorite company.  The box can only be
unlocked by a given person once in that person's lifetime.
 
Khan has infused the box with his genie powers so that it grants the opener a number of wishes equal
to the number of rows in which all the symbols in the row are the same.  Before opening the box, a
person has the opportunity to flip the symbols in any number of the columns (P will become T and T will
become P for each symbol in the column) in order to maximize the number of wishes they receive when
opening the box.
 
On your first day at Palantir, Khan uses his ninja stealth to sneak up to your desk unseen and leaves
the box and instructions for you.  How will you decide which columns to flip in order to maximize the
number of wishes granted by Khan's box?  Given a description of the box as input, write a program
that outputs a single number, which is the maximum number of wishes you can receive from the box.
Remember that a human will be reading your code.  Not only should your solution be correct and efficient,
it should also be clean and easy to read!
 
Input Format
The first line contains 2 space separated integers M and N, the number of rows and the number of columns
in the box's lock. M lines follow each line containing N characters ( not separated by any space ) 'P' or 'T'.
 
Output Format
A single number representing the maximum number of wishes you can receive
 
Constraints
1<=M<=100000
1<=N<=500
 
Sample Input
5 3
TTP
PTP
TPP
PTP
TPT
 
Sample Output
3
 
Explanation
Flipping column 2 yields:
TPP
PPP
TTP
PPP
TTT
Giving us 3 wishes.  If we try to get the first row to match instead, we have to either flip columns 1 and 2
or only column 3, and this gives only 1 wish.  If we want to get row 3 to match, we'd have to flip either
column 1 or columns 2 and 3, again granting only one wish.
'''
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
# Enter your code here. Read input from STDIN. Print output to STDOUT
 
# A library for counting occurences of elements in an iterable
from collections import Counter
 
# Assign m and n from the first line
(m, n) = raw_input().split(' ')
(m, n) = (int(m), int(n))
 
# Create representation of the box
box_list = []
for i in range(m):
    box_list.append(raw_input())
 
# Designates the columns you need to flip for a given row.
# Ex: For row "PTT" you would append "0"
# Ex: For row "PPTT" you would append "01|23"
 
flip = []
 
for i in range(m):
    cur_list = box_list[i]
    
    # Counts number of T's and P's in current row
    t_count = box_list[i].count("T")
    p_count = box_list[i].count("P")
 
    # 
    if t_count > p_count:
        flip.append(''.join([str(j) for j in range(n) if cur_list[j] == "P"]))
    elif p_count > t_count:
        flip.append(''.join ([str(j) for j in range(n) if cur_list[j] == "T"]))
    else:
        st = ''.join([str(j) for j in range(n) if box_list[i][j] == "P"])
        st += "|" + ''.join([str(j) for j in range(n) if cur_list[j] == "T"])
        flip.append(st)
 
# Creates a counter for the possible column flips that counts
# the number of times each possible column flip combination occurs.
count = Counter(flip)
 
# Finds the column flip combination that occurs the most, and
# returns the number of rows that column flip combination
# would complete.
print(count.most_common(1)[0][1])


# Alternative method that doesn't use outside libraries
counts = {}
for row in flip:
    counts[row] = counts.get(row, 0) + 1
print(max(counts.values()))