Červenonosé reporty
V minulém díle jsme nalezli možné lokace výskytu hlavního historika. Nyní prozkoumáváme první z nich. Je to fúzní/štěpící továrna sobů rudonosých. Hlavní historik však nikde, zato problémů plno.
Část 1 (odkaz)
Sice jsme zde historika nenašli, ale elfové jsou rádi, že nás vidí, jelikož si sami nejsou schopni poradit s danými reporty. Máme za úkol zjistit, které z daných reportů jsou bezpečné a které nikoliv.
Dostaneme testovací vstup:
8 7 5 3 2
0 1 6 7 8
9 8 6 2 9
5 7 6 8 9
8 5 4 4 1
0 3 6 8 9
Každý řádek označuje jeden level. Tento level je bezpečný právě tehdy když čísla v něm pouze klesají, nebo pouze stoupají a to minimálně o 1 a maximálně o 3.
Otázka zní: "Kolik bezpečných reportů je vygenerováno?"
Abychom to zjistili, musíme si projet všechny řádky, (Split podle řádků provádím vždy stejně, proto jej zde nebudu dále uvádět) a rozdělit si je na jednotlivé reporty.
foreach ($this->grid as $level) {
$level = explode(' ', $level);
// Zde budeme psát zbytek kódu
}
Dále se nechceme zaobírat rostoucí, potažmo klesající posloupností, ale sjednotíme si je vždy na rostoucí. Toto je u programátorů důležité, pokud chtějí psát čitelné kódy. Tedy algoritmus zůstane pro různé případy stejný, jen se normalizují vstupy.
foreach ($this->grid as $level) {
$level = explode(' ', $level);
// posloupnost je rostoucí jen tehdy, je-li první prvek menší, než poslední prvek.
if (reset($level) > end($level)) {
$level = array_reverse($level);
}
// Zde budeme psát zbytek kódu
}
Nakonec musíme ověřit, jestli daná stoupající posloupnost je bezpečná, či nikoliv. Pokud ano, započítáme si ji mezi ostatní bezpečné.
$result = 0;
foreach ($this->grid as $level) {
$level = explode(' ', $level);
if (reset($level) > end($level)) {
$level = array_reverse($level);
}
if ($this->isSafe($level)) {
$result++;
}
}
bdump($result);
Stále ale musíme napsat obsah metody isSafe. Ten je jednoduchý. Jde čistě jen o průchod polem a ověření, zda je
opravdu rozdíl každých dvou po sobě jdoucích prvků je maximálně 3 a minimálně 1.
public function isSafe(array $level): bool
{
for ($i = 0; $i < count($level) - 1; $i++) {
$diff = $level[$i + 1] - $level[$i];
if ($diff < 1 || $diff > 3) {
return false;
}
}
return true;
}
Spustíme => 2
Celý výsledný kód vypadá takto:
<?php
declare(strict_types=1);
require __DIR__ . '/../vendor/autoload.php';
class Advent2a
{
private array $grid;
private string $input = '8 7 5 3 2
0 1 6 7 8
9 8 6 2 9
5 7 6 8 9
8 5 4 4 1
0 3 6 8 9';
public function solve(): void
{
$this->grid = explode("\n", $this->input);
$result = 0;
foreach ($this->grid as $level) {
$level = explode(' ', $level);
if (reset($level) > end($level)) {
$level = array_reverse($level);
}
if ($this->isSafe($level)) {
$result++;
}
}
bdump($result);
}
public function isSafe(array $level): bool
{
for ($i = 0; $i < count($level) - 1; $i++) {
$diff = $level[$i + 1] - $level[$i];
if ($diff < 1 || $diff > 3) {
return false;
}
}
return true;
}
}
// Turn on tracy
$configurator = App\Bootstrap::bootWeb();
(new Advent2a())->solve();
Část 2
Hmm ta čísla jsou nějaká malá. Buď máme špatné reaktory, nebo máme špatný algoritmus. Nová výzva znamená, že v každém ne-bezpečném reportu můžeme tolerovat jeden jediný záznam. Pokud takový tolerovaný záznam udělá z reportu bezpečný report, je nadále brán za bezpečný.
Musíme kód trochu upravit, kdy budeme zkoušet možnosti hrubou silou. Obvykle není hrubá síla na místě, jelikož zjistit výsledek může trvat velice dlouho, kvůli vysoké asymptotické složitosti. Pro naše malé vstupy ale toto nemusíme nutně řešit. budeme se sice snažit o co nejefektivnéjší algoritmus, ale cílem úkolů je odevzdat v co nejkratším čase, ne co nejefektivnější kód a proto je zde možné bruteforce použít.
Vlastně jediné, co se v našem kódu změní, bude to, že přibyde jeden nový cyklus a z tohoto:
foreach ($this->grid as $level) {
$level = explode(' ', $level);
if (reset($level) > end($level)) {
$level = array_reverse($level);
}
if ($this->isSafe($level)) {
$result++;
}
}
Se stane toto:
foreach ($this->grid as $level) {
$originalLevel = explode(' ', $level);
for ($i = 0; $i < count($originalLevel); $i++) {
$level = $originalLevel;
unset($level[$i]);
$level = array_values($level);
if (reset($level) > end($level)) {
$level = array_reverse($level);
}
if ($this->isSafe($level)) {
$result++;
break;
}
}
}
Spustíme => 4
Všichni jsou spokojení, že vše funguje a továrna neexploduje.
Celý kód je opět zde:
<?php
declare(strict_types=1);
require __DIR__ . '/../vendor/autoload.php';
class Advent2b
{
private array $grid;
private string $input = '8 7 5 3 2
0 1 6 7 8
9 8 6 2 9
5 7 6 8 9
8 5 4 4 1
0 3 6 8 9';
public function solve(): void
{
$this->grid = explode("\n", $this->input);
$result = 0;
foreach ($this->grid as $level) {
$originalLevel = explode(' ', $level);
for ($i = 0; $i < count($originalLevel); $i++) {
$level = $originalLevel;
unset($level[$i]);
$level = array_values($level);
if (reset($level) > end($level)) {
$level = array_reverse($level);
}
if ($this->isSafe($level)) {
$result++;
break;
}
}
}
bdump($result);
}
public function isSafe(array $level): bool
{
for ($i = 0; $i < count($level) - 1; $i++) {
$diff = $level[$i + 1] - $level[$i];
if ($diff < 1 || $diff > 3) {
return false;
}
}
return true;
}
}
// Turn on tracy
$configurator = App\Bootstrap::bootWeb();
(new Advent2b())->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.000008209s
Odhadovaný čas vývoje: 00:09:00
Část 2:
Asymptotická složitost: O(n * m**2)
Čas běhu na mém stroji: 0.000011084s
Odhadovaný čas vývoje: 00:03:45
To je pro tento díl vše. Pokud něco nechápeš, tak mi napiš.
Tak užívej a já jdu barvit sobům nosy na červeno.