May's Blog

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.

#AdventOfCode