advent-of-code-2019/src/day_3/puzzle_2.rs

use std::fs::File;
use std::io::{BufRead, BufReader};

/*
--- Part Two ---

It turns out that this circuit is very timing-sensitive; you actually need to minimize the signal
delay.

To do this, calculate the number of steps each wire takes to reach each intersection; choose the
intersection where the sum of both wires' steps is lowest. If a wire visits a position on the grid
multiple times, use the steps value from the first time it visits that position when calculating
the total value of a specific intersection.

The number of steps a wire takes is the total number of grid squares the wire has entered to get to
that location, including the intersection being considered. Again consider the example from above:

...........
.+-----+...
.|.....|...
.|..+--X-+.
.|..|..|.|.
.|.-X--+.|.
.|..|....|.
.|.......|.
.o-------+.
...........

In the above example, the intersection closest to the central port is reached after 8+5+5+2 = 20
steps by the first wire and 7+6+4+3 = 20 steps by the second wire for a total of 20+20 = 40 steps.

However, the top-right intersection is better: the first wire takes only 8+5+2 = 15 and the second
wire takes only 7+6+2 = 15, a total of 15+15 = 30 steps.

Here are the best steps for the extra examples from above:

    R75,D30,R83,U83,L12,D49,R71,U7,L72
    U62,R66,U55,R34,D71,R55,D58,R83 = 610 steps
    R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51
    U98,R91,D20,R16,D67,R40,U7,R15,U6,R7 = 410 steps

What is the fewest combined steps the wires must take to reach an intersection?
*/

#[derive(Copy, Clone)]
struct Point {
    x: i32,
    y: i32,
}

impl Point {
    pub fn manhattan_dist_to(&self, other: Point) -> i32 {
        let x_dist = (self.x - other.x).abs();
        let y_dist = (self.y - other.y).abs();

        x_dist + y_dist
    }

    pub fn equals(&self, other: Point) -> bool {
        self.x == other.x && self.y == other.y
    }
}

struct Segment {
    p1: Point,
    p2: Point,
    x_min: i32,
    x_max: i32,
    y_min: i32,
    y_max: i32,
    steps: i32,
}

impl Segment {
    pub fn new(p1: Point, p2: Point) -> Segment {
        let x_min = if p1.x < p2.x { p1.x } else { p2.x };
        let x_max = if p1.x > p2.x { p1.x } else { p2.x };
        let y_min = if p1.y < p2.y { p1.y } else { p2.y };
        let y_max = if p1.y > p2.y { p1.y } else { p2.y };

        Segment {
            p1: p1,
            p2: p2,
            x_min: x_min,
            x_max: x_max,
            y_min: y_min,
            y_max: y_max,
            steps: (p1.x - p2.x).abs() + (p1.y - p2.y).abs(),
        }
    }

    pub fn intersects(&self, other: &Segment) -> Option<Point> {
        // make an assumption that segments never overlap, e.g. intersections are always
        // perpendicular

        // self is horizontal, other is vertical
        if self.x_min <= other.x_min
            && self.x_max >= other.x_max
            && other.y_min <= self.y_min
            && other.y_max >= self.y_max
        {
            Some(Point {
                x: other.x_min,
                y: self.y_min,
            })
        // self is vertical, other is horizontal
        } else if other.x_min <= self.x_min
            && other.x_max >= self.x_max
            && self.y_min <= other.y_min
            && self.y_max >= other.y_max
        {
            Some(Point {
                x: self.x_min,
                y: other.y_min,
            })
        } else {
            None
        }
    }

    pub fn steps_to_point(&self, point: Point) -> i32 {
        (self.p1.x - point.x).abs() + (self.p1.y - point.y).abs()
    }
}

type RawWire = Vec<String>;
type Wire = Vec<Segment>;

fn get_raw_wires() -> (RawWire, RawWire) {
    let file = File::open("./src/day_3/puzzle_1.txt").expect("no such file");
    let mut buf = BufReader::new(file);

    let mut raw_wire1 = String::new();
    let _ = buf.read_line(&mut raw_wire1);

    let mut raw_wire2 = String::new();
    let _ = buf.read_line(&mut raw_wire2);

    (
        raw_wire1
            .trim()
            .split(',')
            .map(|seg| seg.to_owned())
            .collect(),
        raw_wire2
            .trim()
            .split(',')
            .map(|seg| seg.to_owned())
            .collect(),
    )
}

fn parse_raw_wire(raw: RawWire) -> Wire {
    let mut wire = Wire::new();

    let mut point = Point { x: 0, y: 0 };

    for seg in raw {
        let (dir, str_amt) = seg.split_at(1);
        let amt = str_amt.parse::<i32>().expect("could not parse segment");

        let mut new_point = point;

        match dir {
            "U" => new_point.x += amt,
            "D" => new_point.x -= amt,
            "L" => new_point.y -= amt,
            "R" => new_point.y += amt,
            _ => panic!(),
        }

        wire.push(Segment::new(point, new_point));
        point = new_point;
    }

    wire
}

pub fn solve() {
    let (raw_wire1, raw_wire2) = get_raw_wires();
    let wire1 = parse_raw_wire(raw_wire1);
    let wire2 = parse_raw_wire(raw_wire2);

    let mut min_steps = i32::max_value();
    let origin = Point { x: 0, y: 0 };

    let mut steps: i32 = 0;
    for seg1 in wire1 {
        let mut seg2_steps = 0;

        for seg2 in &wire2 {
            match seg2.intersects(&seg1) {
                Some(p) => {
                    let total =
                        steps + seg2_steps + seg1.steps_to_point(p) + seg2.steps_to_point(p);

                    if total < min_steps && !p.equals(origin) {
                        min_steps = total;
                    }
                }
                None => (),
            }
            seg2_steps += seg2.steps;
        }
        steps += seg1.steps;
    }

    println!("min steps: {}", min_steps);
}