Solution to the 10th problem

Problem A

The answer for Part A is the maximum distance (in steps) from S to any tile along the loop when traveling along the loop. Since every tile lies on a single cycle, that maximum distance is exactly half the loop length (the visualization shows (count - 1) / 2 once the loop is known). Therefore, the algorithm traverses the loop until it ends in the starting position.

Complexity: it's required to find the connectivity and traversing the loop, which are both linear in the number of grid cells (O(R * C)); memory use is likewise linear for storing visited tiles. Benchmark is for a 140x140 matrix.

» cargo build -p aoc-23 --release && hyperfine ./target/release/aoc-23 -N --warmup 5
Benchmark 1: ./target/release/aoc-23
Time (mean ± σ):       6.3 ms ±   2.9 ms    [User: 1.3 ms, System: 1.0 ms]
Range (min … max):     3.1 ms …  37.9 ms    599 runs

Problem B

For part B, most of the code is the same, as traversin the loop is requied. When the loop is known, the egdes are found whic hare they used to know the loops area with the shoelace formula. Knowing the surface, the Pick's theorem is applied, giving us the number of tiles inside the loop.

In order to make the visualization more appealing, once the solution is found, the points inside the polygon are calculated by doing a point in polygon test, which basically implies an additional iteration to the entire grid (O(m * n)).

Complexity: the same as for part A, but with an additional parameter when traversing the loop to calculate the edges. The memory use is also linear, as the edges are stored in a vector. Benchmark is for a 140x140 matrix.

» cargo build -p aoc-23 --release && hyperfine ./target/release/aoc-23 -N --warmup 5
Benchmark 1: ./target/release/aoc-23
Time (mean ± σ):       5.4 ms ±   2.6 ms    [User: 1.3 ms, System: 1.0 ms]
Range (min … max):     3.4 ms …  30.9 ms    337 runs