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
Luetuimmat keskustelut
- Älä unohda minuaNainen ethän unohda minua. Asiat olisivat voineet mennä toisin, olisi vain pitänyt uskaltaa lähestyä sinua kun annoit siihen mahdollisuuden. Olen pettynyt itseeni, ja se kyllä närästää. Naiselle Mieheltä
- Nyt on nytTurha miettiä menneitä tapahtumia. Niitä ei saa tekemättömäksi. Tärkeintä on mitä tekee nyt ja tulevaisuudessa. Korjausliikkeetkin voi tehdä jos niihin tuntee tarvetta. Paluu tulevaisuuteenkin voi olla mahdollinen jos v…
- Kadutko mies?Silloin kuin vielä yritin lähestyä, etkä tarttunut siihen. Asioista pitäisi voida aina keskustella.
- Hyvää huomentaEräälle Naiselle ❤️🩹
- Eläkeikä nousee 70 vuoteen. Joudunko palaamaan työelämään?Nyt se on sitten päätetty, että eläkeikä Suomessa nostetaan 70 vuoteen. https://www.is.fi/politiikka/art-2000012324133.html Pääsin 67 vuotiaana eläkkeelle viime syksynä. Tarkoittaakohan tämä, että joudun palaamaan takai…
- Haluatko ettäUnohdetaan toisemme?
- Onko tällainen kuvio teistä okOnko tällainen kuvio teidän mielestänne ihan normaali ja hyväksyttävä? Nainen seurustelee miehen kanssa, mutta pitää samaan aikaan läheistä yhteyttä toiseen mieheen kertomatta tälle toiselle, että on parisuhteessa. Tämä…
- Jos haluat viestin...Olen vielä tämän illan palstalla. Laita halutessasi vinkki, sinä komea keski-ikäinen mies 😗
- Tuntuu kuin olisin vaimosiSe on erikoista se.
- Nyt kun kaikki on ohiToivon, että sulla menee hyvin ja pystyisin sinut kokonaan unohtamaan. Joskus on vaikeita hetkiä ja olen tosi pahoillani, miten sinua loukkasin ja loukkaan yhä. Se täytyy saada loppumaan.
- Empaattiset ihmisetOnko empaattiset ihmiset, etenkin naiset antavaisempia, kun ns. tavikset? Kaverin puolesta kysyn Oisko niinku mahkui?
- Niin haluaisin sut nähdä ja jutella!🙂
- Sut tahtoisinSinä senkin kusimutteri menit ja katkaisit kaiken yhteyden minuun. Tajuan nyt, että meidän roolit vaihtuivat ja sinä projektoit omia pelkojasi minuun. Anna minun välittää sinusta, älä työnnä mua pois. En oo vaatinut sul…
- Pitäisikö Vantaa liittää Helsinkiin.Mitä mieltä olette asiasta?
- TTK-juontaja Veronica Verho lataa suorat sanat tatuointien arvostelijoille: "Mä toivoisin, että..."Veronica Verho juontaa Tanssii Tähtien Kanssa -ohjelmaa yhdessä Ernest Lawsonin kanssa. Yksi puhuttaneimmista aiheista on ollut, miten suosikkijuontajan näyttävät tatuoinnit sopivat ohjelman pukuohjeistukseen ja tullaa…
- Nyt sinä siellä pohjoisessaNainen siellä laita viesti!
- Perussuomalaiset nostamassa eläkeiän 70 vuoteenRiikka Purran johtama valtiovarainministeriö haluaa nostaa eläkeiän 70 vuoteen ja taloutta sopeutettaisiin ensi vaalikaudella 8–11 miljardilla eurolla. Perussuomalaisten johtama ministeriö ilmeisesti arvelee, että seits…
- Mahdatko ymmärtääEttä olet samassa korissa kaikkein rakkaimpien kanssa. Öitä.
- Tunnetko piston sydämessäsiTunnetko piston sydämessäsi?
- Hyttikallion koulu homeessaHyttikallion koulu on homeessa ja opettajat on painostettu olemaan hiljaa asiasta, myöskään mitään korjauksia ei ole tehty, vakavia tapaturmia tapahtunut kun turvavälineet ovat lähteneet irti yms. Ilmeisesti halutaan kä…
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