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

Anonyymi

3

291

    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. Sä olet epävakaa

      tai ainakin yrität onnistuneesti vaikuttaa siltä. Ei sun kanssa uskalla ruveta yhtään mihinkään, menis hommat ojasta all
      Ikävä
      27
      1941
    2. Mieti miten paljon yritin

      Löytää yhteyttä kanssasi uudelleen sen väärinymmärryksen jälkeen. Koen etten tullut puoleltasi hyvin kohdelluksi mies😔
      Ikävä
      57
      1779
    3. Kurkkiiko myyrä jo

      Milloin tulee kolostaan?
      Ikävä
      36
      1494
    4. Kaikki on hyvin rakkaani

      Ja tulee olemaan.
      Ikävä
      77
      1200
    5. En enää uskalla laittaa sulle viestiä

      Naiselta miehelle ****
      Ikävä
      52
      1079
    6. Yksi viesti häneltä ja ottaisin takaisin

      Mutta ei sitä tule. Ja ehkä parempi niin, tein jo valintani. En saanut häneltä tarpeeksi, kaikki muu meni minun edelle j
      Ikävä
      23
      1075
    7. En ikinä koskaan

      En tule ikinä hyväksymään!
      Tunteet
      54
      920
    8. Sovitaanko ja halataanko?

      Pyydetään toisiltamme anteeksi...❤️
      Ikävä
      49
      893
    9. Olen selvästi rikki

      Narsistiset ihmiset jotenkin koukuttaa minut.
      Ikävä
      24
      884
    10. Keskisarjan puheet

      Onko kansanedustajan sopivaa puhua tuollai vai pitäisikkö potkia pois eduskunnasta?
      Suomussalmi
      178
      879
    Aihe