Advent of code 2021: Day 5
This article is part of a series where I'll be diving head first into the Advent of code 2021. I'll be documenting the challenge of solving such a puzzle and how I got to the answer. I want to prefix this by stating that I can't cheat for any of these challenges; with that, I mean I can't look up any other implementations online.
In this article I'll be solving: Advent of code 2021: Day #5.
Part 1
The puzzle gives you an input file with a bunch of lines in it. The lines are formatted like such:
0,9 -> 5,9
8,0 -> 0,8
9,4 -> 3,4
2,2 -> 2,1
7,0 -> 7,4
6,4 -> 2,0
0,9 -> 2,9
3,4 -> 1,4
0,0 -> 8,8
5,5 -> 8,2
A line goes from a starting point (0,9) to an end point (5,9). This means that the first line’s coordinates are: [(0,9), (1,9), (2,9), (3,9), (4,9), (5,9)]. The first puzzle wants to know how many times a line intersects more than 1 time (so; 2 times or more) at a certain coordinate (or point).
For the first part, only horizontal or vertical lines are considered. To set up this puzzle, I started out with writing a Point and a Line struct:
#[derive(Debug)]
struct Point {
x: u32,
y: u32
}
#[derive(Debug)]
struct Line {
p1: Point,
p2: Point
}
impl Line {
fn from(input: &str) -> Line {
let points: Vec<Vec<u32>> = input
.split(" -> ")
.map(|coords|
coords
.split(",")
.map(|n| n.parse::<u32>().unwrap())
.collect()
)
.collect();
Line {
p1: Point { x: points[0][0], y: points[0][1] },
p2: Point { x: points[1][0], y: points[1][1] }
}
}
}
With the Line#from-method, I can initialize Line objects from string slices. The next methods to define are is_horizontal() and is_vertical() which are fairly straightforward - even the puzzle itself describes how to do this:
impl Line {
fn from(input: &str) -> Line {
// ...
}
pub fn is_horizontal(&self) -> bool {
self.p1.x == self.p2.x
}
pub fn is_vertical(&self) -> bool {
self.p1.y == self.p2.y
}
}
The next part is the tricky bit, but we have to define the coordinates that form between two lines. Considering that only horizontal lines and vertical lines are valid, we’ll use a simple two-dimensional loop to generate said coordinates:
pub fn points(&self) -> Vec<Point> {
let mut points = vec![];
if !self.is_horizontal() && !self.is_vertical() {
return points
}
let (minx, maxx) = if self.p1.x > self.p2.x {
(self.p2.x, self.p1.x)
} else {
(self.p1.x, self.p2.x)
};
let (miny, maxy) = if self.p1.y > self.p2.y {
(self.p2.y, self.p1.y)
} else {
(self.p1.y, self.p2.y)
};
for x in minx..=maxx {
for y in miny..=maxy {
points.push(Point { x: x, y: y });
}
}
points
}
The way to resolve part 1 is like such:
fn two_line_overlaps(input: &Vec<&str>) -> usize {
let mut point_counts: HashMap<Point, u32> = HashMap::new();
for line in input {
let l = Line::from(line);
for p in l.points() {
let counter = point_counts.entry(p).or_insert(0);
*counter += 1;
}
}
point_counts.iter().filter(|(_, &count)| count >= 2).count()
}
Because Point needs to be put into a HashMap, some traits need to be implemented on Point, namely the following:
#[derive(Debug, Hash, Eq)]
struct Point {
x: u32,
y: u32
}
impl PartialEq for Point {
fn eq(&self, other: &Self) -> bool {
self.x == other.x && self.y == other.y
}
}
Part 2
The next part is the same question as the previous part, but including diagonal lines as well. Where we first rejected them, right now we actually need to include them. The diagonal lines are all at an angle of 45 degrees, meaning we don’t have to do anything too complicated. The way I resolved this, is like such:
fn list_coords(&self, m1: u32, m2: u32) -> Vec<u32> {
let mut list = vec![];
let (min, max, pos) = if m1 > m2 {
(m2, m1, None)
} else {
(m1, m2, Some(0))
};
for m in min..=max {
let position = match pos {
Some(n) => n,
None => list.len()
};
list.insert(position, m);
}
list
}
pub fn points(&self) -> Vec<Point> {
let mut points = vec![];
let xlist = self.list_coords(self.p1.x, self.p2.x);
let ylist = self.list_coords(self.p1.y, self.p2.y);
let mut xlist_iter = xlist.iter();
let mut ylist_iter = ylist.iter();
loop {
let point = match (xlist_iter.next(), ylist_iter.next()) {
(Some(x), Some(y)) => Point {x: *x, y: *y },
(Some(x), None) => Point { x: *x, y: self.p1.y },
(None, Some(y)) => Point { x: self.p1.x, y: *y },
(None, None) => break
};
points.push(point)
}
points
}
The list_coords-method gives a list of x coordinates and y coordinates in descending order depending on the direction of the line. The points-method has been rewritten to a zip-method, which will continue until both lists are consumed. In horizontal and vertical cases, the lines can have only one single x or y value.
The two_line_overlaps() method, which I described earlier, will remain in a similar form, however to make it work for both part 1 and part 2, I added an extra argument:
fn two_line_overlaps(input: &Vec<&str>, incl_diagonals: bool) -> usize {
let mut point_counts: HashMap<Point, u32> = HashMap::new();
for line in input {
let l = Line::from(line);
if incl_diagonals || l.is_horizontal() || l.is_vertical() {
for p in l.points() {
let counter = point_counts.entry(p).or_insert(0);
*counter += 1;
}
}
}
point_counts.iter().filter(|(_, &count)| count >= 2).count()
}
This way I can solve both part 1 and part 2 like such:
fn main() {
let input = fs::read_to_string("lines")
.unwrap_or("".to_string());
let lines: Vec<&str> = input
.split_terminator("\n")
.collect();
println!(
"Amount of overlaps >= 2 (no diagonals): {:?}",
two_line_overlaps(&lines, false)
);
println!(
"Amount of overlaps >= 2 (incl. diagonals): {:?}",
two_line_overlaps(&lines, true)
);
}
Voilà! Solved, and another two stars added. ⭐️⭐️
The full solution is available on GitHub.
