Keskustelu: Ohjelmointiputka: Putkaposti 20v

Ensimmäinen Putkaposti julkaistiin vuonna 2005. Viisi vuotta myöhemmin ongelmia oli jo 42 (plus kolme b-tehtävää) ja Antti listasi Putkapostin avoimia ongelmia. Jotkut ratkovat näitä vielä tänäkin päivänä ja päätin tehdä 20v-juhlavuoden kunniaksi päivitetyn listan, jossa on Antin listaamien ongelmien nykyinen tilanne (omien tietojeni mukaan) ja muutama aiemman listan jälkeen julkaistu tehtävä.

15: Kielitiedettä (avoin)

Ennätystä pystynee vielä parantamaan.

19: Älykäs robotti (ratkaistu)

Tuloksen 29 voi osoittaa optimaaliseksi yllättävän pienellä laskentamäärällä. Ratkaisin muistaakseni myös 4x5-ruudukon, mutta 5x5 oli vanhalle koodilleni liian vaikea.

29: Käänteislauseke (avoin)

Nykyinen 111 tuskin on paras mahdollinen.

Algoritmi-ideoita voi testata ratkomalla helpompia versioita. SL-haasteen tehtävä 5.8 on samantapainen ja isashkar ja zebraze paransivat sen ennätystä ihan hiljattain!

30b: Ahdas ruudukko 2 (avoin)

Hakuavaruus on valtava eikä ole mitään syytä olettaa, että 112 olisi viimeinen sana.

Avoin kysymys on myös, onko 116 = 4x29 mahdollinen.

35: Peilauskomento (ratkaistu)

Tämän voi varmaan ratkaista alle sekunnissa. Paras tietämäni aikakompleksisuus on O(N * log(N) * 2^N).

37: Kaulaketju (ratkaistu)

Tulosta 72 ei voi parantaa ja oleellisesti erilaisia ratkaisuja on 5.

Jos kaulaketjun pituus olisi 50 merkkiä, optimaalinen tulos olisi 90 sanaa.
Jos kaulaketjun pituus olisi 56 merkkiä, siihen mahtuisi jo 100 sanaa.

Seuraavat tehtävät julkaistiin vasta Antin listan jälkeen:

45: Lottovoitto (avoin?)

En tiedä, tai ainakaan en osaa itse todistaa, onko tulos optimaalinen.

47: Lukulauseke (avoin)

Yllättyisin, jos tätä voisi parantaa, mutta regexit ovat yllättäneet ennenkin.

48: Triplatulkinta (avoin)

Käytin heuristista hakualgoritmia.

Lupaan tarjota pullakahvit sille joka ratkaisee MD5 tehtävän 20merkkisen sanan.

wy5vn kirjoitti:

Lupaan tarjota pullakahvit sille joka ratkaisee MD5 tehtävän 20merkkisen sanan.

Aika riskitön lupaus :D

Itse laskeskelin niitä silloin 2011 silloisen tietokoneeni GPU:lla (joka oli ajan nopein kuluttaja-GPU tiivisteiden laskentaan), ja 11 merkin salasanassa kesti 40 tuntia. Eli jos ajatellaan että nykyiset näytönohjaimet (tai muut käytössä olevat välineet) olisi 26 kertaa nopeampia niin 12 merkkisen murtamiseen menisi 40 tuntia ja 20 merkkisen murtamiseen n. miljardi vuotta.

Toki jos keksisi bruteforcausta tehokkaamman algoritmin, niin tilanne voisi muuttua, mutta tällaista ei tietääkseni ole ainakaan julkisesti tunnettu.