Pitäisikö uudenvuoden juhlinnan lomassa olla enemmän koodattavaa? 🙂

Minulla liikeni vihdoin aikaa kyhätä jonkinlainen koodi kasaan seuraavaa matemaattista koodaustehtävää varten. En ihan saanut ulos tätä ennen joulua. Kuulin tämän itse aikanaan lukiossa.

Pulma:
Sadistinen ja kummallisista oikuistaan tunnettu Tiademon Von Ginvar on kaapannut sata (100) matemaatikkoa vangikseen ja pitää heitä linnassaan eristysselleissä. Vangit eivät voi koskaan kommunikoida toistensa kanssa mitenkään. Tämä käy Von Ginvarista kuitenkin pidemmän päälle pitkästyttäväksi, ja hän kutsuu kaikki sata vankia yhteen suureen saliin ja kertoo heille:

“Tämän linnan tyrmässä on tyhjä huone, jossa on valo ja valonkatkaisija. Huomisesta päivästä alkaen arvon teistä satunnaisen uhrin ja vien hänet tähän huoneeseen. Hän saa olla siellä tunnin, jonka jälkeen tulen kysymään häneltä, onko teistä kurjimuksista joka ikinen käynyt jo ainakin kerran huoneessa. Mikäli jonain päivänä saan myöntävän vastauksen ja se pitää paikkansa, pääsette kaikki vapaaksi. Mutta jos saan myöntävän vastauksen ja se ei pidäkään paikkansa, teloitan teidät kaikki. Lisäksi vapautan myrkkyä suurkaupunkimme juomaveteen! Jos vanki ei anna myöntävää vastausta, rontti palatkoon eristysselliinsä. Saatte pitää huonetta pimeänä tai valaistuna miten haluatte. En aio koskea valoihin. Mutta jos yritätte viestiä toisillenne, teloitan teidät välittömästi! Saatte olla vielä tämän päivän yhdessä, mutta illalla palaatte eristysselleihin, ettekä enää koskaan tapaa toisianne.”

Katalasti nauraen Von Ginvar jättää vangit suljettuun saliin lopuksi päivää. Millaisen suunnitelman vangit voivat laatia päästäkseen lopulta vapaaksi?

Koska Von Ginvar valitsee joka päivä satunnaisesti vangin, voi olla, että arpa osuu samaan vankiin joka kerralla. Tässä tapauksessa vangit eivät vapaudu koskaan, vaikka he olisivat kuinka ovelia tahansa. Se on kuitenkin hyvin epätodennäköistä. Onko siis mahdollista löytää strategiaa, jolla vangit pääsevät vankilasta pois 100% todennäköisyydellä keskimäärin vaikkapa viiden vuoden kuluttua?

Odotusarvolaskut tähän pulmaan liittyen ovat pidemmän päälle riittävän kauheita, jotta tekee mieli ottaa koodi avuksi! Loin valmiin rungon oman ratkaisun testaamista varten python2:lla (löytyy postauksen lopusta). Koodissa on toteutettu luokat Room, Prisoner, Prison ja Simulation. Vankien nykyinen strategia on olla tekemättä mitään huoneessa ja vastaamalla negatiivisesti (return False) vanginvartija Tiademonin kysymykseen. Evaluate.py ajaa oletusarvoisesti sata simulaatiota vankiongelmasta ja tulostaa arvion ratkaisusta.

Oman ratkaisun voi toteuttaa Prisoner-luokan sleep- ja goToRoom-metodeihin ja arvioida sen ajamalla evaluate.py.

Vanki saa tietää huoneen valotilanteen room-instanssilta:

valotilanne = room.light

Vanki voi asettaa valon päälle tai pois:

room.light = True

Vanki voi myös muistaa asioita, esim.:

self.__memories.append["The prison food was bad today."]

…ja muistella asioita, esim.:

if len(self.__memories > 0): memory = self.__memories[-1]

Koodini ei estä tekemästä tuhmia asioita, kuten asettamasta valon arvoksi “Kilroy was here”, jos vain osaa Pythonia. Yritin toteuttaa testikoodista version, jossa voisi muokata vapaasti solution.py-nimistä tiedostoa ja saada evaluate.py-koodin ajamisesta vastaukseksi virheilmoituksen, jos yrittää tehdä jotain kiellettyä. Se meni kuitenkin aika vaikeaksi minun taidoillani – plus hitaaksi. Pythonissa ei ole aidosti privaatteja metodeja tai attribuutteja. Alaviivojen käyttö metodin tai attribuutin nimen edessä, esim. self.__memory, on lähinnä viesti lukijalle: en halua ulkopuolisten koskevan tähän! Yksi viiva: pliis älä; kaksi viivaa: pliis pliis älä.

Jos löydät koodista bugeja, kerro blogin tai Facebook-postauksen kommenteissa. Jos on kysyttävää, kysy. Jos osaat tehdä paremman koodin, jaathan sen kanssamme 🙂 Minä vasta harjoittelen pythonia. Parhaan ratkaisun laatijalle paljon rispektiä ja ehkä jotain muutakin, jos keksitään!

Terkuin,
Valhe Kouneli

Pääset lataamaan zipatut kooditiedostot klikkaamalla tästä.

class Room(object):
    """
    True  => light is on
    False => light is off
    """

    def __init__(self):
        self.__light = True

    @property
    def light(self):
        return self.__light

    # sure, you can circumvent this, but don't
    @light.setter
    def light(self, value):
        if value == True or value == False:
            self.__light = value
        else:
            print "Cannot switch light to '%r'." % value

from room import Room

class Prisoner(object):

    def __init__(self, value):
        self.__id = value
        self.__memories = [] # use me

    @property
    def id(self):
        return self.__id

    def sleep(self):
        # chill in your cell
        # watch the endless days go by
        pass

    def goToRoom(self, room):
        # do something in the room
        # make the light go strobo and have a private disco
        # make happy new memories
        # return True if all prisoners have been in the room
        return False

from prisoner import Prisoner
from room import Room
import random

class Prison(object):

    def __init__(self):
        self.day = 0
        self.prisoners = []
        # Prison has 100 Prisoners
        for i in range(0, 100):
            self.prisoners.append(Prisoner(i))
        self.room = Room()

    def passDay(self):
        for prisoner in self.prisoners:
            prisoner.sleep() # staying awake is strictly forbidden

    def sendToRoom(self, id):
        silence = not self.prisoners[id].goToRoom(self.room)
        if (silence == True or silence == False):
            return silence
        else:
            return True

from prison import Prison
from room import Room
from random import randint

class Simulation(object):

    def __init__(self):
        self.prison = Prison()
        self.day = 0
        self.result = ''       # result = 'old', 'freed' or 'died'
        self.__roomed = set()  # Keeps count of the prisoners
                               # who have been in the room

    def run(self):
        # simulation stops when too many days have passed,
        # which means the prisoners have died of old age,
        # or when one of the prisoners makes a declaration
        # that every prisoner has been in the room;
        # that is, when sendToRoom(id) returns True

        silence = True
        while silence and self.day < 365*80:

            self.prison.passDay()
            self.day += 1

            # a random prisoner is chosen
            id = randint(0,99)

            # send prisoner to the room and listen if they make a    
            # declaration
            silence = self.prison.sendToRoom(id)

            # guard takes note who has been in the room
            self.__roomed.add(id)

        # end of simulation
        if silence:
            self.result = "old"
        elif len(self.__roomed) == 100: # all 100 prisoners have been 
                                        # in the room
            self.result = "freed"
        else:
            self.result = "died"

from simulation import Simulation
import sys

"""
Simulates the prison problem 100 times or any number of times that
is given as an argument to the script.
Prints out statistics about how well the prisoners did
based on the algorithm the prisoners used.
"""


if (len(sys.argv) > 1 and
    arg.isdigit() and
    int(arg) > 0):
    # command line argument is given and it is a number > 0
    simulations = int(sys.argv[1])
else:
    simulations = 100


old = 0
freed = 0
days_total = 0

# Simulate n=simulations times
for i in range(0,simulations):
    print "Running simulnr %d" % (i+1)
    simul = Simulation()
    simul.run()
    result = simul.result
    day = simul.day
    del simul # is this necessary
    if result == "freed" :
        freed += 1
        days_total += day
    elif result == "old":
        days_total += day
        old += 1

died = simulations - old - freed
success_percent = int( 100 * freed / simulations )
did_not_die = int(( freed + old ) * 100 / simulations)
if freed > 0:
    avg_time = int(days_total / freed)
else:
    avg_time = 0

print "Success percent is %d%%." % success_percent
print "(Died of old age or were freed %d%% of time.)" % did_not_die
if avg_time != 0:
    print "Average time to get out is %d days which is about %d years." \
    % (avg_time, int(avg_time / 365))

Teksti: Valhe Kouneli
Kuva: Laura Pesola