EnEnCode

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)
}

pub fn day05(input: &str) -> (u64, u64) {
    let mut part1 = 0;
    let mut part2 = 0;
    let mut ranges = Vec::new();
    let mut lines = input.trim().lines();
    for line in lines.by_ref() {
        if line.is_empty() {
            break;
        }
        let range = line
            .split_once('-')
            .map(|(l, h)| [l.parse::<u64>().unwrap(), h.parse::<u64>().unwrap()])
            .unwrap();
        ranges.push(range);
    }
    let ranges = combine_ranges(ranges);
    for idx in lines {
        for r in ranges.iter() {
            if (r[0]..=r[1]).contains(&idx.parse::<u64>().unwrap()) {
                part1 += 1;
                break;
            }
        }
    }
    for r in ranges {
        part2 += r[1] - r[0] + 1;
    }
    (part1, part2)
}

fn combine_ranges(ranges: Vec<[u64; 2]>) -> Vec<[u64; 2]> {
    let mut temp_ranges = ranges;
    let mut comp_ranges: Vec<[u64; 2]> = Vec::new();
    let mut run_again: bool = true;
    while run_again {
        run_again = false;
        comp_ranges = Vec::new();
        'outer: for i in 0..temp_ranges.len() {
            for j in 0..comp_ranges.len() {
                if temp_ranges[i][0] <= comp_ranges[j][0] && comp_ranges[j][1] <= temp_ranges[i][1]
                {
                    //temp covers all of comp
                    comp_ranges[j][0] = temp_ranges[i][0];
                    comp_ranges[j][1] = temp_ranges[i][1];
                    run_again = true;
                    continue 'outer;
                } else if comp_ranges[j][0] <= temp_ranges[i][0]
                    && temp_ranges[i][1] <= comp_ranges[j][1]
                {
                    //comp covers all of temp
                    run_again = true;
                    continue 'outer;
                } else if temp_ranges[i][0] <= comp_ranges[j][0]
                    && comp_ranges[j][0] <= temp_ranges[i][1]
                    && temp_ranges[i][1] <= comp_ranges[j][1]
                {
                    //grow left
                    comp_ranges[j][0] = temp_ranges[i][0];
                    run_again = true;
                    continue 'outer;
                } else if comp_ranges[j][0] <= temp_ranges[i][0]
                    && temp_ranges[i][0] <= comp_ranges[j][1]
                    && comp_ranges[j][1] <= temp_ranges[i][1]
                {
                    //grow right
                    comp_ranges[j][1] = temp_ranges[i][1];
                    run_again = true;
                    continue 'outer;
                }
            }
            comp_ranges.push(temp_ranges[i]);
        }
        temp_ranges = comp_ranges.clone();
    }

    comp_ranges
}