Yritin ratkoa tehtävää sivulta https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=mpera . Miksi tämä ei tuota tapauksessa 10 oikeaa vastausta: https://pastebin.com/UxPaEid7
Miksi putkapostin ratkaisuyritys tuottaa väärän tuloksen?
Anonyymi
3503
0Äänestä
Muut lukivat myös
Ketjusta on poistettu 1 sääntöjenvastainen viesti.
Luetuimmat keskustelut
- Hävettävä käytösHävettääkö sinua jokin?
- Tekisin SINUT ONNELLISEKSI NAINENMutta EHKÄ onni EI OLE mitä HALUAT.
- Mitähän sitä...Tsuumailin vähän muuallekin välillä ja törmäsin ajatuksiin, että miehen tulee suojella naista kaikelta pahalta. Mutta yhtään ei oltu eritelty mitä se kaikki paha on, jolta suojella. Jotenpas kysynkin kyselyikäni kyselyn…
- Kuka murtautu illalla kipparilleJotaki hampuusia kannettu ambulanssiin ja kipparin iso ikkuna palasina..Mitä tapahtunu??
- Kuvittelin että oltiin läheisempiäYstäviä, tavallaan. Mutta ei sitten oltukaan sun näkökulmasta. Pettymys, mutta totun kyllä asiaan vähitellen.
- Tule sunnuntaina juna-asemalleKello kymmenen aikaan, tavataan siellä. Ainoa ja viimeinen tilaisuus tavata. Jos et tule niin et enää koskaan näe minua. En halua kirjoitella mitään, en halua kuulla selityksiä. Haluan tavata.
- Tiedätkö yhtäkään näistä "julkkiksista"? Elämäni biisi vieraslista la 10.10. hämmästyttääElämäni Biisissä on totuttu näkemään suomalaisia julkisuuden henkilöitä, jotka ovat koko kansalle tuttuja. Vieraita on ollut mm. viihteen, taiteen, tieteen, urheilun, politiikan ja kulttuurin saralta. Jos on ollut koko …
- Myönnä poisLoukkaannuit mulle silloin aikoinaan? Ne viestit, väärinymmärrykset, kaikki. Miehelle
- Omapahan on vikasi jos jää loppuelämän romanssi välistä kun haluat olla itsepäinen jääräJa tuomita, jotain mitä et kykene ymmärtämään, antamatta edes mahdollisuutta, vaikka olen tehnyt parhaani elämäni edistämiseksi ja oikeasti yrittänyt!! Itken tyynyyn... tuskin edes yhtä vuotta ilman itsetuhoisia ajatuks…
- Vappu Pimiä lataa suorat sanat MasterChef-kritiikistä: "Tee niin tai näin, niin se on aina..."Vappu Pimiä liittyi viime MasterChef Suomi -kaudella arvovaltaiseen tuomaristoon. Pimiän rinnalla tuomaroivat Helena Puolakka ja Henri Alén. Pimiä toi tuomarikolmikkoon näkemystä ja kulmaa huippuravintoloiden keittiöide…
- Onko tarkoitus ottaa ihmisten eläkevarat valtion käyttöön?Vai mistä tässä eläkeiän nostossa hamaan tappiin on kyse? Eihän moni sitten saisi käytännössä eläkettä koskaan vaikka eläkemaksuja koko elämänsä olisi maksellutkin.
- Onko se sinun mielestäsiminun syyni, että tilanne on se mikä se on? En tiedä. Toisaalta, en pysty uskomaan että millään minun tekemisilläni olisi ollut juurikaan merkitystä.
- Alette alas tulla sieltäMissä oletkin, täällä hidastuu koko palstan väki ilman sinua. Tarinaa ei narinaa. 🍃😆 https://youtu.be/4W4DIgbBbsk?is=Vdbj3wnuTGMchXVC
- Sahan puupulaSahalla pitää olla valtava puupula kun Varikkosuoran uudelta myyntipaikan tontilta piti kaataa kaavassa suojellut puut? Kuinka ELINvoimaVALIOlautakunta antanut luva tälläiseen liito-oravien reitipuiden joukkotuhoon. Mas…
- Eiköhän tämä ole jo tässäParivuotta hukkaan heitetty.
- kunnioitan tahtoasiEn tule sinua enää lähestymään.
- Dodii. Kuvailekaivattusi ulkonäköä :)
- Haluan sanoa sulle miesEttä pysytään molemmat pois täältä palstalta. Maltetaan olla pois, koska olosi on silloin parempi. Minä en kirjoittele enää, joten voit unohtaa tämän. Ottaisitko minuun yhteyttä muuta kautta, jos haluat. Olisin onnessan…
- Mitä enää haluat??Tätä on kestänyt liian kauan!
- Perjantai jälleen bläähViikonloppuna sataa, mitä meinaatte tehdä? Pian on syyslomakin, suunnitelmia tähän säähän? Mulla olis pihahommaa vielä, mutta en helvetissä mene sateeseen kastumaan. Kasvoi vähän kyr*äkin otsaan kelin takia. Eikö nyt vo…
Vastaukset 3
Vanhimmat
Sulla kun on tuo testi
s[pos-i] == s[pos i]
niin sehän testaa että pos:ista eteen- ja taaksepäin on samoja merkkejä eli noin löytyisi (parittoman pituisia) palindromi-pötköjä.
Pitää testata, että vierkkäiset merkkijonot i:n matkalta ovat samat eli
s[pos-i:pos] == s[pos:pos i]
Sittenhän tulee ongelmaksi se, että luuppia ei voi katkaista, jos eroava indeksi löytyy, koska se ei tarkoita, että suuremmalla i:n arvolla ei voisi löytyä toistojaksoa.
Nuo korjaukset kun tekee (ja tallenna bestPos, se taisi sinulta unohtua, eikä mjonoa tarvitse mihinkään) ja output olisi näin
print(str(tapaus) " " str(maximi) " " str(bestPos-maximi 1))
Mutta nyt siis ongelma on että tuo koodi on melkolailla hidas. Itse huijasin ja käytin seuraava Sage-koodia:
from sage.combinat.words.suffix_trees import DecoratedSuffixTree
s = 'hfhfggccaggccagccafff'
start, run2 = max((x[1], x) for x in DecoratedSuffixTree(Word(s)).square_vocabulary())[1]
print ("{} {}".format(run2/2, start 1))
https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/words/suffix_trees.html
Tuossa algoritmissä, jota Sagekin käyttää on muuten takana suomalaisen Esko Ukkosen algoritmi:
https://en.wikipedia.org/wiki/Ukkonen's_algorithm
Tämä algoritmi muodostaa merkkijonon suffiksi-puun (kaikki merkkijonon päätteet koodaava tietorakenne) lineaarisessa ajassa (kun käytettävä merkistö on kiinnitetyn kokoinen).
Tai siis Ukkosen algorimia käyttää normaalille suffiksi puulle, "dekoroidulle" näytti olevan tästä: https://www.sciencedirect.com/science/article/pii/S0022000004000364?via=ihub , joka siis onkin ratkaisu juuri Putkapostin ongelmaan. Sen pitäisi olla lineaariaikainen mutta kertoimet ovat varmaan aika isoja (PS. Crochemoren algoritmi https://www.sciencedirect.com/science/article/abs/pii/0020019081900247 on saman ongelman ratkaisu ja sille taisi tilanvienti olla ainakin jotain 11*n), ainakin itselläni vei aika pitkään tuo ratkaisu. Mullahan ei omalla koneellani tuota Sagea ole vaan netissä suoritan: https://sagecell.sagemath.org/ . Olikin muuten aika homma saada nuo isot tapaukset laitettua :D Jotain "Message too long, message too long" se herjas, mutta näytti ne oikein kuitenkin menevän. Lopulta laitoin kympin (ajan takia) erikseen (piti muuten vielä maksimi rekursio-iteraatio limittiä nostaa, jo 9-tapauksessa) ja kyllä se lopulta oikeat vastaukset tuotti.
Tässä videossa näytetään toinen tapa muodostaa suffiksi-puu ja puhutaan sovelluksista, jotka ovat lähellä tätä ongelmaa (esim. pisin toistuva jono (mutta ei tarvitse olla vierekkäin)):
https://www.youtube.com/watch?v=NinWEPPrkDQ
Tänne oli tullut viesti, mutta AI ilmeisesti poistanut (ihan asiallinen mitä alkua inboxistani näin). Kannattaa laittaa koodit linkin taakse johonkin ulkoiseen juttuun, jos se niiden takia poistelee viestejä.
Tein nyt Python-version, jossa käytin kirjastoa https://pypi.org/project/suffix-trees/ . (Käytin aluksi https://pypi.org/project/suffix-tree/ :aa, mutta se on erittäin paljon hitaampi.) Ensin muodostetaan suffiksipuu ja siitä käydään sitten kaikki sisäsolmut läpi, joista jokaiselle käydään sen solmun lehtisolmu parit, joiden syvyyksien erotus on solmun syvyys. Koittelin tuohon tehdä erinäisiä parannuksia eritoteen 9 ja 10 tapauksissa taisi auttaa sellainen, että ensin tallennetaan dictiin kaikki lehtisolmut syvyyden mukaan ja sieltä voidaan sitten poimia tarvitun syvyinen pari kun yksi lehti on kiinnitetty, tarkastetaan vain onko se oikeassa haarassa. Joissain tapauksissa tuo taitaa vaan tulla liian hitaaksi (jos tutkitun syvyisiä lehtiä on paljon).
Tässä koodini https://repl.it/@minkkilaukku2/Mannynpera2#main.py . Ei toimi Python 3:lla, koska siellä _SNodella ei ole __dict__ -attributtia mutta Python 2:ssa on, mitä hittoa?!?? Ahaa: https://stackoverflow.com/questions/41658015/object-has-no-attribute-dict-in-python3
Loppujen lopuksi sain tavalla tai toisella tuolla koodilla kaikki tapaukset järjellisessä ajassa ratkaistua.
Noh,
Putkapostin kommenteissa ollut seuraava idea näyttää toimivan paljon nopeammin:
https://repl.it/@minkkilaukku2/Mannynpera1#main.py