pamiętnik programisty

Zadanie z konkursu algorytmicznego dla uczniów szkół średnich. Zwróciłem na nie uwagę, gdyż współczynnik poprawnych rozwiązań wynosił lekko ponad 30%, a skoro to konkurs dla licealistów to powinienem sobie dać radę. I tu pierwszy szok, nic z tego… Wiedza jaką dysponowałem okazała się daleko nie wystarczająca, a próby znalezienia rozwiązania podanego na tacy spełzły na niczym. Co dodatkowo rozbudziło moją ciekawość to fakt że na forach poświęconych programowaniu, nikt nie szuka pomocy.
Zadanie finalnie okazało się rozbudowaną grą Nim, ale bez znajomości jednego twierdzenia teorii gier prawdopodobnie siedziałbym na tym jeszcze dłuuuugo…
Treść zadania dostępna pod adresem http://hs.spoj.pl/problems/HS09GAME/

Wspomniane twierdzenie to Twierdzenie Sprague-Grundy’ego. Gra przestawiona w zadaniu spełnia wszystkie założenia pozwalające na skorzystanie z twierdzenia. W połączeniu z dokładnie omówioną optymalną strategią, opisem pozycji wygrywających i przegrywających w grze Nim, pierwszą część zadania można rozwiązać w zaledwie 9 liniach

# gry - lista skladajaca sie z list reprezentujacych gre. Kazda reprezentacja
# gry to kolejna lista zaiwerajaca ilosc 'kijkow' na kolejnych stosach
def graj(gry):
    sg = (0, 0, 1, 1, 2, 2, 3)
    for gra in gry:
        g = []
        reszty = []
        for stos in gra:
            reszta = int(stos)%7
            g.append(sg[reszta])
            reszty.append(reszta)
        wynik = reduce(lambda x,y: x^y, g)

        if wynik :
            print "Julia wins."
        else :
            print "Robert wins.\n"

Lekki problem pojawia się przy ustalaniu ruchu wygrywającego. Nie wiem czy istnieje jakieś szybsze rozwiązanie niż takie trochę brute-force’owe która ja wykorzystałem. Polega ono na stwierdzeniu na jakiej pozycji ( wygrywającej czy przegrywającej ) znalazł by się gracz gdyby nie było jednego stosiku, a następnie obliczeniu czy da się odjąć taką liczbę patyczków żeby zostawić przeciwnika na pozycji przegrywającej.
Dodatkowo oprócz wskazania ruchu wygrywającego należy wskazać ten podczas którego bierze się najwięcej patyczków ze stosu o najmniejszym numerze, co w lekki sposób komplikuje sprawę.:

        stos_wygrywajacy = 0;
        licznik = 0
        blokada_5 = False
        blokada_3 = False

        # odwrocenie list, sprawdzanie od konca
        gra_rev = gra[:]
        gra_rev.reverse()

        g_rev = g[:]
        g_rev.reverse()

        reszty.reverse()
        for reszta in reszty:
            # lista reszt bez kolejnych stosow
            tmpr = reszty[:]
            tmpr.pop(licznik)

            # xor wartosci f. Sprague-Grundy'ego
            # bez kolejnych stosow
            tmpg = g_rev[:]
            tmpg.pop(licznik)
            tmpw = reduce(lambda x,y: x^y, tmpg ,0)

            if sg[reszta-5] == tmpw and int(gra_rev[licznik]) >= 5:
                wygrywajacy = 5
                stos_wygrywajacy = len(reszty) - licznik
                blokada_5 = True
            elif sg[reszta-3] == tmpw and int(gra_rev[licznik]) >= 3 and blokada_5 == False:
                wygrywajacy = 3
                stos_wygrywajacy = len(reszty) - licznik
                blokada_3 = True
            elif sg[reszta-2] == tmpw and int(gra_rev[licznik]) >= 2 and blokada_5 == False and blokada_3 == False:
                wygrywajacy = 2
                stos_wygrywajacy = len(reszty) - licznik

            licznik += 1

Jeśli ktoś zna szybsze rozwiązanie chętnie je przeanalizuję
Zaznaczam, że nie dam sobie głowy uciąć że algorytm jest poprawny, bo nie ma już możliwości zgłoszenia rozwiązania – upłynęły terminy.

EDIT:
Lekko poprawiona wersja, działa trochę szybciej, natomiast i tak nie umożliwia zdobycia maximum punktów. Jesli nie ma jakiejś sztuczki na ruch wygrywający, a podejrzewam że coś jest, to lepiej zakodzić to w C…

        stos_wygrywajacy = 0
        blokada_3 = False
        blokada_2 = False
        licznik = 0
        for reszta in reszty :
            tmpg = g[:]
            tmpg.pop(licznik)
            tmpw = reduce(lambda x,y: x^y, tmpg, 0)

            if sg[reszta-5] == tmpw and int(gra[licznik]) >= 5:
                wygrywajacy = 5
                stos_wygrywajacy = licznik + 1
                break
            elif sg[reszta-3] == tmpw and int(gra[licznik]) >= 3 and blokada_3 == False:
                wygrywajacy = 3
                stos_wygrywajacy = licznik + 1
                blokada_3 = True
            elif sg[reszta-2] == tmpw and int(gra[licznik]) >= 2 and blokada_3 == False and blokada_2 == False:
                wygrywajacy = 2
                stos_wygrywajacy = licznik + 1
                blokada_2 = True
            licznik += 1