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

Anonyymi

3

286

    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. Laitetaas nyt kirjaimet tänne

      kuka kaipaa ja ketä ?
      Ikävä
      135
      10681
    2. Pieni häivähdys sinusta

      Olet niin totinen
      Ikävä
      52
      5130
    3. Taas ryssittiin oikein kunnolla

      r….ä hyökkäsi Viroon sikaili taas ajattelematta yhtään mitään https://www.is.fi/ulkomaat/art-2000011347289.html
      NATO
      44
      2332
    4. Lähetä terveisesi kaipaamallesi henkilölle

      Vauva-palstalta tuttua kaipaamista uudessa ympäristössä. Kaipuu jatkukoon 💘
      Ikävä
      107
      2135
    5. Missä olet ollut tänään kaivattuni?

      Ikävä sai yliotteen ❤️ En nähnyt sua tänään söpö mies
      Ikävä
      29
      2053
    6. Vanha Suola janottaa Iivarilla

      Vanha suola janottaa Siikalatvan kunnanjohtaja Pekka Iivaria. Mies kiertää Kemijärven kyläjuhlia ja kulttuuritapahtumia
      Kemijärvi
      13
      1651
    7. Valtimon Haapajärvellä paatti mäni nurin

      Ikävä onnettomuus Haapajärvellä. Vene hörpppi vettä matkalla saaren. Veneessä ol 5 henkilöä, kolme uiskenteli rantaan,
      Nurmes
      41
      1472
    8. Tiedän kuka sinä noista olet

      Lucky for you, olen rakastunut sinuun joten en reagoi negatiivisesti. Voit kertoa kavereillesi että kyl vaan, rakkautta
      Ikävä
      29
      1154
    9. Känniläiset veneessä?

      Siinä taas päästiin näyttämään miten tyhmiä känniläiset on. Heh heh "Kaikki osalliset ovat täysi-ikäisiä ja alkoholin v
      Nurmes
      34
      1113
    10. Rakastuminenhan on psykoosi

      Ei ihme että olen täysin vailla järkeä sen asian suhteen. Eipä olis aikoinaan arvannut, että tossa se tyyppi menee, jonk
      Ikävä
      54
      1017
    Aihe