Uusin putkaposti on aiheeltaan matemaattinen:
https://www.ohjelmointiputka.net/postit/tehtava.
Kirjoitin ohjelman joka ratkaisee tuon. Kolmen lapsen tapauksen se laski oikein. Myös neljän (tarkistin käsin oikean tuloksen), joten logiikka toimii. Ongelma on että ohjelma toimii rekursiivisesti. Kokeilin kuudellatoista lapsella ja ohjelma mietti vielä 7 tunnin jälkeenkin, joten keskeytin sen. Takaisin lähtöruutuun miettimään muita tapoja.
Itsellä vähän sama ongelma. Kymmenen kohdalla meni jo muutama minuutti ja yhdennessätoista loppui kärsivällisyys.
Cvgää vyzrvfrfgv xngfbn cnerzcvn nytbevgzrwä crezhgnngvbvyyr.
Sopivalla algoritmilla suoritusaika on muutamia kymmeniä millisekunteja, myös 150 lapsen tapauksessa.
Kehitysehdotus: Putkaposteista voisi olla "vaikeuslista" eli tehtävät listattu järjestettynä kokonaispisteiden mukaan. Siinä listassa voisi olla myös merkittynä itse tehdyt.
Chiman kirjoitti:
Kehitysehdotus: Putkaposteista voisi olla "vaikeuslista" eli tehtävät listattu järjestettynä kokonaispisteiden mukaan. Siinä listassa voisi olla myös merkittynä itse tehdyt.
Tuostahan sen saisi kai nopeasti sortattua:
https://www.ohjelmointiputka.net/postitaulu.php
Tai no, en nyt äkkiseltään osaa sanoa idioottivarmaa keinoa, jolla pystyisi ilmaisemaan vaikeutta. Ehkä joku täydet pisteet saaneiden osuus kaikista vastaajista? Toisaalta oikein vaikeaan voi olla että moni on yrittänyt muttei saanut mitään ja sitten lähes kaikilla osallistuneilla on täydet. Vastausten määrälläkään ei suoraan voi mitata, koska uudet käyttäjät ei välttämättä ole osallistunut vanhoihin ollenkaan.
Grez kirjoitti:
Tuostahan sen saisi kai nopeasti sortattua:
https://www.ohjelmointiputka.net/postitaulu.phpTai no, en nyt äkkiseltään osaa sanoa idioottivarmaa keinoa, jolla pystyisi ilmaisemaan vaikeutta. Ehkä joku täydet pisteet saaneiden osuus kaikista vastaajista? Toisaalta oikein vaikeaan voi olla että moni on yrittänyt muttei saanut mitään ja sitten lähes kaikilla osallistuneilla on täydet. Vastausten määrälläkään ei suoraan voi mitata, koska uudet käyttäjät ei välttämättä ole osallistunut vanhoihin ollenkaan.
On hyvä jos sivulla voisi lajitella "vaikeusasteen" lisäksi myös osallistuja määrän ja muiden indikaattoreiden avulla.
Olen melko varma, että tilastotieteestä löytyy joku tapa arvioida vaikeutta. Voin kysyä eräältä matikkafoorumilta. En vaan muista, miten pisteytyssysteemi on laadittu siinä tapauksessa, että henkilö on saanut jonkun tuloksen, joka ei ole paras mahdollinen.
Chiman kirjoitti:
Sopivalla algoritmilla suoritusaika on muutamia kymmeniä millisekunteja, myös 150 lapsen tapauksessa.
Silti paras suoritus tähän asti on 27 lasta.
[muokkaa]
Jaa, tarkoittaako 27 sittenkin 30 lasta?
Tapaukset 4–30 eli yhteensä 27 tapausta.
jutti kirjoitti:
Chiman kirjoitti:
Sopivalla algoritmilla suoritusaika on muutamia kymmeniä millisekunteja, myös 150 lapsen tapauksessa.
Silti paras suoritus tähän asti on 27 lasta.
[muokkaa]
Jaa, tarkoittaako 27 sittenkin 30 lasta?
Tehtävässä ei oltu kiinnostuneita tapauksista, joissa lapsia oli vain 1-3.
Näinhän se oli. Keksin kaavan tuijottelemalla lukuja, jotka sain rekursiivisella ohjelmallani. En ymmärrä vielä kaavaa analyyttisellä tasolla, mutta se toimii. Olenko siis tyhmä? En tarvitse koodipätkää enää ratkaistakseni tehtävän, pelkkä openOffice riittää.
Antti Laaksonen kirjoitti:
2 tapauksessa 1 lapsi näkee eteensä
Onko tuossa virhe? Ensimmäinen näkee joka tapauksessa eteensä ja jotta kukaan muu ei näe eteensä, on lasten oltava pituusjärjestyksessä. Minusta ainoastaan yhdessä tapauksessa vain yksi lapsi näkee eteensä.
Jaska kirjoitti:
Antti Laaksonen kirjoitti:
2 tapauksessa 1 lapsi näkee eteensä
Onko tuossa virhe? Ensimmäinen näkee joka tapauksessa eteensä ja jotta kukaan muu ei näe eteensä, on lasten oltava pituusjärjestyksessä. Minusta ainoastaan yhdessä tapauksessa vain yksi lapsi näkee eteensä.
Siinähän se kuvassa näkyy, alhaalta keskimmäine.
Olinpas hölmö, jotenkin ajattelin, että eteenpäin näkeminen tarkoittaa sitä, että hän ei näe juuri edessä istuvan takaraivoa. Mutta tehtävässä pitikin nähdä ilmeisesti eteenpäin junan etupäästä. Nyt selkisi.
Joo, jännempää on oikeesti nähdä vuoristoradassa ohi kaikkien edellä istuvien, eikä vain jotain takaraivoa muutaman penkin päässä.
Ai niin, pitikö tulos sieventää? Siihen loppu mun tietämys. Koska loppuarvo on desimaaliluku 1 ja 30 väliltä, ehkä on mahdollista tehdä tuo sievennys jo itse algoritmiin ja ehkä välttyä joutumasta käyttämään niin tähtitieteellisiä lukuja, että kokonaislukumuuttujien lukualue loppuu kesken.
Tämähän ei ole sievennetty, eihän:
11 1.23456e+008/7.89123e+007 12 2.34567e+009/8.91234e+008
No, raavas mies ei sievennystä kaipaa!
(Mod. sensuroi lukuarvot.)
Tehtävän ratkaisussa auttaa jokin murtolukuja käsittelevä kirjasto. Esimerkiksi Pythonissa on kätevä luokka fractions.Fraction.
Itse kyllä pärjäsin ihan hyvin ilman mitään kirjastoa. Yksi muuttuja osoittajalle ja toinen nimittäjälle. Käytännössä lopullinen tuloste syntyi lopulta alle 100 merkillä C:tä.
Täytyy sanoa että pyörittelin noita lukuja hetken aikaa ja sain ihan jäätävän kaavan. Sitä sitten pyörittelin ja sievensin monta kertaa ja lopulta jäljelle jäi kaava joka aiheutti todellisen facepalmin. Siis sen verran pitäisi ehkä kuitenkin osata todennäköisyyslaskentaa, että näkee yksinkertaisen kaavan suoraan tehtävänannosta.
No, tulipa tehtyä vaikeimman kautta. Laittaisin mielelläni sen ekan ratkaisukaavani näkyville että saisitte nauraa, mutta se ei oikein muutu vähemmän selväksi ROT13:lla. :(
jutti kirjoitti:
En ymmärrä vielä kaavaa analyyttisellä tasolla, mutta se toimii.
Sitten kun huomaat mistä on kyse niin tajuat heti että olisihan se pitänyt heti ymmärtää. Hauskaa muuten, että olin ratkaissut oikeastaan täsmälleen saman tehtävän murobbs:n matemaattiset -ongelmat ketjussa noin kuukauden sisään ja silti lähdin samalla tavalla ratkaisemaan tätä kuin sinäkin.
Jos sievennetyssä vastauksessa on viimeinen rivi muodossa:
30 a/b
...niin onko sekä a että b mahdollisesti 32 bittisen kokonaislukumuuttujan lukualueella? Minun mielestäni ne menee aika lailla yli, vaikka murtoluvun arvo tietenkin on välillä 1-30.
Eivät ole 32-bittisen muuttujan alueella. Useimmissa kielissä on kuitenkin mahdollisuus joko 64-bittisiin kokonaislukuihin tai rajoittamattoman mittaisiin kokonaislukuihin. Myös double-tyyppinen liukuluku taitaa tällä kertaa riittää arvojen tarkkaan tallentamiseen, jos sievennys tehdään joka välissä eikä vasta lopussa.
Grez kirjoitti:
Chiman kirjoitti:
Kehitysehdotus: Putkaposteista voisi olla "vaikeuslista" eli tehtävät listattu järjestettynä kokonaispisteiden mukaan.
Tuostahan sen saisi kai nopeasti sortattua:
https://www.ohjelmointiputka.net/postitaulu.phpTai no, en nyt äkkiseltään osaa sanoa idioottivarmaa keinoa, jolla pystyisi ilmaisemaan vaikeutta. Ehkä joku täydet pisteet saaneiden osuus kaikista vastaajista?
Jaska kirjoitti:
Olen melko varma, että tilastotieteestä löytyy joku tapa arvioida vaikeutta.
Jaska, tietenkin tilastotieteestä löytyy tapa arvioida vaikeutta. ;) Tilastotieteen toisen vuoden opiskelijana voisin jonkinlaista ehdotusta tälle vaikeusasteen laskemiselle antaa.. Tietenkään emme saa selville niitä henkilöitä, jotka ovat yrittäneet ratkaista tehtävää, mutta epäonnistuneet siinä ja näin jättäneet kokonaan vastaamatta. Pitää siis turvautua siihen tietoon joka on käytettävissä (=jonkinlaisen tuloksen saaneet).
Pikaisesti mietittynä tehtävän vaikeus voisi olla yksinkertaisesti tehtävästä saatujen pisteiden mediaani tai sitten md/(1+s) (jossa Md = mediaani ja s = keskihajonta). Eivät nämä varmasti parhaat mahdolliset tavat tehtävän vaikeuden laskemiseen ole. Ne tulivat kuitenkin ensimmäisenä mieleen.
Ääh.. Tein PHP:llä tuollaisen pikku ohjelman, joka tutkii kaikki mahdolliset lasten istumajärjestykset läpi. Siitä oli tarkoitus jatkaa laskemaan se eteensä näkevien lasten odotusarvo, mutta koko homma kaatui siihen, että ohjelmani ei laske kuin 8 lapsen istumajärjestykset. 9:nnen lapsen kohdalla ohjelma kaatuu, koska on liian paljon laskettavaa.. Saisin kyllä ohjelmaa vielä hiukan järkevöitettyä, mutta se tuskin auttaa niin paljon, että saisin 30 lasta laskettua. Pitää varmaan keksiä jokin muu laskutapa kuin katsoa kaikki mahdolliset istumajärjestykset läpi. Täytyy kuitenkin sanoa, että keksin melko älykkään tavan laskea mahdolliset istumajärjestykset, vaikkei siitä loppuenlopuksi riittävän kevyttä ohjelmaa saanutkaan.. xD
Ei ehkä kovin hyvä tapa vaikeusasteen arviointiin: vastauksien_määrä*vastauksien_täydellisyys / Sivun_avauskerrat
Ongelmana tulee tietenkin jo 100 pistettä saaneiden tilaston katsomiskerrat.
Mun mielestä ei ole mitään merkitystä, montako kertaa sivua on katsottu, vaan ennemmin kuinka moni on katsonut.
AkeMake, toisen vuoden tilastotieteilijänä varmaan osaat laskea, että 30 lapsella on suunnilleen 265 kvintiljoonaa erilaista istumajärjestystä, joten jos saisit kaikki 10 lapsen tapaukset (3628800 järjestystä) tutkittua sekunnissa, 30 lapsen tapauksiin kuluisi samalla vauhdilla 73 kvadriljoonaa sekuntia eli 846 triljoonaa päivää eli 2,3 triljoonaa vuotta. Kaikkien vaihtoehtojen kokeileminen on siis aika huono ratkaisu.
Sivun katsomiskerrat tai sivua katsoineiden henkilöiden määrä ei kerro tehtävän vaikeudesta yhtään mitään. Sivun latauskerrat voisivat antaa jotain viitteitä siihen suuntaan, sillä vaikeaa tehtävää tuskin tullaan toista kertaa katsomaan. Tosin helppo tehtävä vastaavasti ratkaistaan ensimmäisellä sivun katselukerralla. Nämä eivät siis ole hyviä mittareita tehtävän vaikeusasteeksi. Sensijaan tehtävän mielenkiintoisuuden mittauksessa niitä voisi käyttää apuna. Itse liputtaisin edelleen yksinkertaisen mediaanin puoleen. Jos haluaa laskea vaikeuden vaikeammin niin sitten se mediaani jaettuna 1+keskihajonnalla. :)
Nyt vedetään halvalla koko yritykseni laskea lasten istumajärjestyksiä ja samalla kyseenalaistetaan opiskeluni. :P En jostain syystä ajatellut ollenkaan sitä kuinka monta istumajärjestystä on jo 15 lapsella (saati 30 lapsella). Lähdin vain sokeasti koodaamaan jotain jolla tutkia ne istumajärjestykset, kun se tuntui mielenkiintoiselta haasteelta. Näin jälkikäteen ajateltuna oli tietysti tyhmää edes yrittää moista. :)
Pitää yrittää nyt sitten löytää se oikea tapa ratkaistu tuo tehtävä eli löytää tapa laskea ne eteensä näkevät lapset.. Kyllä tämä tästä. :)
AkeMake kirjoitti:
Sivun katsomiskerrat tai sivua katsoineiden henkilöiden määrä ei kerro tehtävän vaikeudesta yhtään mitään.
Niin siis pointtina olikin toki suhteuttaa tehtävää katselleiden määrä siihen, moniko tehtävän on ratkaissut. Mielestäni jos jostain tehtävästä olisi vastauksina vaikka 3 täydellistä ratkaisua, niin olisi mielenkiintoista tietää onko sitä tehtävää katsonut 3 vai 300 käyttäjää.
Askartelin tämän avulla ad hoc -skriptin:
#!/bin/sh
wget https://www.ohjelmointiputka.net/postitaulu.php
mv -f postitaulu.php data.html
python html2csv.py data.html
sed 's/\([^,]*,\)\{3\}/ /;s/\"\"/na/g;s/\"//g;s/ //g;s/,/\t/g;1d;$d' < data.csv > data.m
sed 's/[^,]*,\"\([^,]*\)\".*/\1/;1d;$d' < data.csv > tekijat.txt
grep "<th>" data.html | sed 's/tunnus=\([^"]*\)/\n\1/g' | sed 's/\([^\"]*\).*/\1/g' | grep -v "<" > tehtavat.txtjolla tulostaulun sisällön saa esim. Octaven ymmärtämään muotoon (data.m, tekijat.txt, tehtavat.txt).
Tuossahan on periaatteessa tehtävien määrää vastaava määrä datapisteitä, eli vektoreita, joissa on kaikkien tekijöiden määrää vastaava määrä komponentteja. Tästä datasta pitäisi sitten ekstraktoida yksi tehtävän vaikeutta kuvaava luku jokaiselle pisteelle. Varmaan parhaisiin tuloksiin pääsee katsomalla jollain fiksulla menetelmällä kokonaiskuvaa eikä vain yksittäisiä pistevektoreita (ja ehkä myös käyttämällä alkuperäisiä pistemääriä noiden 0-100 sijaan).
No nyt onnistuin tuon penteleen vuoristoradan kanssa. Hieman ärsyttää, etten vieläkään oivalla tuota kaavaa, vaikka yksinkertaistin sitä loppuun asti. Käytin ratkaisuun yhtä kirjastoa, jonka löysin (C++-luokka). Vielä piti itse optimoida muutama funktio, jotta tulos selvisi tällä vuosituhannella.
Väitän kyllä että et yksinkertaistanut loppuun asti, jos tarvitsee optimoida funktioita. Kuten Chiman sanoikin: Sopivalla algoritmilla suoritusaika on muutamia kymmeniä millisekunteja, myös 150 lapsen tapauksessa.
Xnaanggnn habugnn xbxbanna rfvzrexvxfv zbarraxb wäewrfglxfrra yncfrg ibvqnna ynvggnn wn xrfxvgglä inva fvvura inefvanvfrra xlflzlxfrra: Zvxä ba bqbghfneib.
Kyllä mulla on loppuun asti yksinkertaistettu ratkaisun kaava. Mutta kun siihen liittyy aika hankalia murtolukuja, jossa nimittäjä ja osoittaja on 64-bittisiä lukuja, ja käyttämäni kirjasto ei kovin fiksusti laskenut suurinta yhteistä nimittäjää.
Epäilen kyllä että se laskentakaava ei ole yksinkertaisimmaksi mahdolliseksi yksinkertaistettu, jos et suoraan näe siitä mihin se perustuu. Ihan vihjeenä että kaavan pituus on alle 10 merkkiä.
Ja tietty kirjastojahan löytyy joka lähtöön, mutta vaikea kuvitella että jokin suosittu kirjasto olisi huonompi kuin oma koodini. En käyttänyt mitään kirjastoa, käytin naivistisinta mahdollista tapaa sieventää, enkä tehnyt mitään optimointeja ja tehtävässä pyydettyjen tapausten laskemiseen meni 155 ms. Sama koodi toimii c, c++ tai c#, varmaan toimisi myös Javalla suoraan. Tulosten tulostaminen hieman tietty riippuu kielestä.
Optimoin sitä vielä hieman ja nyt sievennys on hieman vähemmän naiivi ja koko tehtävä pyörähtää alle 10ms.
Suuret murtoluvut ongelmina mullakin, tai siis niiden osoittajat ja nimittäjät. Pitääpi miettiä hieman miten sais fiksusti lavennettua/supistettua lukuja ilman, että ne missään vaiheessa ovat tolkuttoman suuria.
Melkeen vois kokeilla muutamaa matematiikan sovellusta, jos ne osaisivat suoraan laskea murtolukuja kivasti.
Aihe on jo aika vanha, joten et voi enää vastata siihen.