Verkkopeli

Kaksi pelaajaa pelaavat peliä suunnatussa syklittömässä verkossa, jonka solmut ovat $1,2,\dots,n$.

Pelissä on yksi yhteinen pelinappula, joka on alussa solmussa $x$. Pelaajat siirtävät nappulaa vuorotellen johonkin solmuun, johon pääsee suoraan kaarella nykyisestä solmusta.

Peli jatkuu, kunnes vuorossa oleva pelaaja ei voi tehdä mitään siirtoa eli pelinappula on solmussa, josta ei pääse mihinkään toiseen solmuun kaarta pitkin. Tällöin toinen pelaaja voittaa pelin.

Toteuta tiedostoon graphgame.py luokka GraphGame, jossa on seuraavat metodit:

• add_link lisää kaaren solmusta $a$ solmuun $b$
• winning kertoo, voittaako aloittaja pelin solmusta $x$, kun molemmat pelaajat pelaavat optimaalisesti

Metodi winning tulee toteuttaa tehokkaasti dynaamisen ohjelmoinnin avulla.

class GraphGame:
    def __init__(self, n):
        # TODO

    def add_link(self, a, b):
        # TODO

    def winning(self, x):
        # TODO

if __name__ == "__main__":
    game = GraphGame(6)

    game.add_link(3, 4)
    game.add_link(1, 4)
    game.add_link(4, 5)

    print(game.winning(3)) # False
    print(game.winning(1)) # False

    game.add_link(3, 1)
    game.add_link(4, 6)
    game.add_link(6, 5)

    print(game.winning(3)) # True
    print(game.winning(1)) # False
    print(game.winning(2)) # False