Miksi putkapostin ratkaisuyritys tuottaa väärän tuloksen?

Anonyymi

3

502

Äänestä

    Vastaukset 3

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • minkkilaukku

      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))

      • minkkilaukku

        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

    • minkkilaukku

      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

    Ketjusta on poistettu 1 sääntöjenvastaista viestiä.

    Takaisin ylös

    Luetuimmat keskustelut

    1. Miksi et halua kaivattusi

      kanssa suhteeseen? Onko jokin syy vaikka rakastat häntä?
      Ikävä
      136
      1302

    2. Miten hän käyttäytyy kun näette jossain?

      😁
      Ikävä
      73
      1223

    3. Carunan hinnat

      Yks proffa vauuttaa, ettei Caruna voi noin vain nostaa hintoja koska suomen laki kieltää, toinen proffa sanoo että Carun
      Maailman menoa
      105
      986

    4. Mikä sun kaivatussa on se miksi ihastuit

      ja ikävöit? Eli se jokin asia, mikä aiheutti tunteen, että tuossa on sitä jotain? Meinasitko tehdä asialle jotain vai ka
      Ikävä
      50
      925

    5. Koetko vielä et

      Olen elämäsi rakkaus?
      Ikävä
      78
      822

    6. Joko uskallat.

      Huomenna nähdään.
      Ikävä
      45
      791

    7. Kunnan päätie ja sen lähialueet

      Arvon hyrynsalmelaiset. Tätä palstaa on näin Ukkohallan mökkiläisena ihan viihteellistä lukea. Milloin teitä ahdistaa la
      Hyrynsalmi
      40
      788

    8. Oletko tullut siihen

      Tulokseen ettet saa minua
      Ikävä
      67
      663

    9. Olen tumma ja tulinen

      Ja vielä suora - en ollut sinua varten. n to m
      Ikävä
      113
      634

    10. Tunnustuksia

      Haluatko tunnustaa jotain, mitä on sydämelläsi?
      Ikävä
      45
      557
    Aihe
    TietosuojaselosteKäyttöehdotEvästeasetuksetSäännöt