#\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
#\\ SAGE Class for Ethiopian Dinner Game   v. 1.0                      \\
#\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
#\\ Lionel Levine  and  Katherine E. Stange                            \\
#\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
#\\ This is a class for use in SAGE which implements ethiopian dinner  \\
#\\ games.                                                             \\
#\\                                                                    \\
#\\ For info, see http://math.katestange.net or contact                \\
#\\ <math at katestange dot net> or <levine at math dot mit dot edu>.  \\
#\\                                                                    \\
#\\ An ethiopian dinner (a "game") is a set of tuples (a,b)            \\
#\\ representing morsels, where a is the value of the morsel to Alice  \\
#\\ and b is the value of the morsel to Bob.  We use the convention    \\
#\\ that Bob always goes last, so that the first player depends on the \\
#\\ parity of the number of morsels in the game.                       \\
#\\                                                                    \\
#\\ Feel free to distribute this script.  If you alter it, add a       \\
#\\ description of the alteration.  Acknowledge the original version.  \\
#\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

from sage.sets.set import is_Set

class Dinner:
    """An ethiopian dinner game."""

    my_crossout_score = None;
    my_all_scores = None;
    my_is_pareto = None;
    my_is_weak_pareto = None;
    my_crossout_move = None;
    my_bob_vs_crossout = None;
    my_alice_vs_crossout = None;
    my_is_nash = None;


    ##########################################
    ### The initialisation and representation
    ##########################################

    def __init__(self, *indata):
        if isinstance(indata[0], sage.rings.integer.Integer):
            n = indata[0];
            self.my_size = indata[0];
            p = Permutations(n).random_element();
            G = Set( [] );
            for i in range(1,n+1):
                G = G.union( Set( [ tuple([i,p(i)]) ] ) );
            self.my_morsels = G;
        elif type(indata[0]) == sage.combinat.permutation.Permutation_class:
	    n = len(indata[0]);
            G = Set( [] );
            for i in range(1,n+1):
                G = G.union( Set( [ tuple([i,indata[0](i)]) ] ) );
            self.my_morsels = G;
            self.my_size = n;
        elif is_Set(indata[0]):
            self.my_morsels = indata[0];
            self.my_size = indata[0].cardinality();
        else:
            print "Input an integer (for a random game of that size), a permutation, or a set of tuples."
        if self.my_size % 2 == 0:
            self.my_is_even = True;
            self.my_is_odd = False;
        else:
            self.my_is_even = False;
            self.my_is_odd = True;

    def __repr__(self):
	return "An ethiopian Dinner having %s morsels: %s" % (self.size(), self.morsels())




    ####################################
    ### The following are user functions
    ####################################

    def morsels(self):
	### Returns the morsels of the game as a set of tuples.
	return self.my_morsels

    def size(self):
        ### Returns the size of the game (number of morsels).
        return self.my_size

    def is_even(self):
        ### Returns True if the game is of even size (Alice goes first).
        return self.my_is_even

    def is_odd(self):
        ### Returns True if the game is of odd size (Bob goes first).
        return self.my_is_odd

    def crossout_score(self, verbose=False):
        ### Returns the score of this game played Crossout-vs-Crossout
        if verbose or self.my_crossout_score is None:
            self.my_crossout_score = self.crossout_score_internal(0, 0, verbose);
            return self.my_crossout_score;
        else:
            return self.my_crossout_score;

    def all_scores(self, verbose=False):
        ### Returns all possible scores
        if verbose or (self.my_all_scores is None):
            self.my_all_scores = self.all_scores_internal(verbose);
            return self.my_all_scores;
        else:
            return self.my_all_scores;

    def is_pareto(self):
        ### Returns True if the game is Pareto optimal
        if self.my_is_pareto is None:
            self.is_pareto_internal();
            return self.my_is_pareto;
        else:
            return self.my_is_pareto;

    def is_weak_pareto(self):
        ### Returns True if the game is weakly Pareto optimal
        if self.my_is_pareto is None:
            self.is_pareto_internal();
            return self.my_is_weak_pareto;
        else:
            return self.my_is_weak_pareto;

    def crossout_move(self, verbose=False):
        ### Returns the first player's next move according to crossout
        if verbose or self.my_crossout_move is None:
            self.my_crossout_move = self.crossout_move_internal(verbose);
            return self.my_crossout_move;
        else:
            return self.my_crossout_move;

    def bob_vs_crossout(self, verbose=False):
        ### Returns the set of scores of all games played against Alice's crossout
        if verbose or self.my_bob_vs_crossout is None:
            self.my_bob_vs_crossout = self.bob_vs_crossout_internal(verbose);
            return self.my_bob_vs_crossout;
        else:
            return self.my_bob_vs_crossout;

    def alice_vs_crossout(self, verbose=False):
        ### Returns the set of scores of all games played against Bob's crossout
        if self.my_alice_vs_crossout is None:
            self.my_alice_vs_crossout = self.alice_vs_crossout_internal(verbose);
            return self.my_alice_vs_crossout;
        else:
            return self.my_alice_vs_crossout;

    def is_nash(self):
        ### Returns True if the game is a Nash equilibrium for both players
        if self.my_is_nash is None:
            self.my_is_nash = self.is_nash_internal();
            return self.my_is_nash;
        else:
            return self.my_is_nash;

    def show_all_scores(self):
        print self.morsels();
        return self.set_show(self.all_scores(),"blue");
    
    def show_bob_vs_crossout(self):
        print self.morsels();
        return self.set_show(self.bob_vs_crossout(),"orange");
  
    def show_alice_vs_crossout(self):
        print self.morsels();
        return self.set_show(self.alice_vs_crossout(),"orange");
    
    def show_all(self):
        print self.morsels();
        b = self.bob_vs_crossout();
        a = self.alice_vs_crossout();
        p1 = self.set_show(self.all_scores(),"black");
        p2 = self.set_show(b,"orange");
        p3 = self.set_show(a,Color("green").lighter().lighter());
        p4 = self.set_show(b.intersection(a),Color("green").lighter().lighter().blend(Color("orange"),0.55));
        return(show(p1+p2+p3+p4,aspect_ratio=1));




    ####################################################
    ### The following are meant to be internal functions
    ####################################################
   
    def crossout_score_internal(self, ascore, bscore, verbose=False):
        g = self.morsels();
        if verbose:
            print "The game is: ", g, ", with Alice's score: ", ascore, ", and Bob's score: ", bscore, ".";
        if g.cardinality() == 0:
            return [ascore, bscore];
        m = g.an_element();
        for i in g:
            if i[0] < m[0]:
                m = i;
        minset = Set([m]);
        if verbose:
            print "Alice crosses off: ", m, "and Bob gets ", m[1], "points.";
        bscore = bscore + m[1];
        g = g.symmetric_difference(minset);
        #print "The remaining game is: ", g;
        if g.cardinality() == 0:
            return [ascore, bscore];
        m = g.an_element();
        for i in g:
            if i[1] < m[1]:
                m = i;
        minset = Set([m]);
        if verbose:
            print "Bob crosses off: ", m, "and Alice gets ", m[0], "points.";
        ascore = ascore + m[0];
        g = g.symmetric_difference(minset);
        if verbose:
	    	print "Current score: ", [ascore, bscore];
        return( Dinner(g).crossout_score_internal(ascore, bscore, verbose) );

    def all_scores_internal(self, verbose=False):
        g = self.morsels();
        s = self.size();
        if s%2 == 0:
	    	s = s/2;
        else:
	    	s = (s-1)/2; # the number of morsels Alice eats in a game
        scoreset = Set([]);
        for r in g.subsets(s):
            ascore = 0;
            bscore = 0;
            for m in r:
                ascore = ascore + m[0];
            for m in g.symmetric_difference(r):
                bscore = bscore + m[1];
            if verbose:
                print "Subset ", r, "has score", [ascore, bscore];
            scoreset = scoreset.union(Set([tuple([ascore,bscore])]));
        return(scoreset);

    def is_pareto_internal(self):
        g = self.morsels();
        scores = self.all_scores();
        c = self.crossout_score();
        self.my_is_pareto = True;
        self.my_is_weak_pareto = True;
        for s in scores:
            if s[0] > c[0] and s[1] >= c[1]:
                self.my_is_pareto = False;
            if s[1] > c[1] and s[0] >= c[0]:
                self.my_is_pareto = False;
            if s[0] > c[0] and s[1] > c[1]:
                self.my_is_weak_pareto = False;
        return;

    def crossout_move_internal(self, verbose=False):
        g = self.morsels();
        if verbose:
            print "game is", g;
        m = g.an_element();
        for i in g:
            if i[0] < m[0]:
                m = i;
        minset = Set([m]);
        g = g.symmetric_difference(minset);
        if verbose:
            print "alice crossed", m, "game is", g;
        if g.cardinality() == 0:
            return m;
        m = g.an_element();
        for i in g:
            if i[1] < m[1]:
                m = i;
        minset = Set([m]);
        g = g.symmetric_difference(minset);
        if verbose:
            print "bob crossed", m, "game is", g;
        if g.cardinality() == 0:
            return m;
        return( Dinner(g).crossout_move_internal(verbose) );

    def bob_vs_crossout_internal(self, verbose=False):
        g = self.morsels();
        gsize = self.size();
        if gsize == 0:
            return(Set([tuple([0,0])]));
        ascore = 0;
        if gsize%2 == 0: # if the game is even, take Alice's move
            m = Dinner(g).crossout_move_internal();
            g = g.symmetric_difference(Set([m]));
            if verbose:
                print g;
            ascore = m[0];    
        global_scoreset = Set([]);
        for i in g:
            bscore = i[1];
            local_scoreset = Dinner(g.symmetric_difference(Set([i]))).bob_vs_crossout_internal(verbose);
            for s in local_scoreset:
                newa = s[0]+ascore;
                newb = s[1]+bscore;
                local_scoreset = local_scoreset.symmetric_difference(Set([s]));
                local_scoreset = local_scoreset.union(Set([tuple([newa,newb])]));
            if verbose:
                print "local_scoreset: ", local_scoreset;
            global_scoreset = global_scoreset.union(local_scoreset);
        return(global_scoreset);

    def alice_vs_crossout_internal(self, verbose=False):
        g = self.morsels();
        gsize = self.size();
        if gsize == 0:
            return(Set([tuple([0,0])]));
        bscore = 0;
        if gsize%2 == 1: # if the game is odd, take Bob's move
            m = Dinner(g).crossout_move_internal();
            g = g.symmetric_difference(Set([m]));
            if verbose:
                print g;
            bscore = m[1];    
        global_scoreset = Set([]);
        if g.cardinality() == 0:
            return( Set([tuple([0,bscore])]) );
        for i in g:
            ascore = i[0];
            local_scoreset = Dinner(g.symmetric_difference(Set([i]))).alice_vs_crossout_internal(verbose);
            for s in local_scoreset:
                newa = s[0]+ascore;
                newb = s[1]+bscore;
                local_scoreset = local_scoreset.symmetric_difference(Set([s]));
                local_scoreset = local_scoreset.union(Set([tuple([newa,newb])]));
            if verbose:
                print "local_scoreset: ", local_scoreset;
            global_scoreset = global_scoreset.union(local_scoreset);
        return(global_scoreset);

    def is_nash_internal(self):
        c = self.crossout_score();
        for s in self.bob_vs_crossout():
            if s[1] > c[1]:
                return False;
        for s in self.alice_vs_crossout():
            if s[0] > c[0]:
                return False;
        return True;

    def set_show(self, scores, col="blue"):
        p = sage.plot.plot.Graphics();
        for s in scores:
            p = p + point(s, color=col);
        p = p + point( self.crossout_score(), color="red");
        return(p);


################################################
### FUNCTIONS THAT YOU MIGHT USE WITH THIS CLASS
################################################

### CHECKS OVER ALL GAMES OF A GIVEN SIZE

def check_pareto(n):
    for s in Permutations(n):
        G = Dinner(s);
        if G.is_pareto() == False:
            print G;
    return "Done";

def check_weak_pareto(n):
    for s in Permutations(n):
        G = Dinner(s);
        if G.is_weak_pareto() == False:
            print G;
    return "Done";

def check_nash(n):
    for s in Permutations(n):
        G = Dinner(s);
        if G.is_nash() == False:
            print G;
    return "Done";