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.