# Day 3: Rucksack Reorganization

(izvirnik naloge)

## Vrednosti črk

Podatki vsebujejo seznam nizov. V prvem delu je potrebno za vsak niz ugotoviti, kateri znak se pojavi tako v prvi kot v drugi polovici. V drugem delu pa je potrebno gledati po tri zaporedne vrstice in ugotoviti, kateri znak se pojavi v vseh. V obeh primerih je iskani rezultat vsota vrednost teh znakov. Vrednosti znakov so a=1, b=2, c=3 in tako naprej do z=26, potem pa A=27, B=28 in tako do Z.

Za začetek poglejmo, kako dobiti vrednosti znakov, če imamo nek znak `c`, na primer

    c = "R"

### Kode ASCII

Pomagamo si lahko s kodo ASCII, ki jo vrne funkcija `ord`:

    ord("a")

    97

    ord("b")

    98

    ord("c")

    99

    ord("A")

    65

    ord("B")

    66

Vrednost znaka je enaka kodi minus 96, če gre za malo črko, oz. kodi -64 + 26, če gre za veliko. Torej:

    ord(c) - (96 if c >= "a" else (64 - 26))

    44

Ali, malenkost kompaktneje in zavedajoč se, da je `True` isto kot 1 in `False` isto kot 0:

    ord(c) - [64 - 26, 96][c >= "a"]

    44

### Seznam črk

Modul `string` ima spremenljivko `ascii_letters`, ki vsebuje vse črke angleške abecede.

    import string

    string.ascii_letters

    'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'

Vrednost črke je enaka indeksu v ta niz + 1:

    string.ascii_letters.index(c) + 1

    44

Če bi radi malo skrajšali program, podtaknemo nizu na začetek še en znak:

    import string

    letters = " " + string.ascii_letters

In zdaj

    letters.index(c)

    44

### Slovar

Seznami so, vsaj teoretično, počasni, zato je bolj prav uporabiti slovar. Kako sestaviti slovar, katerega ključi bodo črke, vrednosti pa vrednosti teh črk?

Načinov je kolikor hočemo.

V vsakem primeru se nam splača iti prek znakov v `string.ascii_letters`. Razlike bodo v tem, kako pridelati vrednosti.

Uporabimo lahko gornje trike, na primer `ord`

    vrednosti = {c: ord(c) - [64 - 26, 96][c >= "a"] for c in string.ascii_letters}

ali `index`

    vrednosti = {c: string.ascii_letters.index(c)  + 1 for c in string.ascii_letters}

Vrednosti pa lahko dobimo tudi s štetjem:

    vrednosti = {c: i for i, c in enumerate(string.ascii_letters, start=1)}

`enumerate` ima uporaben argument `start`. Preživeli pa bi tudi brez, le namesto `c: i` bi pisali `c: i + 1`.

Še bolj luštno je, če se spomnimo, da lahko `dict` sestavimo tudi tako, da mu podamo seznam parov:

    dict([("Ana", 5), ("Berta", 9)])

    {'Ana': 5, 'Berta': 9}

Tega seveda ne počne noben normalen človek, saj je lažje `{"Ana": 5, "Berta": 9}` ali kar `dict(Ana=5, Berta=9)`. Pač pa bomo slovar sestavili na ta način, kadar seznam takšnih parov slučajno že imamo ali pa si ga lahko pridelamo s kakim `zip`. Konkretno, tule sestavljamo seznam iz črk, ki jih priskrbi `string.ascii_letters` in številk od 1 naprej, ki jih dobimo s funkcijo `count` iz modula `itertools`.

    import string
    from itertools import count

    vrednosti = dict(zip(string.ascii_letters, count(1)))

Ta seveda zmaga.

## Prvi del: Samo preseki

Ni kaj: začetniška naloga iz presekov. Iz niza potegnemo prvo in drugo polovico ter ju spremenimo v množici. Sestavimo presek; ta bo, če je verjeti sestavljalcu naloge, vseboval točno en element, in dobimo ga s `pop()`.

    vsota = 0
    for vrstica in open("input.txt"):
        sredina = len(vrstica) // 2
        prva = set(vrstica[:sredina])
        druga = set(vrstica[sredina:])
        skupni = (prva & druga).pop()
        vsota += vrednosti[skupni]

    print(vsota)

    8085

Če tole bere kdo, ki ni prav izkušen v Pythonu, ga opozorimo na par detajlov.

Prvi je celoštevilsko deljenje. Rezultat deljenja z `/` je v Pythonu vedno `float`, `float`-ov pa ne moremo uporabiti za indekse. Zato delimo celoštevilsko, z `//`. Nizi v nalogi so vedno sode dolžine, tako da smo lahko brzz skrbi.

Funkcija (no, v resnici konstruktur tipa) `set` kot argument prejme poljubno reč, prek katere je možno iterirati. Torej mu damo preprosto niz, pa imamo množico.

Nato sestavimo presek in `pop`-nemo iz njega prvi element. Preseka ni potrebno spravljati v novo množico, pač pa seveda ne smemo izpustiti oklepajev.

Gornja rešitev je napisana lepo, počasi, po korakih. Šlo pa bi tudi brez vmesnih spremenljivk.

    vsota = 0
    for vrstica in open("input.txt"):
        vsota += vrednosti[(set(vrstica[:len(vrstica) //2]) & set(vrstica[len(vrstica) // 2:])).pop()]

    print(vsota)

    8085

A je to boljše? Niti slučajno. Je hitrejše? (Dvomim. Vsaj ne bistveno. Čemu potem to kažem? Samo zato, da pridemo do (med nekaterimi cenjene) rešitve v eni vrstici. :)

    print(sum(
        vrednosti[(set(vrstica[:len(vrstica) //2])
                   & set(vrstica[len(vrstica) // 2:])
                  ).pop()]
        for vrstica in open("input.txt")))

    8085

Če se zdi komu goljufija, da smo že poprej napisali vrstico, v kateri sestavimo slovar `vrednosti`, pa ga lahko nadomesti s katero od drugih različic, torej `ord` ali `indeks`.

## Drugi del: kosi po tri

Drugi del je zelo podoben: računamo preseke po treh zaporednih vrstic. Zabavno je vprašanje, ko priti do treh vrstic.

### Preberemo vrstico in še dve

Odpremo datoteko, a tokrat shranimo njeno ime v spremenljivko. Z zanko `for` beremo vrstice, a po vsaki prebrani vrstici z `readline()` preberemo še dve. Vse tri pretvorimo v množice in izračunamo presek.

    vsota = 0

    with open("input.txt") as f:
        for vrstica in f:
            presek = set(vrstica.strip()) & set(f.readline()) & set(f.readline())
            vsota += vrednosti[presek.pop()]

    print(vsota)

    2515

Čemu `strip()`? In čemu le enkrat? Vse tri vrstice se končajo z `\n`, torej se bo poleg iskanega znaka v vseh treh vrsticah pojavil tudi ta znak. Moramo se ga torej znebiti; zadošča pa, da se ga znebimo enkrat.

### Generatorji

Bolj zabavno je uporabljati generator. Kot vsi objekti, čez katere je mogoče iterirati, tudi datoteka vrne generator, če pokličemo funkcijo `iter`. Priskrbimo si torej iterator, potem pa ga trikrat podtaknemo `zip`-u. Zip ne ve - oziroma ga, točneje, nič ne briga - da je trikrat dobil isti iterator. Ko poženemo zanko čez `zip`, bo pač pridobil po en element od vsakega iteratorja in ker gre za en in isti iterator, bomo dobili tri zaporedne elemente.

Kako to deluje, si za začetek raje oglejmo na preprostem seznamu.

    s = [4, 2, 6, 9, 7, 5, 2, 4, 7]
    it = iter(s)
    for x in zip(it, it, it):
        print(x)

    (4, 2, 6)
    (9, 7, 5)
    (2, 4, 7)

Razred `set` ima metodo `intersection`, ki ji podamo poljubno število poljubnih objektov in vrnila bo njihov presek. Le prvi element mora biti nujno množica.

    set.intersection({3, 6, 7}, (1, 2, 6), [6, 3, 1])

    {6}

    set.intersection(set("peter"), "jože", "janez")

    {'e'}

Tako pridemo do te rešitve:

    it = iter(open("input.txt"))
    print(sum(
        vrednosti[(set.intersection(*map(set, triplet)) - {"\n"}).pop()]
    for triplet in zip(it, it, it)))

    2515

Z `for triplet in zip(it, it, it)` dobivamo trojke.

Zdaj pa moramo brati od znotraj: `map(set, triplet)` jih bo spremenil v množice (ker moramo spremiti eno, je vseeno, če spremenimo vse tri). Te tri množice moramo podati kot argument funkciji `set.intersection`; ker gre tu za tri reči, mi pa potrebujemo tri argumente, je potrebna zvezdica. Iz preseka odstranimo `\n` in s `pop` poberemo preostali element. Potem pa vzmemo vrednost in seštevamo.

Če bi radi to spravili v eno vrstico, zamenjamo `it, it, it` z `*[iter(open("input.txt"))] * 3`, torej

    it = iter(open("input.txt"))
    print(sum(
        vrednosti[(set.intersection(*map(set, triplet)) - {"\n"}).pop()]
    for triplet in zip(*[iter(open("input.txt"))] * 3)))

    2515

    [iter(open("input.txt"))] * 3

    [<_io.TextIOWrapper name='input.txt' mode='r' encoding='UTF-8'>,
     <_io.TextIOWrapper name='input.txt' mode='r' encoding='UTF-8'>,
     <_io.TextIOWrapper name='input.txt' mode='r' encoding='UTF-8'>]

vsebuje tri kopije istega iteratorja, natančno isto kot `[it, it, it]`). Vendar ne moremo klicati

    zip([iter(open("input.txt"))] * 3)

    <zip at 0x7f8b30371d80>

saj bi `zip` v tem primeru kot argument dobil en sam seznam. Kot argument mu hočemo dati vse elemente tega seznama, zato torej

    zip(*[iter(open("input.txt"))] * 3)

    <zip at 0x7f8b3036d300>

Mimogrede pa opazimo: `iter(f)`, kjer je `f` neka datoteka, vrne kar to datoteko:

    f = open("input.txt")

    f is iter(f)

    True

Torej niti ni potrebno klicati `iter`, temveč lahko napišemo kar

    print(sum(
        vrednosti[(set.intersection(*map(set, triplet)) - {"\n"}).pop()]
    for triplet in zip(*[open("input.txt")] * 3)))

    2515

## Kotlin

Pa dajmo še v Kotlinu. :)

    import java.io.File

    println(
        File("input.txt")
        .readLines()
        .map { it.trim() }
        .map { it.take(it.length / 2).toSet()
                .intersect(it.takeLast(it.length / 2).toSet()).first() }
        .sumOf { it.code -  (if (it >= 'a') 96 else 64 - 26) }
    )

    println(
        File("input.txt")
        .readLines()
        .map { it.trim() }
        .chunked(3)
        .map {
            it.map { it.toSet }
            .reduce { acc, s -> acc.intersect(s) }
            .first()
        }
        .sumOf { it.code -  (if (it >= 'a') 96 else 64 - 26) }

    )

Ideja je enaka: naredimo množici, presek in potem seštejemo vrednosti znakov; dobimo jih z `it.code`, ki je ekvivalenten Pythonovemu `ord(it)`.

Bolj zanimiv je drugi del: Kotlinovi seznami imajo `chunked(n)`, ki vrne seznam seznamov po `n` elementov. Te potem spremenimo v množice, z `reduce` izračunamo njihov presek in vzamemo prvi element.