Kancelář hlavního elfího historika
V KAŽDÉM dni budeme mít za úkol vyřešit dvě hádanky. Tyto na sebe navazují, tedy je nutné nejdříve vyřešit první a až poté dostaneme zadání druhé, přičemž vstupní data jsou pro obě části totožné. Já používám pro usnadnění řešení taktéž Nette knihovny, které mi poskytují příjemnější dumpy proměnných a některé další funkce.
Část 1 (odkaz)
V prvním úkolu AoC nám elfové donesli seznam historicky významných míst. Tito elfové byli rozděleni do 2 skupin, a každá skupina přinesla odlišný seznam. První skupina přinesla seznam v levém sloupci a druhá ve sloupci pravém.
7 3
3 7
4 6
9 5
1 4
2 8
6 3
Tyto seznamy se však hodně liší. My musíme pomoci historikům jejich seznamy sladit.
Možná jsou tyto seznamy mimo jen trochu. Abychom to zjistili, musíme spárovat nejmenší číslo v levém seznamu s nejmenším číslem v pravém seznamu. Potom druhé s druhým atd.
Jakmile budeme mít spárováno, musíme zjistit, jak daleko od sebe místa jsou. Vezeme tedy vzdálenost těchto míst od sebe a všechny tyto vzdálenosti sečteme.
Výsledek poté zadáme do vstupního pole.
V AoC je skvělé, že vstupy jsou vždy přesně formátované a tedy se nemusíme zabývat validací vstupu, ale můžeme se soustředit jen na samotné řešení, díky čemuž si můžeme vstup jednoduše rozparsovat.
protected function solve(): void
{
// Parsování vstupu na řádky toto bude ve většině úkolů stejné
// grid a input jsou pomocné proměnné, do kterých ukládám vstup a rozparsovaný vstup.
$this->grid = explode("\n", $this->input);
// Připravím si 2 seznamy, jeden pro každou skupinu.
$list1 = [];
$list2 = [];
// Naplním seznamy daty ze vstupu
foreach ($this->grid as $val) {
[
$list1[],
$list2[],
] = explode(' ', $val);
}
}
Nyní, když máme vstup rozparsován, můžeme si seznamy seřadit:
sort($list1);
sort($list2);
A nakonec musíme vybrat všechny prvky seshora obou seznamů a sečíst jejich rozdíly:
$result = 0;
for ($i = 0; $i < count($list1); $i++) {
$result += abs($list1[$i] - $list2[$i]);
}
// Toto je dump z Nette/Tracy, který mi vypíše výsledek
bdump($result);
Spustíme a vidíme, že výsledné číslo je 6, což je správný výsledek.
Celý výsledný kód vypadá tatko:
<?php
declare(strict_types=1);
require __DIR__ . '/../vendor/autoload.php';
class Advent1a
{
private array $grid;
private string $input = '7 3
3 7
4 6
9 5
1 4
2 8
6 3';
public function solve(): void
{
$this->grid = explode("\n", $this->input);
$list1 = [];
$list2 = [];
foreach ($this->grid as $val) {
[
$list1[],
$list2[],
] = explode(' ', $val);
}
sort($list1);
sort($list2);
$result = 0;
for ($i = 0; $i < count($list1); $i++) {
$result += abs((int) $list1[$i] - (int) $list2[$i]);
}
bdump($result);
}
}
// Turn on tracy
$configurator = App\Bootstrap::bootWeb();
(new Advent1a())->solve();
Část 2
Ale nééé. Naše výpočty odhalili chybu. Respektive, seznamy jsou hodně jiné. Mozná.
Historici se hádají, kdo udělal chybu. My jsme ti, kdo to musí rozlousknout.
Myslíme si, že seznamy jsou podobné, jen úplně nesedí pořadí. Jak jinak.
Zkusíme tedy vzít číslo z prvního seznamu, podívat se, kolikrát se objeví v druhém seznamu a hodnotu čísla vynásobit počtem výskytů. Tyto výsledky nakonec musíme sečíst. Celkem jednoduchý úkol. nejdříve si ale musíme trošku pozměnit naše řazení seznamů. Nově totiž nebudeme řadit vůbec.
Jediné, co nám stačí je, že si $list2 pomocí nativní PHP funkce
array_count_values shlukneme podle hodnot a
necháme si vypočítat počet výskytů. Výsledné pole pak bude vypadat tak, že jako klíč bude vždy původní hodnota a
jako hodnota bude informace, kolikrát se tato hodnota v původním poli vyskytovala. Výsledek je hashovací tabulka,
která má konstantní přístup.
$list2 = array_count_values($list2);
Díky tomu nyní můžeme proiterovat skrze položky v $list1 a vyhledat je rychle v hash table $list2 a následně
vypočítat výsledek. jelikož výsledek má být jedno konkrétní číslo, můžeme v PHP využít tzv. redukci pole na hodnotu.
Toto se v PHP dá jednoduše udělat pomocí nativní funkce
array_reduce:
$result = array_reduce(
$list1,
fn(int $carry, string $item): int => $carry + $item * ($list2[$item] ?? 0),
0,
);
Pro testovací vstup nám vyjde správně 23.
Výsledek zadáme do inputu a máme první den hotov.
Celý kód je opět zde:
<?php
declare(strict_types=1);
require __DIR__ . '/../vendor/autoload.php';
class Advent1b
{
private array $grid;
private string $input = '7 3
3 7
4 6
9 5
1 4
2 8
6 3';
public function solve(): void
{
$this->grid = explode("\n", $this->input);
$list1 = [];
$list2 = [];
foreach ($this->grid as $val) {
[
$list1[],
$list2[],
] = explode(' ', $val);
}
$list2 = array_count_values($list2);
$result = array_reduce(
$list1,
fn(int $carry, string $item): int => $carry + $item * ($list2[$item] ?? 0),
0,
);
bdump($result);
}
}
// Turn on tracy
$configurator = App\Bootstrap::bootWeb();
(new Advent1b())->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 * log(n))
Čas běhu na mém stroji: 0.001832627s
Odhadovaný čas vývoje: 00:04:30
Část 2:
Asymptotická složitost: O(n)
Čas běhu na mém stroji: 0.002218615s
Odhadovaný čas vývoje: 00:01:00
To je pro tento díl vše. Pokud něco nechápeš, tak mi napiš.
Tak užívej a já jdu historikům radit, jak se dělají seznamy.