Se tavallinen APL-tarina

Eräänä päivänä noin vuosi takaperin työtoverini MKS - tietojenkäsittelyopin DI, muuten - marssi ovesta sisään, ongelman kera. Hän aloitti tarinansa haasteellisella "Sinähän olet aina kertonut APL:n kyvyistä, minulla on ongelma, joka saattaisi kiinnostaa..". Kehotin istumaan.

Lyhyessä ajassa sain selville, että eräs internetissä lymyilevä henkilö on tekemässä strategiapeliä, jonka keskeisenä osana on hankalaksi viritetty korttipeli. Tekijä oli päättänyt tehdä sellaisen korttipakan sääntöineen, jonka eri jakokäsien todennäköisyyslaskennan piti olla niin vaikeata, ettei kukaan saisi sitä järjellisessä ajassa lasketuksi.

Tämähän oli MKS:lle punainen vaate, ja hän riensi tekemään Visual B:llä raa'asti eri kädet läpiluuppaavan ohjelman. Yhden ja kahden kortin kädet laskeutuivat triviaalitapauksina heti, kolmikorttisen käden tapaus oli sitten vienyt useamman tunnin, nelikorttisen laskenta oli menossa.

Muuten meni mukavasti, mutta sen estimoitiin vievän yli viikonlopun ja viiden kortin laskenta selvinneisi ehkä ennen joulua…

Nopea ja tyhmä algoritmi ei ollutkaan se paras mahdollinen. Eli siis - olisiko APL:stä johonkin?

Kyseisessä korttipakassa on kolmen värisiä (G, R, Y) peruskortteja, joilla on arvoja nollasta kolmoseen, ja lisäksi eri tyyppisiä erikoiskortteja (b, m, d, f). Jokaista korttityyppiä on pakassa vaihtelevat määrät. Kädessä voi olla yhdestä viiteen korttia. Käden arvo määräytyy eri värikorttien summasta (ei väriä = -1), ja siitä, onko jotain erikoiskorttia kädessä (-1) vai ei (0). Esimerkiksi käsi "G3 G3 Y0 b b m" on arvoltaan "G6 R-1 Y0 b0 m0 d-1 f-1".

Tulisi siis saada selville eri käsien mahdolliset jakaumat.

Onneksi oli kotiinlähdön aika, jotta sain ajatustaukoa. Pasilan rullaportaissa sain ideantyngän, lasten nukutustoimien jälkeen pääsin vihdoin koneen ääreen ja perusrunko syntyi nopeasti, ainoastaan indeksivariaatioiden laskentafunktion teko takkuili (suora ulkotuloidiomi hyytyi ikävästi isoilla massoilla).

Aamulla pääsin vakavalla naamalla kertomaan MKS:lle että laskenta vie siinä kymmenen minuuttia - kymmenen kortin kädelle! Viiden kortin tapaus hujahti sentään seitsemässä sekunnissa.

Pitkä hiljaisuus, ja sitten: "Olisko sulla jotain APL-matskua luettavaksi?".

Ratkaisutapa syntyi intuitiolla, joten todennäköisesti jossain on vieläkin parempi "oikea" algoritmi vaanimassa, mutta väliäpä hällä. Tämän ratkaisun ytimenä on tarkastella kuinka monta erilaista korttivaihtoehtoa eri suuruisiin käsiin voi saada, ja painottaa saatuja kombinaatioita eri tyyppisten korttien lukumäärien permutaatioilla. Ratkaisun ydin on näin vain yhdestä APL-symbolista kiinni!

Käydään suoraan koodiin: ensin pääfunktio, argumenttina on käden koko (1-5, isommatkin sujuvat).

’ z„Jako n;a;arv;b;i;ind;inx;j;kasi;lkm;lst;rho;tul;ŒIO;ŒML
[1] (ŒIO ŒML)„1 3
[2] © G: 0 1 2 3,R: 0 1 2 3,Y: 0 1 2 3,boom sdf sdt & mob
[3] lkm„3 10 7 5, 5 20 15 10, 3 10 7 5, 5 2 5 7
[4] arv„0 1 2 3, 0 1 2 3, 0 1 2 3, 1, 1, 1, 1

Samanlaisten korttiryhmien lukumäärät ja arvot (huomaa erikoiskorttien ns. omalaatuiset nimet).

[5] rho„½lkm ª lst„rho Kadet n
[6] ind„rho Indeksit n

Kadet tuottaa ne lukukombinaatiot, joilla saadaan haluttu summa; eli siis millä tavoin jakokäsi voidaan koostaa eri korttiryhmistä. Indeksit tuottaa ne indeksivaihtoehdot, joilla n korttia voidaan ottaa rho:sta eri pakasta. Kummankin funktion listaus seuraa jäljempänä.

[7] z„0 8½0

Tulosmatriisiin viedään käsittäin lukumäärä ja käden sisältö järjestyksessä värikortit G, R, Y (summattuina) ja erikoiskorttien esiintymät (boo sdf sdt mob).

[8] :For i :In ¼½lst
[9] kasi„,iœlst ª inx„(½kasi)œind

Hommiin: käydään kaikki käsikombinaatiot läpi.

[10] b„lkm[inx] ª j„^/b‰(½b)½kasi ª inx„jšinx
[11] b„((½b)½kasi)!b ª b„,['']j/×/b

Poistetaan mahdottomat vaihtoehdot ja lasketaan tarvittavat permutaatiot (tässä koko homman clou!).

[12] tul„((†½b),rho)½((rho-4),4)/¯1 0
[13] :For j :In ¼†½tul ª tul[j;inx[j;]]„kasi×arv[inx[j;]] ª :End

Tulostaulun rakennusta; rivin 13 sain myöhemmin hieman nopeutumaan dynaamisella funktiolla.

[14] a„tul[;¼4] ª j„^/a=¯1 ª ((,a=¯1)/,c)„0 ª b,„(+/a)-j
[15] a„tul[;4+¼4] ª j„^/a=¯1 ª ((,a=¯1)/,c)„0 ª b,„(+/a)-j
[16] a„tul[;8+¼4] ª j„^/a=¯1 ª ((,a=¯1)/,c)„0 ª b,„(+/a)-j
[17] b,„-×tul[;12+¼4]

Tiivistetään eri väriset korttisummat ja erikoiskortit yhteen. Tämänkin voi nopeuttaa d-funktiolla.

[18] z®„b ª a„b„inx„kasi„tul„ŒWA

Liitetään tulosaihioon ja putsataan muistia.

[19] :If (n>4)Ÿi=½lst
[20] a„"0 1‡z ª z„z[a;] ª b„Ÿ/0 1‡z¬¯1´z
[21] a„+/¨(+\1,1‡b)›z[;1] ª z„a,0 1‡bšz
[22] :EndIf
[23] :EndFor

Summataan samanarvoiset kädet yhteen ja jatketaan luuppia.

Käytetyt alifunktiot saattanevat olla hyödyksi myös muuallakin :)

’ z„mx Kadet n;a;b;c;i
[1] ©| Jakaumakädet, eli miten luku n saadaan enintään mx:stä (>5)
[2] ©| luvusta 1..n
[3]
[4] :Select n © perustapaukset käsin
[5] :Case 1 ª z„,›,1
[6] :Case 2 ª z„(1 1)(,2)
[7] :Case 3 ª z„(1 1 1)(1 2)(2 1)(,3)
[8] :Case 4 ª z„(1 1 1 1)(1 1 2)(1 2 1)(2 1 1)(1 3)(3 1)(2 2)(,4)
[9] :Case 5 ª z„(1 1 1 1 1)(1 1 1 2)(1 1 2 1)(1 2 1 1)(2 1 1 1)
[10] z,„(1 1 3)(1 3 1)(3 1 1)(2 2 1)(2 1 2)(1 2 2)
[11] z,„(1 4)(4 1)(2 3)(3 2)(,5)
[12] :EndSelect

Huijasin hieman laskemalla kombinaatiot etukäteen. Puhdas APL-ratkaisu on sitten käytössä jo yli viiden kortin käsille:

[14] …0˜¼n<6 ª b„a„0,¼n-1 © >5: siemenarvot (nolla mukana!)
[15]
[16] :For i :In ¼¯2+mx˜n © n-2 silmukka (1½n & n½1 suoraan)
[17] b„,b°.,a ª c„n‰+/¨b © lisää seuraavat, ylivuotoja?
[18] b„c/b ª b„žb~¨0 ª c„ŒWA © supista ehdokkaat; muisti
[19] :EndFor © † tuon pitäisi olla unioni ("kiitos", Word)
[20]
[21] c„n=+/¨b ª b„c/b © vain ne, joiden summa = n
[22] z„((mx‰n)/›n½1),b,›,n © lisää reunatapaukset

’ z„m Indeksit n;a;b;c;i;j
[1] ©| 1..n-indeksivariaatiot joukosta 1..m
[2]
[3] z„,›,[«]¼m © yhden indeksin tapaus suoraan
[4]
[5] :For i :In 1‡¼n © ulommassa indeksit 2..n
[6] a„¼m-i-1 © alkusiemeneksi väli-indeksit
[7]
[8] :For j :In ¼i-1 © sisäluupissa 1,2 3..; 2,3 4...
[9] b„¹¯1†¨a © reuna-arvo on suurin
[10] c„m-b+i-j+1 © paljonko mahtuu
[11] a„(c/a),¨¹b+¼¨c © jokaiseen eri vaihtoehdot
[12] :EndFor
[13]
[14] z,„›œa © lisää tulokseen
[15]
[16] :EndFor

Veli-Matti Jantunen
veli-matti.jantunen@stat.fi
(90) 1734 2326