#! /usr/bin/env python

"""
Opis
====
Program pennies.py napisal David Goodger. Sluzy on do rozwiazania 
lamiglowki, zwanej Co do grosza (ang. Penny Pinching puzzle: 
[penny-pincher to dusigrosz - przyp. tlum.] 
http://www.primroselodge.com/Playtime/weekly_puzzle_20.htm).

Dane:
- N graczy tworzy krag
- kazdy gracz rozpoczyna z jednym groszem (lub pensem)
- gracze na przemian przekazuja 1, potem 2, potem 1, potem 2 (itd.)
  groszy do obok siedzacego gracza
- gracz opuszcza krag, kiedy nie ma juz monet jednogroszowych

Gracze 1 & 2 zawsze natychmiast opuszcza krag. Niekiedy, jeden
gracz zakonczy ze wszystkimi groszami. W pozostalych przypadkach,
 gra bedzie sie toczyc w nieskonczonym cyklu.

Pytania:
1. Jaka jest najmniejsza liczba graczy na poczatku gry, która toczy
   sie w nieskonczonosc?
2. Z wiecej niz 10 graczami, jaka jest najmniejsza liczba graczy
   w grze w której jeden z graczy zdobywa wszystkie monety
   jednogroszowe?
3. Jaki jest schemat dla liczby graczy, przy których gra toczy sie
   w nieskonczonosc?

Uzycie
======
    pennies.py [-t] [-v] liczbagraczy [do_liczbagraczy]

Z jednym argumentem - calkowita liczba graczy - pojedyncza symulacja 
dla tej liczby graczy bedzie wykonana. Z dwoma argumentami - 
poczatkowa i koncowa liczba graczy - symulacje sa przeprowadzane 
dla calego podanego zakresu liczb graczy.

Opcje
-----
-t : tryb testowy: wykonuje testowy zestaw symulacji.
-v : tryb komunikatywny (ang. verbose): pokazuje kazdy krok symulacji;
     domyslnie jest jedynie podsumowanie wyników.

Przyklady
---------
1. "pennies.py -v 5" przeprowadzi rozgadana symulacje dla 5 graczy.
2. "pennies.py 1 100" przeprowadzi i podsumuje symulacje dla liczby
    graczy od 1 do 100.

"""


class Player:
    """Reprezentuje pojedynczego gracza.
        Moze przekazywac i odbierac monety (grosze czy pensy)."""

    def __init__(self, playerNo):
        self.pennies = 1
        self.number = playerNo

    def passes(self, toPass):
        """Przekaz monety do mojego sasiada. Zwraca liczbe 
           przekazanych i pozostalych monet."""
        if toPass > self.pennies:   # sprawdza czy wystarczy monet
            print ("Warning: Player %s has only %s penny, must pass %s" 
                   % (self.number, self.pennies, toPass))
            print "(This shouldn't happen!)"
            toPass = self.pennies
        self.pennies = self.pennies - toPass
        return (toPass, self.pennies)

    def receives(self, toGet):
        """Odbierz monety od mojego sasiada. Zwraca calkowita liczbe
           posiadanych monet."""
        self.pennies = self.pennies + toGet
        return self.pennies


class Simulation:
    """Symulator lamiglówki Co do grosza (Penny Pinching)."""

    def __init__(self, nPlayers):
        self.nPlayers = nPlayers
        # tworzy liste obiektów Player:
        self.players = map(Player, range(1, nPlayers + 1))
        self.pennyList = [1] * nPlayers
        self.active = range(nPlayers)
        self.passer = ""            # gracz przekazujacy monety
        self.toPass = ""            # liczba monet wlasnie przekazanych
        width = len(str(nPlayers))
        self.playerFormat = ("%%-%ss  " % width) * nPlayers
        self.stateFormat = self.playerFormat + "P%s passes %s"
        self.header = (("P%%-%ss " % width) * nPlayers) % \
                      tuple(range(1, nPlayers + 1))

    def __str__(self):
        """Lancuchowa reprezentacja graczy."""
        return self.playerFormat % tuple(self.pennyList)

    def state(self):
        """Lancuchowa reprezentacja stanu symulatora."""
        return self.stateFormat % tuple(self.pennyList + 
                                        [self.passer, self.toPass])

    def run(self, verbosely=1):
        """Przeprowadz pojedyncza symulacje. Zwraca dwie listy:
           aktywnych graczy i calkowitej liczby zebranych monet."""
        if verbosely:
            print "Penny Pinching: %s Players\n" % self.nPlayers
            print self.header
        toPass = 1      # liczba monet dla nastepnego gracza
        toGet = 0       # liczba monet do dostania od ostatniego gracza
        states = {}     # zapis wszystkich wczesniejszych stanow
                        # symulacji dla wykrycia cyklicznych powtorzen
        if verbosely: print str(self) + "initial"
        index = 0
        while 1:
            if len(self.active) == 1:   # tylko 1 gracz pozostal?
                if verbosely: print str(self) + "final"
                break
            this = self.active[index]   # indeks biezacego gracza
                                        # indeks nastepnego gracza:
            next = self.active[(index + 1) % len(self.active)]
            # przypisz 2-elementowa wartosc zwrócona dwóm celom:
            (toGet, self.pennyList[this]) = \
                                    self.players[this].passes(toPass)
            self.pennyList[next] = self.players[next].receives(toGet)
            toPass = 3 - toPass         # przelacz miedzy 1 & 2 monety
            if not self.pennyList[this]:    # bez grosza?
                self.pennyList[this] = ""   # uporzadkuj ekran
                del self.active[index]      # gracz nieaktywny
                index = index % len(self.active)  # indeks bez zmian
            else:                       # gracz nadal aktywny.
                index = (index + 1) % len(self.active)  # indeks rosnie
            if verbosely:
                self.passer = this + 1  # +1 dla list opartych o 0
                self.toPass = toGet     # monety faktycznie przekazano
                print self.state()
            # utworz niezmienna wielokrotke, która moze byc uzyta jako
            # klucz slownika:
            state = tuple(self.pennyList + [self.passer, toPass])
            if states.has_key(state):   # sprawdza powtorzenia
                if verbosely: print str(self) + "repeats"
                break
            else:
                states[state] = 1       # zachowaj stan, przyda sie pozniej
        if verbosely:
            print "\n"
        return (self.active, self.pennyList)

def runSimulations(minPlayers, maxPlayers, verbosely=1, summarize=0):
    """Wykonaj symulacje dla podanego zakresu liczby graczy.
       Zwraca liste (poczatkowa liczba graczy, lista aktywnych graczy,
       lista calkowitej liczby zebranych monet)."""
                                        # inicjalizuje tablice results:
    results = [None] * (maxPlayers - minPlayers + 1)
    for n in range(minPlayers, maxPlayers + 1):     # zdobadz wyniki
        results[n - minPlayers] = (n,) + Simulation(n).run(verbosely)
        if summarize:
            summarizeOne(results[n - minPlayers])
    return results

def summarizeResults(results=[]):
    """Bez zadnego argumentu drukuje jedynie naglówek z podsumowaniem.
       Argument "results": ten sam output co z runSimulations"""
    print "Initial   Final"
    print "Players   Players"
    for result in results:
        summarizeOne(result)

def summarizeOne(result):
    print "%5s     %5s" % (result[0], len(result[1]))

def test():
    """Uruchamia symulacje dla od 1 do 100 graczy."""
    results = runSimulations(1, 20, 1, 0)  # info dla pierwszych 20-tu
    summarizeResults(results)
    runSimulations(21, 100, 0, 1)       # potem tylko podsumowanie

def showUsageAndExit(message=None):
    import sys
    sys.stdout = sys.stderr             # drukuj na strumien stderr
    if message:
        print 'Error: %s' % message
    print __doc__                       # lancuch z opisem dla modulu
    sys.exit(1)

# nie wykonywac tego kodu jesli zaimportowane jako modul:
if __name__ == "__main__":
    import getopt, sys
    verbose = 0
    try:
        opts, args = getopt.getopt(sys.argv[1:], 'tv')
        # opts to lista wielokrotek: kazda zawiera dwa elementy:
        # opcje i jej argument jesli wystepuje. Ponizsza petla for
        # przypisuje kazda opcje wielokrotki do o oraz argument do a.
        for o, a in opts:
            if o == '-t':
                test()
                sys.exit()
            elif o == '-v':
                verbose = 1
            else:
                raise getopt.error, 'Unknown option "%s"' % o
        if not 1 <= len(args) <= 2:
            raise getopt.error, 'One or two arguments needed.'
        firstnum = int(args[0])
        args.append(args[0])            # kopiuj firstnum na lastnum
        lastnum = int(args[1])          # chyba, ze juz specyfikowane
    except:                             # przechwyc tu wszystkie bledy
        type, value = sys.exc_info()[:2] # wydobadz info o wyjatku
        showUsageAndExit(value)
    if not verbose:                     # bedzie podsumowanie w trakcie
        summarizeResults()              # zatem drukuj jedynie naglowek
    results = runSimulations(firstnum, lastnum, verbose, not verbose)
