#
# Exploring how to maximize the conversations at a dinner table with one reseating.
# Inspired by a team dinner at a long straight table.
#
# Brute force search so far. I haven't come up with a better algorithm. Brute force
# at 12 people takes ~2 hours on my laptop, so I've reach the realistic limit of
# this approach.
#
# Maybe
#   - Performance
#       - Using Python sets for the union function - may be able to make this much faster with a
#         less general data structure.
#       - Using strings where integers or characters might be faster.
#   - Remembers only the first solution for each improved value. If it remembered (and
#     printed) all it might be easier to find a pattern.
#   - I'm interested in exploring a "distance" metric and using that to find the "minimal"
#     change that still maxmizes the number of conversations. Could potentially be "number
#     of seats that change" or sum of the distances of changes.
#   - Convert to Python 3. Might already be compatible?
#
# Notes
#   - Much non-idiomatic Python here.
#       - Put everything in a function and use the __main()__ trick to make testing easier
#   - Perhaps some of this should be converted to classes - e.g. class SeatingConfiguration
#

import itertools
import time
import sys


# FIXME There has to be a less duplicative way to do this...
people4 = ["A", "B", "C", "D"]
people6 = ["A", "B", "C", "D", "E", "F"]
people8 = ["A", "B", "C", "D", "E", "F", "G", "H"]
people10 = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J"]
people12 = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L"]

# This makes it easy to change which problem size we are using
people = people8


#
# A six person table is numbered thusly
#   0 1 2     A B C
#   5 4 3     F E D
#
# An eight person table is numbered thusly
#   0 1 2 3     A B C D
#   7 6 5 4     H G F E
#
# A ten person table is numbered thusly
#   0 1 2 3 4     A B C D E
#   9 8 7 6 5     J I H G F
#
# Computing the index of the seat opposite:
# The sum of the indices of opposite seats = length-1.
# So the index of the seat opposite seat i is ((length-1)-i
#

# Downstream code assumes each conversation pair has [0] < [1]
def add_pair(result, a, b):
    if (a < b):
        result.add((a, b))
    else:
        result.add((b, a))


# Given a set of people p, return the set of conversations.
# p must be even and >= 4.
# We only add tuples with the first value < second value.
def conversations(p):
    result = set()
    n = len(p)

    # First corner: seat 0 can talk to 1, len-2 and len-1
    add_pair(result, p[0], p[1])
    add_pair(result, p[0], p[n - 2])
    add_pair(result, p[0], p[n - 1])
    # print "After first corner: %r" % sorted(list(result))

    # Second corner: seat ((n/2)-1) can talk to the seat one smaller,
    # one greater, and two greater
    temp = (n / 2) - 1
    add_pair(result, p[temp], p[temp + 1])
    add_pair(result, p[temp], p[temp + 2])
    # print "After second corner: %r" % sorted(list(result))

    # Third corner: seat n/2 can talk to two smaller, one smaller
    # and one greater
    add_pair(result, p[n / 2], p[(n / 2) + 1])
    # print "After third corner: %r" % sorted(list(result))

    # Fourth corner: seat n-1 can only talk to seats < n-1, so nothing to do.
    # print "After fourth corner: %r" % sorted(list(result))

    # "top" side of the table. There are five neighbors, but the one to the
    # left is smaller.
    for i in range(1, (n / 2) - 1):
        opposite = (n - 1) - i
        add_pair(result, p[i], p[i + 1])
        add_pair(result, p[i], p[opposite - 1])
        add_pair(result, p[i], p[opposite])
        add_pair(result, p[i], p[opposite + 1])
    # print "After 'top' side: count=%d %r" % (len(result), sorted(list(result)))


    # "bottom" side of the table. There are five neighbors. But all of those one the
    # "top" side of the table, and the one to the right, have already been added.
    for i in range((n / 2) + 1, n - 1):
        add_pair(result, p[i], p[i + 1])
    # print "After 'bottom' side: count=%d %r" % (len(result), sorted(list(result)))

    #    print "conversations: p=%r count=%d result=%r" % (
    #        str(p).replace(" ", ""), len(result), str(sorted(list(result))).replace(" ", ""))

    return result


# Utility function to produce a compact string from a permutation
def permutation_to_string(p):
    result = ""
    for x in p:
        result = result + str(x)
    return result


# Utility function to produce a compact string from a set of conversations, represented
# as a set of two-valued tuples.
def conversations_to_string(conv):
    conv_list = sorted(list(conv))

    t = {}

    # intialize the dictionary with the first character as key and
    # an empty value. Dupes don't matter.
    for x in conv_list:
        t[x[0]] = x[0] + ":"

    # For each first chaacter, accumulate a string of 2nd characters
    for x in conv_list:
        t[x[0]] = t[x[0]] + x[1]

    result = "<<n=%d" % len(conv)
    for k, v in sorted(t.items()):
        result = result + " " + v
    result = result + ">>"

    return result


# Utility function to print conversations and
# a permutation (presumably that generated those conversations)
def print_conversations_and_permutations(leading_string, conv, permutation):
    print "%sperm=%s conv=%s" % (leading_string, permutation_to_string(permutation), conversations_to_string(conv))


# The conversations created by the initial seating
starting_conversations = conversations(people)

# Keep track of the best so far. Constants are just convenience keys into the dictionary.
best_so_far = {}
PERMUTATION = 0
CONVERSATIONS = 1
COUNT = 2

best_so_far[PERMUTATION] = people
best_so_far[CONVERSATIONS] = starting_conversations
best_so_far[COUNT] = len(starting_conversations)

print_conversations_and_permutations("INITIAL: ", best_so_far[CONVERSATIONS], best_so_far[PERMUTATION])

people_permutations = itertools.permutations(people)
i = 0
count_of_best = 0
start_time = time.time()
for perm in people_permutations:
    second_conversations = conversations(perm)
    unique_conversations = starting_conversations | second_conversations
    if (len(unique_conversations) > best_so_far[COUNT]):
        best_so_far[PERMUTATION] = perm
        best_so_far[CONVERSATIONS] = unique_conversations
        best_so_far[COUNT] = len(unique_conversations)
        count_of_best = 1
        print "IMPROVE(1): unique_conversations: %s additional_conversations: %s" % (
            conversations_to_string(unique_conversations),
            conversations_to_string(unique_conversations - starting_conversations))
        print_conversations_and_permutations("IMPROVE(2): ", best_so_far[CONVERSATIONS], best_so_far[PERMUTATION])
    elif (len(unique_conversations) == best_so_far[COUNT]):
        count_of_best = count_of_best + 1
        print "FOUND ANOTHER WITH SAME i=%d %d count_of_best=%d" % (i, best_so_far[COUNT], count_of_best)

    i = i + 1
    if ((i % 1000) == 0):
        print "i=%d t=%d t_per_thousand=%f" % (i, (time.time()-start_time), ((time.time()-start_time))/i)

print ""
print_conversations_and_permutations("BEST: ", best_so_far[CONVERSATIONS], best_so_far[PERMUTATION])