Hlavní navigace

Názor ke článku Sliding puzzle - skládání kostiček od anonym - Super clanok, aspon som sa tiez nieco naucil,...

  • 19. 1. 2021 20:28

    bez přezdívky

    Super clanok, aspon som sa tiez nieco naucil, napr. ze existuje heapq. Cele by sa mi to urcite nechcelo riesit, ale aspon som to trocha pooptimalizoval. Napr. len zamenou 2 riadkov som urobil asi o 40% vyssi vykon:

    class Tiles:
        def __init__(self, seq):
            self.data = bytes(seq)
            self.value = self.data

    Povodne mi ten kod ale nezbehol cez test case 8 (38), stale uletel timeoutom, tak som to este dalej optimalizoval a par zmenami sa mi to podarilo zbehnut. Aj ked je pravda, ze to nezbehne stale, treba parkrat kliknut na opakovany test8, ale asi na 20-30% to zbehne bez timeoutu.

    Upravil som to, ze som vlastne cele Tiles zrusil, pouzil priamo bytes a z next_states som urobil funkciu. Dalej som este upravil swap, aby bol rychlejsi pre pouzitie bytes:

    def swap(data, a, b):
        if a<b:
          return data[:a]+data[b:b+1]+data[a+1:b]+data[a:a+1]+data[b+1:]
        return data[:b]+data[a:a+1]+data[b+1:a]+data[b:b+1]+data[a+1:]

    Ak ma niekto zaujem, zverejnim aj cely kod.
    Povodny kod riesil 20 opakovani tych testov co su v clanku asi 1290ms, upraveny na bytes asi 818ms, vratane vsetok uprav asi 448ms, takze ten novy zbehne asi za 1/3 casu.

    Samozrejme riesenie s bytes je obmedzene na puzzle velkosti x*y<256, ale ak by ste chceli vacsie, je vhodne este pouzit array.array, tam mozete s dobrym vykonom ist az do velmi velkych puzzle.