Rust
The problem today just flustered me. Sometimes I'm not convinced I've gotten any better at programming since 2022 (yes, I still used that exact hack of a combine_ranges for this problem)
Runs on my Thinkpad P1 Gen2 in 180.9 +- 0.9 ms on external power (or 726.8 +- 2.1 ms on battery; can't remember how I configured performance/battery saver honestly lol)
solution
pub fn day09(input: &str) -> (u64, u64) {
let mut part1 = 0;
let mut part2 = 0;
let mut squares = Vec::new();
for line in input.trim().lines() {
let (x, y) = line.split_once(',').unwrap();
squares.push([x.parse::<u64>().unwrap(), y.parse::<u64>().unwrap()]);
}
let mut chunks = squares.chunks_exact(2).peekable();
let mut lines = Vec::new();
let peek = chunks.peek().unwrap();
// dir is true if scanning vertically, false if horizontally
let dir = peek[0][1] == peek[1][1];
if !dir {
debug_assert_eq!(peek[0][0], peek[1][0]);
}
// Each line is a tuple where .0 is the index in the scan direction and .1 is the pair of end
// points for a line perpendicular to the scan direction
for line in chunks {
lines.push((
line[0][dir as usize],
[line[0][!dir as usize], line[1][!dir as usize]],
));
}
lines.sort();
// rot is true if field 0 being less than field 1 enters the shape, false for exiting
let rot = lines[0].1[0] < lines[0].1[1];
for idx_1 in 0..squares.len() - 1 {
'o: for idx_2 in (idx_1 + 1)..squares.len() {
let s1 = squares[idx_1];
let s2 = squares[idx_2];
let area = (s1[0].abs_diff(s2[0]) + 1) * (s1[1].abs_diff(s2[1]) + 1);
part1 = std::cmp::max(part1, area);
if area <= part2 {
continue;
}
// Think of "up" as the direction the scan line travels
let floor = std::cmp::max(s1[dir as usize], s2[dir as usize]);
let ceil = std::cmp::min(s1[dir as usize], s2[dir as usize]);
let left_wall = std::cmp::min(s1[!dir as usize], s2[!dir as usize]);
let right_wall = std::cmp::max(s1[!dir as usize], s2[!dir as usize]);
let floor_idx = lines.binary_search_by_key(&floor, |(l, _)| *l).unwrap();
let ceil_idx = lines.binary_search_by_key(&ceil, |(l, _)| *l).unwrap();
// If a line contracts the valid range, check if that contraction intersects the walls,
// since that necessitates uncolored tiles in the bounding box
let skip = |line: [u64; 2]| {
if rot != (line[0] < line[1]) {
return (left_wall..right_wall).contains(&line[0])
|| (left_wall..right_wall).contains(&line[1]);
}
false
};
for line in &lines[ceil_idx..floor_idx] {
if skip(line.1) {
continue 'o;
}
}
let mut combo_ranges = Vec::new();
// This `rev` is needed for correctness, although the full input does not seem to care
// It actually hurts performance a lot :(
for line in lines[0..=ceil_idx].iter().rev() {
if skip(line.1) {
continue 'o;
}
if rot {
combo_ranges.push(line.1);
} else {
combo_ranges.push([line.1[1], line.1[0]]);
}
combo_ranges = combine_ranges(combo_ranges);
// If overlapping the target range results in no change of range, then the target
// range is fully covered and this rectangle is valid
let mut test_range = combo_ranges.clone();
test_range.push([left_wall, right_wall]);
if combo_ranges == combine_ranges(test_range) {
part2 = area;
continue 'o;
}
}
}
}
(part1, part2)
}