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

Anonyymi

3

128

    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. Sinkun läheisyyspula FWB uhka vai mahdollisuus?

      Aloin tässä vakavasti harkitsemaan FwB-miehen ”ottamisen” mahdollisuutta. Tosiaan itsellä alkaa kohtapuolin olemaan viik
      Sinkut
      206
      2312
    2. Voiko noin komea mies olla epävarma?

      Jotenkin mahdoton ajatus, mut nyt ymmärtäisin sen käytöksen mua kohtaan, jos näin on 🤔
      Ikävä
      166
      2144
    3. Luovuttaisit jo

      Tekee pahaa katsoa näitä keskusteluja, joissa kaipaat minua niin paljon. En ole susta kiinnostunut, joten voisitko lopet
      Ikävä
      169
      1612
    4. Jos Martina nai Aussi miehen

      Tekeekö saman homman, kun meni Eskon kanssa naimisiin, veti pullollisen valkoviiniä aamupalaksi, ja oli kännissä omissa
      Kotimaiset julkkisjuorut
      345
      1523
    5. Aamun ajatuksia

      Meillä oli vahva yhteys. Sitä ei voi selittää, sen vain tunsi. Olen ikävöinyt sinua siitä asti, kun tiemme tavallaan erk
      Ikävä
      105
      1415
    6. R.I.P. taas nuori urheilija - menehtyi 37-vuotiaana.

      Petri Koivisto vartioi Oulun Kärppien ja Espoon Bluesin maalia. https://www.is.fi/sm-liiga/art-2000010252054.html
      Maailman menoa
      26
      1261
    7. No oletko nyt

      Nainen tyytyväinen kun ei olla kohta enää missään tekemisissä? Minä en mutta ei sillä väliä. Vanhemmalle naiselle
      Ikävä
      54
      1184
    8. Vaitiolo velvollisuus!

      Meinasin jo mennä sanomaan,kaksi hoitajaa keskusteli kovaäänisesti kahvilassa hoitokodin asioita kuinka kurjaa,on saatto
      Karstula
      19
      1019
    9. Ethän sinä

      vaan luule, että oon varattu🤔
      Ikävä
      37
      985
    10. Mitä ihminen tekee, olipa se sitten fyysistä tai henkistä, sama energia tulee lopulta takaisin

      Monien kansojen tiedossa on karman laki, vaikka he eivät tietäisikään, että kyse on karman laista. Mitä ihminen tekee,
      Hindulaisuus
      109
      815
    Aihe