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
1..F7.
2.FJ|.
3SJ.L7
4|F--J
5LJ...
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.
1. . .
2. S .
3. . .
Lets say starting position is at [0, 0] so the other positions will looks like this
1[-1,-1] [-1,0] [-1,1]
2[0,-1] [0,0] [0,1]
3[1,-1] [1,0] [1,1]
This tells me how the pipes are connected to the each other
1'|' => [[0, -1], [0, 1]], // up and down (N/S)
2'-' => [[-1, 0], [1, 0]], // left and right (W/E)
3'L' => [[-1, 0], [0, 1]], // 90 degree left (N/E)
4'J' => [[-1, 0], [0, -1]], // 90 degree right (N/W)
5'7' => [[1, 0], [0, -1]], // 90 degree left (S/W)
6'F' => [[1, 0], [0, 1]], // 90 degree right (S/E)
7'.' => [[0, 0]], // ground (no direction from here)
8'S' => [[0, 0]], // starting positifion
And to find the coordinates of my starting position, I used
1foreach ($map as $index => $row) {
2 if (in_array('S', $row)) {
3 $start = [$index, array_search('S', $row)]; // [2, 0] for test input
4 }
5}
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.
1..45.
2.236.
301.78
414567
523...
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.
1$getPipe = function($x, $y) use ($map, $pipes): array {
2 $pipe = $map[$x][$y];
3 if (!isset($pipes[$pipe]) || $pipe == 'S') {
4 return $pipes;
5 }
6
7 return [$pipes[$pipe]];
8};
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.
1$areConnected = function (array $start, array $destination) use ($map, $pipes): bool {
2 [$x,$y] = $start;
3 [$dx, $dy] = $destination;
4 $pipe = $map[$dx][$dy];
5
6 // connected to each pipe when tere is connection from it
7 if ($pipe == 'S') {
8 return true;
9 }
10
11 foreach($pipes[$pipe] as $direction) {
12 [$px, $py] = $direction;
13 [$px, $py] = [$dx + $px, $dy + $py];
14
15 if ($px == $x && $py == $y) {
16 return true;
17 }
18 }
19 return false;
20};
I have tested this function manually and I get the following responses. They looked fine to me.
12 Possible connections for [2,0] S
2Possible connection 0: 3 0 |
3Possible connection 1: 2 1 J
4
5. . .
6
72 Possible connections for [1,3] |
8Possible connection 0: 0 3 7
9Possible connection 1: 2 3 L
10
112 Possible connections for [2,3] L
12Possible connection 0: 1 3 |
13Possible connection 1: 2 4 7
14
152 Possible connections for [2,4] 7
16Possible connection 0: 3 4 J
17Possible connection 1: 2 3 L
18
192 Possible connections for [3,4] J
20Possible connection 0: 2 4 7
21Possible connection 1: 3 3 -
22
232 Possible connections for [3,3] -
24Possible connection 0: 3 2 -
25Possible connection 1: 3 4 J
26
272 Possible connections for [3,1] F
28Possible connection 0: 4 1 J
29Possible connection 1: 3 2 -
30
312 Possible connections for [4,1] J
32Possible connection 0: 3 1 F
33Possible connection 1: 4 0 L
34
352 Possible connections for [4,0] L
36Possible connection 0: 3 0 |
37Possible connection 1: 4 1 J
38
392 Possible connections for [3,0] |
40Possible connection 0: 2 0 S
41Possible connection 1: 4 0 L
So it was time to put it all together.
1function findNext($x, $y, $map, $pipes, $next): array
2{
3
4 $areConnected = function (array $start, array $destination) use ($map, $pipes): bool {
5 [$x,$y] = $start;
6 [$dx, $dy] = $destination;
7 $pipe = $map[$dx][$dy];
8
9 // / connected to each pipe when tere is connection from it
10 if ($pipe == 'S') {
11 return true;
12 }
13
14 foreach($pipes[$pipe] as $direction) {
15 [$px, $py] = $direction;
16 [$px, $py] = [$dx + $px, $dy + $py];
17
18 if ($px == $x && $py == $y) {
19 return true;
20 }
21 }
22
23 return false;
24
25 };
26
27 $getPipe = function($x, $y) use ($map, $pipes): array {
28 $pipe = $map[$x][$y];
29
30 if (!isset($pipes[$pipe]) || $pipe == 'S') {
31 return $pipes;
32 }
33
34 return [$pipes[$pipe]];
35 };
36
37 foreach ($getPipe($x,$y) as $index => $pipe)
38 {
39 foreach ($pipe as $dIndex => $direction) {
40 [$dx, $dy] = $direction;
41 [$dx, $dy] = [$x + $dx, $y + $dy];
42
43 // this is the same location
44 if ($x == $dx && $y == $dy) {
45 continue;
46 }
47
48 // skip if location not exists
49 if (!isset($map[$dx][$dy])) {
50 continue;
51 }
52
53 // skip if ground
54 if ($map[$dx][$dy] == '.') {
55 continue;
56 }
57
58 // check if both points are connected
59 if (!$areConnected([$x, $y], [$dx, $dy])) {
60 continue;
61 }
62
63 $possibleNext = [
64 $dx,
65 $dy,
66 ];
67
68 if (array_search($possibleNext, $next) !== false) {
69 continue;
70 } else {
71 $next[] = $possibleNext;
72 $possibleNext = [];
73 }
74 }
75 }
76
77 return $next;
78}
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.
1while($hasNext) {
2 foreach($next as $index => $possibleNext) {
3 [$x, $y] = [$possibleNext[0], $possibleNext[1]];
4 echo 'Checking [' . $x . ',' . $y . ']' . PHP_EOL;
5 $next = findNext($x, $y, $map, $pipes, $next);
6
7 foreach($next as $nIndex => $nValue) {
8 if (array_search([$nValue[0], $nValue[1]], $connections) !== false) {
9 unset($next[$nIndex]);
10 } else {
11 $connections[] = [$nValue[0], $nValue[1]];
12 }
13 }
14
15 $hasNext = count($next) > 0;
16 }
17}
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.