Skip to content

Commit 4329c24

Browse files
codeforkjeffcodeforkjeff
committed
day 14 part 2; add notes to journal
1 parent 57a3cdf commit 4329c24

File tree

4 files changed

+110
-134
lines changed

4 files changed

+110
-134
lines changed

‎README.md

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -125,3 +125,22 @@ Day 23 was one of those problems where I took an entirely different approach in
125125
Usually when this happens, I "align" the two solutions so they re-use the same code. I started to do that
126126
after finishing part 2 but the approaches are so algorithmically different that I decided it wasn't worth
127127
the energy.
128+
129+
(time passes)
130+
131+
Well, I've finished a solid pass through all the problems. Here's what I need to return to:
132+
133+
```
134+
Day 14 part 2 = finding the christmas tree
135+
Day 17 part 2 = [quine](https://en.wikipedia.org/wiki/Quine_(computing))-ish problem
136+
Day 21 part 2 = keypad problem
137+
Day 24 part 2 = find 4 swaps of logic gates to make addition work
138+
```
139+
140+
I think I can do 14 and 21, if I put my mind to it. Honestly, I'm not sure about the other two.
141+
For those, I may ask my friend Rob who's also doing AoC this year, or look at reddit, instead of beating my
142+
head against a wall. Which I did for WEEKS for some problems during AoC 2018. Which was not healthy.
143+
144+
(more time passes)
145+
146+
Hey I figured out day 14!

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

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
package com.codefork.aoc2024.day14;
2+
3+
import com.codefork.aoc2024.Problem;
4+
5+
import java.util.stream.Stream;
6+
7+
public class Part02 extends Problem {
8+
9+
public String solve(int width, int height, Stream<String> data) {
10+
// I tried a bunch of different strategies, including looking for unbalanced robot
11+
// counts in different quadrants, thinking that the quadrant stuff in part 1 was a hint.
12+
// I couldn't get that to work. after stepping away from it for over a week,
13+
// I thought to try a different approach: just look for clusters of adjacent robots,
14+
// since a picture is likely to have such clusters. at a low threshold, it displayed
15+
// a few false positives before yielding the answer, so it was just a matter of increasing
16+
// the threshold to something reasonable once I knew what the Christmas tree actually looked like.
17+
18+
System.out.println("This takes ~40 seconds");
19+
var swarm = Swarm.create(data, width, height);
20+
var keepGoing = true;
21+
var i = 0;
22+
while(keepGoing) {
23+
var newSwarm = swarm.doMoves(1);
24+
25+
var adjacentClusters = newSwarm.getAdjacentClusters();
26+
27+
var hasLines = adjacentClusters.stream().anyMatch(cluster ->
28+
cluster.size() > 20);
29+
30+
if(hasLines) {
31+
newSwarm.print();
32+
keepGoing = false;
33+
} else {
34+
swarm = newSwarm;
35+
i++;
36+
}
37+
}
38+
39+
return String.valueOf(i+1);
40+
}
41+
42+
@Override
43+
public String solve() {
44+
return solve(101, 103, getInput());
45+
}
46+
47+
public static void main(String[] args) {
48+
new Part02().run();
49+
}
50+
}

‎src/main/java/com/codefork/aoc2024/day14/Part02.java.bak

Lines changed: 0 additions & 83 deletions
This file was deleted.

‎src/main/java/com/codefork/aoc2024/day14/Swarm.java

Lines changed: 41 additions & 51 deletions
Original file line numberDiff line numberDiff line change
@@ -2,8 +2,11 @@
22

33
import com.codefork.aoc2024.util.Maps;
44

5+
import java.util.ArrayList;
6+
import java.util.HashSet;
57
import java.util.List;
68
import java.util.Map;
9+
import java.util.Set;
710
import java.util.regex.Pattern;
811
import java.util.stream.Collectors;
912
import java.util.stream.IntStream;
@@ -14,7 +17,11 @@
1417
public record Swarm(List<Robot> robots, int width, int height) {
1518

1619
public record Position(int x, int y) {
17-
20+
public boolean isAdjacent(Position other) {
21+
var xDiff = Math.abs(other.x() - x);
22+
var yDiff = Math.abs(other.y() - y);
23+
return xDiff + yDiff <= 1;
24+
}
1825
}
1926

2027
public record Velocity(int dx, int dy) {
@@ -116,58 +123,41 @@ public Map<Integer, Integer> getQuadrantCounts() {
116123
));
117124
}
118125

119-
/**
120-
* testing for part 2: try smaller sections
121-
*/
122-
public Map<Integer, Integer> getCustomSectionCounts() {
123-
var byQuadrant = robots.stream()
124-
.collect(Collectors.groupingBy(
125-
(robot) -> {
126-
if (robot.position().y() < height / 3) {
127-
if (robot.position().x() < width / 2) {
128-
return 0;
129-
} else if (robot.position().x() > width / 2) {
130-
return 1;
131-
}
132-
} else if (robot.position().y() > height / 3 && robot.position().y() < (height / 3) * 2) {
133-
if (robot.position().x() < width / 2) {
134-
return 2;
135-
} else if (robot.position().x() > width / 2) {
136-
return 3;
137-
}
138-
} else if (robot.position().y() > (height / 3) * 2) {
139-
if (robot.position().x() < width / 2) {
140-
return 4;
141-
} else if (robot.position().x() > width / 2) {
142-
return 5;
143-
}
144-
}
145-
// put the robots on the center lines in a separate group
146-
// that we'll discard
147-
return DISCARD;
148-
})
149-
);
150-
return byQuadrant.entrySet().stream()
151-
.filter(entry -> entry.getKey() != DISCARD)
152-
.collect(Collectors.toMap(
153-
Map.Entry::getKey,
154-
entry -> {
155-
// count occupied positions rather than robots, since they can be stacked, and we only
156-
// care about what they look like from above
157-
record Pos(int x, int y) {
158-
}
159-
var list = entry.getValue();
160-
var occupiedPositions = list.stream()
161-
.map(robot -> new Pos(robot.position().x(), robot.position().y()))
162-
.collect(Collectors.toSet());
163-
return occupiedPositions.size();
164-
},
165-
Integer::sum
166-
));
167-
}
168-
169126
public int getSafetyFactor() {
170127
return getQuadrantCounts().entrySet().stream()
171128
.reduce(1, (acc, entry) -> acc * entry.getValue(), Integer::sum);
172129
}
130+
131+
/**
132+
* Look for groups of adjacent robots. this returns a list of sets of positions, not
133+
* the Robots themselves, because we only care about positions. We actually only care about the
134+
* existence of clusters, not even the positions.
135+
*/
136+
public List<Set<Position>> getAdjacentClusters() {
137+
var clusters = new ArrayList<Set<Position>>();
138+
for(var robot : robots()) {
139+
var position = robot.position();
140+
141+
var newClusters = new ArrayList<Set<Swarm.Position>>();
142+
143+
var mergedCluster = new HashSet<Position>();
144+
for(var cluster : clusters) {
145+
var belongs = cluster.stream().anyMatch(p -> p.isAdjacent(position));
146+
if(belongs) {
147+
mergedCluster.addAll(cluster);
148+
mergedCluster.add(position);
149+
} else {
150+
newClusters.add(cluster);
151+
}
152+
}
153+
if(mergedCluster.isEmpty()) {
154+
mergedCluster.add(position);
155+
}
156+
newClusters.add(mergedCluster);
157+
158+
clusters = newClusters;
159+
}
160+
return clusters;
161+
}
162+
173163
}

0 commit comments

Comments
 (0)