Blog

Skladiště? Ne. KATASTROFA!!

Naposledy jsme zabránili katastrofě u rudonosého reaktoru. Nyní nás kroky zavedly hledat historika do skladu.

Část 1 (odkaz)

Historik zde není široko daleko, ani vysoko hluboko. Když jsme se zeptali operátora skladu, jen odpověděl, že nemá tušení, jestli tam historik je. Nefungují jim totiž počítače. Mají rozbitou paměť. Data jsou zkorumpovaná, což má za následek to, že se mezi násobícími instrukcemi objevuje nějaký šelest.

Ostatní elfové historici se rozběhly hledat ve skladu historika stařešinu, zatímco my jsme se rozhodli opravit počítače, jelikož tak jej najdeme v tomto obrím skladu rychleji.

Vypíšeme si obsah paměti a vidíme toto (vstup je vždy 1 jediný řádek!!!):

dmulx(1,5)mul(5,3)do(/*5.2
mul(3,5)don't()$mef6mul(4,8)@a|€q^mul[4,5)do()(4,7)mul(9,3)

Podle informací od operátora musíme najít sekvence mul(), které v závorce obsahují přesně 2 celá čísla zapsaná v dekadickém tvaru, oddělená čárkou a v rozmezí 0-999, tedy jedno až tří ciferná. V této sekvenci se taktéž nesmí objevit bílý znak.

Jelikož je celý tento úkol značně jednoduchý (na 2 řádky), napíši jej rovnou.

$parsed = \Nette\Utils\Strings::matchAll($this->input, '~mul\((\d{1,3}),(\d{1,3})\)~');
$result = array_reduce($parsed, fn (int $carry, array $item): int => $carry + $item[1] * $item[2], 0);

RegEx tedy hledá zadaný pattern a matchne mi toužená čísla, která mi stačí mezi sebou vynásobit. Na řešení jsem použil knihovnu od Nette, tedy \Nette\Utils, jejíž třída Stríngs mi poskytuje metodu matchAll. Tato metoda vrátí pole všech matchů, přičemž každý match je taktéž pole, které má na nulté pozici celý matchnutý výraz a na každé další obsah jednotlivých Groups.

Spustíme => 89

Celý výsledný kód vypadá takto:

<?php

declare(strict_types=1);

require __DIR__ . '/../vendor/autoload.php';

class Advent3a
{
    private string $input = 'dmulx(1,5)mul(5,3)do(/*5.2
mul(3,5)don\'t()$mef6mul(4,8)@a|€q^mul[4,5)do()(4,7)mul(9,3)';

    public function solve(): void
    {
        $parsed = \Nette\Utils\Strings::matchAll($this->input, '~mul\((\d{1,3}),(\d{1,3})\)~');
        $result = array_reduce($parsed, fn (int $carry, array $item): int => $carry + $item[1] * $item[2], 0);
        bdump($result);
    }
}

// Turn on tracy
$configurator = App\Bootstrap::bootWeb();
(new Advent3a())->solve();

Část 2

Během procházení paměti jsme však narazili na další dvě instrukce, které je potřeba brát v potaz.

První je do()

Druhá je don't()

do() značí, že máme za ním dělat onu operaci z bodu 1 a don't(), že ne.

Z toho vyplývá, že chceme ignorovat části řetězce uzavřené mezi don't() a do() a mezi don't() a koncem řetězce $

Jediné, co pro to musíme udělat je přesně to, co jsme si řekli v minulém dílu, a tedy normalizovat náš vstup na chtěný vstup, aby zbytek algoritmu zůstal stejný.

Pravděpodobně by šel jen upravit regex, ale to by bylo příliš náročné. Nejdříve si tedy ze vstupního řetězce odstraníme části, které chceme ignorovat:

$normalizedInput = \Nette\Utils\Strings::replace($this->input, '~don\'t\(\).*?((do\(\))|$)~s');

Metoda \Nette\Utils\Strings::replace je vlastně nahrazení podřetězce definovaného regulárním výrazem, nějakým statickým řetězcem. Pokud není replacement specifikován, bere se prázdný řetězec.

Velmi důležité je v daném regexu mít příznak s, který zajistí, že se celý řetězec bude chovat jako single line i když jsou v něm konce řádku. Bez tohoto by řešení nefungovalo.

Celá metoda se tedy rozšíří na 3 řádky:

$normalizedInput = \Nette\Utils\Strings::replace($this->input, '~don\'t\(\).*?((do\(\))|$)~s');
$parsed = \Nette\Utils\Strings::matchAll($normalizedInput, '~mul\((\d{1,3}),(\d{1,3})\)~');
$result = array_reduce($parsed, fn (int $carry, array $item): int => $carry + $item[1] * $item[2], 0);

Spustíme => 57

Bohužel i když jsme počítače opravili, historika se nám najít nepodařilo. Musíme se poohlédnout jinde.

Celý kód je opět zde:

<?php

declare(strict_types=1);

require __DIR__ . '/../vendor/autoload.php';

class Advent3b
{
    private string $input = 'dmulx(1,5)mul(5,3)do(/*5.2
mul(3,5)don\'t()$mef6mul(4,8)@a|€q^mul[4,5)do()(4,7)mul(9,3)';

    public function solve(): void
    {
        $normalizedInput = \Nette\Utils\Strings::replace($this->input, '~don\'t\(\).*?((do\(\))|$)~s');
        $parsed = \Nette\Utils\Strings::matchAll($normalizedInput, '~mul\((\d{1,3}),(\d{1,3})\)~');
        $result = array_reduce($parsed, fn (int $carry, array $item): int => $carry + $item[1] * $item[2], 0);
        bdump($result);
    }
}

// Turn on tracy
$configurator = App\Bootstrap::bootWeb();
(new Advent3b())->solve();

Závěr

V každém díle (snad) si ještě probereme jak dlouho může průměrnému programátorovi trvat takový algoritmus napsat (včetně čtení zadání) a nějaké čísla k němu. Všechny časy běhu jsou uvedené pro můj vstup.

Část 1:

Asymptotická složitost: O(n)

Čas běhu na mém stroji: 0.000142004s

Odhadovaný čas vývoje: 00:02:00

Část 2:

Asymptotická složitost: O(n)

Čas běhu na mém stroji: 0.00017589s

Odhadovaný čas vývoje: 00:02:00

To je pro tento díl vše. Pokud něco nechápeš, tak mi napiš.

Tak užívej a já jdu zatáčet tobogány.