#!/usr/bin/env python

# Copyright (c) 2012-2013, Christopher R. Wagner
#  
# 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.

"""Another pickle ball doubles matchup problem.

How to optimally choose matchups for a doubles tournament of n people,
where each person plays n-1 matches, to optimize pairing so that each
person is only paired with another once, and plays against another
person at most twice. Also want to solve as a tournament so we can
maximize court usage (e.g., if there are 8 players, at each round we
should be using two courts.)

This can be cast as an exact cover problem.
"""


import itertools
from copy import deepcopy
from collections import defaultdict
from functools import partial


def iflatten2d(list2d):
    return itertools.chain.from_iterable(list2d)


PLAYER_IDS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'


def chooser(board):
    if board.unable_to_solve():
        return None
    if board.is_solved():
        return board
    constrained_pos = board.canplace()
    if constrained_pos is not None:
        return chooser(board.place(constrained_pos, board.choices(constrained_pos)[0]))
    # Have to make a choice
    pos = board.first_position_with_choices()
    for i_choice, choice in enumerate(board.choices(pos)):
        boardcopy = chooser(deepcopy(board).place(pos, choice))
        if boardcopy is not None:
            return boardcopy
    return None


class PickleBallBoardState(object):
    def __init__(self, n):
        allpairs = []
        for i in xrange(n):
            for j in xrange(i+1, n):
                allpairs.append(PLAYER_IDS[i] + PLAYER_IDS[j])

        assert n % 4 == 0

        # Initialize choices
        n_courts = n / 4
        positions_per_court = 2
        n_matches = n - 1
        self.matches = []
        for i_match in xrange(n_matches):
            match = []
            for i_position in xrange(n_courts * positions_per_court):
                match.append(list(allpairs))
            self.matches.append(match)

        # Initialize is_placed matrix
        self.placed = []
        for i_match in xrange(n_matches):
            self.placed.append([False] * n_courts * positions_per_court)

        # Initialize play_count matrix
        self.play_counts = defaultdict(partial(defaultdict, int))

        # Place initial pairs
        for i_match in xrange(n_matches):
            self.place((i_match, 0), PLAYER_IDS[0] + PLAYER_IDS[i_match + 1])
        
    def unable_to_solve(self):
        return any(not choices for choices in iflatten2d(self.matches))

    def is_solved(self):
        return all(len(choices) == 1 for choices in iflatten2d(self.matches)) \
               and all(iflatten2d(self.placed))

    def canplace(self):
        for i_match, match in enumerate(self.matches):
            for i_pos, choices in enumerate(match):
                if len(choices) == 1 and not self.placed[i_match][i_pos]:
                    return (i_match, i_pos)
        return None

    def first_position_with_choices(self):
        for i_match, match in enumerate(self.matches):
            for i_pos, choices in enumerate(match):
                if len(choices) > 1:
                    assert not self.placed[i_match][i_pos]
                    return (i_match, i_pos)
        return None

    def choices(self, location):
        i_match, i_pos = location
        return self.matches[i_match][i_pos]

    def _filter_out_players(self, i_match, i_pos, players):
        if not self.placed[i_match][i_pos]:
            self.matches[i_match][i_pos] = filter(
                lambda c: (c[0] not in players) and (c[1] not in players),
                self.matches[i_match][i_pos])

    def _blocked_players(self, players):
        blocked_set = set()
        for player in players:
            blocked_set.update(p for p, count in self.play_counts[player].iteritems() if count >= 2)
        return blocked_set

    def _update_play_counts(self, i_match, i_pos):
        """Update counts of how many times each player has played each other player."""
        opposing_pos = i_pos + 1 if i_pos % 2 == 0 else i_pos - 1
        assert self.placed[i_match][i_pos]
        assert self.placed[i_match][opposing_pos]
        pair1 = self.matches[i_match][i_pos][0]
        pair2 = self.matches[i_match][opposing_pos][0]
        self.play_counts[pair1[0]][pair2[0]] += 1
        self.play_counts[pair1[0]][pair2[1]] += 1
        self.play_counts[pair1[1]][pair2[0]] += 1
        self.play_counts[pair1[1]][pair2[1]] += 1
        self.play_counts[pair2[0]][pair1[0]] += 1
        self.play_counts[pair2[0]][pair1[1]] += 1
        self.play_counts[pair2[1]][pair1[0]] += 1
        self.play_counts[pair2[1]][pair1[1]] += 1

    def place(self, location, choice):
        placed_match, placed_pos = location
        assert not self.placed[placed_match][placed_pos]

        # First check if we are completing a versus match
        opposing_pos = placed_pos + 1 if placed_pos % 2 == 0 else placed_pos - 1
        completing_versus = self.placed[placed_match][opposing_pos]
        
        # Place the choice
        self.matches[placed_match][placed_pos] = [choice]
        self.placed[placed_match][placed_pos] = True

        # Remove all other instances of this pairing
        for i_match, match in enumerate(self.matches):
            for i_pos, choices in enumerate(match):
                if not self.placed[i_match][i_pos]:
                    try:
                        choices.remove(choice)
                    except ValueError:
                        pass
            
        # Remove all choices containing these players from this match
        for i_pos in xrange(len(self.matches[placed_match])):
            self._filter_out_players(placed_match, i_pos, choice)
            
        # Make sure person only plays against another player maximum twice
        if completing_versus:
            self._update_play_counts(placed_match, placed_pos)
            for i_match, match in enumerate(self.matches):
                for i_pos, choices in enumerate(match):
                    opposing_pos = i_pos + 1 if i_pos % 2 == 0 else i_pos - 1
                    if self.placed[i_match][opposing_pos] and not self.placed[i_match][i_pos]:
                        self._filter_out_players(
                            i_match, i_pos,
                            self._blocked_players(self.matches[i_match][opposing_pos][0]))

        return self

    def solnstr(self):
        lines = []
        for i_match, match in enumerate(self.matches):
            lines.append(('Match %d: ' % (i_match + 1)) + \
                         ', '.join(match[ipos][0] + ' vs ' + match[ipos+1][0]
                                   for ipos in xrange(0, len(match), 2)))
        return '\n'.join(lines)


def solve(n):
    board = PickleBallBoardState(n)
    return chooser(board)


def usage():
    print ('pickleball2.py n\n'
           'Solve doubles tournament for n people')


if __name__ == '__main__':
    import sys
    if len(sys.argv) != 2:
        usage()
    else:
        n = int(sys.argv[1])
        print solve(n).solnstr()