advent_of_code_2021/day_12/part_2.php

45 lines
1.2 KiB
PHP
Raw Permalink Normal View History

2021-12-13 11:14:13 +01:00
<?php
$paths = explode("\n", file_get_contents('./input.txt'));
$possible_paths = [];
foreach ($paths as $path) {
[$start, $end] = explode('-', $path);
if ($start !== 'end' && $end !== 'start') {
if (array_key_exists($start, $possible_paths)) {
$possible_paths[$start][] = $end;
} else {
$possible_paths[$start] = [$end];
}
}
if ($start !== 'start' && $end !== 'end') {
if (array_key_exists($end, $possible_paths)) {
$possible_paths[$end][] = $start;
} else {
$possible_paths[$end] = [$start];
}
}
}
echo track($possible_paths, 'start', [], false);
function track($possible_paths, $cave, $history, $went_once) {
$count = 0;
$history[] = $cave;
foreach ($possible_paths[$cave] as $path) {
if ($path === 'end') {
$count++;
} elseif(ctype_lower($path) && in_array($path,$history)) {
if ($went_once === false) {
$count += track($possible_paths, $path, $history, true);
}
} else {
$count += track($possible_paths, $path, $history, $went_once);
}
}
return $count;
}