On Day 5 we’re mapping lines onto a 2D plane/grid and counting the number of intersections (well not exactly that, but close enough.)
The input lines are all either horizontal, vertical, or perfectly at 45 degrees. For part one you need to filter out the ones at 45 degrees.
For my solution, I created classes to represent points, lines and the grid itself. Then I regex’d the input into 4 integers representing x1,y1 and x2,y2 to create a line. I then asked the grid to map the line onto itself, which had it ask the line for all of its constituent points to do the mapping. To get the result you just ask the grid to count all the points where the number of intersections is at or above the threshold.
Here’s my basic Point class, this is practically boilerplate to most developers I assume, to the point (no pun intended) that there is no point (no pun intended again) to spoiler blur it:
final class Point
{
final int x;
final int y;
Point(final int x, final int y)
{
this.x = x;
this.y = y;
}
int getX()
{
return x;
}
int getY()
{
return y;
}
}
The line class is only slightly less boilerpoint because the conversion to points is mildly tricky:
final class Line
{
final int x1;
final int y1;
final int x2;
final int y2;
// For part 1 we need to filter on only horizontal or vertical lines
final boolean isHorizontal;
final boolean isVertical;
Line(final int x1, final int y1, final int x2, final int y2)
{
this.x1=x1;
this.y1=y1;
this.x2=x2;
this.y2=y2;
if (x1==x2) isVertical = true; else isVertical = false;
if (y1==y2) isHorizontal = true; else isHorizontal = false;
}
Point[] getPointsOnLine()
{
// For 45 degree lines both values will be identical, otherwise one will be 1
final int lineLen = Math.max(getSize(x1,x2), getSize(y1,y2));
final Point[] result = new Point[lineLen];
int x=x1;
int y=y1;
int xdir=0;
if (x1<x2) xdir=1;
if (x2<x1) xdir=-1;
int ydir=0;
if (y1<y2) ydir=1;
if (y2<y1) ydir=-1;
for (int i=0; i<lineLen; i++)
{
final Point p = new Point(x, y);
x+=xdir;
y+=ydir;
result[i] = p;
}
return result;
}
private static int getSize(final int val1, final int val2)
{
final int result;
if (val1<=val2)
result = val2-val1+1;
else
result = val1-val2+1;
return result;
}
@Override
public String toString()
{
return String.format("Line[%d,%d -> %d,%d]", x1,y1, x2,y2);
}
}
And the grid class is hardly tricky at all, I don’t think there is anything here that isn’t obvious, so no point blurring any:
final class GridForLines
{
final int[][] grid;
final int width;
final int height;
GridForLines(final int width, final int height)
{
this.width = width;
this.height = height;
grid = new int[width][height];
}
void mapALineIntoGrid(final Line lineToMap)
{
final Point[] points = lineToMap.getPointsOnLine();
for(final Point p : points)
{
grid[p.getX()][p.getY()]++;
}
}
int getNumberOfPointsWithSpecifiedNumberOfLinesOrMore(final int numberOfLines)
{
int result = 0;
for(final int[] row: grid)
{
for(final int i: row)
{
if (i>=numberOfLines) result++;
}
}
return result;
}
@Override
public String toString()
{
final StringBuilder sb = new StringBuilder();
for (int x=0; x<width; x++)
{
for (int y=0; y<height; y++)
{
sb.append(String.format("[%2d] ", grid[x][y]));
}
sb.append("\n");
}
return sb.toString();
}
}
The rest of the code is just the “problem” of parsing the input and pulling it all together, here’s the code for part one which is actually more code than part two because you need to filter the 45 degree lines out. Again, I don’t think there is anything here that’s not obvious, so no point blurring anything. I did pass in the grid size as a parameter, so I could reasonably debug the provided example, but I made it 1000 for the sample input as I did a quick look through mine and didn’t see anything bigger than three digits.
public static long getPart1Answer(final String day05Input, final String[] day05InputLines, final int gridSize)
{
final Pattern p = Pattern.compile(" *(\\d+),(\\d+) *-> *(\\d+),(\\d+)");
final GridForLines grid = new GridForLines(gridSize, gridSize);
for (final String lineDescription : day05InputLines)
{
final Matcher m = p.matcher(lineDescription);
if (!m.matches()) throw new IllegalStateException("Couldn't parse line description: " + lineDescription);
final Line line = new Line(
Integer.parseInt(m.group(1)),
Integer.parseInt(m.group(2)),
Integer.parseInt(m.group(3)),
Integer.parseInt(m.group(4)));
if (line.isHorizontal || line.isVertical)
{
grid.mapALineIntoGrid(line);
}
}
return grid.getNumberOfPointsWithSpecifiedNumberOfLinesOrMore(2);
}