#!/usr/bin/env python

# Copyright (C) 2011 by Travis Hudson

# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:

# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.

# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
# THE SOFTWARE.

#####################################################################################################
# summertime_lunch.py (v 0.0)
# Travis Hudson (August 15, 2011)
#
# Accepts a text file listing out all votes to be counted and
# returns the winning rank using the Kemeny-Young algorithm.
# This program is designed to run under Python 2.7.
#
# The input file must look like this:
#
#      # Lines that start with # are comments.
#      1. Chipotle 2. Fuji Sushi 3. Biff's
#      1. Chipotle 2. Fuji Sushi 3. Taco Bell
#      1. Fuji Sushi 2. Chipotle 3. Biff's
#      1. Chipotle 2. DQ 3. Taco Bell
#####################################################################################################

import re
import sys
import itertools

#
# Return the total number of votes that prefer x over y
#
def total_preferring(x, y, votes):
    if len(votes) == 0:
        return 0

    return total_preferring(x, y, votes[1:]) + vote_prefers(x, y, votes[0])

#
# 1 if x is preferred over y in this vote, 0 otherwise
#
def vote_prefers(x, y, vote):
    if (x in vote) and (y not in vote):
        return 1           # if x is in the vote but y isn't, then x is preferred over y

    try:
        if vote.index(x) < vote.index(y):
            return 1
        else:
            return 0
    except ValueError:
        return 0           # x is not in the vote, so x is not preferred over y

#
# Assign a rating to a vote's popularity
#
def rate_vote(vote, pairs):
    total = 0
    passed = []
    for place in vote:
        for pair in pairs:
            if pair[0] == place and pair[1] not in passed:
                total += pair[2]
        passed.append(place)

    return total

#
# Main function to execute when run on the command line
#
def main():
    print "Summertime Lunch Voting System"

    #
    # Make sure that the required list of votes has been passed in on the command line
    #
    if len(sys.argv) < 2:
        print "One argument is required, the text document containing the list of votes to tally."
        print "Usage: summertime_lunch.py input.txt"
        sys.exit()

    #
    # Read the votes into a list
    #
    all_votes = []
    infile = open(sys.argv[1])
    for line in infile:
        line = line.strip()
        if len(line) > 0 and line[0] != "#":
            line = line.replace("\'", "")
            matches = re.findall("(?<=\d\.)\s*(\D+)", line)
            matches = [match.upper().strip() for match in matches]
            all_votes.append(matches)
    infile.close()

    #
    # Make a list of all unique names of places
    #
    unique_names = []
    for vote in all_votes:
        unique_names.extend(vote)
    unique_names = set(unique_names)

    #
    # Make a table of pairwise comparisons
    #
    pairs = []
    for place1 in unique_names:
        for place2 in unique_names:
            if place1 != place2:
                pairs.append([place1, place2, total_preferring(place1, place2, all_votes)])

    #
    # Generate every possible order of places, keeping track of the highest-rated one
    #
    all_orders = []          # keep track of all possible orders and their ratings, even the unpopular ones
    best_order = [-1, ()]    # keep track of the most popular order and its rating as: [rating, order]
    for possible_order in itertools.permutations(unique_names):
        rating = rate_vote(possible_order, pairs)
        all_orders.append([rating, possible_order])
        if rating > best_order[0]:
            best_order = [rating, possible_order]
    all_orders.sort()
    all_orders.reverse()

    #
    # Show the highest-rated order of places as the winner
    #
    print "Winning Order: " + str(best_order[1])
    print "Winning Score: " + str(best_order[0])
    print
    print "All Possibilities: "
    for possibility in all_orders:
        print possibility

#
# Only run code if this file is not being imported as a module for another Python file
#
if __name__ == "__main__":
    main()