Vaihtuuko tuo Putkaposti koskaan? :o mun mielestä tuolla etusivulla luki jotain kuukausittain vaihtuvasta Putkapostista.. Kuukaus on kyllä menny jo :P
Antti totesi aiemmassa keskustelussa, että mitään säännöllistä rytmiä ei ole. Eiköhän sieltä uusi posti tule, jahka hän ehtii sen miettimään.
Uusi tehtävä on melkein valmiina, mutta kiireiden vuoksi sen julkaisu on harmillisesti viivästynyt. Pian se kumminkin tulee!
Onko uutta arviota 3. putkapostin ilmestymisestä? Mieluummin tietysti huolella toteutettu kuin juosten... julkaistu, mutta olisi kiva päästä pian pähkäilemään.
Eiköhän se tule sitten kun se tulee.
Toki. Ja elämä on laiffii.
Julkaisu lykkääntyy varmaankin hostinvaihdon takia, ja paljon puhutuista uudistuksista Ohjelmointiputkassa. Ennustus: Ohjelmointiputkan uudistunut versio näkee päivänvalon 01/01/06!
Oma veikkaus 24/12/05 ;)
Nah, eiköhän se paras ajankohta julkaisulle ole 06/06/06..
-Grey-
Tai miksei 04/05/06? :)
Kuten näette, kolmas putkapostitehtävä on nyt näkyvissä!
Kuka pystyy ensimmäisenä ratkaisemaan kaikki testitapaukset?
Tarvitseeko tuohon putkapostiin vastata kerralla kaikkia, vai voiko ensin vastata muutamiin ensimmäisiin, ja myöhemmin lähettää koko nivaskan?
Meitsi, kokeilemalla se selvisi. Myös epätäydellisiä vastaussarjoja voi palauttaa.
Entäs sitten, kun haluaa lisätä vastauksia? Lähettää aina uuden vastauksen pelkästään, ja se lisäytyy tulokseen?
Lähettäjän paras tulos näkyy aina sivulla. Putkapostin ongelmiin hyväksytään tosiaan myös epätäydelliset vastaukset.
Ratkaisin kaikki testitapaukset. Aika kauan joutui hieromaan tuota laskentakaavaa, mutta irtosihan se sieltä. Hyvä tehtävä! Toivottavasti kukaan ei anna nopeita vinkkejä, jotta porukka saa pähkäillä rauhassa.
Mukavastihan tässä aika kuluu bruteforcetessa ;) Ei vain jaksanut ajatella mitään kaavoja tuon laskeskeluun...
Saako sen verran noobittaa, että kun long loppuu kesken, doubleko, vai teettekö itse jonkintapaisen luokan? Voi toki olla että kykyni ovat vähän alempaa tasoa kuin muiden...
32-bittisellä koneella unsigned long longiin mahtuu aika paljon (2^64-1 eli 18446744073709551615), mutta 12345678987654321 kertaa looppaaminen tyhjäänkin kestää aika tuskaisen kauan, eli kyllä tohon kantsii se kaava löytää. :)
sooda kirjoitti:
32-bittisellä koneella unsigned long longiin mahtuu aika paljon (2^64-1 eli 18446744073709551615), mutta 12345678987654321 kertaa looppaaminen tyhjäänkin kestää aika tuskaisen kauan, eli kyllä tohon kantsii se kaava löytää. :)
Äläpäs nyt, mulla on laskenut luvusta 123456789876 jo 1 / 5 eikä ole mennyt kuin pari tuntia. ;P
water_flea, ainakin joillain c++-kääntäjillä 64 bittinen muuttuja "long long int" ajaa asian.
Jep jep, kämmäsin pahasti. 12345678 ohjelmani laski alle sekunnin, 123456789 jäi jumiin niin jotenkin aattelin että vika on longissa, mutta koodissahan se tietenkin piilikin.
Oma algoritmini hoitaa laskennan 0,007 sekunnissa. Kielenä tuulennopea Python ja tehomyllynä 700 MHz Athlon.
Chiman kirjoitti:
Oma algoritmini hoitaa laskennan 0,007 sekunnissa. Kielenä tuulennopea Python ja tehomyllynä 700 MHz Athlon.
Tässä näemmekin edun mietityissä algoritmeissä, verrattuna bruteforcaukseen ;)
EDIT: Oma ohjelmani on nyt jäänyt öbaut tasaiseen 2miljoonaa lukua sekunnissa vauhtiin. Mitä nyt tuossa kellon mukaan laskeskelin...
Meitsi kirjoitti:
EDIT: Oma ohjelmani on nyt jäänyt öbaut tasaiseen 2miljoonaa lukua sekunnissa vauhtiin. Mitä nyt tuossa kellon mukaan laskeskelin...
Omani taas pyörittää siinä 5 miljoonaa sekunnissa. Eli ehkä, kun huomenna käyn koulussa, saan päivän aikana laskettua luvun 123456789876.
Kun ei lukuteoriaa eikä muutenkaan numeroiden kanssa pelleilyä osaa niin näin se menee...
Deewiant kirjoitti:
Meitsi kirjoitti:
EDIT: Oma ohjelmani on nyt jäänyt öbaut tasaiseen 2miljoonaa lukua sekunnissa vauhtiin. Mitä nyt tuossa kellon mukaan laskeskelin...
Omani taas pyörittää siinä 5 miljoonaa sekunnissa. Eli ehkä, kun huomenna käyn koulussa, saan päivän aikana laskettua luvun 123456789876.
Kun ei lukuteoriaa eikä muutenkaan numeroiden kanssa pelleilyä osaa niin näin se menee...
Mikäs prosessori / käyttis / paljonko muistia? :p
Itsellä AMD Athlon XP 2600+, WinXP Home (hyi!, gentookin löytyis kyl), 1gb dualchannel
Optimoin binäärin omalle prossulle ja kaikki muut optimoinnit mitä nyt Devc++:san valikoista löytyi, kääntäjänä siis mingw. Koodi oli kyllä varmaankin aika purkka...
EDIT: korjasin vähän...
EDIT: jotain 39% nyt ajellut luvusta 123456789876, Kun tuo lakkaa niin pitänee huomenna optimoida vähän koodia, (toivottavasti tulee oikea tulos tällä), ja sitten ajella ehkä gentoossa..
Meitsi kirjoitti:
Mikäs prosessori / käyttis / paljonko muistia? :p
AMD Athlon 64 3000+, Windows XP Pro SP2, 1024 GB DDR SDRAM. Ei dual-channel, koska prossu on sockettia 754 eikä tue sitä.
Ohjelmointikieltä et kysynyt, mutta sanotaan kuitenkin, että se on D.
Chimanin ratkaisu on loistava. Tahkosin tuota jonkin aikaa ja huomasin, että noiden loppujen laskenta (1234567898 jälkeen) taitaa viedä vuosia. (VB5)
Olen ilmeisesti keksinyt paremman bruteforcen (käy yhä kaikki luvut läpi, eli ei ole siitä kiinni), kun omani pääsee suunnilleen tuohon Deewiantin vauhtiin, koneella AMD Athlon XP 2400+. Muut tekijäthän eivät tässä varmaan juurikaan vaikuta. Ainakin minä saisin tuon helposti assemblyllä tehtyä niin, että luvut pysyisivät vain rekistereissä ja pinossa. Huono on GCC, jos ei siihen pysty.
No, heitinpä sen nyt kuitenkin mäkeen. Oikea vastaus lähetetty. Spoilerina voin kertoa, että koodi on äärimmäisen yksinkertainen, kun sitä vain jaksaa mietiskellä tarpeeksi.
Niin ja aikaa näyttää menevän näin:
real 0m0.025s user 0m0.020s sys 0m0.020s
Windowsissa, ja vielä hieman erikoisia tulostusmenetelmiä (selitä nyt long long printf:lle ^^), eli oletettavasti itse algoritmin kuluttama aika on samaa luokkaa kuin Chimanilla.
Edit: Ja onnistuinpa jo "optimoimaan" koodiani vähäsen... Ei tullut kirjoitettua vanhaa vastausta ylös, ja kun yritän näitä tarkistuttaa tuolla vastauslomakkeella, se väittää, että viimeinen kohta olisi väärin. Ei jotenkin tunnu uskottavalta, kun 16 edellistä ovat kuitenkin oikein...
Metabolix kirjoitti:
(selitä nyt long long printf:lle ^^)
%lld? :)
man 3 printf kirjoitti:
ll (ell-ell). A following integer conversion corresponds to a long
long int or unsigned long long int argument, or a following n
conversion corresponds to a pointer to a long long int argument.
Minusta tuon ratkaiseminen ei-bruteforcella on aika helppo juttu. Tai siis, minulle oma ideani oli ainakin aivan ilmeinen. Pitäisi vain viritellä vielä tuo toimimaan long longien kanssa.
Loppujenlopuksi tuo on hyvinkin helppo tehtävä, kun vaan tajuaa kuinka se menee. Koodin pituus on n. 50 riviä, josta hieman alle 20 on käytetty lukuarvojen syöttämiseen.
Parin pahimman tehosyöpön optimoinnin jälkeen koko tehtävän laskemiseen kuluu aikaa vain n. 0,5 ms, eikä luvun pituuden kasvattaminenkaan suuremmin vaikuta suoritusaikaan (esimerkiksi suuruusluokkaa 10^5000 olevalle luvulle laskeminen vie aikaa vajaan sekunnin, kun taas bruteforcettamalla saisi odottaa melkoisen pitkän ajan :).
Vähän kiva tehtävä :)) paperille piirtäminen auttoi hahmottamaan yllättävän paljon. Suosittelen muilleki.
Vai helppo! Kauan sain säätää kaavoja ennenkuin ne toimi oikein. Taitaa tuo kalkkeutimen vaivata muuallakin kuin polvissa. Aikamoisia neropatteja täällä putkassa.
Kyllä tuota tuli kieltämättä hetken aikaa väännettyä aivan väärästä suunnasta, kun ei tullut mieleen, että näin helpolla pääsisi.
Hmm, tulipas tuotakin kokeiltua minun amatöörin untuvikon taidoillani. Näyttäisi tuo algoritmi laskevan oikein ainakin nuo alkupään lukemat mitä paperilla tarkistelin.
Pitänee opetella kuinka noita isompia luku muuttujia käytetään :P joskos saisi vastauksen loppuihinkin.
Olisi ihan mukava oppimismielessä päästä näkemään noita nopeimpia algoritmejä kun seuraava putkaposti julkaistaan. :)
Eiköhän näihin kaikkiin aikanaan anneta ratkaisumenetelmiä ja vastaukset. Viilasin hieman omaa algoritmiani ja sain laskentajaksi alle 0,5 ms (Athlon 1800+, Win XP Home). Algoritmi on luotu VB5:n omilla funktioilla, API-funktioita käytetty vain ajanmittaukseen.
Tosaainkin, kaikki 17 lukua laskee toi oma athlon 2800+ parissa sekunnin sadasosassa. Olisi hauska nähdä muidenkin vastaukset, oma ei kylläkään ole yksinkertainen, tai ainakaan yksinkertaisuudessaan kaunis. :)
Itseänikin alkoi kiinnostaa minkälainen se yksinkertainen ratkaisu tähän tehtävään on. Itse kehitin kaksi eri perusratkaisutapaa, joista kumpikaan ei mielestäni ollut kovin yksinkertainen tai helppo toteuttaa. Ensimmäiseen liittyi erilaisten kombinaatioden lukumäärien summaaminen ja toiseen melko yksinkertainen idea, mutta joka toimi kaksoisrekursiolla ja josta piti käytännössä optimoida toinen haara pois ennen kuin se oli hyödyllinen isompiin lukuihin. Lopulta näistä ratkaisuista parhaita ideiota yhdistämällä sain tehtyä hyvin yksinkertaisen näköisen ja todella optimoidun ratkaisun. Itse en kuitenkaan enää näe suoraa yhteyttä tämän kaavan ja itse ongelman välillä, joten en usko, että kukaan päätyy siihen 'helposti' ja pitäisi tehtävää yksinkertaisena ratkaista.
Niin joo, C-versio ohjelmastani tarvitsee koko tehtävään noin 0.0026ms, Java-versio 0.0095ms. Ajat otettu 10000000 toiston keskiarvona, ilman tulostusfunktiota. Koneena Athlon 3000+, WinXp Pro. Ratkaisussa kutakin luvun bittiä kohden tehdään korkeintaa 11 yksinkertaita operaatiota (<<, +, &) ja 2 ehtotarkistusta.
0.0026 ms !! Tuohan on 2,6 µs eli 0,000 002 6 s. tarkoititko todella tuota ? Eikö tuohon tarvita jo superkonetta?
setä kirjoitti:
0.0026 ms !! Tuohan on 2,6 µs eli 0,000 002 6 s. tarkoititko todella tuota ? Eikö tuohon tarvita jo superkonetta?
Kyllä tarkoitin ja ei näköjään ;) Se laskentakaava pelkistyi lopulta aika paljon eikä suurimmaankan luvun laskemiseen tarvita kuin alle 600 perusoperaatiota. Jos olisi käytössä 64-bittinen prosessori niin se toimisi vielä huomattavasti nopeammin.
Voi huoh, tulee oman pään toimivuutta miettiessä väkisinkin mieleen aikanaan matematiikan opettajan käyttämä vertaus rotanaivoista. :P
Eli lyhyesti: rottakin tyhmistyy kun ei saa virikkeitä. Pitäkää siis päänne virikkeellisenä.
Vähän offaria, mutta kumminski...
Bugaa toi putkaposti sivu ilman sivun määritys-muuttujaa:
https://www.ohjelmointiputka.net/postit/
Näköjään tuo aiempi tulokseni tuli time-ohjelman heikosta tarkkuudesta. Piti testata uudestaan, kun luin nuo FooBatin tulokset, ja nähdäkseni oma ohjelmani on suunnilleen samoissa lukemissa komentojen määrän puolesta. 1000000 kierroksella tulee 9,473s taikka O3-flagilla käännettynä 8,642s. Eli mikrosekunteja kierrokselle.
Siitä olen kyllä eri mieltä, etteikö tästä löydy suoraa yhteyttä alkuperäiseen tehtävään (tietenkin kirjoitetaan shiftaukset jakolaskuina). Minä ainakin päädyin tähän kirjoittamalla lukuja peräkkäin ja tuijottamalla sitä listaa. Optimmointia tuli tehtyä juuri sen verran, että muuntelin jako- ja kertolaskut shiftauksiin ja muihin "halpoihin" operaatioihin.
Vaikkakin tästä on todennäköisesti jo mainittu aiemmin, mainostan vielä kerran USACO:a. Kyseessä on siis internetin välityksellä toimiva kansainvälinen ohjelmointikilpailu, johon osallistumalla saa hyvän kuvan "oikeista" ohjelmointikilpailuista (kuten datatähdestä ja IOI:stä).
Lisää tietoa kilpailusta löytyy osoitteesta www.usaco.org. Seuraava virallinen erä näyttää olevan 13-16.1.2006, mutta sitä ennen pääsee vielä kokeilemaan edellisen kilpailun tehtäviä osoitteessa http://ace.delos.com/contestgate , tai harjoittelemaan muuten vain osoitteessa http://ace.delos.com/usacogate .
Varsinkin mainittu USACOn harjoittelusivusto on mainio tapa parantaa ohjelmointitaitoja. Tehtävät ovat vaihtelevia ja kiinnostavia, ja lähdekoodin pystyy lähettämään palvelimelle tarkistettavaksi. Lisäksi kaikkia tehtäviä ei näe heti, vaan ne pitää ratkaista tietyssä järjestyksessä. Tämän takia USACOon jää helposti melkein koukkuun.
USACO on yksi Putkapostin ulkomaisista esikuvista. Aikojen kuluessa Putkapostiin kertyy toivottavasti samanlainen laaja tehtäväkokoelma, joka on suomenkielisenä ainutlaatuinen.
Tuommoisissa nettitarkistussysteemeissä on vain se vikana, että se rajoittaa kielen valintaa kylmästi. C, C++, Pascal ja Java käyvät tuonne. Käyttäisin mieluusti jotain aivan muuta, mutta saapahan sitä harjoitusta näinkin.
Deewiant kirjoitti:
Tuommoisissa nettitarkistussysteemeissä on vain se vikana, että se rajoittaa kielen valintaa kylmästi.
Tässä suhteessa Putkaposti on ihanteellinen, sillä koodin asemesta tulokset tarkistetaan, jolloin kielellä ei ole väliä. Antti on ajatellut tätä selvästi pitkään ja hartaasti :)
Todellisuudessa Putkapostin järjestely on pakkoratkaisu. Ohjelmien kääntämiseen ja suorittamiseen palvelimella ei ole tällä hetkellä mahdollisuutta. Mutta onhan tässä kyllä hyviäkin puolia.
Aihe on jo aika vanha, joten et voi enää vastata siihen.