Today’s quest is called Haunted Wasteland. You are riding a camel across a desert island. You find a map in one of the camel’s bags. The map contains instructions on how to navigate through the desert and a bunch of knots. It looks like this
RL
AAA = (BBB, CCC)
BBB = (DDD, EEE)
CCC = (ZZZ, GGG)
DDD = (DDD, DDD)
EEE = (EEE, EEE)
GGG = (GGG, GGG)
ZZZ = (ZZZ, ZZZ)
You start at node AAA and need to get to node ZZZZ. And you need to know how many steps it takes to get to node ZZZ.
Part 1#
Parsing map into arrays was easy
$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);
at the end I had map
[
point => AAA,
L => XXX,
R =? BBB,
]
And now all I had to do was go through all the instructions and see if I needed to go left or right.
while ($currentPoint != 'ZZZ') {
$currentPoint = move($currentPoint, $map, $leftRight[$i]);
$i++;
if ($i >= strlen($leftRight) ) {
$i = 0;
}
$steps++;
}
The map guide says that if you go to the end of the instructions on which side to choose, you have to repeat them from start to finish. To ensure this, I simply reset the counter when I reach the end of the instructions.
if ($i >= strlen($leftRight) ) {
$i = 0;
}
To find next point I using array_search
function move($startpoint, $map, $leftRight)
{
$point = array_search($startpoint, array_column($map, 'point'));
return $map[$point][$leftRight];
}
This one was relatively easy part. Alt least easier than day 3 and I’m happy with my solution.
Part 2#
This one was (as always) more difficult than the first. Now you have to follow several paths. Start nodes are any node whose last character is A and similarly the destination nodes have last character Z. The start and end nodes are the same number. The legend says that maybe the maps weren’t made for humans, but for ghosts. Scary 👻
Version One#
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';
})));
To go through the nodes I use a while loop similar to the one in part 1, but added another cycle to go through each node (from above) that I need to follow.
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 ++;
}
I also updated the move function to return the whole point (node) instead of just the node name.
function move($to, $map)
{
$point = array_search($to, array_column($map, 'point'));
return $map[$point];
}
To check if I’m at destination I check how many nodes (in nodes that I’m on) have last letter Z. From description I know they are same number as nodes with letter A. So in end I must have same number of both A and 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;
}
And that was it. This solution does not work with large amounts of data. (After a few minutes and many steps, I still haven’t reached the end).
Version Two#
My next thought was to use trees and the breadth-first search algorithm to find paths from start to finish. So I built a tree structure as follows
$tree = [];
foreach ($map as $value) {
$tree[$value['point']] = [
'L' => $value['L'],
'R' => $value['R'],
];
}
Next, I found all the nodes from which I start and also the destination nodes.
$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'; });
List all paths and count their steps with code
$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";
}
}
}
Gives me the following value
(first of each path is start node co steps per path are count of elements -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
I wasn’t very good at maths, but I asked the AI how to calculate when all paths end at the same point. And it recommended using the LCM method. This works for the test input and with a time break for the personalised input, but the LCM does not seem to be the answer for this.
I think the problem with my solution is that I don’t take into account which node all the nodes are on the same number of steps. Whether they all have last letter Z or not. I just find the first place where the nodes are on the same length and that’s it.
Probably my v1 code from above will reach correct number but I will need much more faster computer or much more time to figure it out. OR just another solution.