Advent of Code 03-04

Ebben a sorozatban az Advent of Code nevű weboldal kis adventi programozói feladványainak megoldásait írom le. Lássuk a 3. és 4. nap feladatait:

#03 — Day 3: Perfectly Spherical Houses in a Vacuum —

A mese most az, hogy a télapó a végtelen 2D-s térben osztogatja az ajándékait. Azt, hogy épp merre kell haladni a térben a következő ház felé, egy részeg manó diktálja neki a CB-n. Ha az utasítás ^ akkor északra, ha v akkor délre, > esetén keletre, < esetén pedig nyugatra kell repülnie.

Mivel a manó teljesen be van baszva ezért előfordul hogy rossz irányt diktál, így télapó kétszer ugyan abba a kéménybe dobja az ajándékot.

A kérdés: hány házba érkezik legalább egy ajándék?

Például:
- Egy darab > irány esetén 2 otthonba érkezik ajándék: egy a kiindulási, és egy az érkezési helyre.
- ^>v< esetén 4 házba jön ajándék. Négyzet alakban haladt a télapó, és a végén vissza jutott a kiindulási házba, így azt nem számoljuk még egyszer.
- A ^v^v^v^v^v hatására a télapó 2 ház között ugrál folyamatosan.

Nem készültem semmi fancy adatstruktúrával, dehát nem is az a célja ennek a feladatnak.

santa = [0, 0]
positions = set()

route = input()

positions.add(tuple(santa))
for direction in route:
    if direction == '^':
        santa[0] += 1
    elif direction == 'v':
        santa[0] -= 1
    elif direction == '>':
        santa[1] += 1
    elif direction == '<':
        santa[1] -= 1
    positions.add(tuple(santa))
print(len(positions))

Mivel a télapó a kétdimenziós térben mászkál, ezért deklaráltam a santa változót, ami egy két elemű tömb, a 0. indexen az x, 1. pedig az y koordinátát tárolja majd. Az origóból indulunk.
A positions halmaz tárolni fogja a télapó összes egyedi koordinátáját. A halmaz típus gondoskodik róla, hogy kétszer ugyan az az objektum ne kerüljön tárolásra (ettől halmaz, minden érék egyedi benne). A koordináták sorrendje elvész ugyan, de nem lesz rájuk szükség később.

Ahogy megkaptuk a route változóba az útvonalat, úgy egyből hozzá is adjuk a halmazhoz a kiindulási pontot (ezt még az inicializálásnál is meg lehetett volna tenni, nem számít igazából).
Ez után karakterenként végig megyünk az útvonalon, és módosítjuk a santa tömb értékeit annak függvényében hogy az x vagy y koordinátán melyik irányba mozdulunk el. Az egész végén a positons-höz adjuk az aktuális pozíciót. Fontos, hogy a position objektum list, ami unhashable, ezért tuple-é kell alakítani.
Az egész végén egyszerűen kiírjuk a halmaz méretét, ami az összes egyedi pozíció lesz.

2. rész

A feladat folytatásában a télapó munkájának gyorsításához munkába állítják a Robo-Santa robotot, így ketten haladnak végig az útvonalon.

A kérdés ugyan az: hány otthonba érkezik legalább egy ajándék?

• ^v esetén 3 házba, mert a télapó egyet megy északra, és a robotélapó egyet délre
• ^>v< esetén szintén 3 helyre, és a végén a télapó és a robotélapó is visszaérnek a kiindulási pontba
• ^v^v^v^v^v esetén 11 házba érnek oda, mert a télapó folyamatosan északra, míg a robotélapó folyamatosan délre halad.

# coding: utf-8

santa = [0, 0]
robo_santa = [0, 0]

positions = set()

route = input()

positions.add(tuple(santa))
positions.add(tuple(robo_santa))

for i, direction in enumerate(route):
    if i % 2 == 0:
        position = santa
    else:
        position = robo_santa

    if direction == '^':
        position[0] += 1
    elif direction == 'v':
        position[0] -= 1
    elif direction == '>':
        position[1] += 1
    elif direction == '<':
        position[1] -= 1
    positions.add(tuple(position))
print(len(positions))

Sokat nem változott a feladat, egyszerűen a robotélapó is kapott egy tömböt a pozíciójához robo_santa névvel. A beolvasás után mindkét pozíciót hozzá adjuk a positions halmazhoz. Igazából, mivel azonos helyről indulnak mind ketten, ezért felesleges a robo_santa-t hozzá adni a positions-höz, de aki ezt nem ismeri fel, abban felmerülhetne a kérdés hogy:

Oszt’ a robo_santa-t miért lehetett kihagyni?

Visszakanyarodva tehát, a ciklus kap egy számlálót, és ez után egyszerű oszthatósággal vizsgáljuk hogy az épp feldolgozott irány az a télapóé vagy a robotélapóé-e. Itt a position referenciáját ráállítom a megfelelő halmazra, és ez után minden pontosan úgy folyik tovább mint az első feladatban.

#04 — Day 4: The Ideal Stocking Stuffer —

A feladat szerint a télapó egy kis AdventCoint szeretne bányászni, amit kioszthat a kisfiúk és kislányok között. Ehhez olyan MD5 hashekre van szüksége, amik hexadecimálisan pontosan 5 darab 0-ás számjeggyel kezdődnek. A bányászathoz a hashelő algoritmus egy egymás után fűzött titkos kulcsot és egy decimális számot kap. A sikeres bányászathoz azt a legkisebb decimális számot kell megtalálni, ami a titkos kulccsal együtt 5 db nullával kezdődő MD5 hasht produkál. Most szépen sikerült leírnom kétszer ugyan azt a gondolatot, de így biztos éri mindenki hogy mi a helyzet.

Pár példa:
- Ha a titkos kulcsod abcdef akkor a válasz 609043, mert ha az abcdef609043 MD5-ölve 000001dbbfa3a5c83a2d506429c7b00e, ami 5 darab nullással kezdődik.
- Ha a kulcsod pqrstuv akkor a válasz 1048970.

Ez bizony egy nem túl bonyolult feladat, de jobb ötlet híján brute force módszerrel kell megtalálni a választ, azaz addig kell próbálgatni a számokat amíg olyan hasht nem kapunk ami teljesíti a fenti követelményt.

# coding: utf-8

import hashlib
from time import time

secret = input('Secret: ')

start = time()
i = 0
while True:
    md5 = hashlib.md5('{0}{1}'.format(secret, i).encode())

    if md5.hexdigest().startswith('00000'):
        break
    i += 1

print('Answer:', i)
print('Found in {0:.2f}s'.format(time() - start))

A secret beolvasása után sajnos lövésünk sincs hogy mégis mennyi számot kell kipróbálni mire jó hasht találunk, ezért egy szép kis végtelen ciklus indul, ami majd talán egyszer megáll majd a jövőben.

A 6. sorban előállítjuk a hasht, amihez egyszerűen egy format stringben egymás mellé kerül a secret és az i. Az md5() bytest típust vár, így az egész stringet encode()-olni kell. Ez után a hexdigest() visszatér az MD5 hashel stringként, amit aztán jól megnézünk hogy '00000'-el kezdődik-e. Az egész végén nem elfelejteni növelni az i változót!

Hogy látszódjon hogy hány percig bambuljuk az üres képernyőt miközben a számítógép bőszen melegszik, a ciklus végén kiírom a keresésre szánt időt (nálam 0.25s alatt végzett).

2. rész

A második rész annyira rövid, hogy be se másolom a forráskódot. A feladat annyi, hogy most találjuk meg azt a hast, ami 6 darab 0-val kezdődik. Ehhez egyszerűen a fenti forráskódban át kell írni a 11. sorban a '00000'-t '000000'-ra.

Kis várakozás után meg is lesz az eredmény, ez nálam 5.59s volt.

Gyorsabban multiprocessinggel

Miközben szegény CPU0 majd meghal a munkában a maradék 3 nem csinál semmit se a gépemben, és közben nekem meg 6 másodpercet kell várakoznom, szóval ideje többszálasítani a programot, meg minden lófaszt belepakolni amivel a legutolsó kis energia fröccs is kipréselhető a jó öreg PC-ből.

# coding: utf-8

import hashlib
from time import time
from multiprocessing import cpu_count, Process, Queue


def miner(secret: bytes, ranges: Queue, requests: Queue):
    requests.put(True)
    while True:
        range_object = ranges.get()

        for i in range_object:
            if hashlib.md5(secret % i).digest()[:3] == b'\x00\x00\x00':
                requests.put(i)
                break
        requests.put(True)


if __name__ == '__main__':
    BATCH_SIZE = 10**6

    secret = input('Secret: ')

    start = time()

    secret_bytes = secret.encode() + b'%i'
    processes = []
    ranges = Queue()
    requests = Queue()

    for _ in range(cpu_count()):
        process = Process(target=miner, args=(secret_bytes, ranges, requests))
        process.start()
        processes.append(process)

    i = 0
    while True:
        request = requests.get()
        if request is True:
            ranges.put(range(i * BATCH_SIZE, (i+1) * BATCH_SIZE))
            i += 1
        else:
            print('Answer:', request)
            break

    print('Found in {0:.2f}s'.format(time() - start))

    for process in processes:
        process.terminate()

Ez gyakorlatilag a jó öreg producer-consumer pattern, ahol a producer a main thread, a consumerek pedig a Process objektumok. A hashelő logika kikerült a miner függvénybe. Ez paraméterül kapja a titkos kulcsot, és két Queue objektumot: a ranges-ben range objektumok lesznek. A sorból mindegyik process kivesz egy darabot, és szépen végig iterálja a maga intervallumát. A requests Queue-ba teszi bele mindegyik process a kérését újabb intervallum generálásához.

A miner függvényben, a 14. sorban, az md5()-nek átadott paraméter is változott: a secret várhatóan bytes típusú lesz, és mivel Python 3.5.0-ban támogatott a bytes interpolation (PEP 461), ezért pofon egyszerűen mindenféle lószarok nélkül össze tudom fűzni a két értéket és még encode-olnom se kell. A hexdigest() is eltávozott, helyette a digest()-el bytest-ként megkapom a hasht. Felesleges hexadecimális értéket tartalmazó unicode stringgé alakítani a hasht, hiszen a bytest típusú értékben pontosan ugyan az szerepel, csak binárisan. Éppen ezért az összehasonlítás is bytest-hoz történik. Ha a feltétel igaz, akkor a requests-ek közé bekerül az érték maga amire igaz volt a feltétel, és kimászunk a ciklusból.

A 9. és 17. sorban szerepelnek a kérések. Ahogy elindul egy process, az azonnal berak a requests-be egy értéket. Ez most nálam egy sima True de akár az is lehetne hogy 'ready' vagy bármi ami serialize-álható. A 17. sorban, mivel befejeződött az intervallum iterálása, újra bekerül egy érték a requests-be. Ennyit csinál a miner.

Odalent, a 27. sorban gyors bytes-é alakítjuk a begépelt secret-et, és a végére csapjuk a format-ot, hogy a miner-nek már csak interpolálnia kelljen. A 32. sorban aztán elindulnak a Process objektumok, pont annyi mint ahány processzormag van.

A 38. sorban kezdődik a móka. Itt is egy végtelen ciklus indul, mert nem tudjuk előre hogy meddig kell majd várni. A main thread ki is vesz a requests-ek közül egyet. A get() az blocking utasítás, tehát itt addig áll a futás amíg nem lesz akármi amivel vissza lehetne térni. Eddigre jó eséllyel minden process fut már és mindegyik berakott valamit a requests-ek közé, de ha mégse, akkor ugye tovább várunk. Ez után egy gyors érték ellenőrzés következik. Ha a request True objektum (itt használhatjuk az is operátort) akkor generálunk egy új range objektumot. Python 3-ban a range már nem list-el tér vissza ugye, és az objektum gond nélkül berakható a queue-ba. A range méretének képlete elég egyértelmű szerintem. A szelet méretét a BATCH_SIZE szabályozza, ami 10**6 (1,000,000). Ezt így hasraütésre írtam.. Ja és ne felejtsd el növelni azt a nyomorult i-t, kérlek (nem úgy mint én ~)

Ugye ha a request objektum nem True akkor minden bizonnyal egy int-et kaptunk, ami az eredmény. Ezt gyorsan kiírjuk, és az egész végén angolosan killeljük az összes processt, majd az oprendszer gondoskodik memóriáról.

Ezzel a módosítással sikerült 2.08s-ra lenyomni a hashelést, ami már tűrhető szerintem. Ez 2.68x gyorsabb mint egy szálon.