You’re about to settle near a complex arrangement of garden plots when some Elves ask if you can lend a hand. They’d like to set up fences around each region of garden plots, but they can’t figure out how much fence they need to order or how much it will cost. They hand you a map (your puzzle input) of the garden plots.
Solution in Java
Full source can be found: in GitHub
Part 1
First step was to create a helper class to contain the price of an area.
1record Price(int area, int perimeter) {
2 public int compute() {
3 return area * perimeter;
4 }
5}
Then I created a method to calculate the prices per area in the input. This method iterates over each position in the grid and if not yet processed starts consuming all neighbouring points with the same character (line 12).
1private int computeTotalPrice() {
2 var grid = inputLoader.charGrid();
3 var processed = new HashSet<Point>();
4
5 var prices = new ArrayList<Price>();
6 for (var x = 0; x < grid.cols(); x++) {
7 for (var y = 0; y < grid.rows(); y++) {
8 if (processed.contains(new Point(x, y))) {
9 continue;
10 }
11
12 prices.add(computePrice(grid, new Point(x, y), processed));
13 }
14 }
15
16 return prices.stream().mapToInt(Price::compute).sum();
17}
To actually calculate the Price of each region the following method is created. This method starts to walk over all neighbours starting at start marking them as processed, but with the condition that the neighbour must have the same character in it then the given start. If the neighbour contains a different character then we have found a border.
1private Price computePrice(CharGrid grid, Point start, Set<Point> processed) {
2 var processQueue = new LinkedHashSet<Point>();
3 var shapePoints = new HashSet<Point>();
4 processQueue.add(start);
5
6 var borders = 0;
7 while (!processQueue.isEmpty()) {
8 var current = processQueue.removeFirst();
9 processed.add(current);
10 shapePoints.add(current);
11
12 for (var neighbour : current.neighbours()) {
13 if (processed.contains(neighbour)) {
14 if (grid.at(neighbour) != grid.at(current)) {
15 borders++;
16 }
17 continue;
18 }
19
20 if (grid.at(neighbour) == grid.at(current)) {
21 processQueue.add(neighbour);
22 } else {
23 borders++;
24 }
25 }
26 }
27
28 log.debug("Processed at {} for character {}, with {} borders.", start, grid.at(start), borders);
29 return new Price(shapePoints.size(), borders);
30}
Now that all the algorithms are in place the actual calling of them for part 1 can be created.
1public void part1() {
2 validator.part1(computeTotalPrice());
3}
Part 2
For part 2 we are no longer interested in each border segment, but the number of actual borders. So if both point [1,2] and point [1,3] would be borders in part 1 this would be considered a single border in part 2.
The easiest way is to leave most of the algorithms intact from part 1, but recompute the amount of borders by calculating the amount of corners each area has.
1private Price computePrice(CharGrid grid, Point start, Set<Point> processed, boolean trackSimpleBorders) {
2 ... all the code above the logging of the previous snippet ...
3 if (trackSimpleBorders) {
4 borders = computeCorners(shapePoints);
5 }
6}
And of course the algorithm to actually compute the corners.
1private int computeCorners(Set<Point> shapePoints) {
2 var corners = 0;
3 for (var point : shapePoints) {
4 // inward corners
5 if (shapePoints.contains(point.up()) && shapePoints.contains(point.up().right()) && !shapePoints.contains(point.right())) {
6 corners++;
7 }
8 if (shapePoints.contains(point.up()) && shapePoints.contains(point.up().left()) && !shapePoints.contains(point.left())) {
9 corners++;
10 }
11 if (shapePoints.contains(point.down()) && shapePoints.contains(point.down().left()) && !shapePoints.contains(point.left())) {
12 corners++;
13 }
14 if (shapePoints.contains(point.down()) && shapePoints.contains(point.down().right()) && !shapePoints.contains(point.right())) {
15 corners++;
16 }
17
18 // outer corners
19 if (!shapePoints.contains(point.up()) && !shapePoints.contains(point.left())) {
20 corners++;
21 }
22 if (!shapePoints.contains(point.up()) && !shapePoints.contains(point.right())) {
23 corners++;
24 }
25 if (!shapePoints.contains(point.down()) && !shapePoints.contains(point.left())) {
26 corners++;
27 }
28 if (!shapePoints.contains(point.down()) && !shapePoints.contains(point.right())) {
29 corners++;
30 }
31 }
32 return corners;
33}
After these changes the part 2 implementation can be added.
1public void part2() {
2 validator.part2(computeTotalPrice(true));
3}