Listapeli

Listapelissä kaksi pelaajaa poistaa vuorotellen lukuja listasta. Joka vuorolla pelaajan tulee poistaa listalta joko ensimmäinen tai viimeinen luku. Peli päättyy, kun kaikki luvut on poistettu.

Pelin voittaa pelaaja, jonka poistamien lukujen summa on suurempi. Jos kummankin pelaajan lukujen summa on sama, tuloksena on tasapeli. Tehtäväsi on selvittää, voittaako pelin aloittaja varmasti, jos hän pelaa optimaalisesti.

Esimerkiksi jos lista on $[2,1,3]$, aloittaja voittaa varmasti, koska hän voi poistaa ensin luvun $3$ ja sitten luvun $1$. Pelin lopussa aloittajan lukujen summa on $4$ ja toisen pelaajan lukujen summa on $2$.

Jos taas lista on $[1,3,1]$, aloittaja ei voita varmasti, koska hänen täytyy poistaa ensin luku $1$. Tämän jälkeen toinen pelaaja voi poistaa luvun $3$, mikä takaa hänelle pelin voiton.

Toteuta tiedostoon listgame.py funktio first_wins, jolle annetaan lista kokonaislukuja. Funktion tulee palauttaa True, jos pelin aloittaja voittaa varmasti, ja muuten False.

Funktion tulee toimia tehokkaasti, kun listalla on $1 \dots 50$ lukua.

def first_wins(numbers):
    # TODO

if __name__ == "__main__":
    print(first_wins([2, 1, 3])) # True
    print(first_wins([1, 3, 1])) # False

    print(first_wins([1])) # True
    print(first_wins([1, 1])) # False
    print(first_wins([1, 5])) # True
    print(first_wins([1, 1, 1])) # True
    print(first_wins([1, 2, 3, 4])) # True
    print(first_wins([1, 3, 3, 7, 4, 2, 1])) # False

    print(first_wins([1] * 50)) # False
    print(first_wins([1, 2] * 25)) # True