Oppaat: Python-ohjelmointi: Osa 11 - Alkeita edemmäs

Tämä opas sisältää hyödyllistä lisätietoa ohjelmoinnista ja Python-kielestä. Oppaan asiat eivät ole enää ohjelmoinnin alkeita, ja ilman niitä tulee tavallisesti toimeen mainiosti. Asiat kuuluvat silti ohjelmoijan yleissivistykseen, ja niiden tunteminen on silloin tällöin kullanarvoista.

Opas esittelee aluksi rekursiiviset funktiot, joiden avulla voi yleistää sisäkkäiset silmukkarakenteet. Oppaan muita aiheita ovat funktioparametri sekä Python-kielen hienouksiin kuuluva listakooste. Lopuksi nähdään neljä erilaista tapaa toteuttaa sama funktio: yleinen ilmiö ohjelmoinnissa.

Johdanto: Sisäkkäiset silmukat

DNA-ketju muodostuu merkeistä A, C, G ja T. Seuraava ohjelma listaa kaikki DNA-ketjut, joissa on kolme merkkiä (yhteensä 64 kpl):

for a in "ACGT":
    for b in "ACGT":
        for c in "ACGT":
            print(a + b + c)

Ohjelman tulostus on seuraava:

AAA
AAC
AAG
AAT
... (välissä rivejä)
CTG
CTT
GAA
GAC
... (välissä rivejä)
TTA
TTC
TTG
TTT

Ohjelman rakenteessa on ongelma: ohjelmassa on yhtä monta for-silmukkaa sisäkkäin kuin DNA-ketjussa on merkkejä. Ohjelman rakenne siis muuttuu sen mukaan, kuinka pitkiä DNA-ketjuja sen täytyy tulostaa. Tämä ei ole toivottava ilmiö, ja avuksi tulee rekursiivinen funktio.

Rekursio

Seuraava ohjelma listaa DNA-ketjut rekursiivisen funktion avulla. Ohjelman toiminta vastaa edellistä ohjelmaa, mutta funktio on yleiskäyttöinen: se pystyy muodostamaan kaikenpituisia DNA-ketjuja.

def ketju(pituus, alku = ""):
    if len(alku) == pituus:
        print(alku)
        return
    for jatko in "ACGT":
        ketju(pituus, alku + jatko)

ketju(3)

Funktio ketju on rekursiivinen eli se kutsuu itseään. Funktion parametrit ovat DNA-ketjun lopullinen pituus ja alkuosa. Jos DNA-ketju on halutun pituinen, funktio tulostaa sen eikä tee muuta. Muuten funktio käy läpi kaikki vaihtoehdot, mikä merkki tulee DNA-ketjun seuraavaksi merkiksi. Joka vaihtoehdon kohdalla funktio lisää merkin DNA-ketjuun ja kutsuu itseään.

Seuraava kuva esittää funktion ketju toiminta, kun DNA-ketjun alkuosa on "A" ja lopullinen pituus on 3. Funktio käy läpi kaikki vaihtoehdot DNA-ketjun toiseksi merkiksi ja kutsuu itseään alkuosilla "AA", "AC", "AG" ja "AT". Näissä kutsuissa funktio käy vastaavasti läpi kaikki vaihtoehdot DNA-ketjun kolmanneksi merkiksi.

Tässä ratkaisussa DNA-ketjun pituuden vaihtuminen ei ole ongelma: riittää muuttaa toista parametria funktion kutsussa. Esimerkiksi ohjelma voisi kysyä DNA-ketjun pituuden käyttäjältä seuraavasti:

pituus = int(input("Pituus: "))
ketju(pituus)

Rekursiivinen funktio sopii yleisemminkin tilanteisiin, joissa ohjelman täytyy käydä läpi jotain sisäkkäin ja kerrosten määrä vaihtelee.

Esimerkki: Reitinhaku

Seuraava ohjelma etsii reitin ulos labyrintista rekursiivisesti. Ohjelma lähtee liikkeelle labyrintin vasemmasta yläkulmasta ja pyrkii labyrintista ulos johtavaan ruutuun.

Sama labyrintti esiintyi aiemmin oppaassa 10.

kartta = [
    [1, 1, 1, 1, 1, 1],
    [1, 0, 1, 1, 0, 0],
    [1, 0, 0, 0, 0, 1],
    [1, 0, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1]
]

def haku(y, x, reitti = []):
    global kartta
    if y == 1 and x == 5:
        print("Ulos pääsee näin:")
        for suunta in reitti:
            print("Mene", suunta)
        return
    if kartta[y][x] == 0:
        kartta[y][x] = 2
        haku(y - 1, x, reitti + ["ylös"])
        haku(y + 1, x, reitti + ["alas"])
        haku(y, x - 1, reitti + ["vasemmalle"])
        haku(y, x + 1, reitti + ["oikealle"])

haku(1, 1)

Ohjelman tulostus on seuraava:

Ulos pääsee näin:
Mene alas
Mene alas
Mene alas
Mene oikealle
Mene oikealle
Mene oikealle
Mene ylös
Mene ylös
Mene ylös
Mene oikealle

Funktio haku merkitsee luvulla 2 ruudut, joissa se on käynyt. Jos funktio saapuu uuteen ruutuun, se käy läpi kaikki suunnat, johon ruudusta voi jatkaa. Parametri reitti on lista, joka kertoo, miten aloitusruudusta pääsee käsiteltävään ruutuun.

Ohjelma yrittää aina liikkua ensin ylös, sitten alas, sitten vasemmalle ja lopuksi oikealle. Tämän vuoksi ohjelma ei välttämättä löydä lyhintä reittiä ulos labyrintista. Näin käy myös tässä tapauksessa: ohjelma kiertää turhan lenkin labyrintin toiselta laidalta.

Funktioparametri

Seuraavassa ohjelmassa funktio suurin etsii listan suurimman alkion. Erikoista on, että funktion kutsussa voi määrittää, missä mielessä suurimman alkion funktio valitsee: parametri tapa on funktio, joka ratkaisee, mikä listan alkioista on suurin.

def suurin(lista, tapa):
    tulos = lista[0]
    for alkio in lista:
        if tapa(alkio) > tapa(tulos):
            tulos = alkio
    return tulos

nimet = ["Uolevi", "Henrikki", "Antti"]
print("Pisin nimi:", suurin(nimet, len))

luvut = [-2, 7, 3, -10, 5, 8]
print("Suurin itseisarvo:", suurin(luvut, abs))

def vokaalit(mjono):
    maara = 0
    for merkki in mjono:
        if merkki in "aeiouyäö":
            maara += 1
    return maara

luvut = ["apina", "banaani", "cembalo"]
print("Eniten vokaaleja:", suurin(luvut, vokaalit))

Ohjelman tulostus on seuraava:

Pisin nimi: Henrikki
Suurin itseisarvo: -10
Eniten vokaaleja: banaani

Ohjelma kutsuu funktiota suurin kolmesti: Ensin tapa on len, jolloin funktio etsii listan pisimmän merkkijonon. Sitten tapa on abs, jolloin funktio etsii listan luvun, jonka itseisarvo on suurin. Lopuksi funktio etsii listan merkkijonon, jossa on eniten vokaaleita, oman funktion vokaalit avulla.

Esimerkki: Listan järjestys

Seuraava ohjelma järjestää tuloslistan:

def avain(rivi):
    return -rivi[1], rivi[0]

lista = [
    ["Nimetön", 0],
    ["Henrikki", 80],
    ["Antti", 30],
    ["Uolevi", 100],
    ["Einari", 80]
]

lista.sort(key = avain)

for tulos in lista:
    print(tulos[0], tulos[1])

Ohjelman tulostus on seuraava:

Uolevi 100
Einari 80
Henrikki 80
Antti 30
Nimetön 0

Ohjelmassa on käytössä funktio avain, joka muuttaa alkion uuteen muotoon järjestämistä varten. Kun lista järjestetään, vertaillaankin alkioiden sijaan näitä avaimia. Avaimessa ensimmäisenä on pistemäärä negatiivisena. Suurin pistemäärä (100) onkin siis avainten joukossa pienin luku (-100) ja päätyy vertailussa listan kärkeen. Avaimessa toisena on pelaajan nimi, joten tasatilanteessa järjestyksessä vertaillaan nimiä.

Avainfunktion palauttamia tuloksia ja niiden järjestystä voi tutkia näin:

print(avain(["Einari", 80]))
# tulostaa (-80, 'Einari')

print(avain(["Einari", 80]) < avain(["Antti", 30]))
# tulostaa True, eli Einari tulee tuloksissa ennen Anttia

Listakooste

Seuraava ohjelma tulostaa lukujen 0–9 neliöt käyttäen listakoostetta:

neliot = [x * x for x in range(0, 10)]
print("Lukujen 0-9 neliöt:")
print(neliot)

Ohjelman tulostus on seuraava:

Lukujen 0-9 neliöt:
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

Listakoosteen avulla voi muodostaa kätevästi listoja. Listakooste kertoo, mitä muotoa listalle tulevat alkiot ovat ja mistä lähtöarvot haetaan. Tässä uuden listan alkiot ovat muotoa x * x eli luvun neliöitä ja lähtöarvo x tulee lukujonosta range(10) eli luvuista 0–9.

Listakooste voi sisältää myös ehdon:

neliot = [x * x for x in range(0, 10) if x % 2 == 0]
print("Parillisten lukujen 0-9 neliöt:")
print(neliot)

Ohjelman tulostus on seuraava:

Parillisten lukujen 0-9 neliöt:
[0, 4, 16, 36, 64]

Tässä listakoosteen ehto x % 2 == 0 tarkoittaa, että luvuista 0–9 otetaan mukaan vain parilliset luvut neliöiden pohjaksi.

Listakooste on usein hyödyllinen lyhennysmerkintä, mutta sen sijasta voi käyttää aina tavallisia silmukoita ja ehtoja. Esimerkiksi äskeisen ohjelman voi toteuttaa myös seuraavasti:

neliot = []
for x in range(0, 10):
    if x % 2 == 0:
        neliot.append(x * x)
print("Parillisten lukujen 0-9 neliöt:")
print(neliot)

Esimerkki: Korttipakka

Seuraava ohjelma valitsee korttipakasta viisi korttia satunnaisesti:

import random
maat = ["pata", "ruutu", "risti", "hertta"]
arvot = [str(x) for x in range(1, 14)]
kortit = [x + "-" + y for x in maat for y in arvot]
random.shuffle(kortit)
print("Kortteja on", len(kortit))
print("Viisi satunnaista korttia:")
for kortti in kortit[0:5]:
    print(kortti)

Ohjelman tulostus voi olla seuraava:

Kortteja on 52
Viisi satunnaista korttia:
pata-12
ruutu-7
hertta-3
ruutu-10
hertta-10

Tässä listakoosteen pohjana on kaksi listaa, mikä tarkoittaa, että listan alkioiden muodostuksessa käydään läpi kaikki tavat valita yksi alkio listasta maat ja yksi alkio listasta arvot – eli listaan tulevat kaikkien maiden kaikki kortit. Ohjelma tulostaa sekoitetun listan viisi ensimmäistä alkiota.

Uusinta: Merkkijonon kääntö

Seuraavassa on neljä erilaista funktiota, jotka kääntävät merkkijonon toisinpäin. Ensimmäinen funktioista on tuttu oppaasta 7, mutta muut funktiot ovat uusia.

def kaanna1(mjono):
    uusi = ""
    for merkki in mjono:
        uusi = merkki + uusi
    return uusi

def kaanna2(mjono):
    merkit = list(mjono)
    merkit.reverse()
    return "".join(merkit)

def kaanna3(mjono):
    if mjono == "":
        return mjono
    return mjono[-1] + kaanna3(mjono[:-1])

def kaanna4(mjono):
    return mjono[::-1]

Funktio kaanna1 turvautuu merkkijonojen peruspiirteisiin: se käy läpi alkuperäisen merkkijonon merkit ja muodostaa uuden merkkijonon yhdistämällä merkkejä toisiinsa. Funktion toimintaperiaate on siinä mielessä yleinen, että merkkijonon käännön voisi toteuttaa samalla tavalla monessa muussakin ohjelmointikielessä. Esimerkiksi C++:lla ja Visual Basicilla funktiot voisivat olla seuraavat:

// C++
string kaanna(string mjono) {
    string uusi = "";
    for (int i = 0; i < mjono.length(); i++) {
        uusi = mjono[i] + uusi;
    }
    return uusi;
}

' Visual Basic
Function kaanna(mjono)
    uusi = ""
    For i = 1 To Len(mjono)
        uusi = Mid(mjono, i, 1) + uusi
    Next
    kaanna = uusi
End Function

Funktio kaanna2 muuttaa merkkijonon listaksi, kääntää listan ja muuttaa listan takaisin merkkijonoksi. Tämä on järkevää, koska listassa on valmis metodi reverse, jolla sen voi kääntää helposti. Toisin sanoen funktio palauttaa merkkijonon kääntämisen ongelman listan kääntämisen ongelmaan, johon on tiedossa vaivaton ratkaisu.

Funktio kaanna3 toimii rekursiivisesti: Jos merkkijono on tyhjä, sitä ei tarvitse kääntää. Muuten funktio siirtää merkkijonon viimeisen merkin alkuun ja kääntää muun merkkijonon kutsumalla itseään. Tässä tapauksessa rekursiosta ei ole samanlaista hyötyä kuin aiemmissa esimerkeissä, koska merkkijonon voi kääntää helposti ilmankin, mutta funktio tuo silti kiinnostavan lähestymistavan ongelmaan.

Funktio kaanna4 hyödyntää hakasulkumerkintää, joka ottaa mukaan kaikki merkit käänteisessä järjestyksessä. Joku voisi sanoa, että tämä on Python-kielelle ominainen tapa kääntää merkkijono. Funktio on todella lyhyt, ja erillisen funktion sijasta merkkijonon voisi kääntää myös suoraan hakasulkumerkinnän avulla.

Mikä funktioista on sitten paras merkkijonon kääntämiseen? Tähän kysymykseen ei ole oikeaa vastausta, vaan kyseessä on mielipideasia. Ohjelmoinnissa saman asian voi tehdä usein monella tavalla ja mahdolliset ratkaisumenetelmät voivat olla hyvinkin erilaisia. Ohjelmoija saa olla luova ja kokeilla uutta, mikä on monen mielestä yksi hauskimmista asioista ohjelmoinnissa.