Robotti

Tässä tehtävässä robotille annetaan syötteenä merkkijono, joka muodostuu merkeistä 0 ja 1. Robotti käsittelee merkkijonon säännöstön perusteella ja hyväksyy tai hylkää sen.

Ennen robotin käsittelyä merkkijonon vasemmalle puolelle lisätään merkki L ja oikealle puolelle lisätään merkki R. Tämän avulla robotti voi tunnistaa, missä ovat merkkijonon rajat. Esimerkiksi jos syötteenä on merkkijono 0110, robotti saa sen muodossa L0110R.

Käsittelyn alussa robotti on merkkijonon ensimmäisen merkin (L) kohdalla ja robotin tila on 1.

Robotti käsittelee merkkijonon säännöstön perusteella. Tietty sääntö aktivoituu, kun robotti on tietyn merkin kohdalla tietyssä tilassa. Tällöin robotti muuttaa merkkiä ja tilaansa sekä suorittaa toiminnon. Toiminto on yksi seuraavista:

• LEFT: liiku askel vasemmalle
• RIGHT: liiku askel oikealle
• ACCEPT: hyväksy syöte
• REJECT: hylkää syöte

Säännöissä jokainen merkki on 0, 1 tai kirjain välillä A–Z. Jokainen tila on kokonaisluku välillä 1–100. Jokaiseen merkin ja tilan yhdistelmään liittyy enintään yksi sääntö. Jos robotti liikkuu merkkijonon ulkopuolelle tai ei löydä tilanteeseen sopivaa sääntöä, robotti hylkää syötteen.

On mahdollista, että robotti jää ikuiseen silmukkaan eikä hyväksy tai hylkää syötettä koskaan. Tämän takia jos robotti ei ole hyväksynyt tai hylännyt syötettä tuhannen toiminnon suorittamisen jälkeen, robotin toiminta tulee keskeyttää ja myös silloin robotti hylkää syötteen.

Toteuta tiedostoon robocalc.py funktio calculate, jolle annetaan syöte sekä robotin säännöstö. Funktion tulee ilmoittaa, hyväksyykö vai hylkääkö robotti syötteen. Esimerkiksi sääntö ("0", 2, "X", 4, "RIGHT") tarkoittaa, että kun robotti on merkin 0 kohdalla tilassa 2, se muuttaa merkiksi X ja tilaksi 4 sekä liikkuu askeleen oikealle.

def calculate(input, rules):
    # TODO

if __name__ == "__main__":
    rules = []

    rules.append(("L", 1, "L", 2, "RIGHT"))
    rules.append(("L", 3, "L", 2, "RIGHT"))

    rules.append(("0", 2, "X", 4, "RIGHT"))
    rules.append(("1", 4, "X", 5, "RIGHT"))
    rules.append(("1", 2, "X", 6, "RIGHT"))
    rules.append(("0", 6, "X", 7, "RIGHT"))

    rules.append(("0", 4, "0", 4, "RIGHT"))
    rules.append(("0", 5, "0", 5, "RIGHT"))
    rules.append(("0", 7, "0", 7, "RIGHT"))
    rules.append(("1", 6, "1", 6, "RIGHT"))
    rules.append(("1", 5, "1", 5, "RIGHT"))
    rules.append(("1", 7, "1", 7, "RIGHT"))

    rules.append(("X", 2, "X", 2, "RIGHT"))
    rules.append(("X", 4, "X", 4, "RIGHT"))
    rules.append(("X", 5, "X", 5, "RIGHT"))
    rules.append(("X", 6, "X", 6, "RIGHT"))
    rules.append(("X", 7, "X", 7, "RIGHT"))

    rules.append(("R", 2, "R", 2, "ACCEPT"))
    rules.append(("R", 4, "R", 4, "REJECT"))
    rules.append(("R", 6, "R", 6, "REJECT"))

    rules.append(("R", 5, "R", 3, "LEFT"))
    rules.append(("R", 7, "R", 3, "LEFT"))
    rules.append(("0", 3, "0", 3, "LEFT"))
    rules.append(("1", 3, "1", 3, "LEFT"))
    rules.append(("X", 3, "X", 3, "LEFT"))

    print(calculate("0", rules)) # False
    print(calculate("00", rules)) # False
    print(calculate("01", rules)) # True
    print(calculate("0110", rules)) # True
    print(calculate("0101", rules)) # True
    print(calculate("1000", rules)) # False
    print(calculate("00110101", rules)) # True
    print(calculate("00111101", rules)) # False

Tässä säännöstön tarkoituksena on, että robotti tunnistaa, onko merkkien 0 ja 1 määrä syötteessä sama. Robotti käy syötettä läpi vuorotellen vasemmalta oikealle ja oikealta vasemmalle. Aina oikealle liikkuessaan robotti korvaa yhden merkin 0 merkillä X ja yhden merkin 1 merkillä X. Jos lopulta kaikki merkit on korvattu merkillä X, robotti hyväksyy syötteen.