Skip to content

Commit 8fa35fe

Browse files
codeforkjeffcodeforkjeff
committed
day23
1 parent 77cb70e commit 8fa35fe

File tree

8 files changed

+302
-0
lines changed

8 files changed

+302
-0
lines changed

‎README.md

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -115,3 +115,13 @@ the rules imply and calculating a "shortcut" solution. Just nice efficient codin
115115
Day 20 was the first puzzle where a recursive method caused a StackOverflowError
116116
when running it on the real input. This is yet another limit of trying to do pure FP in Java:
117117
it doesn't have [tail call optimization](https://en.wikipedia.org/wiki/Tail_call).
118+
119+
### 12/26/2024
120+
121+
Unsurprisingly, I didn't finish AoC by or on Christmas. I do think this December's progress has
122+
been better than my last attempt in 2018, at least. We'll see how long it takes me to wrap this all up.
123+
124+
Day 23 was one of those problems where I took an entirely different approach in part 2 than part 1.
125+
Usually when this happens, I "align" the two solutions so they re-use the same code. I started to do that
126+
after finishing part 2 but the approaches are so algorithmically different that I decided it wasn't worth
127+
the energy.

‎src/main/java/com/codefork/aoc2024/day23/Network.java

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
package com.codefork.aoc2024.day23;
2+
3+
import java.util.ArrayList;
4+
import java.util.HashMap;
5+
import java.util.HashSet;
6+
import java.util.List;
7+
import java.util.Map;
8+
import java.util.Set;
9+
import java.util.stream.Collectors;
10+
import java.util.stream.Stream;
11+
12+
import static com.codefork.aoc2024.util.FoldLeft.foldLeft;
13+
14+
/**
15+
* A set of computers that include every other member in its list of neighbors.
16+
*/
17+
public record Network(Set<String> computers, String last) {
18+
19+
/**
20+
* adds a computer to this network if its neighbors includes every other computer already in set,
21+
* and returns the new set; if not in the network, just return the existing set
22+
*/
23+
public Network addIfBelongs(String computerToAdd, Map<String, List<String>> edges) {
24+
var newComputers = new HashSet<>(computers);
25+
newComputers.add(computerToAdd);
26+
var neighbors = new HashSet<>(edges.get(computerToAdd));
27+
if (neighbors.containsAll(computers())) {
28+
return new Network(newComputers, computerToAdd);
29+
}
30+
return this;
31+
}
32+
33+
public boolean contains(String computer) {
34+
return computers().contains(computer);
35+
}
36+
37+
public int size() {
38+
return computers().size();
39+
}
40+
41+
public Network withoutLast() {
42+
return new Network(computers, "DONE");
43+
}
44+
45+
public static Map<String, List<String>> parseEdges(Stream<String> data) {
46+
return data.collect(foldLeft(
47+
HashMap::new,
48+
(acc, line) -> {
49+
var parts = line.split("-");
50+
if (!acc.containsKey(parts[0])) {
51+
acc.put(parts[0], new ArrayList<>());
52+
}
53+
acc.get(parts[0]).add(parts[1]);
54+
if (!acc.containsKey(parts[1])) {
55+
acc.put(parts[1], new ArrayList<>());
56+
}
57+
acc.get(parts[1]).add(parts[0]);
58+
return acc;
59+
})
60+
);
61+
}
62+
63+
@Override
64+
public String toString() {
65+
return computers().stream().sorted().collect(Collectors.joining(","));
66+
}
67+
}

‎src/main/java/com/codefork/aoc2024/day23/NetworkFinder.java

Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
package com.codefork.aoc2024.day23;
2+
3+
import java.util.Comparator;
4+
import java.util.HashSet;
5+
import java.util.List;
6+
import java.util.Map;
7+
import java.util.Set;
8+
import java.util.stream.Collectors;
9+
10+
/**
11+
* Solver for part 2. This uses an entirely different strategy from part 1.
12+
* <p></p>
13+
* Start with an initial set of networks, each consisting of a t-computer and one
14+
* of its known neighbors. After this seeding, we have a set of known good networks: we can
15+
* visit "outward" from these in the graph, adding computers to the known networks as appropriate,
16+
* and merging networks as we go.
17+
* <p></p>
18+
* Because the Network record was originally created for part 1, its holds the "last" computer added
19+
* to the network as part of that data structure. We don't use that field here, so we just use a placeholder.
20+
*/
21+
public record NetworkFinder(Map<String, List<String>> edges, List<Network> networks, Set<String> visited, Set<String> toVisit) {
22+
23+
static String UNUSED = "UNUSED";
24+
25+
/**
26+
* Initialize with a list of networks, each consisting of a t-computer
27+
* and one its known neighbors.
28+
*/
29+
public static NetworkFinder seed(Map<String, List<String>> edges) {
30+
var initial = edges.keySet().stream()
31+
.filter(s -> s.startsWith("t"))
32+
.collect(Collectors.toSet());
33+
34+
var networks = initial.stream()
35+
.flatMap(s -> edges.get(s).stream().map(target ->
36+
new Network(Set.of(s, target), UNUSED)
37+
))
38+
.toList();
39+
40+
var toVisit = initial.stream()
41+
.flatMap(s -> edges.get(s).stream())
42+
.collect(Collectors.toSet());
43+
44+
return new NetworkFinder(edges, networks, initial, toVisit);
45+
}
46+
47+
public List<Network> findAllNetworks() {
48+
var walker = this;
49+
while(!walker.toVisit().isEmpty()) {
50+
var computer = walker.toVisit().iterator().next();
51+
52+
if(walker.visited().contains(computer)) {
53+
var newVisited = new HashSet<>(walker.visited());
54+
newVisited.add(computer);
55+
56+
var newToVisit = new HashSet<>(walker.toVisit());
57+
newToVisit.remove(computer);
58+
59+
walker = new NetworkFinder(walker.edges(), walker.networks(), newVisited, newToVisit);
60+
61+
continue;
62+
}
63+
64+
//System.out.println(walker.networks());
65+
66+
// add the computer to all possible networks
67+
var newNetworks = walker.networks().stream().map(network -> {
68+
var newNetwork = network.addIfBelongs(computer, edges);
69+
if(!newNetwork.equals(network)) {
70+
return newNetwork;
71+
}
72+
return network;
73+
}).toList();
74+
75+
// merge newNetworks
76+
var grouped = newNetworks.stream().collect(Collectors.toMap(
77+
Network::computers,
78+
(network) -> 1,
79+
(v1, v2) -> 1
80+
));
81+
newNetworks = grouped.keySet().stream().map(networkSet -> {
82+
return new Network(networkSet, UNUSED);
83+
}).toList();
84+
85+
var newVisited = new HashSet<>(walker.visited());
86+
newVisited.add(computer);
87+
88+
var newToVisit = new HashSet<>(walker.toVisit());
89+
newToVisit.addAll(edges.get(computer));
90+
newToVisit.remove(computer);
91+
92+
walker = new NetworkFinder(edges(), newNetworks, newVisited, newToVisit);
93+
}
94+
return walker.networks();
95+
}
96+
97+
public Network findLargestNetwork() {
98+
return findAllNetworks().stream()
99+
.max(Comparator.comparingInt(Network::size))
100+
.orElseThrow();
101+
}
102+
103+
}

‎src/main/java/com/codefork/aoc2024/day23/NetworkGrower.java

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
package com.codefork.aoc2024.day23;
2+
3+
import java.util.List;
4+
import java.util.Map;
5+
import java.util.Set;
6+
import java.util.stream.Collectors;
7+
import java.util.stream.Stream;
8+
9+
/**
10+
* Solver for part 1. Grow an initial set of single t-computer networks,
11+
* following its neighbors, in a one-to-many iterative pattern, until we find all the networks
12+
* of a given size.
13+
*/
14+
public class NetworkGrower {
15+
16+
private final Map<String, List<String>> edges;
17+
private final int size;
18+
19+
private List<Network> networks;
20+
21+
public NetworkGrower(Map<String, List<String>> edges, int size) {
22+
this.edges = edges;
23+
this.size = size;
24+
this.networks = edges.keySet().stream()
25+
.filter(s -> s.startsWith("t"))
26+
.map(s -> new Network(Set.of(s), s))
27+
.toList();
28+
}
29+
30+
/**
31+
* returns true if networks contains any networks that are less than size
32+
*/
33+
public boolean needsGrowing() {
34+
return networks.stream().anyMatch(set -> set.size() < size);
35+
}
36+
37+
public List<Network> grow() {
38+
while (needsGrowing()) {
39+
networks = networks.stream().flatMap(network -> {
40+
if (network.size() == size) {
41+
return Stream.of(network);
42+
}
43+
var neighbors = edges.get(network.last());
44+
return neighbors.stream()
45+
.filter(neighbor -> !network.contains(neighbor))
46+
.flatMap(neighbor -> {
47+
var newNetwork = network.addIfBelongs(neighbor, edges);
48+
if (!newNetwork.equals(network)) {
49+
return Stream.of(newNetwork);
50+
}
51+
// couldn't be added to the network, so filter out
52+
return Stream.empty();
53+
});
54+
}).toList();
55+
networks = networks.stream()
56+
.map(network -> (network.size() == size) ? network.withoutLast() : network)
57+
.collect(Collectors.toSet())
58+
.stream()
59+
.toList();
60+
// System.out.println("networks=");
61+
// for(var set : newSet) {
62+
// System.out.println(set);
63+
// }
64+
}
65+
return networks;
66+
}
67+
68+
}

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

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package com.codefork.aoc2024.day23;
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 edges = Network.parseEdges(data);
12+
var grower = new NetworkGrower(edges, 3);
13+
var networks = grower.grow();
14+
return String.valueOf(networks.size());
15+
}
16+
17+
@Override
18+
public String solve() {
19+
Assert.assertEquals("7", solve(getSampleInput()));
20+
return solve(getInput());
21+
}
22+
23+
public static void main(String[] args) {
24+
new Part01().run();
25+
}
26+
27+
}

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

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package com.codefork.aoc2024.day23;
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 edges = Network.parseEdges(data);
12+
var walker = NetworkFinder.seed(edges);
13+
var network = walker.findLargestNetwork();
14+
return network.toString();
15+
}
16+
17+
@Override
18+
public String solve() {
19+
Assert.assertEquals("co,de,ka,ta", solve(getSampleInput()));
20+
return solve(getInput());
21+
}
22+
23+
public static void main(String[] args) {
24+
new Part02().run();
25+
}
26+
27+
}

‎src/main/resources/day23/input

19.8 KB
Binary file not shown.

‎src/main/resources/day23/sample

214 Bytes
Binary file not shown.

0 commit comments

Comments
 (0)