Integraalipäiväjutun ohjelmointihaaste

Integraalipäiväjutussa [1] Markku Leino kysyi: ”Osaatko (ja pystytkö) rakentamaan ohjelmakoodin, joka tekee itsesimilaarin puun? Mikä ohjelmointikieli olisi kätevä?” Vastatakseni haasteeseen poimin esiin binääripuita koskevan osan yli kolmekymmentä vuotta sitten MAOLin Kiinan matkaa varten valmistelemastani esitelmätekstistä [2]. Matkan sujumisesta olen kertonut aikaisemmin Dimensio-lehdessä [3].

Yksinkertaisin esimerkki fraktalisoituvasta, itsesimilaarisesta puurakenteesta on binääripuu. Sen kasvattaa vaihe vaiheelta rekursiivinen prosessi, joka lisää runkoon kaksi oksaa kerrallaan (kuva 1):

to tree :branch :angle
   if :branch < 1 [stop]
   forward :branch
   left :angle tree 0.62 * :branch :angle
   right 2 * :angle tree 0.62 * :branch :angle
   left :angle back :branch
end
Binääripuun rakentuminen, viivapiirros puusta joka haarautuu joka haarassa symmetrisesti kahdeksi
Kuva 1: Binääripuun rakentuminen vaihe vaiheelta. Kuva on alkuperäisestä käsikirjoituksesta [2].

Ohjelmassa on kaksi parametria: ensimmäisen haaran (eli rungon) pituus ja haarautumiskulma. Ohjelma on kirjoitettu niin, että ne annetaan ohjelmakutsussa. Itse ohjelmakoodissa on kolmas parametri, joka määrää oksan pituuden edelliseen verrattuna: 0.62. Sekin voisi tietysti olla myös ohjelmakutsussa. Näitä vaihtelemalla saadaan jo monenlaisia puita (kuva 2). 

Erilaisilla parametreillä piirrettyjä binääripuita, eri haarautumiskulmat, eri määrä rekursiota
Kuva 2: Binääripuita, joissa haaran pituus ja haarautumiskulma vaihtelevat.

Esimerkkinä soveltamisesta käytin esitelmässäni sukupuuta (kuva 3).

Viivapiirros neljätasoisesta sukupuu, jossa nimetty kullekin ihmiselle äiti ja isä
Kuva 3: Esivanhempien puu on esimerkki binääripuusta, isät aina vasemmassa ja äidit oikeassa haarassa. Kuva on alkuperäisestä käsikirjoituksesta [2].

Puusta saa luonnollisemman ja vaihtelevamman, kun lisätään useampi haara ja niihin paksuutta tai satunnaisuutta (kuva 4). Samalla ohjelmakoodikin pitenee tietysti:

to 3tree :branch :angle
   if :branch < 3 [stop]
   line :branch round :branch / 6
   left :angle 3tree 0.6 * :branch :angle
   right :angle 3tree 0.5 * :branch :angle
   right :angle 3tree 0.6 * :branch :angle
   left :angle back :branch
end
to line :length :thickness
   if 0 = remainder :thickness 2 [make "thickness :thickness +1]
   fd :length
   line1 1
end
to line1 :times
   if not :times < :thickness [lt 90 fd (:thickness - 1) / 2 rt 90 stop]
   lt 90 fd :times lt 90 fd :length
   line1 :times + 1
end
Viivapiirroksia erilaisista binääripuista, kolmihaarainen, sellainen jossa haarojen pituus ja kallistuskulma vaihtelee jne
Kuva 4: Kolmihaarainen puu ja satunnaistettu binääripuu. Kuvat alkuperäisestä käsikirjoituksesta [2].

Muuttamalla haarautumiskulmaa saadaan puut myös taipumaan (kuva 5)

Viivapiirroksia binääripuista, jotka näyttävät taipuvan kuin tuulessa, koska haarojen kallistuskulma vaihtelee
Kuva 5: Myös digitaalipuu taipuu kuin tuulessa. Kuva alkuperäisestä käsikirjoituksesta [2].

Tämä juttu ei yritäkään vastata Markun jälkimmäiseen kysymykseen kätevästä ohjelmointikielestä. Olkoon vain esimerkkinä siitä, miten binääripuita tuotettiin neljättä kymmentä vuotta sitten kilpikonnagrafiikalla. Minulle oli yllätys, että aikoinaan Commodore-Logolla kirjoittamani koodi toimi edelleen sellaisenaan FMS-Logossa.

Lähteet

[1] Palojärvi, Neea ym.: Ensimmäiset Integraalipäivät 16.–18.4.2021. Dimensio 26.8.2021 osoitteessa    https://staging.dimensiolehti.qs.fi/ensimmaiset-integraalipaivat-16-18-4-2021/

[2] Korhonen, Hannu (1989): Fractal demonstrations in Logo language by the help of 乌龟,  wu gui, the turtle. Paper to be presented at Chinese–Finnish-symposium on mathematics and science instruction, Fudan University, Shanghai, June 8th 1989. Julkaisematon.

[3] Korhonen, Hannu (2018): Pakoon junalla luentomatkalta. Dimensio 1/2018, s. 41.

Kirjoittaja