day03.rs

use std::fs::File;
use std::error::Error;
use std::fmt;
use std::io::{BufRead, BufReader};
use std::time::Instant;

type LazyResult<T> = Result<T, Box<dyn Error>>;

#[derive(Debug)]
struct InvalidDirection(char);
impl fmt::Display for InvalidDirection {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{:?}", self)
    }
}
impl Error for InvalidDirection { }

enum Direction {
    Up,
    Down,
    Left,
    Right,
}

impl Direction {
    pub fn from_chr(chr: char) -> Result<Direction, InvalidDirection> {
        let result = match chr {
            'U' => Direction::Up,
            'D' => Direction::Down,
            'L' => Direction::Left,
            'R' => Direction::Right,
            _ => return Err(InvalidDirection(chr))
        };
        Ok(result)
    }
}

type LineInput = Vec<(Direction, isize)>;

fn parse_line(line: &str) -> LazyResult<LineInput> {
    line.split(',')
        .map(|segment| {
            let chr = segment.chars().next().unwrap_or('\0');
            let direction = Direction::from_chr(chr)?;
            let distance = segment[1..].parse::<isize>()?;
            Ok((direction, distance))
        })
        .collect()
}

fn read_input() -> LazyResult<Vec<LineInput>> {
    let file_handle = File::open("day03-input.txt")?;
    let reader = BufReader::new(file_handle);
    reader.lines()
        .map(|line| parse_line(line?.trim()))
        .collect()
}

#[derive(Debug, Clone)]
struct HSegment {
    y: isize,
    min_x: isize,
    max_x: isize,
    wire_index: usize,
    // how many steps does it take to get to the start of this segment
    steps: isize,
    // remember the start of the segment because wire direction may be the opposite
    start_x: isize,
}

#[derive(Debug, Clone)]
struct VSegment {
    x: isize,
    min_y: isize,
    max_y: isize,
    wire_index: usize,
    // how many steps does it take to get to the start of this segment
    steps: isize,
    // remember the start of the segment because wire direction may be the opposite
    start_y: isize,
}

#[derive(Debug)]
struct Point {
    x: isize,
    y: isize,
    // total steps for wires to get here
    steps: isize,
}

// https://www.hackerearth.com/practice/math/geometry/line-intersection-using-bentley-ottmann-algorithm/tutorial/
// Line Intersection using Bentley Ottmann Algorithm
fn find_intersections(
    h_segments: &mut[HSegment],
    v_segments: &mut[VSegment])
    -> Vec<Point>
{
    // list of horizontal segments that cover current X
    let mut current_hs = Vec::new();
    let mut result = Vec::new();

    // sort input segments for horizontal sweep
    h_segments.sort_by_key(|segment| segment.min_x);
    v_segments.sort_by_key(|segment| segment.x);

    let mut h_seg_slice = &h_segments[..];

    // sweep over x using vertical lines positions
    for v_segment in v_segments.iter() {
        let x = v_segment.x;
        // add horizontal lines if we swept over their start
        while let Some((segment, rest)) = h_seg_slice.split_first() {
            if segment.min_x < x {
                current_hs.push(segment.clone());
                h_seg_slice = rest;
            } else {
                break;
            }
        }

        // remove horizontal lines if we swept over their end
        current_hs.retain(|segment| segment.max_x > x);

        for h_segment in current_hs.iter() {
            // check if vertical and horizontal lines are intersecting
            if v_segment.min_y < h_segment.y &&
                v_segment.max_y > h_segment.y &&
                // only add intersections if the wires are different
                v_segment.wire_index != h_segment.wire_index
            {
                let y = h_segment.y;
                let x = v_segment.x;

                // calculate how many steps does it take for each wire to get here
                let v_steps = v_segment.steps + (v_segment.start_y - y).abs();
                let h_steps = h_segment.steps + (h_segment.start_x - x).abs();

                result.push(Point { x, y, steps: h_steps + v_steps });
            }
        }
    }

    result
}

fn main() -> LazyResult<()> {
    let read_start = Instant::now();
    let input = read_input()?;
    println!("parse time: {:?}", read_start.elapsed());

    let solution_start = Instant::now();

    let mut h_segments = Vec::new();
    let mut v_segments = Vec::new();

    for (wire_index, line) in input.iter().enumerate() {
        let mut x = 0;
        let mut y = 0;
        let mut steps = 0;
        for (dir, dist) in line.iter() {
            match dir {
                Direction::Up => {
                    let max_y = y + dist;
                    v_segments.push(VSegment { x, min_y: y, max_y, wire_index, steps, start_y: y });
                    y = max_y;
                }
                Direction::Down => {
                    let min_y = y - dist;
                    v_segments.push(VSegment { x, min_y, max_y: y, wire_index, steps, start_y: y });
                    y = min_y;
                }
                Direction::Left => {
                    let min_x = x - dist;
                    h_segments.push(HSegment { y, min_x, max_x: x, wire_index, steps, start_x: x });
                    x = min_x;
                }
                Direction::Right => {
                    let max_x = x + dist;
                    h_segments.push(HSegment { y, min_x: x, max_x, wire_index, steps, start_x: x });
                    x = max_x;
                }
            }

            steps += dist;
        }
    }

    let intersections = find_intersections(&mut h_segments, &mut v_segments);
    let part1 = intersections.iter()
        .map(|point| point.x.abs() + point.y.abs())
        .min();

    let part2 = intersections.iter()
        .map(|point| point.steps)
        .min();

    let solution_elapsed = solution_start.elapsed();

    println!("part 1: {:?}", part1);
    println!("part 2: {:?}", part2);
    println!("solution time: {:?}", solution_elapsed);

    Ok(())
}