4 회의록 | 에도 사용 가능 English
🎄 Advent of Code 08일차
오늘의 퀘스트는 유령의 황무지입니다. 낙타를 타고 무인도를 가로지르고 있습니다. 낙타의 가방에서 지도를 발견했습니다. 지도에는 사막을 통과하는 방법에 대한 지침과 매듭이 여러 개 있습니다. 지도는 다음과 같이 보입니다.
RL
AAA = (BBB, CCC)
BBB = (DDD, EEE)
CCC = (ZZZ, GGG)
DDD = (DDD, DDD)
EEE = (EEE, EEE)
GGG = (GGG, GGG)
ZZZ = (ZZZ, ZZZ)
노드 AAA
에서 시작하여 노드 ZZZZ
에 도달해야 합니다. 그리고 노드 ZZZ
에 도달하는 데 몇 단계가 필요한지 알아야 합니다.
파트 1
맵을 배열로 구문 분석하는 것은 쉬웠습니다.
$map = array_slice($map, 1);
$map = array_map(function ($value) {
[$point, $lr] = explode(' = ', str_replace(['(', ')'], '', str_replace(['(', ')'], '', $value)));
[$L, $R] = explode(', ', $lr);
return compact('point', 'L', 'R');
}, $map);
결국 지도를 가지고 있었어
[
point => AAA,
L => XXX,
R =? BBB,
]
이제 내가 해야 할 일은 모든 지침을 살펴보고 왼쪽으로 가야 하는지 오른쪽으로 가야 하는지 확인하는 것뿐이었습니다.
while ($currentPoint != 'ZZZ') {
$currentPoint = move($currentPoint, $map, $leftRight[$i]);
$i++;
if ($i >= strlen($leftRight) ) {
$i = 0;
}
$steps++;
}
지도 가이드에는 어느 쪽을 선택해야 하는지 안내가 끝까지 가면 처음부터 끝까지 반복해야 한다고 나와 있습니다. 이를 보장하기 위해 지침이 끝나면 카운터를 재설정하기만 하면 됩니다.
if ($i >= strlen($leftRight) ) {
$i = 0;
}
다음 지점을 찾으려면 array_search
를 사용합니다.
function move($startpoint, $map, $leftRight)
{
$point = array_search($startpoint, array_column($map, 'point'));
return $map[$point][$leftRight];
}
이 부분은 비교적 쉬운 부분이었습니다. 적어도 3일차보다는 쉬웠고 솔루션에 만족합니다.
파트 2
이것은 (항상 그렇듯) 첫 번째 것보다 더 어려웠습니다. 이제 여러 경로를 따라야 합니다. 시작 노드는 마지막 문자가 A
인 노드이고 마찬가지로 대상 노드의 마지막 문자는 Z
입니다. 시작 노드와 끝 노드의 번호는 같습니다. 전설에 따르면 지도는 인간을 위해 만들어진 것이 아니라 유령을 위해 만들어진 것일 수도 있습니다. 무섭다 👻
버전 1
To find all start nodes I used following function
$startPoints = array_values(array_map(function ($value) {
return $value;
}, array_filter($map, function ($value) {
return substr($value['point'], -1) == 'A';
})));
노드를 통과하기 위해 파트 1에서와 유사한 while
루프를 사용하지만, 따라야 하는 각 노드(위에서부터)를 통과하기 위해 다른 사이클을 추가했습니다.
while(!isEverythingAtEnd($currentPoints, $startPointsCount)) {
foreach ($currentPoints as &$point) {
$point = move($point[$leftRight[$i]], $map);
array_values($currentPoints);
}
$i++;
if ($i >= strlen($leftRight) ) {
$i = 0;
}
$steps ++;
}
또한 노드 이름만 반환하는 것이 아니라 전체 지점(노드)을 반환하도록 move
함수를 업데이트했습니다.
function move($to, $map)
{
$point = array_search($to, array_column($map, 'point'));
return $map[$point];
}
목적지에 도착했는지 확인하기 위해 (내가 있는 노드에서) 마지막 글자가 Z인 노드가 몇 개 있는지 확인합니다. 설명에서 A
가 있는 노드와 같은 수라는 것을 알 수 있습니다. 따라서 결국 A
와 Z
가 모두 같은 수여야 합니다.
function isEverythingAtEnd($currentPoints, $startPointsCount) {
$atTheEnd = array_filter($currentPoints, function ($value) {
return substr($value['point'], -1) == 'Z';
});
if (count($atTheEnd) == $startPointsCount) {
return true;
}
return false;
}
그게 다입니다. 이 솔루션은 많은 양의 데이터에서는 작동하지 않습니다. (몇 분 동안 여러 단계를 거쳐도 아직 끝까지 도달하지 못했습니다).
버전 2
다음으로 생각한 것은 트리와 넓이 우선 검색 알고리즘을 사용하여 처음부터 끝까지 경로를 찾는 것이었습니다. 그래서 다음과 같이 트리 구조를 만들었습니다.
$tree = [];
foreach ($map as $value) {
$tree[$value['point']] = [
'L' => $value['L'],
'R' => $value['R'],
];
}
다음으로, 시작 노드와 목적지 노드를 모두 찾았습니다.
$startNodes = array_filter(array_keys($tree), function($node) { return substr($node, -1) == 'A'; });
$endNodes = array_filter(array_keys($tree), function($node) { return substr($node, -1) == 'Z'; });
모든 경로를 나열하고 코드로 걸음 수를 계산하세요.
$pathSizes = [];
foreach ($startNodes as $start) {
foreach ($endNodes as $end) {
$path = bfs($start, $end, $tree);
if ($path !== null) {
$pathSizes[] = count($path) - 1;
echo "Path from $start to $end: " . implode(' -> ', $path) . "\n";
}
}
}
다음과 같은 값을 반환합니다.
(각 경로의 첫 번째는 시작 노드 경로당 공동 단계는 요소 수 -1
)
Path from 11A to 11Z: 11A -> 11B -> 11Z
Path from 22A to 22Z: 22A -> 22B -> 22C -> 22Z
Steps per path: [2, 3]
LCM: 6
저는 수학에 능숙하지 않지만 모든 경로가 같은 지점에서 끝나는 시점을 계산하는 방법을 AI에게 물어봤습니다. 그러자 LCM 방법을 사용할 것을 추천했습니다. 이 방법은 테스트 입력과 개인화된 입력에 대해 시간 간격을 두고 작동하지만, LCM은 이에 대한 해답이 아닌 것 같습니다.
내 솔루션의 문제점은 모든 노드가 동일한 수의 단계에 있는 노드를 고려하지 않는다는 것입니다. 모든 노드의 마지막 글자가 Z
인지 여부는 고려하지 않습니다. 나는 단지 노드가 같은 길이에있는 첫 번째 장소를 찾고 그게 다입니다.
아마도 위의 v1 코드는 정확한 숫자에 도달 할 수 있지만 훨씬 더 빠른 컴퓨터 나 훨씬 더 많은 시간이 필요할 것입니다. 또는 다른 해결책.
내 소스 코드는 다음에서 사용할 수 있습니다. GitHub.