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

Anonyymi

3

<50

    Vastaukset

    • 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

    suomi24-logo

    Osallistu keskusteluun

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

    Luetuimmat keskustelut

    1. Torppa sairaalaan

      Kas kas..oliko ullatus, että taas tapahtuu..
      Kotimaiset julkkisjuorut
      61
      1462