45 lines
1.2 KiB
PHP
45 lines
1.2 KiB
PHP
|
<?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;
|
||
|
|
}
|