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

Anonyymi

3

308

    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. Kylläpä on nautinnollista taas tämä palstan vassari valitus!

      Lähes jokainen avaus on vassareiden kitinää ja valitusta. Eikö se tarkoitakin, että silloin asiat menee maassamme parem
      Maailman menoa
      30
      2592
    2. Yksi kuoli nokkakolarissa

      Asiasta YLEn verkkosivuilla uutinen klo 23.02. Oliko itsemurha?
      Oulainen
      11
      1262
    3. Helvetistä ei ole paluuta

      Kun ihminen laskeutuu kuolleiden maailmaan, kauhujen valtakuntaan ja tuonelan ovet sulkeutuu kiinni, se on karu tunne ku
      Idän uskonnot
      333
      1002
    4. Mikä on kaivattusi ammatti

      entäpä sinun? 💶
      Ikävä
      45
      892
    5. Terveisiä vanhemmalle

      J-miehelle. Ehkä nähdään vielä 😉
      Ikävä
      45
      854
    6. Järjetön Topi-ilta

      Lisää tappiota konkurssipesälle. Miten voi olla mahdollidta , että annetaan järjestää tämä. Sorsakoski pyörii haudassaan
      Ähtäri
      20
      829
    7. Miksi nainen nukut huonosti

      Onko sulla jotakin huolia, vai jotakin miestäkö mietit? Vai tunnemaailmassako velloo? Ajatteletko koskaan minua? Paljo
      Ikävä
      61
      754
    8. Niin siinä Kävi

      Ettemme koskaan saaneet toisiamme
      Ikävä
      44
      730
    9. Halutaan toisiamme

      Mutta se on Salaisuus❤️
      Intohimo
      44
      716
    10. Jos olisit kaivattusi

      Kanssa kahdestaan samassa tilassa niin miten kävisi
      Ikävä
      46
      656
    Aihe