Skip to content

Commit 26e68e1

Browse files
codeforkjeffcodeforkjeff
committed
day 12
1 parent 7628eb7 commit 26e68e1

File tree

9 files changed

+357
-0
lines changed

9 files changed

+357
-0
lines changed

‎src/main/java/com/codefork/aoc2024/day12/Edge.java

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
package com.codefork.aoc2024.day12;
2+
3+
public enum Edge {
4+
Top, Right, Bottom, Left
5+
}

‎src/main/java/com/codefork/aoc2024/day12/GardenPlots.java

Lines changed: 134 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,134 @@
1+
package com.codefork.aoc2024.day12;
2+
3+
import com.codefork.aoc2024.util.WithIndex;
4+
5+
import java.util.ArrayList;
6+
import java.util.HashMap;
7+
import java.util.List;
8+
import java.util.Map;
9+
import java.util.Set;
10+
import java.util.stream.Collectors;
11+
import java.util.stream.Stream;
12+
13+
import static com.codefork.aoc2024.util.FoldLeft.foldLeft;
14+
15+
/**
16+
* In two places in the code, this solution makes use of a merging strategy to build groups of
17+
* adjacent things from an unordered collection. The logic is:
18+
* - check if an item is adjacent to any existing groups of adjacent items; if so,
19+
* merge those groups together and add the item to the new group
20+
* - if item isn't adjacent, create a group for it
21+
* The key is that we can't know ahead of time which groups may need to be merged;
22+
* we just do it along the way.
23+
*/
24+
public class GardenPlots {
25+
26+
// intermediate data structure
27+
private record PlotWithPlantType(String plantType, int x, int y) {
28+
29+
}
30+
31+
private final Map<String, List<Region>> regions;
32+
33+
public GardenPlots(Stream<String> data) {
34+
var plots = data
35+
.map(WithIndex.indexed())
36+
.flatMap(lineIndexed -> {
37+
var y = lineIndexed.index();
38+
var line = lineIndexed.value();
39+
return line.chars()
40+
.boxed()
41+
.map(WithIndex.indexed())
42+
.map(charIndexed -> {
43+
var x = charIndexed.index();
44+
var ch = String.valueOf((char) charIndexed.value().intValue());
45+
return new PlotWithPlantType(ch, x, y);
46+
});
47+
})
48+
.toList();
49+
50+
var byPlantType = plots
51+
.stream()
52+
.collect(Collectors.toMap(
53+
(plot) -> plot.plantType,
54+
Set::of,
55+
(v1, v2) -> Stream.concat(v1.stream(), v2.stream()).collect(Collectors.toSet())
56+
));
57+
58+
this.regions = byPlantType.entrySet().stream().collect(
59+
foldLeft(
60+
HashMap::new,
61+
(acc, entry) -> {
62+
var plantType = entry.getKey();
63+
var plantTypePlots = entry.getValue();
64+
65+
for (var plantTypePlot : plantTypePlots) {
66+
var plot = new Plot(plantTypePlot.x(), plantTypePlot.y());
67+
if (!acc.containsKey(plantType)) {
68+
var newRegion = new Region(plantType, new ArrayList<>(List.of(plot)));
69+
acc.put(plantType, new ArrayList<>(List.of(newRegion)));
70+
} else {
71+
var regions = acc.get(plantType);
72+
73+
// figure out which regions are adjacent to plantTypePlot and which aren't
74+
var groupedByAdjacency = regions
75+
.stream()
76+
.collect(Collectors.groupingBy(
77+
(region) -> region.anyAdjacent(plot)));
78+
79+
var nonAdjacentRegions = groupedByAdjacency
80+
.getOrDefault(Boolean.FALSE, new ArrayList<>());
81+
82+
// this handles no adjacent region (in which case one is created),
83+
// and one or more adjacent regions (in which case they're merged)
84+
var mergedAdjacentRegion = groupedByAdjacency
85+
.getOrDefault(Boolean.TRUE, new ArrayList<>())
86+
.stream()
87+
.collect(foldLeft(
88+
() -> new Region(plantType, new ArrayList<>()),
89+
(acc2, region) -> {
90+
acc2.plots().addAll(region.plots());
91+
return acc2;
92+
}
93+
));
94+
mergedAdjacentRegion.plots().add(plot);
95+
96+
acc.put(plantType, Stream.concat(Stream.of(mergedAdjacentRegion),
97+
nonAdjacentRegions.stream()).toList());
98+
}
99+
}
100+
return acc;
101+
}
102+
)
103+
);
104+
}
105+
106+
public Map<String, List<Region>> getRegions() {
107+
return regions;
108+
}
109+
110+
public int getFencingCost(boolean bulkDiscount) {
111+
return this.regions.values().stream().reduce(0,
112+
(acc, regionList) ->
113+
acc + regionList.stream().reduce(0, (acc2, region) ->
114+
acc2 + region.getArea() * (bulkDiscount ? region.getSides() : region.getPerimeter())
115+
, Integer::sum)
116+
, Integer::sum);
117+
}
118+
119+
public void print() {
120+
for (var entry : getRegions().entrySet()) {
121+
var plantType = entry.getKey();
122+
var regions = entry.getValue();
123+
System.out.println(plantType);
124+
for (var region : regions) {
125+
for (var plot : region.plots()) {
126+
System.out.print(plot);
127+
}
128+
System.out.println();
129+
System.out.println(region.getArea() + " " + region.getSides());
130+
}
131+
}
132+
}
133+
134+
}

‎src/main/java/com/codefork/aoc2024/day12/Part01.java

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package com.codefork.aoc2024.day12;
2+
3+
import com.codefork.aoc2024.Problem;
4+
import com.codefork.aoc2024.util.Assert;
5+
6+
import java.util.stream.Stream;
7+
8+
public class Part01 extends Problem {
9+
10+
public String solve(Stream<String> data) {
11+
var gardenPlots = new GardenPlots(data);
12+
return String.valueOf(gardenPlots.getFencingCost(false));
13+
}
14+
15+
@Override
16+
public String solve() {
17+
Assert.assertEquals("1930", solve(getSampleInput()));
18+
return solve(getInput());
19+
}
20+
21+
public static void main(String[] args) {
22+
new Part01().run();
23+
}
24+
}

‎src/main/java/com/codefork/aoc2024/day12/Part02.java

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package com.codefork.aoc2024.day12;
2+
3+
import com.codefork.aoc2024.Problem;
4+
import com.codefork.aoc2024.util.Assert;
5+
6+
import java.util.stream.Stream;
7+
8+
public class Part02 extends Problem {
9+
10+
public String solve(Stream<String> data) {
11+
var gardenPlots = new GardenPlots(data);
12+
return String.valueOf(gardenPlots.getFencingCost(true));
13+
}
14+
15+
@Override
16+
public String solve() {
17+
Assert.assertEquals("1206", solve(getSampleInput()));
18+
return solve(getInput());
19+
}
20+
21+
public static void main(String[] args) {
22+
new Part02().run();
23+
}
24+
}

‎src/main/java/com/codefork/aoc2024/day12/Plot.java

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package com.codefork.aoc2024.day12;
2+
3+
public record Plot(int x, int y) {
4+
5+
public boolean isAdjacent(Plot other) {
6+
var xDiff = Math.abs(other.x() - x());
7+
var yDiff = Math.abs(other.y() - y());
8+
return xDiff + yDiff == 1;
9+
}
10+
11+
/**
12+
* returns the edge along which the other plot is adjacent
13+
* @param other
14+
* @return
15+
*/
16+
public Edge getAdjacentEdge(Plot other) {
17+
if(other.x() == x() && other.y() == y() - 1) {
18+
return Edge.Top;
19+
} else if(other.x() == x() && other.y() == y() + 1) {
20+
return Edge.Bottom;
21+
} else if(other.x() == x() - 1 && other.y() == y()) {
22+
return Edge.Left;
23+
} else if(other.x() == x() + 1 && other.y() == y()) {
24+
return Edge.Right;
25+
}
26+
throw new RuntimeException("this should never happen");
27+
}
28+
29+
}

‎src/main/java/com/codefork/aoc2024/day12/Region.java

Lines changed: 121 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,121 @@
1+
package com.codefork.aoc2024.day12;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.Collection;
6+
import java.util.HashSet;
7+
import java.util.List;
8+
import java.util.stream.Collectors;
9+
import java.util.stream.Stream;
10+
11+
import static com.codefork.aoc2024.util.FoldLeft.foldLeft;
12+
13+
public record Region(String plantType, List<Plot> plots) {
14+
15+
public boolean anyAdjacent(Plot other) {
16+
return this.plots.stream().anyMatch(p -> p.isAdjacent(other));
17+
}
18+
19+
public int getArea() {
20+
return plots.size();
21+
}
22+
23+
public int getPerimeter() {
24+
return plots.stream()
25+
.reduce(0L, (acc, plot) -> {
26+
var countAdjacent = plots.stream()
27+
.filter(possibleAdjacent ->
28+
possibleAdjacent.isAdjacent(plot)
29+
)
30+
.count();
31+
return acc + (4 - countAdjacent);
32+
}, Long::sum).intValue();
33+
}
34+
35+
/**
36+
* This finds the side group(s) that the passed-in side is adjacent to,
37+
* and merges them, returning a new list of lists.
38+
*
39+
* @param side the side to add to one of the lists of adjacent sides
40+
* @param groups list of lists of adjacent sides
41+
*/
42+
public List<List<Side>> groupAdjacent(Side side, List<List<Side>> groups) {
43+
// the types are tricky here. would be nice to create a wrapper record/class
44+
// for List<Side> named AdjacentSides for clarity, the same way we have a Region
45+
// class, but this works fine
46+
var groupedByAdjacency = groups
47+
.stream()
48+
.collect(Collectors.groupingBy(
49+
(group) -> group.stream()
50+
.anyMatch(sideItem -> sideItem.isAdjacent(side))
51+
));
52+
53+
// this is a list of lists
54+
var nonAdjacentSides = groupedByAdjacency
55+
.getOrDefault(Boolean.FALSE, new ArrayList<>());
56+
57+
// this is also a list of lists
58+
var mergedAdjacentSides = new ArrayList<>(groupedByAdjacency
59+
.getOrDefault(Boolean.TRUE, new ArrayList<>())
60+
.stream()
61+
.flatMap(Collection::stream)
62+
.toList());
63+
mergedAdjacentSides.add(side);
64+
65+
return Stream.concat(
66+
nonAdjacentSides.stream(),
67+
Stream.of(mergedAdjacentSides))
68+
.toList();
69+
}
70+
71+
/**
72+
* @return number of contiguous sections of sides of the plot (this is for part 2)
73+
*/
74+
public int getSides() {
75+
// create a list of all the sides of this region
76+
var sides = plots.stream()
77+
.flatMap((plot) -> {
78+
var edges = new HashSet<>(Arrays.stream(Edge.values()).toList());
79+
// remove the edges shared by plots
80+
var edgesToRemove = plots.stream()
81+
.filter(plot::isAdjacent)
82+
.map(plot::getAdjacentEdge)
83+
.collect(Collectors.toSet());
84+
edges.removeAll(edgesToRemove);
85+
return edges.stream().map(edge -> new Side(plot, edge));
86+
})
87+
.toList();
88+
89+
// count the contiguous sides
90+
var totalContigsCount = Arrays.stream(Edge.values())
91+
.collect(foldLeft(
92+
() -> 0,
93+
(countContigs, edge) -> {
94+
// this combining fn finds the number of contiguous sides for a given edge,
95+
// and adds it to countContigs
96+
97+
//System.out.println("doing edge=" + edge);
98+
99+
var sidesForEdge = sides.stream()
100+
.filter(side -> side.edge().equals(edge))
101+
.toList();
102+
103+
var groupedAdjacent = sidesForEdge.stream()
104+
.collect(foldLeft(
105+
() -> (List<List<Side>>) new ArrayList<List<Side>>(),
106+
(acc, side) -> groupAdjacent(side, acc)
107+
)
108+
);
109+
110+
//System.out.println("grouped=" + groupedAdjacent);
111+
112+
return countContigs + groupedAdjacent.size();
113+
}
114+
)
115+
);
116+
117+
//System.out.println("total contiguous sides = " + totalContigsCount);
118+
119+
return totalContigsCount;
120+
}
121+
}

‎src/main/java/com/codefork/aoc2024/day12/Side.java

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
package com.codefork.aoc2024.day12;
2+
3+
/**
4+
* A side is an edge along a plot
5+
*/
6+
public record Side(Plot plot, Edge edge) {
7+
8+
public boolean isAdjacent(Side other) {
9+
if(edge.equals(other.edge())) {
10+
if(edge.equals(Edge.Left) || edge.equals(Edge.Right)) {
11+
var yDiff = Math.abs(other.plot().y() - plot().y());
12+
return other.plot().x() == plot().x() && yDiff == 1;
13+
} else if (edge.equals(Edge.Top) || edge.equals(Edge.Bottom)) {
14+
var xDiff = Math.abs(other.plot().x() - plot().x());
15+
return other.plot().y() == plot().y() && xDiff == 1;
16+
}
17+
}
18+
return false;
19+
}
20+
}

‎src/main/resources/day12/input

19.3 KB
Binary file not shown.

‎src/main/resources/day12/sample

132 Bytes
Binary file not shown.

0 commit comments

Comments
 (0)