Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit8fa35fe

Browse files
committed
day23
1 parent77cb70e commit8fa35fe

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.
Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
packagecom.codefork.aoc2024.day23;
2+
3+
importjava.util.ArrayList;
4+
importjava.util.HashMap;
5+
importjava.util.HashSet;
6+
importjava.util.List;
7+
importjava.util.Map;
8+
importjava.util.Set;
9+
importjava.util.stream.Collectors;
10+
importjava.util.stream.Stream;
11+
12+
importstaticcom.codefork.aoc2024.util.FoldLeft.foldLeft;
13+
14+
/**
15+
* A set of computers that include every other member in its list of neighbors.
16+
*/
17+
publicrecordNetwork(Set<String>computers,Stringlast) {
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+
publicNetworkaddIfBelongs(StringcomputerToAdd,Map<String,List<String>>edges) {
24+
varnewComputers =newHashSet<>(computers);
25+
newComputers.add(computerToAdd);
26+
varneighbors =newHashSet<>(edges.get(computerToAdd));
27+
if (neighbors.containsAll(computers())) {
28+
returnnewNetwork(newComputers,computerToAdd);
29+
}
30+
returnthis;
31+
}
32+
33+
publicbooleancontains(Stringcomputer) {
34+
returncomputers().contains(computer);
35+
}
36+
37+
publicintsize() {
38+
returncomputers().size();
39+
}
40+
41+
publicNetworkwithoutLast() {
42+
returnnewNetwork(computers,"DONE");
43+
}
44+
45+
publicstaticMap<String,List<String>>parseEdges(Stream<String>data) {
46+
returndata.collect(foldLeft(
47+
HashMap::new,
48+
(acc,line) -> {
49+
varparts =line.split("-");
50+
if (!acc.containsKey(parts[0])) {
51+
acc.put(parts[0],newArrayList<>());
52+
}
53+
acc.get(parts[0]).add(parts[1]);
54+
if (!acc.containsKey(parts[1])) {
55+
acc.put(parts[1],newArrayList<>());
56+
}
57+
acc.get(parts[1]).add(parts[0]);
58+
returnacc;
59+
})
60+
);
61+
}
62+
63+
@Override
64+
publicStringtoString() {
65+
returncomputers().stream().sorted().collect(Collectors.joining(","));
66+
}
67+
}
Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
packagecom.codefork.aoc2024.day23;
2+
3+
importjava.util.Comparator;
4+
importjava.util.HashSet;
5+
importjava.util.List;
6+
importjava.util.Map;
7+
importjava.util.Set;
8+
importjava.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+
publicrecordNetworkFinder(Map<String,List<String>>edges,List<Network>networks,Set<String>visited,Set<String>toVisit) {
22+
23+
staticStringUNUSED ="UNUSED";
24+
25+
/**
26+
* Initialize with a list of networks, each consisting of a t-computer
27+
* and one its known neighbors.
28+
*/
29+
publicstaticNetworkFinderseed(Map<String,List<String>>edges) {
30+
varinitial =edges.keySet().stream()
31+
.filter(s ->s.startsWith("t"))
32+
.collect(Collectors.toSet());
33+
34+
varnetworks =initial.stream()
35+
.flatMap(s ->edges.get(s).stream().map(target ->
36+
newNetwork(Set.of(s,target),UNUSED)
37+
))
38+
.toList();
39+
40+
vartoVisit =initial.stream()
41+
.flatMap(s ->edges.get(s).stream())
42+
.collect(Collectors.toSet());
43+
44+
returnnewNetworkFinder(edges,networks,initial,toVisit);
45+
}
46+
47+
publicList<Network>findAllNetworks() {
48+
varwalker =this;
49+
while(!walker.toVisit().isEmpty()) {
50+
varcomputer =walker.toVisit().iterator().next();
51+
52+
if(walker.visited().contains(computer)) {
53+
varnewVisited =newHashSet<>(walker.visited());
54+
newVisited.add(computer);
55+
56+
varnewToVisit =newHashSet<>(walker.toVisit());
57+
newToVisit.remove(computer);
58+
59+
walker =newNetworkFinder(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+
varnewNetworks =walker.networks().stream().map(network -> {
68+
varnewNetwork =network.addIfBelongs(computer,edges);
69+
if(!newNetwork.equals(network)) {
70+
returnnewNetwork;
71+
}
72+
returnnetwork;
73+
}).toList();
74+
75+
// merge newNetworks
76+
vargrouped =newNetworks.stream().collect(Collectors.toMap(
77+
Network::computers,
78+
(network) ->1,
79+
(v1,v2) ->1
80+
));
81+
newNetworks =grouped.keySet().stream().map(networkSet -> {
82+
returnnewNetwork(networkSet,UNUSED);
83+
}).toList();
84+
85+
varnewVisited =newHashSet<>(walker.visited());
86+
newVisited.add(computer);
87+
88+
varnewToVisit =newHashSet<>(walker.toVisit());
89+
newToVisit.addAll(edges.get(computer));
90+
newToVisit.remove(computer);
91+
92+
walker =newNetworkFinder(edges(),newNetworks,newVisited,newToVisit);
93+
}
94+
returnwalker.networks();
95+
}
96+
97+
publicNetworkfindLargestNetwork() {
98+
returnfindAllNetworks().stream()
99+
.max(Comparator.comparingInt(Network::size))
100+
.orElseThrow();
101+
}
102+
103+
}
Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
packagecom.codefork.aoc2024.day23;
2+
3+
importjava.util.List;
4+
importjava.util.Map;
5+
importjava.util.Set;
6+
importjava.util.stream.Collectors;
7+
importjava.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+
publicclassNetworkGrower {
15+
16+
privatefinalMap<String,List<String>>edges;
17+
privatefinalintsize;
18+
19+
privateList<Network>networks;
20+
21+
publicNetworkGrower(Map<String,List<String>>edges,intsize) {
22+
this.edges =edges;
23+
this.size =size;
24+
this.networks =edges.keySet().stream()
25+
.filter(s ->s.startsWith("t"))
26+
.map(s ->newNetwork(Set.of(s),s))
27+
.toList();
28+
}
29+
30+
/**
31+
* returns true if networks contains any networks that are less than size
32+
*/
33+
publicbooleanneedsGrowing() {
34+
returnnetworks.stream().anyMatch(set ->set.size() <size);
35+
}
36+
37+
publicList<Network>grow() {
38+
while (needsGrowing()) {
39+
networks =networks.stream().flatMap(network -> {
40+
if (network.size() ==size) {
41+
returnStream.of(network);
42+
}
43+
varneighbors =edges.get(network.last());
44+
returnneighbors.stream()
45+
.filter(neighbor -> !network.contains(neighbor))
46+
.flatMap(neighbor -> {
47+
varnewNetwork =network.addIfBelongs(neighbor,edges);
48+
if (!newNetwork.equals(network)) {
49+
returnStream.of(newNetwork);
50+
}
51+
// couldn't be added to the network, so filter out
52+
returnStream.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+
returnnetworks;
66+
}
67+
68+
}
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
packagecom.codefork.aoc2024.day23;
2+
3+
importcom.codefork.aoc2024.Problem;
4+
importcom.codefork.aoc2024.util.Assert;
5+
6+
importjava.util.stream.Stream;
7+
8+
publicclassPart01extendsProblem {
9+
10+
publicStringsolve(Stream<String>data) {
11+
varedges =Network.parseEdges(data);
12+
vargrower =newNetworkGrower(edges,3);
13+
varnetworks =grower.grow();
14+
returnString.valueOf(networks.size());
15+
}
16+
17+
@Override
18+
publicStringsolve() {
19+
Assert.assertEquals("7",solve(getSampleInput()));
20+
returnsolve(getInput());
21+
}
22+
23+
publicstaticvoidmain(String[]args) {
24+
newPart01().run();
25+
}
26+
27+
}
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
packagecom.codefork.aoc2024.day23;
2+
3+
importcom.codefork.aoc2024.Problem;
4+
importcom.codefork.aoc2024.util.Assert;
5+
6+
importjava.util.stream.Stream;
7+
8+
publicclassPart02extendsProblem {
9+
10+
publicStringsolve(Stream<String>data) {
11+
varedges =Network.parseEdges(data);
12+
varwalker =NetworkFinder.seed(edges);
13+
varnetwork =walker.findLargestNetwork();
14+
returnnetwork.toString();
15+
}
16+
17+
@Override
18+
publicStringsolve() {
19+
Assert.assertEquals("co,de,ka,ta",solve(getSampleInput()));
20+
returnsolve(getInput());
21+
}
22+
23+
publicstaticvoidmain(String[]args) {
24+
newPart02().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)
[8]ページ先頭
©2009-2025 Movatter.jp