day3.rs

use std::io::{self, BufRead};

fn main() {
    let (w1, w2) = load_wires();
    let tw1 = transform_wire(&w1);
    let tw2 = transform_wire(&w2);
    let intersections = find_intersections(tw1, tw2);
    let dist = find_min_distance(&intersections);
    println!("Min distance: {}", dist);
    let steps = find_min_steps(&intersections, &w1, &w2);
    println!("Min total steps: {}", steps);
}

fn find_min_steps(intersections: &Vec<(i32, i32)>, w1: &Vec<((i32, i32), i32)>, w2: &Vec<((i32, i32), i32)>) -> i32 {
    let mut min_dist = std::i32::MAX;
    for i in intersections {
        let s1 = steps_to_point(w1, *i);
        let s2 = steps_to_point(w2, *i);
        min_dist = i32::min(min_dist, s1 + s2)
    }
    min_dist
}

fn steps_to_point(w: &Vec<((i32, i32), i32)>, p: (i32, i32)) -> i32 {
    let mut cx = 0;
    let mut cy = 0;
    let mut n_steps = 0;
    for seg in w {
        let ((dx, dy), steps) = seg;
        for _ in 0..*steps {
            n_steps += 1;
            cx = cx + dx;
            cy = cy + dy;
            if (cx, cy) == p {
                return n_steps
            }
        }
    }
    panic!("Could not find steps to point.")
}

fn find_min_distance(points: &Vec<(i32, i32)>) -> i32 {
    points.iter().map(
        |(x, y)| x.abs() + y.abs()
    ).fold(std::i32::MAX, i32::min)
}


fn find_intersections(w1: Vec<((i32, i32), (i32, i32))>, w2: Vec<((i32, i32), (i32, i32))>) -> Vec<(i32, i32)> {
    let mut is: Vec<(i32, i32)> = vec![];    
    for seg1 in w1.iter() {
        for seg2 in w2.iter() {
            is.append(&mut find_seg_intersections(seg1, seg2))
        }
    }
    is
}

fn find_seg_intersections(seg1: &((i32, i32), (i32, i32)), seg2: &((i32, i32), (i32, i32))) -> Vec<(i32, i32)> {
    let mut is: Vec<(i32, i32)> = vec![];    
    let ((l1x1, l1y1),(l1x2, l1y2)) = seg1;
    let ((l2x1, l2y1),(l2x2, l2y2)) = seg2;
    if let Some((xmin, xmax)) = overlap((*l1x1, *l1x2), (*l2x1, *l2x2)) {
        if let Some((ymin, ymax)) = overlap((*l1y1, *l1y2), (*l2y1, *l2y2)) {
            for x in xmin..xmax+1 {
                for y in ymin..ymax+1 {
                    if x != 0 || y != 0 {
                        is.push((x, y))
                    }
                }
            }
        }
    }
    is
}

fn overlap(seg1: (i32, i32), seg2: (i32, i32)) -> Option<(i32, i32)> {
    let (x11, x12) = seg1;
    let (x21, x22) = seg2;
    let x1min = i32::min(x11, x12);
    let x1max = i32::max(x11, x12);
    let x2min = i32::min(x21, x22);
    let x2max = i32::max(x21, x22);
    if x1min > x2max {
        None
    }  else if x2min > x1max {
        None
    } else {
        if x1min >= x2min {
            Some((x1min, i32::min(x1max, x2max)))
        } else {
            Some((x2min, i32::min(x1max, x2max)))
        }
    }
}

fn load_wires() -> (Vec<((i32, i32), i32)>, Vec<((i32, i32),i32)>) {
    let stdin = io::stdin();
    let line1 = stdin.lock().lines().next().expect("Could not read from stdin");
    let line1 = line1.expect("No string there.");
    let line2 = stdin.lock().lines().next().expect("Could not read from stdin");
    let line2 = line2.expect("No string there.");
    (generate_wire(line1), generate_wire(line2))
}

fn transform_wire(steps: &Vec<((i32, i32), i32)>) -> Vec<((i32, i32), (i32, i32))> {
    let mut w: Vec<((i32, i32), (i32, i32))> = vec![];
    let mut cx = 0;
    let mut cy = 0;
    for s in steps {
        let ((dx, dy), n_steps) = s;
        let start = (cx, cy);
        for _ in 0..*n_steps {
            cx = cx + dx;
            cy = cy + dy;
        }
        let end = (cx, cy);
        w.push((start, end))
    }
    w
}

fn generate_wire(line: String) -> Vec<((i32, i32), i32)> {
    let mut w: Vec<((i32, i32), i32)> = vec![];
    for s in line.split(",") {
        let code = &s[0..1];
        let n_steps = i32::from_str_radix(&s[1..], 10).expect("Could not parse int");
        let (dx, dy) = match code {
            "U" => (0, 1),
            "D" => (0, -1),
            "R" => (1, 0),
            "L" => (-1, 0),
            _ => panic!("Unknown direction code")
        };
        w.push(((dx, dy), n_steps))
    }
    w
}