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

Anonyymi

3

474

    Vastaukset

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • 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))

    • 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ä.

    Luetuimmat keskustelut

    1. Vesikin maksaa, miksei hengitysilma?

      Jatkuvasti itketään ettei ole rahaa mihinkään, mutta tilastojen mukaan rahaa on enemmän kuin koskaan, joten miksei asial
      Maailman menoa
      1
      1546
    2. Satuolennoista tarinointi ei kuulu peruskoulun tehtäviin

      Opetustunteja on muutenkin käytössä vain rajallinen määrä. Eli nämä satuhommat koulun ulkopuolelle vapaaehtoisiin harras
      Maailman menoa
      91
      1450
    3. Lahkokasteen ja kristillisen kasteen erot

      Raamatun mukaan Kristillisessä yhdessä kasteessa Jumala pesee ja puhdistaa ihmisen sydämen ja poistaa perisynnin kirouks
      Kaste
      422
      1031
    4. Suomalainen perheenisä vaatii Suvivirren esittämisestä hyvityksiä

      Itse lapsena uskonnonopetuksesta vissiin traumoja saanut ihka suomalainen (!) perheenisä vaatii Espoon kaupungilta korva
      Maailman menoa
      186
      891
    5. Heikki Paasosen Marita-vaimo jätti tunteikkaat jäähyväiset: "Tällä kertaa me..."

      Heikki Paasonen on naimisissa Marita Paasosen (os. Alatalo) kanssa ja heillä on kaksi pientä lasta. Nyt koitti aika jätt
      Suomalaiset julkkikset
      2
      777
    6. Mitä haluaisit

      Tehdä kaivattusi kanssa?
      Ikävä
      103
      757
    7. Pirkanlinna yleisötapahtuma

      Oli todella hyvä tilaisuus. Ja EERO. L. Aivan mahtava tyyppi. Veti rennosti ja asiallisesti. Ja yleisöltä hyviä kysymyks
      Ähtäri
      42
      731
    8. Kuka omistaa keltaisen vanhan aravan?

      Pitäs saada rakennuksen omistajaan yhteys, rappukäytävät on siivottomassa kunnossa. Hiekkaa ja roskia rappusissa, lisäks
      Haapavesi
      29
      730
    9. Känsäkoura ja hotelli

      Tietoa kuka ostanut?
      Kuhmo
      7
      694
    10. Nostetaanko nainen kissa pöydälle?

      Ja selvitetään nämä tunteet?
      Ikävä
      60
      683
    Aihe