Today you are looking at a strange metal country with lots of pipes. How did I get there? Oh, with the glider - I had to read it again while writing this post. After quickly sketching the positions of all the pipes, you get this
..F7.
.FJ|.
SJ.L7
|F--J
LJ...
And also have a legend of what each of the symbols mean. For easier understanding, I made a much simpler map that contains only empty ground and starting position.
. . .
. S .
. . .
Lets say starting position is at [0, 0] so the other positions will looks like this
[-1,-1] [-1,0] [-1,1]
[0,-1] [0,0] [0,1]
[1,-1] [1,0] [1,1]
This tells me how the pipes are connected to the each other
'|' => [[0, -1], [0, 1]], // up and down (N/S)
'-' => [[-1, 0], [1, 0]], // left and right (W/E)
'L' => [[-1, 0], [0, 1]], // 90 degree left (N/E)
'J' => [[-1, 0], [0, -1]], // 90 degree right (N/W)
'7' => [[1, 0], [0, -1]], // 90 degree left (S/W)
'F' => [[1, 0], [0, 1]], // 90 degree right (S/E)
'.' => [[0, 0]], // ground (no direction from here)
'S' => [[0, 0]], // starting positifion
And to find the coordinates of my starting position, I used
foreach ($map as $index => $row) {
if (in_array('S', $row)) {
$start = [$index, array_search('S', $row)]; // [2, 0] for test input
}
}
It is at [2,0] so only possible directions are N, S, and E
At this point I still didn’t know what to do with it :D I just knew that I had to find a loop and find how many steps it takes to get to the farthest point from the starting position.
..45.
.236.
01.78
14567
23...
For test input it is 8.
I was able to find the start point and now I had to find the next one. My first attempt was to check all the destinations around my current position. Yes, this worked for the S pipe, but not for the special pipes.
I created another function to get the destination for a pipe type based on its location on the map.
$getPipe = function($x, $y) use ($map, $pipes): array {
$pipe = $map[$x][$y];
if (!isset($pipes[$pipe]) || $pipe == 'S') {
return $pipes;
}
return [$pipes[$pipe]];
};
But not all the pipes around my current position are connected to it. When I find a possible next position, I check if it is connected back by looking at the shape of the pipe at that position and where it can connect.
$areConnected = function (array $start, array $destination) use ($map, $pipes): bool {
[$x,$y] = $start;
[$dx, $dy] = $destination;
$pipe = $map[$dx][$dy];
// connected to each pipe when tere is connection from it
if ($pipe == 'S') {
return true;
}
foreach($pipes[$pipe] as $direction) {
[$px, $py] = $direction;
[$px, $py] = [$dx + $px, $dy + $py];
if ($px == $x && $py == $y) {
return true;
}
}
return false;
};
I have tested this function manually and I get the following responses. They looked fine to me.
2 Possible connections for [2,0] S
Possible connection 0: 3 0 |
Possible connection 1: 2 1 J
. . .
2 Possible connections for [1,3] |
Possible connection 0: 0 3 7
Possible connection 1: 2 3 L
2 Possible connections for [2,3] L
Possible connection 0: 1 3 |
Possible connection 1: 2 4 7
2 Possible connections for [2,4] 7
Possible connection 0: 3 4 J
Possible connection 1: 2 3 L
2 Possible connections for [3,4] J
Possible connection 0: 2 4 7
Possible connection 1: 3 3 -
2 Possible connections for [3,3] -
Possible connection 0: 3 2 -
Possible connection 1: 3 4 J
2 Possible connections for [3,1] F
Possible connection 0: 4 1 J
Possible connection 1: 3 2 -
2 Possible connections for [4,1] J
Possible connection 0: 3 1 F
Possible connection 1: 4 0 L
2 Possible connections for [4,0] L
Possible connection 0: 3 0 |
Possible connection 1: 4 1 J
2 Possible connections for [3,0] |
Possible connection 0: 2 0 S
Possible connection 1: 4 0 L
So it was time to put it all together.
function findNext($x, $y, $map, $pipes, $next): array
{
$areConnected = function (array $start, array $destination) use ($map, $pipes): bool {
[$x,$y] = $start;
[$dx, $dy] = $destination;
$pipe = $map[$dx][$dy];
// / connected to each pipe when tere is connection from it
if ($pipe == 'S') {
return true;
}
foreach($pipes[$pipe] as $direction) {
[$px, $py] = $direction;
[$px, $py] = [$dx + $px, $dy + $py];
if ($px == $x && $py == $y) {
return true;
}
}
return false;
};
$getPipe = function($x, $y) use ($map, $pipes): array {
$pipe = $map[$x][$y];
if (!isset($pipes[$pipe]) || $pipe == 'S') {
return $pipes;
}
return [$pipes[$pipe]];
};
foreach ($getPipe($x,$y) as $index => $pipe)
{
foreach ($pipe as $dIndex => $direction) {
[$dx, $dy] = $direction;
[$dx, $dy] = [$x + $dx, $y + $dy];
// this is the same location
if ($x == $dx && $y == $dy) {
continue;
}
// skip if location not exists
if (!isset($map[$dx][$dy])) {
continue;
}
// skip if ground
if ($map[$dx][$dy] == '.') {
continue;
}
// check if both points are connected
if (!$areConnected([$x, $y], [$dx, $dy])) {
continue;
}
$possibleNext = [
$dx,
$dy,
];
if (array_search($possibleNext, $next) !== false) {
continue;
} else {
$next[] = $possibleNext;
$possibleNext = [];
}
}
}
return $next;
}
Now I finally had a working function which returns me each location to which pipe is connected. Every time there are 2, only exception is start pipe as I mentioned above.
I still had one piece missing. How to count the farthest path. For this I created another array where I put every possible next location that my function returns. (possibleNext locations are pipes that are connected to my current location)
In the next step I compared these (from findNext function) against this connections array and removed location if it was checked before (is already in connections).
When hasNext was zero, I knew that I had checked every connected location in the loop.
while($hasNext) {
foreach($next as $index => $possibleNext) {
[$x, $y] = [$possibleNext[0], $possibleNext[1]];
echo 'Checking [' . $x . ',' . $y . ']' . PHP_EOL;
$next = findNext($x, $y, $map, $pipes, $next);
foreach($next as $nIndex => $nValue) {
if (array_search([$nValue[0], $nValue[1]], $connections) !== false) {
unset($next[$nIndex]);
} else {
$connections[] = [$nValue[0], $nValue[1]];
}
}
$hasNext = count($next) > 0;
}
}
Next I just counted how many entires I had in the connections array and divided by 2 to get the furthest point.
🥳 Tada! Wow, that was hard. Only part 1 for me today, but I’m really glad I did it.
As before my code is available on my GitHub
Reply by Email