Kilpatehtävä 2: Ratkaisukonsteja

[vastaus aiempaan viestiin]

> Ennenkuin kerron omista keinoistani olisi hauska kuulla Reijolta,
> mitä konsteja hän on käyttänyt vai onko pelkkä intuitio riittänyt.

Lähdin ratkaisemaan tehtävää tutustumalla sucro-koodiin sen verran,
että ymmärsin miten arvausten yhteydessä annettava todennäköisyys
lasketaan. Pienen pähkäilyn jälkeen tulin siihen tulokseen, että
tuon todennäköisyyden maksimointi joka arvauskerralla on yleisessä
tapauksessa erittäin hyvä ratkaisustrategia. Se johtikin molempien
tehtävien osalta kohtalaisiin ratkaisuihin ja antoi "ylärajan"
arvailuketjujen pituudelle.

Seuraavaksi kävi mielessä, että tuota strategiaa voisi hioa
näiden tehtävien erikoistapauksiin sopivammaksi. Hylkäsin idean
kuitenkin nopeasti, sillä kohtuullisen lyhyet ratkaisut olivat jo
olemassa ja ennalta kiinnitettyjen satunnaislukugeneraattorien
takia (mahdollinen) hyöty olisi joka tapauksessa olematon.

Seuraavaksi huomio kiinnittyi siihen, että oikeastaan tehtävänä
onkin muokata siirtymämatriisia lennossa niin, että ennalta annetusta

satunnaislukujonosta löytyy ratkaisuun sopiva pätkä. Tutkimalla
sucron sananarvontakoodia on helppo nähdä, että seuraava kirjain (tila)
määräytyy kussakin lähtötilassa "kumulatiivisesti". SATTUMA-tehtävässä
tämän perusteella (kaksi siirtymää A:sta ja T:stä) voidaan päätellä,
että ratkaisu voi löytyä vain sellaisista kohtaa satunnaislukujonoa,
jossa ehdot X[+2] on pienempi kuin X[+7] ja X[+3] on pienempi kuin
X[+4] toteutuvat. Valitettavasti ehto on aivan liian karkea ja
sopivia vaihtoehtoja on turhan runsaasti. SURVO-tehtävän osalta
moista ei edes saa muodostettua. Arvailujonojen alkupäässä
mahdollisia arvottuja sanoja on vain hyvin rajallinen määrä
(eli uuden sanan arvonta alkaa vain tietystä kohtaa satunnais-
lukujonoa). Näin voi tiputtaa pari vaihtoehtoa alusta helposti pois,
mutta valitettavasti homma räjähtää nopeasti käsiin.

Ongelman hankaluudesta tuskastuneena päätin turvautua voimaan, kun
ei järki riittänyt. Systemaattinen haku otti kuitenkin liikaa
aikaa, eikä näin ollen johtanut tuloksiin. Oli pakko tyytyä
arvailemaan ja toivoa, että sopiva kohta satunnaislukujonoa löytyisi
sillä tavalla. Ylärajahan kierrosten määrälle olin jo saanut
todennäisyydenmaksimoimisstrategialla.

Eipä ollut minulla tuuria ja haku oli tuloksetonta. Intuitio sanoi,
että kannattanee ensin oppia kävelemään ja vasta sitten alkaa
loikkimaan päättömästi. Johan alkoivat tulokset paranemaan. Ensin
siis lämmiteltiin "sopivan verran" todennäköisyyden maksimoinnilla ja
sen jälkeen ammuttiin loput kierrokset enemmän tai vähemmän
haulikolla.

Koska samaan kohtaan satunnaislukujonoa voi osua onnistuneesti
vähemmilläkin arvauksilla, päätin tiristää loppupäätä systemaattisilla
hauilla mahdollisimman paljon. Näin tippui vielä muutama kierros pois.
Lopputuloksena sain sitten mm. Sepolle raportoimani tulokset.

Lämmittelykierrosten määrän päätin vain "tuntumalla", en käyttänyt
arvosteluskaalaa kuin viiden pisteen tarkkuudella enkä pystynyt
varmistamaan ratkaisuiden minimaalisuutta. Enempää aikaa tai intoa
pähkäilemiseen ei kylläkään ollut ;).

terv.
Reijo

• Re: Kilpatehtävä 2: Ratkaisuja (Seppo Mustonen 19.1.2003 18:03)

Luettelo keskustelunaiheista

Survo-keskustelupalstan (2001-2013) viestit arkistoitiin aika ajoin sukrolla, joka automaattisesti rakensi viesteistä (yli 1600 kpl) HTML-muotoisen sivukokonaisuuden. Vuoden 2013 alusta Survo-keskustelua on jatkettu entistäkin aktiivisemmin osoitteessa forum.survo.fi. Tervetuloa mukaan!