I'll be doing today's puzzles in Java. Java is the gold standard for mediocre object-oriented languages; I'm sure you've heard of it. It has a weak type system and a heavy-handed emphasis on a very tedious style of essentially OO-bolted-onto-C, although with the welcome addition of garbage collection. Despite the many mistakes in its design, it ends up being a mostly-fine language for actual software development, primarily due to its API's and 3rd-party libraries. It's also commonly used in CS education, where it's one of the worst mainstream choices you could make. Especially for lower-level students, Java shoves your nose in far too many advanced, heavyweight concepts in unavoidable ways, while also making it unnecessarily difficult to play around with other ideas than the ones it was designed for, including the most fundamental building blocks of abstraction. This leads to a kind of "fake it 'til you make it" approach that sets programmers up to go a lifetime without ever really knowing what they're doing. Do your part to make better programmers in the future: discourage newbies from starting with Java.
For today's first task, we start with a grid of empty spaces
represented by .s and antennas represented by letters or digits.
Letters can be uppercase or lowercase, and are case-sensitive, and the
letter/digit is that antenna's "frequency." We want to count the
number of antinodes on the grid. An antinode is a space in line with 2
antennas of the same frequency where the distance between that space
and the nearer antenna is half the distance from this space to the
farther antenna, ie, if you think of the two antennas as being the two
ends of a chess move, we want to make that move again one time farther
out in each direction to find the antinodes. Any 2 antennas with the
same frequency will create 2 antinodes (although one or both may be
off the grid, in which case we don't care). Antinodes can appear on
top of antennas.
We will begin by defining a Point class for representing a 2D
point. The class is about as simple as they come, but if you're new to
Java, note that we override the equals and hashCode methods; this
will allow us to use Point instances as keys in Maps and Sets:
class Point {
private final int x;
private final int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
Point point = (Point) obj;
return x == point.x && y == point.y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
}
Now we can begin on the main class by reading the input file into a
stream of lines using java.nio, and then using those to initialise
an instance of an AntinodeCounter class which will provide a
countAntinodes method:
public class AntinodeCounter {
public static void main(String[] args) throws IOException {
Stream<String> lines = Files.lines(Path.of("2024/input/day-08.txt"));
AntinodeCounter counter = new AntinodeCounter(lines);
System.out.println(counter.countAntinodes());
}
}
As we process the input lines, we'll want to save information in two maps:
Points to the character that was at that
location in the grid.List of the Points
that contain an antenna of that frequency.We'll also want to save the dimensions of the grid so that we can do bounds-checking later. The simplest way to write this code only really lends itself to keeping track of the height as we process the file, but fortunately we can take advantage of the fact that the inputs are both square:
private Map<Point, Character> pointContent;
private Map<Character, List<Point>> antennas;
private int width;
private int height;
public AntinodeCounter(Stream<String> lines) {
pointContent = new HashMap<>();
antennas = new HashMap<>();
// Mutable wrapper
int[] row = {0};
lines.forEach(line -> {
for (int column = 0; column < line.length(); ++column) {
Point point = new Point(row[0], column);
char content = line.charAt(column);
pointContent.put(point, content);
if (isAntenna(content)) {
antennas.putIfAbsent(content, new ArrayList<>());
antennas.get(content).add(point);
}
}
++row[0];
});
width = height = row[0];
}
private boolean isAntenna(char content) {
return content != '.';
}
To count the antinodes, we can loop over each frequency, go through
every 2-element permutation from the list of Points with that
frequency in antennas, calculate the x- and y-distance between the
points, and then apply them to create our new antinodes, storing them
in a Set if they're in-bounds, and finally returning the size of the
set. With the helper methods isInBounds and antennaPairs, the code
is simple:
public int countAntinodes() {
Set<Point> antinodes = new HashSet<>();
for (char frequency : antennas.keySet()) {
for (List<Point> antennaPair : antennaPairs(frequency)) {
int dx = antennaPair.get(1).getX() - antennaPair.get(0).getX();
int dy = antennaPair.get(1).getY() - antennaPair.get(0).getY();
Point[] newAntinodes = {
new Point(antennaPair.get(0).getX() - dx, antennaPair.get(0).getY() - dy),
new Point(antennaPair.get(1).getX() + dx, antennaPair.get(1).getY() + dy),
};
for (Point antinode : newAntinodes) {
if (isInBounds(antinode)) antinodes.add(antinode);
}
}
}
return antinodes.size();
}
private boolean isInBounds(Point point) {
return point.getX() >= 0 && point.getX() < width &&
point.getY() >= 0 && point.getY() < height;
}
private List<List<Point>> antennaPairs(char frequency) {
List<Point> antennasWithFrequency = antennas.get(frequency);
List<List<Point>> result = new ArrayList<>();
for (Point pointA : antennasWithFrequency) {
for (Point pointB : antennasWithFrequency) {
if (pointA.equals(pointB)) continue;
result.add(Arrays.asList(pointA, pointB));
}
}
return result;
}
For part 2, we need to modify the program so that instead of 1 antinode in each direction of the original antenna pair, there should now be an antinode on every space in that line in the grid (taking the gap between the two original points as a "chess move" that creates the line), including on those antennas themselves.
This is a very easy change. Inside of countAntinodes, we only need to change it from a hardcoded one-antinode-in-each-direction approach that ignores out-of-bounds antinodes into two loops that start at each of the antennas and count up and down by dx/dy until they're out-of-bounds:
// ...
int dy = antennaPair.get(1).getY() - antennaPair.get(0).getY();
int x = antennaPair.get(0).getX();
int y = antennaPair.get(0).getY();
for (Point antinode = new Point(x, y); isInBounds(antinode); antinode = new Point(antinode.getX() - dx, antinode.getY() - dy)) {
antinodes.add(antinode);
}
x = antennaPair.get(1).getX();
y = antennaPair.get(1).getY();
for (Point antinode = new Point(x, y); isInBounds(antinode); antinode = new Point(antinode.getX() + dx, antinode.getY() + dy)) {
antinodes.add(antinode);
}
}
}