2015. december 23., szerda

avsort

Az elmúlt egy évemet, mióta minden tárgyamat abszolváltam a főiskolán, a szakdolgozatom szövegének megszülésével töltöttem. Ez töltötte ki a szabadidőm legnagyobb részét, még úgy is hogy csak szaros 80 oldal a teljes produktum.

Na de lássuk hogy miről is van szó:

Talán láttátok már a fenti videót, vagy esetleg ennek a lokalizált verzióját:

Az első videón Timo Bingmann sound-of-sorting nevű szoftvere látható működés közben. Ez a program mindenféle számítógépes rendező algoritmus működését mutatja be animációval, és azzal az édes 8-bites fütyüléssel. Az animáció során látható ahogy az algoritmus összehasonlít és megcserél értékeket, és a vizsgált értékek nagyságával arányos frekvenciájú hang is hallható. Az egész játék arról szól, hogy nem csak nézni, hallgatni is érdekes ahogy az értékek növekvő sorrendbe rendeződnek.


avsort

A szakdolgozatom témája ennek a szoftvernek egy javascriptes implementációjáról szól. Természetesen egyáltalán nem titkoltam hogy honnan ered az ötlet, de kifejezetten nem klónt akartam készíteni. A programom, az avsort, elég sok mindenben különbözik a sound-of-sortingtól, elsősorban renderelési lehetőségekben (a sound-of-sorting javára), de egy szerintem egész izgalmas funkcióval sikerült ellátnom, még hozzá hogy nem csak elolvasható a betöltött algoritmus forráskódja, de szerkeszthető is. Tehát a program limitációin belül bárki írhat magának saját algoritmusokat, és mutogathatja őket a csajoknak.

Mivel minden eszköz amit a dolgozat elkészítéséhez felhasználtam nyílt és szabad szoftver, ezért az avsort is egy nyílt alkalmazás, és ezzel együtt a dolgozat teljes szövegét is publikusan elérhető mostantól. (Persze a személyes információkat kigereblyéztem a pdfből)

Akit érdekel a program az a slapec.github.io/avsort címen kipróbálhatja. A projekt forráskódja elérhető githubon. A dolgozat szövegét pedig itt lehet elolvasni.

2015. december 12., szombat

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.

2015. december 5., szombat

Advent of Code 01-02

Azt hiszem időszerű újra írni valami kis bejegyzést, elvégre már majdnem vége az évnek!

Redditen találtam az Advent of Code nevű kezdeményezést, ami arról szól, hogy a programozói adventi kalendáriumnak minden ablaka 2 kis kódolni való feladványt rejt. A történt ismertetése után adnak pár kisebb példát hogy milyen inputra milyen outputot kell adni, majd elengedik az ember kezét, és egyedül kell onnantól válaszolni. A részvételhez regisztráció szükséges, de a feladatok szövege a nélkül is elolvasható. Ebben a bejegyzésben a feladat címére kattintva elolvashatjátok a részleteket is. Ahogy a címből látszik, ez post az első 2 ablakról szól, összesen 4 példáról. A teljes sorozatot itt ki lehet listázni.

Na akkor lássuk is őket:

#01 — Day 1: Not Quite Lisp —

A történt szerint a jó öreg télapó mászkál egy végtelen magas és végtelen mély épületben ajándékokat kézbesítve, és az inputján a ) karakterek azt jelenik, hogy egy emeletet lejjebb kell másznia, míg a ( egy emeletet felfelé jelent.

A kérdés az, hogy az input beolvasása végén melyik emeleten áll majd a télapó?

Ezek szerint:
- A (()) és ()() ugyan úgy a 0. emeletet redeményezi
- A ((( és (()(()( a 3. emeletet
- A ))((((( is a 3. emelet
- A (() és ))( egyaránt a -1. emelet
- A ))) és )())()) egyaránt a -3.

Az egyszerű végénél fogtam meg a problémát: külön-külön megszámolom hogy hányszor halad fel vagy le és kivonom őket egymásból:

data = input()
print(data.count('(') - data.count(')'))

2. rész

A második részben az a kérdés, hogy hányadik volt az az utasítás, amikor először érkezett meg a pincébe a télapó?

Példa:
- Ha az input egy ) akkor az 1. utasításnál érkezett a pincébe
- ()()) esetén az 5. utasításnál

Ez egy picit hosszabb már:

data = input()

position = 0
for i, c in enumerate(data, 1):
    if c == '(':
        position += 1
    elif c == ')':
        position -= 1

    if position < 0:
        print(i)
        break
else:
    print('Never entered the basement')

Az aktuális pozíciót a position változó tárolja. A feladat specifikálta hogy ez a 0. Ez után karakterenként iteráljuk az inputot, az enumerate() gondoskodik a szorszámozásról. Fontos: a feladat szerint 1-től indul a számozás, így itt ezt meg is adtam paraméterül.

Ezek után egyszerűen ( esetén csökkentjük a pozíciót, ) esetén növeljük. Amint a position kisebb mint 0, kiírjuk a karakter sorszámát és brake-el elhagyjuk a terepet.
Ha sose lépünk be a ciklusba, vagy sose érünk le a pincébe, akkor a rend kedvéért kiírjuk hogy Never entered the basement.

#02 — Day 2: I Was Told There Would Be No Math —

Ebben a feladatban azt kellett kiszámolni, hogy a tégla alakú csomagokhoz mennyi csomagoló papírra van szükség. A felületet a 2*l*w + 2*w*h + 2*h*l képlettel lehet kiszámolni. Extra csavar, hogy van egy kis ráhagyás is a csomagolásnál: a legkisebb oldal felülete.

A kérdés: mennyi csomagolóanyag kell összesen?

A példák szerint:
- A 2x3x4-es dobozhoz 2*2*3 + 2*3*4 + 2*4*2 = 52 négyzetláb* mennyiségű csomagolás és 2*3=6 négyzetláb ráhagyás kell, összesen tehát 52 + 6 = 58 négyzetláb csomagolóanyag.
- A 1x1x10-es dobozhoz 2*1*1 + 2*1*10 + 2*10*1 = 42 négyzetláb csomagolóanyag és 1*1 = 1 ráhagyás, összesen 42 + 1 = 43 négyzetláb tehát.
*A mértékegységnek nincs jelentősége ebben a példában

total = 0

while True:
    dimension = input()
    if dimension == '':
        print(int(total))
        break
    else:
        l, w, h  = [int(_) for _ in dimension.split('x')]

        areas = [(2 * l * w), (2 * w * h), (2 * h * l)]
        total += sum(areas) + (min(areas)/2)

A jó öreg Pythonos hátultesztelő patternnel indul a kód: addig olvasunk be méreteket amíg üres sort nem kapunk eredményül (tehát az utolsó adat után egy sima ENTER-t kell nyomni). Ha megvolt az üres sor akkor kiíródik a számláló (amit formai okokból int-é alakítok) és távozunk a ciklusból.

Ha viszont nem üres sort kaptunk, akkor a 'x' karakterek mentén szétvágjuk a beolvasott sort, minden értékét int-é castoljuk és szépen kicsomagoljuk őket 3 változóba: l, w és h.

Ezt követően kiszámoljuk a test 3 oldalának felületeit, ami bekerül az areas tömbbe. A legvégén pedig a számlálóhoz hozzáadjuk az oldalak felületeinek összegét, és a min(areas)-al a legkisebb felületet is. Itt kell még egy plusz osztás, mert korábban fel lett szorozva minden érték!

2. rész

A második részben azt kell kiszámolni hogy egy csomaghoz mennyi szalagra van szükség. Ebbe bele kell számolni a masnihoz szükséges mennyiséget is. A szalag hossza a doboz legkisebb kerületével egyenlő. A masnihoz szükséges plusz mennyiség pedig annyi mint az ajándék térfogata (mértékegység nélkül)

A kérdés az, hogy mennyi szalag kell az összes ajándékhoz?

A példák szerint:
- A 2x3x4-es doboznál egyszer 2+2+3+3 = 10 lábnyi sima szalag és 2*3*4 = 24 láb masnis szalag kell, összesen tehát 10 + 24 = 34 láb.
- A 1x1x10-es doboznál 1+1+1+1 = 4 lábnyi szalag és 1*1*10 = 10 masni szalag kell, összesen 4 + 10 = 14 láb.

total = 0

while True:
    dimension = input()
    if dimension == '':
        print(int(total))
        break
    else:
        l, w, h  = sorted([int(_) for _ in dimension.split('x')])

        total += (l + l + w + w) + (l * w * h)

Ez a kód szinte tök ugyan az mint az előző. A különbség, hogy a szétvágott adat értékeit növekvő sorrendbe rendezem még mielőtt változókba rakosgatnám őket. Így az l és w változó összeadásával megkapom a legkisebb kerületet. A térfogatnak meg mindegy hogy milyen sorrendben jönnek a számok, a szorzás amúgy is kommutatív.

Jóéjt

Ez a kis rövid jutott így ma estére. Igyekszem nem jövő márciusban folytatni a sorozatot.

-slp