Skip to content

Commit 1f7a19f

Browse files
l0sl0s
committed
Day 12
1 parent e413e5b commit 1f7a19f

File tree

2 files changed

+189
-0
lines changed

2 files changed

+189
-0
lines changed

‎src/test/java/com/macasaet/Day12.java

Lines changed: 182 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,182 @@
1+
package com.macasaet;
2+
3+
import java.util.*;
4+
import java.util.stream.Stream;
5+
import java.util.stream.StreamSupport;
6+
7+
import org.junit.jupiter.api.Test;
8+
9+
/**
10+
* --- Day 12: Passage Pathing ---
11+
*/
12+
public class Day12 {
13+
14+
protected Stream<String> getInput() {
15+
return StreamSupport
16+
.stream(new LineSpliterator("day-12.txt"),
17+
false);
18+
}
19+
20+
/**
21+
* @return a map of the connected caves
22+
*/
23+
protected Map<String, Node> getMap() {
24+
final var map = new HashMap<String, Node>();
25+
getInput().forEach(line -> {
26+
final var components = line.split("-");
27+
final var sourceLabel = components[0];
28+
final var targetLabel = components[1];
29+
final var source = map.computeIfAbsent(sourceLabel, Node::new);
30+
final var target = map.computeIfAbsent(targetLabel, Node::new);
31+
source.connected.add(target);
32+
target.connected.add(source);
33+
});
34+
return Collections.unmodifiableMap(map);
35+
}
36+
37+
public Node getStartingPoint() {
38+
return getMap().get("start");
39+
}
40+
41+
/**
42+
* A distinct path through the cave system
43+
*/
44+
public record Path(List<Node> nodes, Node specialCave, int specialCaveVisits) {
45+
46+
public int hashCode() {
47+
int result = 0;
48+
for (final var node : nodes()) {
49+
result = result * 31 + node.hashCode();
50+
}
51+
return result;
52+
}
53+
54+
public boolean equals(final Object o) {
55+
if (o == null) {
56+
return false;
57+
}
58+
try {
59+
final var other = (Path) o;
60+
return nodes().equals(other.nodes());
61+
} catch (final ClassCastException cce) {
62+
return false;
63+
}
64+
}
65+
}
66+
67+
public static class Node {
68+
private final boolean isStart;
69+
private final boolean isEnd;
70+
private final boolean isSmallCave;
71+
private final String label;
72+
73+
private final Set<Node> connected = new HashSet<>();
74+
75+
public Node(final String label) {
76+
this("start".equalsIgnoreCase(label), "end".equalsIgnoreCase(label),
77+
label.toLowerCase(Locale.ROOT).equals(label), label);
78+
}
79+
80+
protected Node(boolean isStart, boolean isEnd, boolean isSmallCave, final String label) {
81+
this.isStart = isStart;
82+
this.isEnd = isEnd;
83+
this.isSmallCave = isSmallCave;
84+
this.label = label;
85+
}
86+
87+
public int hashCode() {
88+
int result = 0;
89+
result += result * 31 + label.hashCode();
90+
return result;
91+
}
92+
93+
public boolean equals(final Object o) {
94+
if (o == null) {
95+
return false;
96+
}
97+
try {
98+
final Node other = (Node) o;
99+
return label.equals(other.label);
100+
} catch (final ClassCastException cce) {
101+
return false;
102+
}
103+
}
104+
105+
}
106+
107+
protected Set<Path> getPaths(final Node node, final Path pathSoFar) {
108+
final var result = new HashSet<Path>();
109+
110+
if (node.isStart && pathSoFar.nodes.size() > 1) {
111+
// "once you leave the start cave, you may not return to it"
112+
return Collections.emptySet();
113+
}
114+
115+
final var nodes = new ArrayList<>(pathSoFar.nodes());
116+
if (node.isEnd) {
117+
// "once you reach the end cave, the path must end immediately"
118+
nodes.add(node);
119+
return Collections.singleton(new Path(Collections.unmodifiableList(nodes), pathSoFar.specialCave(), pathSoFar.specialCaveVisits()));
120+
}
121+
int specialCaveVisits = pathSoFar.specialCaveVisits();
122+
if (node.isSmallCave) {
123+
if (node.equals(pathSoFar.specialCave())) {
124+
// "a single small cave can be visited at most twice"
125+
if (pathSoFar.specialCaveVisits() < 1) {
126+
specialCaveVisits++;
127+
} else {
128+
return Collections.emptySet();
129+
}
130+
} else {
131+
if (pathSoFar.nodes().contains(node)) {
132+
// "the remaining small caves can be visited at most once"
133+
return Collections.emptySet();
134+
}
135+
}
136+
}
137+
nodes.add(node);
138+
for (final var neighbour : node.connected) {
139+
if (neighbour.isSmallCave && pathSoFar.specialCave() == null) {
140+
result.addAll(getPaths(neighbour, new Path(Collections.unmodifiableList(nodes), null, 0)));
141+
result.addAll(getPaths(neighbour, new Path(Collections.unmodifiableList(nodes), neighbour, 0)));
142+
} else {
143+
result.addAll(getPaths(neighbour, new Path(Collections.unmodifiableList(nodes), pathSoFar.specialCave(), specialCaveVisits)));
144+
}
145+
}
146+
return Collections.unmodifiableSet(result);
147+
}
148+
149+
protected int countPaths(final Node node, final Set<Node> visitedSmallCaves) {
150+
int result = 0;
151+
if (node.isEnd) {
152+
return 1;
153+
}
154+
if (visitedSmallCaves.contains(node)) {
155+
// invalid path
156+
return 0;
157+
}
158+
if (node.isSmallCave) {
159+
visitedSmallCaves.add(node);
160+
}
161+
for (final var connected : node.connected) {
162+
final var set = new HashSet<>(visitedSmallCaves);
163+
result += countPaths(connected, set);
164+
}
165+
return result;
166+
}
167+
168+
@Test
169+
public final void part1() {
170+
final var start = getStartingPoint();
171+
final int result = countPaths(start, new HashSet<>());
172+
System.out.println("Part 1: " + result);
173+
}
174+
175+
@Test
176+
public final void part2() {
177+
final var start = getStartingPoint();
178+
final var paths = getPaths(start, new Path(Collections.emptyList(), null, 0));
179+
System.out.println("Part 2: " + paths.size());
180+
}
181+
182+
}

‎src/test/resources/sample/day-12.txt

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
start-A
2+
start-b
3+
A-c
4+
A-b
5+
b-d
6+
A-end
7+
b-end

0 commit comments

Comments
 (0)