Keskustelu: Ohjelmointiputka: Putkaposti alkaa

"Mikä on Putkaposti?"

Tätä on moni kummastellut viikon aikana, ja mainoksen ilmaantuminen sai huhumyllyn liikkeelle. Nyt on aika paljastaa, mistä tässä on kysymys. Viikon kysymyksen tilalla on tästä lähtien ohjelmointiongelma, jonka vastaus lähetetään Ohjelmointiputkan palvelimelle. Ongelma vaihtuu näillä näkymin kuukausittain.

Ongelmat ovat sellaisia, että ne voi ratkaista monella tavalla. Yksinkertainen ohjelma riittää osittaiseen ratkaisuun, mutta täydellisen vastauksen saamiseksi täytyy nähdä enemmän vaivaa. Ongelman yhteyteen tulee myös näkyviin niiden putkalaisten nimet ja tulokset, jotka ovat ongelman ratkaisseet. Aikanaan ongelmaan tulee myös malliratkaisu.

Ensimmäinen ongelma on melko helppo, ja sen nimi on "Palindromiseurat". Pankaa siis tulemaan putkapostia !
https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=palseu

Hyvä idea! Eipä tainnut kukaan arvata lähellekkään oikein tuossa ketjussa! Täytyy yrittää tuota jossain välissä.

Kuulostaa hauskalta, mutta ensimmäinen tehtävä on minulle kyllä yli hilseen. :) Nimi on myös vähän outo.

Samat sanat.

Todella hyvä idea! Äkkiä luettuna myös jopa tajusin tuon ensimmäisen tehtävän. Täytyy koittaa, jos sitä sais jotain ratkaisua aikaseksi.

Hieno idea! Aloin heti paneutua ensimmäineen kysymykseen.

Idea on totisesti loistava, nimeä ois voinu vähän hioa.
Toivottavasti löytyy aikaa yrittää tuota tehtävää, vaikuttaa varsin mielenkiintoselta.

Aivan mahtavaa! Minäkin aloin heti miettimään ensimmäisä kysymystä.

Heti kritiikkiä: Ei systeemi lisännyt ensimmäisellä yrittämällä tuota tulostani, vaikka 99,99% varmuudella oli oikeassa muodossa. Tuli joku mysql-errori. Systeemi kuitenkin väitti, että vastauksen lisäys onnistui, vaikka ei onnistunut. Luulin vastanneeni väärin, kun en päässyt listoille. Eli eli... Virheenkäsittelyyn kannattaisi ehkä panostaa hieman enemmän. Ihan näin käyttäjän kannalta olisi myös kiva tietää mitä tein väärin.

ja mään en tajua tosta kysymyksetstä yhtikäs mitään :D

Eipä se kovin vaikea pitäisi olla kun kahdessa tunnissa tullut jo seitsemän vastausta (kunhan vaan ymmärtää mitä ovat erikantaiset lukujärjestelmät).

Mitenkäs tässä muuten valitaan "voittaja"? Onko voittaja se, joka saa parhaan tuloksen ja palauttaa vastauksen ensimmäisenä? Eli onko tämä myös nopeuskilpailu? Vaikka palkintoja tuskin on, on kiva tietää kuka voitti :)

Tuskin tässä ajalla mitään merkitystä on, kun vastauksia alkaa tulla jo noin monta näin lyhyessä ajassa. Kaikkihan eivät edes tämän päivän aikana ole lukeneet koko foorumia, vaikka saattaisivat muuten menestyä yhtä hyvin.

Mukavan oloinen idea, varmasti monille antaa motivaatiota koodata jos itse ei keksi mitään mieleistä projektia. Onhan tuo vähän kilpailuhenkinen, mutta mikä sen paremmin motivoisikaan (ai perk. tuokin ratkaisi tämän, pakkohan se on minunkin saada! :).

Ihan mielenkiintoisen oloinen tehtävä sinänsä, voishan tuota yrittää.

No eipä ollut paha toi ensimmäinen tehtävä. Mutta mistä ihmeestä repäisit ton putkaposti-nimen? :)

Tälläinen pieni kysymys tosta kysymyksestä. Mitä noi pienet ala numerot tarkoittavat? Muuten sitten olenkin kysymyksen tajunnut.

Ja voiko tohon vastata useita kertoja?

Alanumerot kertovat, mistä lukujärjestelmästä on kyse.

Eihän se vaikea ollut mutta ihan hauska sinänsä. Sopiva taso on varmasti hyvin vaikea määritää mutta eiköhän tämä edusta mielestäni ihan sopivaa tasoa OP:hen. Lukujärjestelmät opetetaan jo yläasteella, joten sikäli edellytykset tehtävän suoritukseen ovat kiinni varmaankin lähinnä ohjelmointitaidosta (ja tietenkin ajasta ja viitseliäisyydestä).

ajv kirjoitti:

Ei systeemi lisännyt ensimmäisellä yrittämällä tuota tulostani, vaikka 99,99% varmuudella oli oikeassa muodossa.

Luulenpa, että kyseessä oli väliaikainen virhe palvelimella. Täytyy parantaa tarkistusta tuollaistenkin varalta.

Heikki kirjoitti:

Mitenkäs tässä muuten valitaan "voittaja"?

Oikeastaan kaikki, jotka onnistuvat saamaan täydellisen ratkaisun, ovat "voittajia". Toistaiseksi ohjelmien nopeusvertailu ei onnistu, koska palvelimelle lähetetään pelkkä ratkaisu. Mutta omista ohjelmista voi kertoa sähköpostilla, niin kuin tehtäväsivulla lukeekin. Erilaisia ratkaisuja sitten esitellään myöhemmin tehtäväsivulla.

sooda kirjoitti:

Mutta mistä ihmeestä repäisit ton putkaposti-nimen? :)

Nimi tuli vain jostain syystä mieleeni. Pian se kuitenkin varmaan alkaa kuulostaa tutulta ja hyvältä. :)

petrinm kirjoitti:

Ja voiko tohon vastata useita kertoja?

Tehtävään saa vastata niin monta kertaa kuin mieli tekee. Paras hyväksytty ratkaisu jää voimaan.

JTS kirjoitti:

Sopiva taso on varmasti hyvin vaikea määritää mutta eiköhän tämä edusta mielestäni ihan sopivaa tasoa OP:hen.

Tehtävien taso tulee olemaan vaihteleva. Tämä palindromitehtävä on helpoimmasta päästä. Vaikeammissa tehtävissä eritasoisissa vastauksissa rupeaa olemaan eroja.

Noniin, tällaista systeemiä olenkin toivonut jonkin aikaa.

Vastausten näkyminen etukäteen on ehkä huono idea, mahdollistaahan se huijauksen, mutta jos meininki on olevinaan rentoa se ei vissiin haittaa. EDIT: käkkäräkää. Enpä lukenut tehtävänantoa tarkkaan... vastaukset pitää antaa, ja sivu ilmoittaa vain niiden määrän.

Nimi voisin tosiaan olla parempi.

postit.php puuttuu, laittaisit edes jonkun template-sivun jos vaatii liikaa hommaa tehdä se kunnolla :-)

EDIT 2: keskustelu tästä kuulunee kilpailukeskusteluun (josta voisi vihdoin tehdä kunnon keskustelualueen)? Jos ei, pitää lisätä yksi keskustelualue :-)

Loistavaa ajanvietettä, itsekin sain uhrattua heti puoli tuntia PHP-skriptin vääntämiseen, tosin jokin (tai siis tiedänkin mikä) mättää kun tuli vain 10 tulosta...

Voin kyllä rehellisesti sanoa että tämä on paras idea pitkästä aikaa, ellei jopa koko putkan historian aikana :) Tämä jos mikä innostaa koodaamiseen, kunhan vain tehtävä on sopiva, ja senhän voisi sanoa olevan koko putkan ideana. Tosin tuo kuukausittainen päivittely kuulostaa hieman turhan hitaalta kun katsoo miten nopeasti noita vastauksia sateli, mutta tiedä sitten keksiikö lyhyemmässä ajassa yhtä nasevia pähkinöitä. Tietenkin tämän ensimmäisen Putkapostin nopeaa ratkaisijoiden määrän kasvua on vauhdittanut tämä hypetys, tilanne varmaan normalisoituu ajan myötä.

Tehtävien julkaisuväli voisi tietenkin olla myös muuttuva. Helpon tehtävän ratkaisuun ei tarvitse niin paljon aikaa kuin vaikean tehtävän ratkaisuun. Kuitenkin hyvien tehtävien laatiminen on työlästä: laatijan pitää itse ensin tutustua ongelmaan perusteellisesti, ja silloin käytössä ei ole malliratkaisua eikä tarkistajaa. Tehtäviä saa muuten ehdottaa minulle, jos hyviä ideoita tulee mieleen.

Niin... Tuon tehtävän sain tehdyksi suunnilleen vartissa, ja kuukausi olisi aikaa...

Minusta ei välttämättä ole hyvä, että tuossa lukee paras annettu vastaus. Tavallaan se tietenkin laittaa ajattelemaan uudestaan, jos on vastannut eri tavalla, mutta toisaalta hajontaa voisi vaikeammissa tehtävissä aiheuttaa se, että parasta vastausta ei ilmoitettaisi. Silloin pitäisi itse huomata virheensä.

Antti Laaksonen kirjoitti:

Tehtäviä saa muuten ehdottaa minulle, jos hyviä ideoita tulee mieleen.

Kyselin jokin aika sitten täällä pikkupuuhasteltavaa, ja löysin tällaisen sivuston: http://acm.uva.es/p/

Jos ideat loppuvat, tuolta voi ottaa vaikkapa satunnaisesti jonkin ongelman. Tietysti joudut itse ratkaisemaan sen ensin, joka vie oman aikansa... ideoita tuolta ainakin löytynee, jos vain jaksaa selailla.

Tämä viesti ei ole minun, vaan tkarkkaisen, mutta hänellä ei Putka jostain syystä toimi, joten hän värväsi minut välittämään viestin tänne:

JTS kirjoitti:

Lukujärjestelmät opetetaan jo yläasteella

Ei muuten opetettu ainakaan meille. Nyt siis jo abivuosi menossa enkä muista että asiasta olisi koskaan koulussa puhuttu.

Tuon sähköpostitse tapahtuvan oman ohjelman kommentoinnin voisi periaatteessa hoitaa myös koodivinkkimäisenä kommentointina, mutta vasta tehtäväajan loppumisen jälkeen spoilereiden välttämiseksi.

Tehtävistä toivoisin tulevaisuudessa haastavampia. Lisäksi olisi kiva jos tehtäviin ripoteltaisiin oikoteitä tai jekkuja. Jekuilla tarkoitan lähinnä "Etpäs muuten hoksannut tuota!" -juttuja. Silloin tehtävässä olisi muutakin kuin pelkkä kaikkien vaihtoehtojen sokea bruteforcettaminen.

Mutta hyvän tehtävän tekeminen todella on vaikeaa, ja nostan hattua aina kun joku viitsii kehitellä mielenkiintoisen tehtävän, vaikka sitten helponkin.

Minulle opetettiin lukujärjestelmät ensimmäisen kerran vasta lukion pitkän matikan 8. kurssissa. Tai no, opetettiin ja opetettiin, olinhan toki opetellut ne itse jo ajat sitten.

Jaa, meillä yläasteella 8-luokalla ATK-tunneilla ei päässyt istumaan ennen kuin osasi vastata oikein opettajan esittämään kysymykseen (tai toisinsanoen pääsi paljon nopeammin istumaan jos osasi vastata kysymyksiin). Lähes aina kysymykset olivat päässälaskettavia lukujärjestelmämuunnoksia... Mutta muistin väärin, kaiketi niitä ei virallisesti opetettu. Mutta meille ainakin tuola ATK-tunneilla opetettiin sekä matematiikan tunneillakin (myös kysyttiin päässälaskuja johon vastaamalla pääsi lähtemään tunnin lopussa, sillointällöin juurikin järjestelmämuunnoksia).

Nimi ei jotenkin istu, mutta idea on hyvä. Jossain voisi tietysti lukea aikaraja, johon mennessä ratkaisut tulee lähettää :). Ja FAQiin infoa Putkapostista.

Tämähän on loistava idea. Ei voi kuin kiittää ja nostaa hattua Laaksosen Antille kun saa putkan fiksun porukan näin aivojumpalle. Aivoahan on treenattava siinä kuin lihastakin. Maikäläiselle rahjukkeellekkin tämä on oivaa aivojumppaa dementiaa vastaan. Tosin en saanut omaa ratkaisuani perille. Ehdottaisin kuitenkin, ettei ratkaisuista hiiskuta mitään, ei edes tuota lukumäärää, kunnes ratkaisuaika on ohi. Vastausten lukumäärän voi tietenkin kertoa. Putkipostin tilalle ehdottaisin ongelmaputkaa. Joskushan on muinaisessa Insinööriuutisissa ollut ongelmakulma, jossa joka viikko jokin yleensä matemaattinen ongelma.

Palindromitehtävään kannattaa miettiä myös vaihtoehtoisia ratkaisuja. Suoraviivainen raa'an voiman käyttö käy kyllä päinsä, mutta ongelman voi ratkaista hienostuneemminkin. Kaikki ovat näköjään päätyneet samaan tulokseen palindromiseurojen määrästä annetulla lukualueella, mutta kuinkahan kaukana lukusuoralla odottelee seuraava vähintään nelijäseninen palindromiseura?

Minä luulen, että vastausten - tai paremminkin vastausten täydellisyyden - julkaiseminen kannattaa. Tieto paremmasta vastauksesta jos jokin houkuttelee oman ohjelman hiomiseen.

Aikarajaa pitää tosiaan miettiä: malliratkaisujen julkaisun jälkeen ei enää kannata hyväksyä vastauslähetyksiä.

Antti Laaksonen kirjoitti:

Kaikki ovat näköjään päätyneet samaan tulokseen palindromiseurojen määrästä annetulla lukualueella, mutta kuinkahan kaukana lukusuoralla odottelee seuraava vähintään nelijäseninen palindromiseura?

Ottaen huomioon lähetettyjen vastausten suuren lukumäärän ja yksitoikkoisuuden olisi ehkä hyvä idea laajentaa lukuväliä 1-1000000 vaikkapa väliksi 1-100000000000000000. Toimenpide olisi varsin vaivaton ja lisäisi huomattavasti nykyisen tehtävän kiinnostavuutta seuraavaa odoteltaessa.

Tosiaan isomman alueen kanssa bruteforce ei enään toimikkaan niin hyvin. Itse pistin huonosti optimoidun ohjelmani tuossa 1,5h sitten tutkimaan väliä 1-900 000 000, vielä jauhaa (ei näytä välituloksia joten en tiedä paljonko uusia on löytynyt), ja ohjelma optimoidusti käännettynä ratkaisi tuon 1-1000000 välin vajaassa 30 sekunnissa. Tuo sinun ehdottamasi jättiluku (1e17) vaatisi jo kunnollista optimointia, sillä oma ohjelmani tutkisi sitä varmaan elinikäni.

Prossuna Athlon XP 1800+, kielenä C++ ja kääntäjä gcc 3.4.4

Minun optimoimaton bruteforce-ohjelmani ratkaisi tuon tehtävävälin siinä parissa sekuntissa (1-5, en muista). Hyvin pienellä optimoinnilla ihan omassa koodissa nopeus tuplaantuisi varmasti. Athlon XP 2400+, C++, MinGW (uusin tällä hetkellä).

Luulen, että tuo suurikin väli olisi mahdollista melko nopeasti laskea, kun tekisi ohjelman oikealla periaatteella. (Onkin jo pari ideaa, mutta toteutus on jo vähän hankalampi kuin tässä ensimmäisessäni...)

Oma bruteforce java-ohjelmani laski 1000000000 ensimmäistä lukua noin tunnissa eikä noiden 11 luvun lisäksi löytynyt muita. Pitänee vähän muuttaa algoritmia, jos meinaa etsiä kovin paljon pidemmälle.

Edit: muokkasin vähän koodia ja nyt samaan työhön meni noin 5 minuuttia. Vieläkin vähän hidas, jos meinaa laskea PALJON pidemmälle.

Taas ilmeisesti tuo vastaus juttu bugittaa, valittaa vaan
Virhe lähetyksessä:
Virhe rivillä: 1

Kyl teil on nopeita ohjelmia, oma laski tätä lähes viitisen minuuttia :) Tosin PHP ei kai kovin hyvin sovellu tämmöisiin hommiin.

Odotan todella nähdäkseni noita koodejanne (lähettäkää niitä Antille niin se julkaisee varmaan niistä parhaat)... Itsellä ei kiinnostus (eikä taidot) riitä alkaa vääntämään tuota muulla kuin itse käyttämälläni PHP:llä, jolla tuon itse tehtävän välin bruteforcaus kesti semmoiset 77sek (1GHz Thunderbird) vaikka sitä mukamas pikkuisen optimoinkin. Tosin paljon siinä vielä olisi puristettavaakin kun nyt ajattelee...

VilleP kirjoitti:

olisi ehkä hyvä idea laajentaa lukuväliä 1-1000000 vaikkapa väliksi 1-100000000000000000. Toimenpide olisi varsin vaivaton ja lisäisi huomattavasti nykyisen tehtävän kiinnostavuutta seuraavaa odoteltaessa.

Pienen laskennan jälkeen selvisi, että toimenpide ei sittenkään lisäisi tehtävän kiinnostavuutta, nuo 4-palindromit kun tuntuvat olevan liian harvassa.

Opiskelija kirjoitti:

Taas ilmeisesti tuo vastaus juttu bugittaa, valittaa vaan - -

Tarkistapa vielä vastauksesi muotoilu.

VilleP kirjoitti:

- -, nuo 4-palindromit kun tuntuvat olevan liian harvassa.

Löysitkö yhtään lisää?

Opiskelija kirjoitti:

Kyl teil on nopeita ohjelmia, oma laski tätä lähes viitisen minuuttia :) Tosin PHP ei kai kovin hyvin sovellu tämmöisiin hommiin.

Omani tekaisin php:llä. Hiukan alle minuutti taisi mennä. Kone, joka laskun suoritti taitaa olla 1Ghz.

Antti Laaksonen kirjoitti:

Tarkistapa vielä vastauksesi muotoilu.

Siitä se oli kiinni, nyt onnistui.

tkarkkainen kirjoitti:

Omani tekaisin php:llä. Hiukan alle minuutti taisi mennä. Kone, joka laskun suoritti taitaa olla 1Ghz.

Juu, täytyy kai yrittää optimoida koodia pikkasen, kunhan tietäisi mistä alottaisi :) Kone hiukkasen nopeempa, joten siitä ei kiikasta. Taitaa tuo iffittely hidastaa.

Antti Laaksonen kirjoitti:

Löysitkö yhtään lisää?

Itse bruteforcasin eilispäivän aikana sellaiset 4-5 tuntia CPU-aikaa eikä löytynyt enempiä. Vertailun vuoksi tuon miljoonan läpikäymiseen menee noin reilut viisitoista sekuntia... Pistin nyt uusiksi päälle siten, että se jopa ilmoittaa aina miljoonan välein, missä vaiheessa lasku on. Katsotaan, tuleeko yhtään vastausta enää vastaan.

Vertailun vuoksi oman php-bruteforceni läpi ajaminen miljoonalla kestää 76 s, eli suurinpiirtein yhtä kauan, kuin meni sen alkkiksen keksimiseen ja kirjoittamiseenkin :P

Edit: Oho, shellistä jopa 66 s :o

Antti Laaksonen kirjoitti:

Löysitkö yhtään lisää?

Ainakaan väliltä 1000000 - 1.6 * 10^18 ei löytynyt yhtään lisää.

Pienellä todennäköisyyslaskennalla voi päätellä, ettei 4-palindromeja luultavasti enää löydykään enempää kuin nuo 11, yhdellä karkealla arviolla P(n on 4-palindromi) = noin suuruusluokkaa 1/n^2 suurilla n:n arvoilla.

Deewiant kirjoitti:

Vertailun vuoksi tuon miljoonan läpikäymiseen menee noin reilut viisitoista sekuntia...

Millä kielellä ja masinalla noin nopsaan. Mulla menee 60 s. VB5:llä (Athlon XP 1800+)

Kielenä C, kääntäjänä GCC versio 3.4.2 (win2k) ja koneena 700 MHz Athlon: miljoonan ekan luvun tutkimiseen kuluu aikaa 8 sekuntia.

Deewiant kirjoitti:

Vertailun vuoksi tuon miljoonan läpikäymiseen menee noin reilut viisitoista sekuntia...

Millä koneella/algoritmilla/(edit: kielellä) siihen menee noin kauan? Omalla bruteforcella (3.4ghz prosessori) kestää miljoonan läpikäymiseen noin kolme tai neljä sekuntia.

[offtopic]
Osaisiko joku C++ guru kertoa, miksi

char * m = new char[7];
// tähän silmukat, jotka iteratiivisesti hakevat palindromit
delete [] m;

aiheuttaa virheen: Unhandled exception 0x7c901230 in palindromi.exe: User breakpoint.
Mitään breakpointia ei tietysti ole olemassakaan. Jos poistan muistin vapautuksen (delete [] m;) virhettä ei esiinny.
[/offtopic]

setä kirjoitti:

Millä kielellä ja masinalla noin nopsaan. Mulla menee 60 s. VB5:llä (Athlon XP 1800+)

Win98 käyttöjärjestelmällä C++:lla 333Mhz pentium II koneella lukuvälin 1-1000000 läpikäymiseen menee keskimäärin 0.03 s.

setä kirjoitti:

Deewiant kirjoitti:

Vertailun vuoksi tuon miljoonan läpikäymiseen menee noin reilut viisitoista sekuntia...

Millä kielellä ja masinalla noin nopsaan. Mulla menee 60 s. VB5:llä (Athlon XP 1800+)

Kieli D, masiina Athlon64 3000+. Ja ihan bruteforcella.

peki: eikös tuo käsky mene "delete[]" eikä "delete []"

VilleP kirjoitti:

Win98 käyttöjärjestelmällä C++:lla 333Mhz pentium II koneella lukuvälin 1-1000000 läpikäymiseen menee keskimäärin 0.03 s.

Ohhoh! Ei taida olla millään bruteforcella. uskomattoman nopea!

Aika suuria nopeuseroja, olisi kiinnostavaa nähdä, miten monella tavalla tämänkin siis voi tehdä.

peki: Itse lauseissa ei ole vikaa, mutta tarkista nyt kuitenkin vielä mahdolliset yliosoitukset yms. Niistä toisinaan tulee tuollaisia.

Metabolix: Siinähän se vika olikin... =)

Oma optimoimaton PHP-kikkareeni väänsi välin 1 - 1 000 000 56 sekunnissa. Hyvin huomaa eron "oikeiden" ja skriptauskielien välillä.

VilleP kirjoitti:

Win98 käyttöjärjestelmällä C++:lla 333Mhz pentium II koneella lukuvälin 1-1000000 läpikäymiseen menee keskimäärin 0.03 s.

Aika ylivertaisen nopea mihinkään tähänastisissa. Jollain normi 2GHz Athlonilla menisi varmaan jotain 4ms aikoja sitten... Mutta aika turhaapa se on, voi olla ettei niitä 4-jäsenisiä seuroja enään ole enempää. Tosin sen toteamiseen tarvitaankin sitten matemaatikko ellei joku löydä vielä lisää näillä bruteforceilla.

Pitihän se kokeilla omalla ykköskoneellakin (1.66GHz XP) tuota PHP skriptiäni ja menihän se 40.7s. Kohta varmaan luovutan ja lähetän ratkaisun Antille, ellen sitten keksi vielä jotain nopeuttavaa algoritmia.

Sain pudotettua ajan 12 sekuntiin hieman ohjelmaa viilaamalla. Mutta tuo 0,03 s ihmetyttää. Miten voi ???

setä kirjoitti:

Mutta tuo 0,03 s ihmetyttää. Miten voi ???

Fiksulla algoritmilla. O(n^2)-tasoinen (sellaiseksi ainakin oman brute-forceni laskin, saatan olla väärässäkin) ei ole lähes koskaan se paras mahdollinen :-)

Hienoa, noin on tarkoituskin. Ilmeisesti valmiista funktioistakin on apua. Täytyypä kehitellä vielä omaa versiota.

Minun ohjelmani ilmoittaa ajaksi 0,001s, eli alle sen menee. 2,0GHz Athlon on prossuna. Varmaan tässäkin olisi vielä optimoinnin varaa, ja koodi on kaikin puolin surkeaa :) Niin ja tämä oli siis ilman vastausten tulostusta, se tietenkin vie oman aikansa. Samana ne vastaukset silti pysyvät.

Antti voisi kerätä noiden koodinpätkien lisäksi myös kunkin ohjelman ilmoitetun suoritusajan, eikö? Mielenkiinnolla odottelen noita nopeita toteutuksia, kun ei itsellä taidot riitä :)

Minun tämänhetkinen ohjelmani kuluttaa linuxin time-ohjelman mukaan ilmeisemminkin 0.051 sekuntia, ja siinä on tulostus.
Acer Aspire 1360:llä, jossa pyörii AMD 2800+ Semptron (?Mobile?). Linuxissa gcc-kääntäjällä.

Muok. (Se käyttää hivenen tehokkaampaa algoritmia, mutta Brute Forcea kuitenkin. Ordoa en ole (vielä?) laskenut, mutta se saattaa olla O(nlog(n))), jos oletetaan n:n olevan käsiteltävän alueen suuruus. Tosin se saattaa olla tarkkaanottaen O(n²log(n)).

Nyt PHP-skripti suoriutuu tuosta miljoonasta 27 sekunnissa, ainoa optimointi oli käyttää PHP:n omaa funktiota lukujärjestelmien muunnokseen.

peran kirjoitti:

Muok. (Se käyttää hivenen tehokkaampaa algoritmia, mutta Brute Forcea kuitenkin. Ordoa en ole (vielä?) laskenut, mutta se saattaa olla O(nlog(n))), jos oletetaan n:n olevan käsiteltävän alueen suuruus. Tosin se saattaa olla tarkkaanottaen O(n²log(n)).

Minun on vaikea mieltää moista brute-forceksi. :-) Käytkö tuossa ajassa tosiaan kaikki luvut välillä 1-1000000 läpi? Jos et, vaan suljet pois joitain välejä jonkin fiksuuden takia, se ei ainakaan minun kirjoissani ole brute-forcea ;-)

Deewiant kirjoitti:

peran kirjoitti:

Muok. (Se käyttää hivenen tehokkaampaa algoritmia, mutta Brute Forcea kuitenkin. Ordoa en ole (vielä?) laskenut, mutta se saattaa olla O(nlog(n))), jos oletetaan n:n olevan käsiteltävän alueen suuruus. Tosin se saattaa olla tarkkaanottaen O(n²log(n)).

Minun on vaikea mieltää moista brute-forceksi. :-) Käytkö tuossa ajassa tosiaan kaikki luvut välillä 1-1000000 läpi? Jos et, vaan suljet pois joitain välejä jonkin fiksuuden takia, se ei ainakaan minun kirjoissani ole brute-forcea ;-)

Ilmeisesti se ei sitten ole Brute forse, koska se käy läpi vain kaikki mahdolliset palidromit.
Kiitoksia, kun tarkensit, sillä Käsite on minulle uusi.
Yritin kyllä googlettaa, ja wikipediaa-käyttää, mutta ei minun englanninkielentaidolla saatu selvyyttä asiaan.

Kun mokaa, niin hokaa. ;)

BTW. mitenkähän BruteForce-määritelmä menee, l. Esim. Jos shakkipelin (tulevat) siirrot ratkaistaan BruteForcea käyttämällä, ilmeisesti käydään nappuloilla kaikki mahdolliset nappula-yhdistelmät ja valitaan valitaan niistä mahdolliset seuraavaan siirtoon? - Se ainakin levahtaa käsiin.

Oma 30 rivin ohjelmani, joka käy aidosti läpi kaikki luvut laskee nuo miljoona ensimmäistä lukua noin 0.15 sekunnissa AMD 3000+ Athlonilla. Nopeampi tapa olisi tosiaan generoida lukuja, jotka ovat palindromeja ainakin jossain lukujärjestelmässä.

Isompia lukuja lähtisin esimään lukujoukosta, joka on 8-järjestelmässä

S = 3S3 | 1S1 | 0S0 | 0 | e

Nuo pitäisi olla palindromeja ainakin lukujärjestelmissä 2,4 ja 8. Noitahan on ääretön määrä, joten on mahdollista, että joku noista luvuista olisi palindromi myös jossain muussa lukujärjestelmässä välillä 2-10, vaikka kyseisen palindromin todennäköisyys pieneekin hyvin pieneksi luvun pituuden kasvaessa.

Brute force = raaka voima. Kai sitä voi tässä jo paljastaa... Eli brute-forcellahan tämä tehtävä menee niin, että käydään kaikki nuo luvut 1 - 1000000 läpi, muunnetaan jokainen tavalla tai toisella kaikkiin tarvittaviin järjestelmiin, ja katsotaan, onko se ainakin neljässä niistä palindromi. Tämän ajatuksen on varmasti jokainen keksinyt ihan itsekin, eli tämä ei toivottavasti pilaa kilpailua.

Brute force siis tarkoittaa aina sitä, että käydään kaikki mahdollisuudet läpi sen kummemmin miettimättä. vähän sama kuin että laskisi matematiikan laskun suoraan järjestyksessä sieventämättä selkeitä asioita ensin pois.

VB5:llä bruteforcella jättäen turhat tarkistukset pois menee 8,46 ms noihin 373 lukuun. Tästä eteenpäin täytyy sitten kehitellä jotain fiksumpaa eli askeltaa palindromeittain koska alkavat olla sitä harvemmassa mitä suuremmasta luvusta ja kantaluvusta on kysymys. Jos nuo kaikki 1000000 bruteforcettaa 0.15 s tai jopa 50 ms niin täytyy varmaan olla apuna tehokkaita funktioita.

Metabolix, ehkä ongelman ratkaisu ei ole järin vaikea mutta mielestäni tuo paljastaa jo liikaa, sehän on ohjelmoinnin muodollisuuksia vaille valmista koodia.

Monia varmasti kiinnostaisi keskutella toisten toteutustavoista, joten jos sallittaisiin omien koodien linkitys, mutta sillä edellytyksellä että siitä käy selkeästi ilmi että kyseisetä linkistä aukeaa ratkaisu.

Eikai noita valmiita ratkaisuja nyt voi vielä paljastaa (vastanneita vasta reilu 30). Jos Antti jaksaa koodata ja kehittää tota systeemiä, niin ainut mahdollisuus olisi oma keskustelualue niille, jotka ovat jo vastanneet ja samalla lähettäneet oman koodinsa julkiseksi ja niin ettei sen jälkeen voi enää uudestaan vastata. Keskustelutkin muuttuisivat julkisiksi sen jälkeen, kun ratkaisu virallisesti julkaistaan. Tälläisessä tapauksessa en luottaisi yhtään kilpailijoiden lojaalisuuteen olla käyttämättä muiden alkkiksia.

setä kirjoitti:

... jopa 50 ms niin täytyy varmaan olla apuna tehokkaita funktioita.

Toi oli huuhaata. Se on tehty tehokkaammalla algoritmilla, mutta tulipahan keskustelua.

ajv kirjoitti:

Eikai noita valmiita ratkaisuja nyt voi vielä paljastaa (vastanneita vasta reilu 30). Jos Antti jaksaa koodata ja kehittää tota systeemiä, niin ainut mahdollisuus olisi oma keskustelualue niille, jotka ovat jo vastanneet ja samalla lähettäneet oman koodinsa julkiseksi ja niin ettei sen jälkeen voi enää uudestaan vastata. Keskustelutkin muuttuisivat julkisiksi sen jälkeen, kun ratkaisu virallisesti julkaistaan. Tälläisessä tapauksessa en luottaisi yhtään kilpailijoiden lojaalisuuteen olla käyttämättä muiden alkkiksia.

Niin no onko Putkapostin idea vain saada nimensä tuonne "hall of fameen" vaiko antaa tekemisen puutteesta kärsiville jotain ajankulua? Kyllähän tuohon ongelmaan voi löytää ratkaisun vaikka Googlella tai vaikka kysymällä joltakulta joka sen osaa ratkaista jos kerta itse ei sitä osaa eikä halua ratkaista...

Mutta ehdotushan se vain oli, voimme toki odottaa tehtävän viralliseen lopetukseenkin. Haluttaa vain nähdä mitä noi huippunopeat toteutukset ovat syöneet :)

Jos joku haluaa laskennallisesti hieman haastavamman tehtävän, voi yrittää etsiä kantaluvuilla 2-1000 palindromiseuroja, joissa on vähintään 10 jäsentä. Hyvä lukualue tälle tehtävälle näyttää olevan 30e6-1e9. Välillä 30e6-40e6 noita seuroja on vain 8 ja niiden lukumäärä näyttää harvenevan isompiin lukuihin mennessä. Tässäkin tehtävässä seuroja, joissa on 9 jäsentä löytyy ääretön määrä, mutta 10 jäsenestä en ole varma.

Kyllä tämä mielstäni on mainio idea innostaa koodaamaan ja pähkäilemään eri vaihtoehtoja. Itselläni eka versio oli virheellinen, eka virheetön vei noin 100 s ja kolmas versio (sekin brute forcea) noin 12 s tulosteineen. Kyllä tämmöinen aivojumppa vanhaakin kiinnostaa. Varsinkin kun siellä näkyy olevan kerrassaan etevää porukkaa ja fiksumpia ratkaisuja. Tosiaan ratkaisuja julki vasta kun vastausaika umpeutuu.

Oman Java version ajaleminen 2GHz Pentium M koneessa kestää
n. 7,5 sek.

Mun Haskell-versiolla kestää modernilla koneella 2 ja puol minuuttia. Ehkäpä siirryn takaisin suunnnittelupöydän ääreen...

setä kirjoitti:

VB5:llä bruteforcella jättäen turhat tarkistukset pois menee 8,46 ms noihin 373 lukuun. Tästä eteenpäin täytyy sitten kehitellä jotain fiksumpaa eli askeltaa palindromeittain koska alkavat olla sitä harvemmassa mitä suuremmasta luvusta ja kantaluvusta on kysymys. Jos nuo kaikki 1000000 bruteforcettaa 0.15 s tai jopa 50 ms niin täytyy varmaan olla apuna tehokkaita funktioita.

C:stä ja C++:sta (ja joistain muistakin) löytyy valmis optimoitu funktio desimaaliluvun konvertointiin haluttuun kantalukumuotoon. VB:llä sen joutuu tietääkseni tekemään itse. VB:llä ei pääse mitenkään samoihin aikoihin c:n kanssa kun joudutaan tekemään konversioita joilla on tekemistä stringin kanssa. Hyvä algoritmi on se joka merkitsee eniten, mutta siitä huolimatta...

Niin arvelinkin, mutta kiinnostaa kuitenkin vääntää sellainen VB:llä ja testata nopeuksia. Harrastelijan puuhastelua mutta oivaa aivojumppaa.

setä kirjoitti:

Niin arvelinkin, mutta kiinnostaa kuitenkin vääntää sellainen VB:llä ja testata nopeuksia. Harrastelijan puuhastelua mutta oivaa aivojumppaa.

Olen itsekin suuri VB:n ystävä, ja tämänkin tehtävän tein alunperin sillä (tosin VB.NET versiolla) Tässä tehtävässä tosin tuli vb:n rajat vastaan (tai sitten omien taitojen) joten tein saman C++:lla.

esakom kirjoitti:

setä kirjoitti:

Niin arvelinkin, mutta kiinnostaa kuitenkin vääntää sellainen VB:llä ja testata nopeuksia. Harrastelijan puuhastelua mutta oivaa aivojumppaa.

Olen itsekin suuri VB:n ystävä, ja tämänkin tehtävän tein alunperin sillä (tosin VB.NET versiolla) Tässä tehtävässä tosin tuli vb:n rajat vastaan (tai sitten omien taitojen) joten tein saman C++:lla.

Mitkä vb:n rajat tarkalleen oli kyseessä?

_Pete_ kirjoitti:

Mitkä vb:n rajat tarkalleen oli kyseessä?

Jouduin kirjoittelemaan itse funktion 10-kantaisen luvun konvertointiin haluttuun kanta-muotoon. En osannut tehdä ks. funktiota ilman ettei olisi jossain määrin tarvinnut käyttää string-tyyppistä muuttujaa. String-käsittelyfunktiot (mid, left, right...) ovat vb:ssä *todella* hitaita C:n vastaaviin verrattuna.

Joten annettu ongelma kyllä ratkesi vb:lläkin, mutta hitaasti. Tosin algoritmikin perustui BruteForcella kaikkien lukujen tutkimiseen, joten aikaa meni minuutti. Vastaava C++:llä noin 10 kertaa nopeampi. Tämä tosin johtuu juuri siitä etten vb:llä osannut tehdä tarpeeksi nopeaa konversio-funktiota, jonka c:stä löysin valmiina.

Jos joku neropatti tekee VB-version joka käy bruteforcella kaikki luvut (1-1000000) läpi ja pääsee viiden sekunnin paikkeille 2,4 Ghz koneella, niin olen kiinnostunut näkemään ratkaisun...

esakom kirjoitti:

_Pete_ kirjoitti:

Mitkä vb:n rajat tarkalleen oli kyseessä?

Jouduin kirjoittelemaan itse funktion 10-kantaisen luvun konvertointiin haluttuun kanta-muotoon. En osannut tehdä ks. funktiota ilman ettei olisi jossain määrin tarvinnut käyttää string-tyyppistä muuttujaa. String-käsittelyfunktiot (mid, left, right...) ovat vb:ssä *todella* hitaita C:n vastaaviin verrattuna.

Joten annettu ongelma kyllä ratkesi vb:lläkin, mutta hitaasti. Tosin algoritmikin perustui BruteForcella kaikkien lukujen tutkimiseen, joten aikaa meni minuutti. Vastaava C++:llä noin 10 kertaa nopeampi. Tämä tosin johtuu juuri siitä etten vb:llä osannut tehdä tarpeeksi nopeaa konversio-funktiota, jonka c:stä löysin valmiina.

Jos joku neropatti tekee VB-version joka käy bruteforcella kaikki luvut (1-1000000) läpi ja pääsee viiden sekunnin paikkeille 2,4 Ghz koneella, niin olen kiinnostunut näkemään ratkaisun...

Ok.. Itse en edes yrittänyt tehdä stringtöntä versiota ja tämä nykyinen versio kävi 1-1000000 läpi 4.5sek entisen 9.5sek sijaista, pikaisen optimoinnin tuloksena.

Pistin ohjelman nyt menemään 1 - Integer.MAX_VALUE ja vauhti on sellaset 180K numeroa per sekunti.

Jaa, mihinkäs tuossa String-tyyppiä tarvitsee? Taulukkoon vain kaikki, niin ei tarvitse mitään turhia funktioita käyttää, ja väitänpä, että toimii liki yhtä nopeasti kuin C++:lla. Kyllä se on enemmän bruteforce-algoritminkin yksityiskohdista kiinni.

Eihän noita sringejä tarvi muutoin kuin jos haluaa tulostaa myös löydetyt palindromiseurat. jolloin aikaa menee VB-versiolla minuutin verran. Ilman stringejä ja edelleen btrute forcella menee 12 s. Fiksulla algoritmilla näköjään pääsee VB:lläkin noin 0,1 sekuntiin. vaan ei vielä pelaa oikein.

Deewiant kirjoitti:

setä kirjoitti:

Mutta tuo 0,03 s ihmetyttää. Miten voi ???

Fiksulla algoritmilla. O(n^2)-tasoinen (sellaiseksi ainakin oman brute-forceni laskin, saatan olla väärässäkin) ei ole lähes koskaan se paras mahdollinen :-)

Itse sanoisin, että jos joku käyttää tähän tehottomanpaa algoritmia kuin O(NBlog(N)), jossa N on laskettavien lukujen lukumäärä ja B kantalukujen määrä, niin on pahasti hakuteillä. Log(N) kuvaa käytännössä luvun yksittäisten numeroiden lukumäärää.

Bruteforce ratkaisuuksien tehokkuuserot selittynevät log(N) termin kertoimen eroilla. Omassa ratkaisussani esimerkiksi tuon termin kerroin on keskimäärin huomattavasti alle 1/2.

Nopeutta toimintaan kuitenkin saisi huomattavasti lisää, jos korvaisi ensimmäisen N:n jollain paljon pienemmällä eli ei käytäisikään kaikkia lukuja läpi vaan vain sellaiset, joilla on mahdollisuus olla ratkaisu.

FooBat kirjoitti:

Itse sanoisin, että jos joku käyttää tähän tehottomanpaa algoritmia kuin O(NBlog(N)), jossa N on laskettavien lukujen lukumäärä ja B kantalukujen määrä, niin on pahasti hakuteillä. Log(N) kuvaa käytännössä luvun yksittäisten numeroiden lukumäärää.

Kävin ajatuksella tuon brute-forceni läpi ja sanoisin nyt, että se on suunnilleen mallia O(NB²log₁₀(N)). Tuohon ei ole laskettu mukaan kielen hoitamaa stringinkääntöä. Arvioin tuon ylimäärä-B:n kantalukukonvertteristani, siitä saatan olla täysin väärässä.

Täytynee miettiä noita toteutustapoja vielä tarkemmin, jospa ylihuomenna löytyisi aikaa... Tosiaan jos stringejä ei tarvita niin vb:kin on varmasti ihan hyvä ase. Ei mitään kiirettä toteutusten julkaisuun, niin ehditään mekin joilla on sekä töitä, koulua että perhettä... =)

Haah! VB5:llä noin 0,015 s fiksulla ja täysin omintakeisella algoritmilla.

Sanoisinpa, että Foobat on myös hakoteillä jos luulee tarvitsevansa ratkaisussa ainuttakaan stringiä, kantalukukonversiota tai edes jakolaskua :)

Eiku oho, Deewiantille piti tietysti sanoa. Tekaisin tuossa kumminkin jo viikonloppuna tuollaisen, joka ratkaisee ongelman 486/66-koneella 0.30 sekunnissa ja siitäkin vain 7% on itse etsintää. Flattitaulukko on hieman huono tietorakenne tuloksille.

Ei sitä ratkaisussa tietenkään tarvitse, mutta sellainen minulle tuli ensimmäisenä mieleen, eli se brute-force. Fiksu ratkaisu tekee ihan eri tavalla.

Tulin tehneeksi sellaisen fiksumman algoritmin, joka käy läpi vain luvut, jotka ovat jossain lukujärjestelmässä palindromeja. Hiukan mietittyäni sen tehokkuusluokka on niinkin yksinkertainen kuin O(sqrt(N)*B*log(N)) (sqrt(N) = B^log_B(N)/2). Se käy 1e9 lukua parissa sekunnissa läpi, vaikka onkin aika kömpelö ja optimoimaton. Miljoonan luvun läpikäynnissä oma optimoitu bruteforce taisi puolestaan jopa olla aavistuksen nopeampi kuin tämä "hyvä" algoritmi.

FooBat kirjoitti:

Tulin tehneeksi sellaisen fiksumman algoritmin, joka käy läpi vain luvut, jotka ovat jossain lukujärjestelmässä palindromeja. Hiukan mietittyäni sen tehokkuusluokka on niinkin yksinkertainen kuin O(sqrt(N)*B*log(N)) (sqrt(N) = B^log_B(N)/2). Se käy 1e9 lukua parissa sekunnissa läpi, vaikka onkin aika kömpelö ja optimoimaton. Miljoonan luvun läpikäynnissä oma optimoitu bruteforce taisi puolestaan jopa olla aavistuksen nopeampi kuin tämä "hyvä" algoritmi.

Se on melko samanlainen algoritmi, jonka minä tein aikaisemmin, ja joka selviytyi 1000000:sta 0,051 sekunnissa.
Hivenen nykyisin optimoituna, sain parannettua hivenen omani O-arvoa ja muutenkin nopeutta, mutten kuitenkaan ole laskenut O-arvoa.

Vielä sitä voisi yrittää nopeuttaa tai parantaa ehtoja, mutta olen melko tyytyväinen jo tämänhetkiseen ratkaisuuni.

Viikon kysymys oli mun mielestä enemmän mukava.. tossa putkapostissa ei ole mitään varsinaista järkeä, vaikka se hyvä juttu onkin että sellainen edes on. mutta: se oli vaan mun mielipide.. :P

No, tässä sitten minun mielipide:
Tuo voittaa Viikon kysymyksen kevyesti, ja tämähän on Ohjelmointiputka.
Minusta on hauskaa, että joku viitsii keksiä harrastelija ohjelmoijille, joilla ei ole mitään tekemistä, tekemistä.

Onko putkaposti liian tylsä, vai vaikea? Sitä voi vaan arvailla, koska vastausmäärä tuskin koskaan nousee samoihin kun Viikon kysymyksen...

CyantLeap kirjoitti:

koska vastausmäärä tuskin koskaan nousee samoihin kun Viikon kysymyksen...

Eikä ole tarkoituskaan.

On täysin eri asia klikata nappia tai oikeasti syventyä jonkin ongelman ratkaisemiseen, kuten on niistä saatava tyydytyskin.