The Elves are constructing a lagoon to hold lava for a machine parts factory. The lagoon's perimeter is described by a series of directional instructions, each specifying a movement direction (Up, Down, Left, Right) and a length. The task is to determine the total volume of the lagoon that can be filled with lava, given these perimeter instructions.
The Elves soon realize that the planned lagoon would be too small due to a mistake in the dig plan. The hexadecimal color codes in the instructions were mistakenly swapped with the direction and distance parameters. The correct instructions must be extracted from these hexadecimal codes, where the first five digits represent the distance in meters (as a hexadecimal number), and the last digit represents the direction (0 for R, 1 for D, 2 for L, and 3 for U).
The challenge is to convert these hexadecimal codes into the correct instructions and calculate the volume of lava the lagoon can hold based on this revised plan
R 6 (#70c710)
D 5 (#0dc571)
L 2 (#5713f0)
D 2 (#d2c081)
R 2 (#59c680)
D 2 (#411b91)
L 5 (#8ceee2)
U 2 (#caa173)
L 1 (#1b58a2)
U 2 (#caa171)
R 2 (#7807d2)
U 3 (#a77fa3)
L 2 (#015232)
U 2 (#7a21e3)
The solution involves two key mathematical concepts: Pick's Theorem and the Shoelace formula.
Pick's Theorem provides a formula to calculate the area of a simple polygon whose vertices are points on a lattice. The formula is:
A=I+B2−1A=I+2B−1
where AA is the area of the polygon, II is the number of lattice points inside the polygon, and BB is the number of lattice points on the boundary of the polygon.
The Shoelace formula is a method for finding the area of a polygon when the coordinates of its vertices are known. The formula is particularly useful for polygons whose edges are not necessarily parallel to the axis, which is the case for the lagoon perimeter. Implementation
The implementation involves parsing the directional instructions to construct the perimeter of the lagoon. The vertices of the polygon formed by this perimeter are then used in the Shoelace formula to calculate the area. To calculate the volume of the lagoon, the perimeter (representing the trench dug around the lagoon) is also considered, and Pick's theorem is applied.
The perimeter is calculated by summing the lengths of all the movements, while the area is calculated using the vertices obtained from the instructions. The total volume of the lagoon is the sum of the interior area and the perimeter. Rust Implementation
I managed to do alright on the first part but ultimately had to look at a few solutions from others' on Reddit to find a path forward.
I'm pretty happy with my solution, ultimately, but I'm just leaving this one in Rust this time - I'm a little tired after this fight