Day 5: Hydrothermal Venture

Day #5 problem description │ Problem input

This challenge requires iterating the integer points between two other points on the plane.

Setup

First, we read the input into a list of lines of the form $((x_1, y_1), (x_2, y_2))$ . We also define the helpful range_between(a, b) function, which returns the (nonempty!) range of integers between a and b, inclusive. The range is ascending if and only if a < b. (This is different from a..=b, which is empty if a > b.)

use crate::Answer;
use num::Integer;
use regex::Regex;
use std::{collections::BTreeMap as Map, str::FromStr};

#[derive(Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
struct Point<T>(T, T);
struct EndpointPair<T: Integer>(Point<T>, Point<T>);
type PointCounter<T> = Map<Point<T>, usize>;

fn get_lines<T: Integer + FromStr>(input: &str) -> Option<Vec<EndpointPair<T>>> {
	let line_re = Regex::new(r"(\d+),(\d+)\s*->\s*(\d+),(\d+)").ok()?;
	input
		.lines()
		.map(|line| {
			let caps = line_re.captures(line)?;
			let [x1, y1, x2, y2] = [1, 2, 3, 4].map(|i| caps.get(i)?.as_str().parse::<T>().ok());
			Some(EndpointPair(Point(x1?, y1?), Point(x2?, y2?)))
		})
		.collect::<Option<Vec<_>>>()
}

fn range_between(a: i32, b: i32) -> num::iter::RangeStepInclusive<i32> {
	let step = if a < b { 1 } else { -1 };
	num::range_step_inclusive(a, b, step)
}

fn get_ans<T>(counter: &PointCounter<T>) -> usize {
	counter
		.values()
		.map(|count| if *count >= 2 { 1 } else { 0 })
		.sum()
}

fn ans_for_input(input: &str) -> Answer<usize, usize> {
	let endpoints = get_lines(input).unwrap();
	(5, (pt1(&endpoints), pt2(&endpoints))).into()
}

pub fn ans() -> Answer<usize, usize> {
	let input = include_str!("input.txt");
	ans_for_input(input)
}

Part 1

Part 1 asks us to count how many times each point belongs to some horizontal or vertical line. These are lines $((x_1, y_1), (x_2, y_2))$ for which $x_1 = x_2$ or $y_1 = y_2$ . Such a line’s points are the Cartesian “product” of the ranges range_between(x1, x2) and range_between(y1, y2) (“product” in quotes because one of those ranges has length 1, so it’s not much of a product).

fn get_hv_point_counts(endpoints: &[EndpointPair<i32>]) -> PointCounter<i32> {
	let mut counter = Map::new();
	for &EndpointPair(Point(x1, y1), Point(x2, y2)) in endpoints {
		if x1 != x2 && y1 != y2 {
			continue;
		}
		for x in range_between(x1, x2) {
			for y in range_between(y1, y2) {
				*counter.entry(Point(x, y)).or_default() += 1;
			}
		}
	}
	counter
}

fn pt1(endpoints: &[EndpointPair<i32>]) -> usize {
	get_ans(&get_hv_point_counts(endpoints))
}

Part 2

Part 2 asks us to count how many times each point belongs to either a horizontal line, a vertical line, or a $45^\circ$ diagonal line (whose slope must be $\pm1$ ). We already found the points on horizontal and vertical lines in Part 1. Diagonal lines are lines $((x_1, y_1), (x_2, y_2))$ whose points $(x_k,y_k)$ satisfy $|x_k-x_1|=|y_k-y_1|$ with $x_k$ between $x_1$ and $x_2$ and $y_k$ between $y_k$ and $y_2$ (inclusive). Since the $k$ ^th element of range_between(a, b) is $k$ away from $a$ , the points of the diagonal line in question are in fact simply the elements of range_between(x1, x2).zip(range_between(y1, y2)).

fn get_diag_point_counts(endpoints: &[EndpointPair<i32>]) -> PointCounter<i32> {
	let mut counter = Map::new();
	for &EndpointPair(Point(x1, y1), Point(x2, y2)) in endpoints {
		if (x1 - x2).abs() != (y1 - y2).abs() {
			continue;
		}

		for (x, y) in range_between(x1, x2).zip(range_between(y1, y2)) {
			*counter.entry(Point(x, y)).or_default() += 1;
		}
	}

	counter
}

fn pt2(endpoints: &[EndpointPair<i32>]) -> usize {
	let hv_counter = get_hv_point_counts(endpoints);

	let all_counter = {
		let mut diag_counter = get_diag_point_counts(endpoints);

		for (k, v) in hv_counter {
			*diag_counter.entry(k).or_default() += v;
		}

		diag_counter
	};
	get_ans(&all_counter)
}