A jdeme hledat Vánoce
V minulém díle jsme rozběhali skladiště, takže dárky se už opět balí správným dětem. Kde to ale nyní vězíme?
Část 1 (odkaz)
Během pokračování pátrání po šéfíkovi nás najednou malý elf tahá za tričko. "Halo halo, potřebuju pomoct. Mám tady křížovku. Pomůžeš mi?"
Zadal nám na první (i druhý) pohled triviální úkol. Na papíře před námi leží spousta písmen ve čtvercové matici. Úkol je prostý. Najdi všechny výskyty slova "XMAS" a to ve všech směrech a zapsat máme počet, kolik výskytů jsme nalezli.
SASAAAMSMS
XAXSSXMMAS
MSSSMSXAAX
SMXAASMXSX
AASXMMMAAX
SSXMXSASMX
SMMAAXXSMX
MMSSXMMMMS
ASXSMXXXSX
AAMMSSASAA
Zde pro řešení využijeme volání obecné funkce, které budeme předávat různé argumenty, díky čemuž zajistíme, že bude vyhledávat ve všech směrech.
Prvně si tedy nadefinujeme tuto funkci:
public function findXmas(int $x, int $y, int $dirX, int $dirY): bool
{
return
($this->grid[$y + $dirY * 0][$x + $dirX * 0] ?? null) === 'X'
&& ($this->grid[$y + $dirY * 1][$x + $dirX * 1] ?? null) === 'M'
&& ($this->grid[$y + $dirY * 2][$x + $dirX * 2] ?? null) === 'A'
&& ($this->grid[$y + $dirY * 3][$x + $dirX * 3] ?? null) === 'S';
}
Násobení nulou a jedničkou v tomto případě je zbytečné. Já je tam ale rád dávám pro přehlednost, aby bylo vidět, že jde o ten stejný vzorec ve všech řádcích. Dobrá vlastnot PHP a jeho JIT je, že tyto drobné věci, které mají dopředu známý výsledek při překladu ignoruje, tedy k násobení nedochází. Když si tedy spustíme kód bez těchto zbytečných věcí, tak poběží stejně dlouho, jako s nimi.
Abychom mohli tuto funkci volat, je třeba si nejprve vstup rozsekat na matici znaků:
$this->grid = explode("\n", $this->input);
foreach ($this->grid as &$val) {
$val = str_split($val);
}
A nakonec si prostě celou matici projedeme a pro každý prvek ověříme, jestli z něj některým směrem toto záhadné slovo XMAS netrčí.
$finded = 0;
for ($x = 0; $x < count(reset($this->grid)); $x++) {
for ($y = 0; $y < count($this->grid); $y++) {
// Chceme ověřovat jen prvky s hodnotou X, protože naše slovo na X začíná
if ($this->grid[$y][$x] !== 'X') {
continue;
}
$finded += $this->findXmas($x, $y, +1, +1);
$finded += $this->findXmas($x, $y, +1, -1);
$finded += $this->findXmas($x, $y, -1, +1);
$finded += $this->findXmas($x, $y, -1, -1);
$finded += $this->findXmas($x, $y, +0, +1);
$finded += $this->findXmas($x, $y, +0, -1);
$finded += $this->findXmas($x, $y, +1, +0);
$finded += $this->findXmas($x, $y, -1, +0);
}
}
Vidíme, že děláme plus nad návratovou hodnotou naší metody findXmas. Jenže tato metoda vrací bool. Výhoda PHP je,
že v tomto případě implicitně přetypuje true na 1 a false na 0, což nám zjednoduší kód.
Spustíme => 2
Celý výsledný kód vypadá takto:
<?php
declare(strict_types=1);
require __DIR__ . '/../vendor/autoload.php';
class Advent4a
{
private array $grid;
private string $input = 'SASAAAMSMS
XAXSSXMMAS
MSSSMSXAAX
SMXAASMXSX
AASXMMMAAX
SSXMXSASMX
SMMAAXXSMX
MMSSXMMMMS
ASXSMXXXSX
AAMMSSASAA';
public function solve(): void
{
$this->grid = explode("\n", $this->input);
foreach ($this->grid as &$val) {
$val = str_split($val);
}
$finded = 0;
for ($x = 0; $x < count(reset($this->grid)); $x++) {
for ($y = 0; $y < count($this->grid); $y++) {
if ($this->grid[$y][$x] !== 'X') {
continue;
}
$finded += $this->findXmas($x, $y, +1, +1);
$finded += $this->findXmas($x, $y, +1, -1);
$finded += $this->findXmas($x, $y, -1, +1);
$finded += $this->findXmas($x, $y, -1, -1);
$finded += $this->findXmas($x, $y, +0, +1);
$finded += $this->findXmas($x, $y, +0, -1);
$finded += $this->findXmas($x, $y, +1, +0);
$finded += $this->findXmas($x, $y, -1, +0);
}
}
bdump($finded);
}
public function findXmas(int $x, int $y, int $dirX, int $dirY): bool
{
return
($this->grid[$y + $dirY * 0][$x + $dirX * 0] ?? null) === 'X'
&& ($this->grid[$y + $dirY * 1][$x + $dirX * 1] ?? null) === 'M'
&& ($this->grid[$y + $dirY * 2][$x + $dirX * 2] ?? null) === 'A'
&& ($this->grid[$y + $dirY * 3][$x + $dirX * 3] ?? null) === 'S';
}
}
// Turn on tracy
$configurator = App\Bootstrap::bootWeb();
(new Advent4a())->solve();
Část 2
Odevzdali jsme výsledek elfovi. Ten se ale plácl do čela. Nepochopili jsme totiž zadání.
Nemáme hledat slovo XMAS, ale X-MAS... Tedy slovo MAS zapsané do tvaru písmene X.
Všechny kombinace vypadají takto:
M.M
.A.
S.S
S.S
.A.
M.M
M.S
.A.
M.S
S.M
.A.
S.M
Zvláštní je, že ačkoliv doposud nám stačilo kód z první části vždy jen rozšířit, nyní jej musíme celý přepsat, jelikož jej již potřebovat nebudeme. Přístup řešení druhé části je diametrálně odlišný, avšak velmi krátký.
Zapíši jej tedy najednou:
$finded = 0;
$allowedCombinations = ['MS' => true, 'SM' => true];
for ($x = 1; $x < count(reset($this->grid)) - 1; $x++) {
for ($y = 1; $y < count($this->grid) - 1; $y++) {
if (
$this->grid[$y][$x] !== 'A'
|| !isset($allowedCombinations[$this->grid[$y - 1][$x - 1] . $this->grid[$y + 1][$x + 1]])
|| !isset($allowedCombinations[$this->grid[$y + 1][$x - 1] . $this->grid[$y - 1][$x + 1]])
) {
continue;
}
$finded++;
}
}
bdump($finded);
Nejprve jsme si připravili pole $allowedCombinations obsahující jako klíče řetězce 'SM' a 'MS'. Jde o to, že toto
vytvoří hash table. Pro tento příklad je to zbytečné, ale je dobré vědět, že to takto funguje a přístup pomocí
funkce isset je pak konstantní.
Jak poté vidíme v podmínce, vyžadujeme aby uprostřed byl znak 'A'. Pokud je, tak vyžadujeme, aby na každé diagonále
byly protilehlé znaky 'M' a 'S' a to vždy v kombinaci 'MS', nebo 'SM'. Tím zajistíme, že pokud nebude podmínka
pro continue splněna, našli jsme daný vzor.
Spustíme => 1
Celý kód je opět zde:
<?php
declare(strict_types=1);
require __DIR__ . '/../vendor/autoload.php';
class Advent4b
{
private array $grid;
private string $input = 'SASAAAMSMS
XAXSSXMMAS
MSSSMSXAAX
SMXAASMXSX
AASXMMMAAX
SSXMXSASMX
SMMAAXXSMX
MMSSXMMMMS
ASXSMXXXSX
AAMMSSASAA';
public function solve(): void
{
$this->grid = explode("\n", $this->input);
foreach ($this->grid as &$val) {
$val = str_split($val);
}
$finded = 0;
$allowedCombinations = ['MS' => true, 'SM' => true];
for ($x = 1; $x < count(reset($this->grid)) - 1; $x++) {
for ($y = 1; $y < count($this->grid) - 1; $y++) {
if (
$this->grid[$y][$x] !== 'A'
|| !isset($allowedCombinations[$this->grid[$y - 1][$x - 1] . $this->grid[$y + 1][$x + 1]])
|| !isset($allowedCombinations[$this->grid[$y + 1][$x - 1] . $this->grid[$y - 1][$x + 1]])
) {
continue;
}
$finded++;
}
}
bdump($finded);
}
}
// Turn on tracy
$configurator = App\Bootstrap::bootWeb();
(new Advent4b())->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.003775182s
Odhadovaný čas vývoje: 00:19:45
Část 2:
Asymptotická složitost: O(n)
Čas běhu na mém stroji: 0.001893727s
Odhadovaný čas vývoje: 00:07:45
To je pro tento díl vše. Pokud něco nechápeš, tak mi napiš.
Tak užívej a já jdu astrologům leštit čočky.