🎄 Advent of Code 08일차

Table of Contents

오늘의 퀘스트는 유령의 황무지입니다. 낙타를 타고 무인도를 가로지르고 있습니다. 낙타의 가방에서 지도를 발견했습니다. 지도에는 사막을 통과하는 방법에 대한 지침과 매듭이 여러 개 있습니다. 지도는 다음과 같이 보입니다.

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.

Reply by Email

파트 1#

파트 2#

버전 1#

버전 2#

파트 1
#

파트 2
#

버전 1
#

버전 2
#