Uusi putkaposti on ilmestynyt:
https://www.ohjelmointiputka.net/postit/tehtava.
Kiinnostaisi muuten tietää miten tämä tarkastetaan. Käykö testaussofta kaikki 15 miljoonaa ja rapiat riviä läpi vai onko siellä joku hieno algoritmi joka pystyy sen päättelemään muullakin tavalla?
Tarkistaja käy kaikki lottorivit läpi, koska tämä on riittävän tehokasta.
Lisähaasteena voi toki miettiä, voisiko tarkistuksen tehdä tehokkaammin.
Väittävät että 329 riviä on paras tunnettu. Itse saan valitettavasti noin tuplasti sen :( Milloinkahan joku putkalainen vetää alle 329 tuloksen :D
Tuo 329 tuntuu melko kaukaiselta tavoitteelta. Nimittäin sain "satunnaisotanta-algoritmilla" 4000 kerran tilastoksi: paras 638, keskiarvo 655 huonoin 674, keskihajonta 5.
Kiinnostava ongelma. Aihe ei ole matematiikassa tuntematon; hyvin nopealla etsinnällä löytyi lyhykäinen, suhteellisen helppolukuinen artikkeli nimeltä On the lottery problem (kirjoittaneet Z. Füredi, G. J. Székely ja Z. Zubor), jonka voi ladata mm. sivulta http://www.math.uiuc.edu/~z-furedi/publ.html.
L2-K2 kirjoitti:
Tuo 329 tuntuu melko kaukaiselta tavoitteelta. Nimittäin sain "satunnaisotanta-algoritmilla" 4000 kerran tilastoksi: paras 638, keskiarvo 655 huonoin 674, keskihajonta 5.
No jos nyt katsoo paljonko sisuaskikin on parantanut tulostaan, niin en pitäisi ainakaan 329:aa ihan mahdottomana. Satunnaisesti hakeminen ei ehkä ole paras lähtökohta.
Sen voin sanoa että alle 84 ei tule kukaan pääsemään. Eli lotossahan tulee noin 1/84 todennäköisyydellä vähintään 4 oikein tulos.
Varmaan hyvän tuloksen saaminen tuosta edellyttäisi tosiaan jotain matematiikkoja tai miettimistä. Jos lottorivejä yrittää ajatella vain n. 15M solmun kokoisena verkkona, törmää ikävän nopeasti suorituskyvyn puolesta rajoitteisiin, mitä on mahdollista tehdä järkevässä ajassa.
Nykyinen 553-tuloksen tuottava koodinikin toimii varsin yksinkertaisesti, mutta sen ajamisessa kestää silti tehokkaalla palvelimellakin n. 15 minuuttia.
Sisuaski kirjoitti:
Varmaan hyvän tuloksen saaminen tuosta edellyttäisi tosiaan jotain matematiikkoja tai miettimistä.
Riippuu tietysti siitä, mikä lasketaan hyväksi tulokseksi. Veikkaisin, että ongelmaa on pohtinut tosissaan ainakin muutama matikan opiskelija tai matemaatikko, joten ennätyksen 329 parantaminen voi olla haastavaa.
tässä menee ikä, henki ja terveys.
rivillä 646 ollaan nyt, ja uusia tupsahtelee parin minuutin välein kun randomina arpoo rivejä tarkastusta varten. aikaa mennyt jo joku 45min.
nytkin arvottu rivi nro 11 766 222 aiheutti uuden rivin kun ei neljää löytynyt. aarghh! (aina kun uusi löytyy niin alkaa laskuri alusta, ja 15 miljoonaa arvottua riviä tarttis onnistua, ja joo olis tarvinnu pistää arvotut rivit muistiin mutten siinä vaiheessa ajatellut. ja kirjoittaa rivitkin tiedostoon vasta lopussa ja alusta en perhana aloita)
olis tarvinnut vähän optimoidumpi tehdä ;)
---Edit----
kone arpoo noin 10000 riviä sekunnissa, ja nyt taas löytyi uusi.
uusi rivi nro 648, löytyi arvotulla rivillä nro 12 307 463.
ei hermot kestä.
groovyb kirjoitti:
olis tarvinnut vähän optimoidumpi tehdä ;)
Muista tweakaus ei kannata juuri koskaan, vaan paremmat algoritmit.
Vinkiksi oma viritelmäni arpoi ilman optimointeja yhden "käden" eli tarvittavat rivit alle 20 sekunnissa. Tämä mahdollisti tuhansien käsien arpomisen, ja siten aavistuksen paremman tuloksen kuin yhdellä arpomiskerralla.
Tämä tekee noin 40 riviä/sekunti koko suorituksen ajan lisää käteen, kun sinulla on nyt hidastunut arvoon <0,01 riviä /sekunti, eli noin 40000-kertainen nopeusero. Toteutukseni olisi siis selvästi nopeampi, vaikka se olisi toteutettu php:llä.
Kuitenkin tuo tapa arpoa kaikki rivit satunnaisessa järjestyksessä ja lisätä ne tarvittaessa käteen ei ole kovin hyvä tapa etsiä minimikäsiä, kuten tuloslistasta näkee. Vaan jotain aivan muuta pitäisi keksiä.
Tämä olikin vain pieni testaus, jos tota haastetta lähtisi purkamaan kunnolla niin menis yöunet. Ekat 500 riviä tuli 20 sekunnissa, loppu kolmevarttia meni muihin. Jo se että ois pitänyt kirjaa jo arvotuista sarjoista ois nopeuttanut eikä arponut n kertaa samoja lukuja samoilla neljän sarjoilla...
Nythän itse algoritmi pääsi vauhtiin vasta kun oli tarpeeksi rivejä joihin sarjoja verrata, oikeaan tapaan varmasti kuuluu myös laskea ekasta rivistä lähtien... mun tapauksessa oli yksi "siemenrivi" 1234567, ja sitten randomilla vaan 7 sarjoja ja aloin tarkastamaan löytyykö neljää samaa,jos ei,rivi lisättiin taulukkoon ja niin edespäin.
Veikkaus Oy kirjoitti:
Lottovoiton todennäköisyys yhdellä rivillä on 1,2 prosenttia.
Tarkempi luku on 1,1286699 prosenttia.
Tämähän tarkoittaa ymmärtääkseni sitä että varmaan voittoon ei tarvita kuin 89 riviä? Aika kaukana on vielä putkapostin numerot =)
edit.
Wikipediaa kun lueskelin niin Uolevin kannattaisi ottaa lisävoittoluokat mukaan peliin.. Ei kuitenkaan maksa kuin 0,20 euroa lisää ja voittoon ei tarvita kuin 40 riviä.
Wikipedia kirjoitti:
Todennäköisyydet voittaa lotossa sekä kuinka monta ruudukkoa joudutaan keskimäärin täyttämään kyseisen voittopotin saamiseksi:
4 oikein 173 600/15 380 937 n. 1/89 = 1,1286699 %
3+1 oikein 383 670/15 380 937 n. 1/40 = 2,4944514 %
edit2.
Kuitenkin rivi hinta tulee halvemmaksi neljä oikein voitolla, 0,67 euroa riviltä, kun taas 3+1 oikein voitolla rivi hinta on 0,97 euroa.
t0ll0 kirjoitti:
Veikkaus Oy kirjoitti:
Lottovoiton todennäköisyys yhdellä rivillä on 1,2 prosenttia.
Tarkempi luku on 1,1286699 prosenttia.
Tämähän tarkoittaa ymmärtääkseni sitä että varmaan voittoon ei tarvita kuin 89 riviä? Aika kaukana on vielä putkapostin numerot =)
Olet väärässä.
Sitä paitsi, mistäs sä tollaisen luvun revit. Tai no, tiedänhän minä, todennäköisyys saada 4 oikein. Mutta tokihan myös 5, 6, 6+1 ja 7 -oikein ovat voittoja. Tarkka luku on 184262/15 380 937 eli n. 1,19799% eli noin joka 83,47. rivi voittaa.
Kuten jo aikaisemmin sanoin, niin alle 84 alle ei voida päästä mitenkään, mutta todennäköisesti varmaan voittoon tarvitaan huomattavasti enemmän rivejä.
Grez kirjoitti:
t0ll0 kirjoitti:
Veikkaus Oy kirjoitti:
Lottovoiton todennäköisyys yhdellä rivillä on 1,2 prosenttia.
Tarkempi luku on 1,1286699 prosenttia.
Tämähän tarkoittaa ymmärtääkseni sitä että varmaan voittoon ei tarvita kuin 89 riviä? Aika kaukana on vielä putkapostin numerot =)Olet väärässä.
Sitä paitsi, mistäs sä tollaisen luvun revit. Tai no, tiedänhän minä, todennäköisyys saada 4 oikein. Mutta tokihan myös 5, 6, 6+1 ja 7 -oikein ovat voittoja. Tarkka luku on 184262/15 380 937 eli n. 1,19799% eli noin joka 83,47. rivi voittaa.
Kuten jo aikaisemmin sanoin, niin alle 84 alle ei voida päästä mitenkään, mutta todennäköisesti varmaan voittoon tarvitaan huomattavasti enemmän rivejä.
Olen Grez:n kanssa samaa mieltä siitä, että t0ll0n päättely oikoo vähän mutkia suoriksi. Kuten Grez totesi, niin yksittäinen rivi "osuu" täsmälleen 184262 riviin (kun osuma määritellään siten, että riveillä pitää olla vähintään neljä samaa numeroa). Kuitenkaan ei käsittääkseni ole mahdollista valita 84:n rivin osajoukkoa noiden 15380937 rivin joukosta siten, että jokainen rivi osuisi aina 184262 eri riviin. En nyt osaa tähän hätään esittää väitteeni pohjaksi mitään formaalia todistusta (joku muu ehkä osaa?), vaan käsitykseni perustuu havaintoihin omasta ratkaisuyritelmästäni.
Ratkoin itse tuota ongelmaa ahneella algoritmilla, joka valitsi ratkaisujoukkoon täydennykseksi jokaisella askeleella rivin, joka osui mahdollisimman moneen sellaiseen riviin, johon mikään aikaisempi ratkaisujoukon rivi ei vielä ollut osunut. Käytännössä ratkaisujoukkoon valittava rivi osuu 184262 uuteen riviin vain muutamien ensimmäisten askelten aikana. Tämän jälkeen uusien osumien määrä lähtee putoamaan. Jos siis t0ll0n ehdottama ratkaisu olisi mahdollinen, niin ratkaisualgoritmini olisi löytänyt sen (tietysti sillä edellytyksellä, etten koodaillut pahasti bugaavaa systeemiä..).
Homman luonnetta kuvaa myös se, että pystyn muodostamaan 250 rivin joukon, jolla voittaa todennäköisyydellä 0,99. Käytännössä täydellisen varmuuden, eli viimeisen prosentin, saavuttaminen generoi ratkaisuun loput rivit. Tuo rivien jakautuminen ensimmäisen 99%:n ja viimeisen 1%:n välille aiheuttaa ainakin itselleni sellaisen fiiliksen, että joillain vähemmän ahneilla valinnoilla saattaa olla mahdollista päästä parempaan tulokseen. Pitäisi ehkä hetki koittaa miettiä tätä ongelmaa ihan kynällä ja paperilla.
Vaikka nyt kerroinkin oman ratkaisuni periaatteen, niin en toivoakseni silti pilannut kenenkään iloa tehtävän ratkaisemisessa. Tuon ahneen algoritmin käytännön toteuttaminen nimittäin vaatii silti kohtuullista askartelua, jos haluaa sitä käyttäen saada ratkaisun aikaan järjellisessä ajassa.. =)
Epsilon kirjoitti:
Vaikka nyt kerroinkin oman ratkaisuni periaatteen, niin en toivoakseni silti pilannut kenenkään iloa tehtävän ratkaisemisessa. Tuon ahneen algoritmin käytännön toteuttaminen nimittäin vaatii silti kohtuullista askartelua, jos haluaa sitä käyttäen saada ratkaisun aikaan järjellisessä ajassa.. =)
Mielestäni putkapostissa pitäisikin ihmisten enemmän puhua ratkaisutavoistaan yms. Muiden ratkaisutavoista kuitenkin pystyy oppimaan paljon enemmän, kuin että miettisi asiaa vain yksin. Toki suurempi spoilaus heti tehtävän saatua olisi ikävää.
Riippuu hirveästi tehtävästä. Mielestäni jos kukaan ei ole saanut parasta mahdollista tulosta, niin ratkaisutavoista keskustelussa ei ole mitään ongelmaa. Jos taas lätkäisee suurinpiirtein pseudokoodin jolla saa helposti parhaan mahdollisen tuloksen, niin se spoilaa mielestäni enemmän.
Epsilon kirjoitti:
En nyt osaa tähän hätään esittää väitteeni pohjaksi mitään formaalia todistusta (joku muu ehkä osaa?), vaan käsitykseni perustuu havaintoihin omasta ratkaisuyritelmästäni.
No tämäkään nyt ei ole mikään formaali todistus, mutta tämä perustuu kuitenkin siihen, että useamman arvontakerran tulos ei ole sama kuin odotusarvo. Eli siis, vaikka 84 satunnaisesti valitulla rivillä voiton odotusarvo onkin luokkaa 1, niin silti seuraavalla arvonnalla voi tulla 0 tai vaikka 3 voittoa.
Tätä voisi havainnollistaa vaikka nopan heittämisellä. Jos valitaan yksi numero ja heitetään 6 kertaa noppaa, niin odotusarvo on saada 1 osuma. Kuitenkaan tämä strategia ei ole varma tapa saada 1 osumaa. Ainoa varma tapa on ottaa kaikki 6 arvoa, jolloin toisaalta varmojen voittojen määrä pomppaa samantien 0:sta 6:een.
Mitenkäs tuo vastauksen lisäys toimii?
Eli tarkistetaanko rivit heti lisätessä vai vasta kun kilpailu päättyy?
t0ll0: katsopa nuo kolme ensimmäistä viestiä.
Niin kyllä siellä tarkistajasta puhutaan muttei siitä käykö se heti ne rivit läpi vai käynnistetäänkö tarkistaja sitten kun aika on kypsä.
Viestisi perusteella nyt tuntuu kuitenkin siltä että ne käydään heti läpi, kiitän.
Joo, ne käydään heti läpi (tosin menee muutamia kymmeniä sekunteja).
Olisikin vähän hassua jos ne tarkistettaisiin "kilpailun päättyessä", kun putkapostit ei yleensäkään ole aikarajoitteisia kilpailuja. Tai sitten aika pitkällä ajalla, kun ensimmäinenkin putkaposti on yhä avoinna osallistujille ja se on sentään tullut jo vuonna 2005.
Keksin tuohon aika mukavan idean, joka rajoitti hakuavaruutta merkittävästi, jopa tasolle josta voisi löytää lähelle 400 rivin tuloksia kunnollisella haulla. Nyt käytössa on vain yksinkertainen ahne haku, joka harvoin pääsee ihan parhaimpaan tulokseen. Pitäisi löytää jostain aikaa koodata parempi.
Minun päättelyjen mukaan tuloksen alaraja on vähintään 250 riviä, mutta todennäköisesti aika paljon suurempi.
Tehtävä on osoittautunut varsin vaikeaksi ja tarjoaa varmaan haastetta vielä pitkäksi aikaa. Tässä tehtävässä omista ratkaisutavoista (onnistuneista ja epäonnistuneista) voi minusta kertoa avoimesti.
FooBat: Ratkaisuideastasi olisi hauska kuulla lisää.
Onko kukaan koettanut muodostaa ratkaisun runkoa käsin?
Periaatteessa ongelmaa voisi lähestyä myös tutkimalla ensin jotain pienempää (vähemmän laskentatehoa vaativaa) tapausta.
Antti Laaksonen kirjoitti:
Tässä tehtävässä omista ratkaisutavoista (onnistuneista ja epäonnistuneista) voi minusta kertoa avoimesti.
Aloitin yksinkertaisella algoritmilla: Käyn läpi kaikki mahdolliset lottorivit. Testaan jokaisen kohdalla löytyykö jo käyttämistäni riveistä vähintään 4 yhteistä numeroa sen kanssa. Jos ei, lisään rivin käyttämiini.
Yksinkertainen bruteforce-parannus olisi arpoa kaikkien lottorivien järjestys aina uusiksi, jolloin omatkin rivit tulisi valittua satunnaisesti.
Pistetään tällä kertaa vielä rot13 salauksella kun toi spoilaa aika paljon.
Zha vqrn ba wnxnn ahzrebwbhxxb chbyvxfv wn engxnvfgn xnxfv cnywba cvrarzcää bfnbatryznn. Xbfxn nvan iäuvagää 4 neibvghfgn 7 ahzrebfgn bfhh wbzcnna xhzcnna inyvghvfgn chbyvfxbvfgn, ibvqnna unxrn engxnvfhn fvgra, rggä inyvgnna evivg wbvfgn yölgll xnvxxv 4 ahzreba xbzovanngvbg xhzznfgnxva chbyvfxbfgn, zhggn ibvqnna wäggää uhbzvbvggn xnvxxv xbzovanngvbg, wbvffn ba ahzrebvgn frxnvfva aävfgä ahzrebwbhxbvfgn. Ahzrebvqra 1-20 bfnwbhxbffn ba 4845 rev 4 ahzreba xbzovanngvbgn wn rev ybggbevirwä wbvqra wbhxbfgn rgfvgääa ba inva 77520. Ahzrebvqra 21-39 wbhxbffn ba inva 3876 xbzovanngvbgn wn 50388 evivä.
Minusta tuntuu, että yhdistämällä Epsilonin ja FooBatin ideoita voisi saada aikaan todella hyvän ratkaisun.
Aihe on jo aika vanha, joten et voi enää vastata siihen.