use std::cmp::Ord;
use std::cmp::Ordering;
use std::collections::{BTreeMap, HashSet};
use std::io::{self, BufRead};

struct WireStep {
    dir : char,
    len : i32,
}

type WirePath = Vec<WireStep>;

#[derive(Clone, Debug)]
struct WirePoint {
    wire: u8,
    steps: usize,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd)]
// https://newspaint.wordpress.com/2016/07/05/implementing-custom-sort-for-btree-in-rust/
struct MapCoords {
    x: i32,
    y: i32,
}

type MapPoint = Vec<WirePoint>;
type WireMap = BTreeMap<MapCoords, MapPoint>;

impl Ord for MapCoords {
    fn cmp(&self, other:&Self) -> Ordering {
        let self_distance = i32::abs(self.x) + i32::abs(self.y);
        let other_distance = i32::abs(other.x) + i32::abs(other.y);

        if self_distance < other_distance {
            Ordering::Less
        } else if self_distance > other_distance {
            Ordering::Greater
        } else if self.y < other.y {
            Ordering::Less
        } else if self.y > other.y {
            Ordering::Greater
        } else if self.x < other.x {
            Ordering::Less
        } else if self.x > other.x {
            Ordering::Greater
        } else {
            Ordering::Equal
        }
    }
}

fn read_input() -> Vec<WirePath> {
    let stdin = io::stdin();

    stdin.lock().lines()
        .map(|line| {
            line.unwrap().split(',').map(|s| WireStep {
                dir: s.chars().next().unwrap(),
                len: s.get(1..).unwrap().parse().unwrap(),
            }).collect()
        }).collect()
}

fn map_wire(wire: u8, path:&WirePath, map:&mut WireMap) {
    let mut x = 0;
    let mut y = 0;

    let wp = WirePoint { wire, steps: 0 };
    let mp = map.entry(MapCoords{x, y}).or_insert(vec![]);
    mp.push(wp);
    let mut steps = 0;
    for trace in path.iter() {
        for _ in 0..trace.len {
            match trace.dir {
                'U' => y -= 1,
                'D' => y += 1,
                'R' => x += 1,
                'L' => x -= 1,
                d => panic!("Invalid direction {}", d),
            }
            steps += 1;
            let wp = WirePoint { wire, steps };
            let mp = map.entry(MapCoords{x, y}).or_insert(vec![]);
            mp.push(wp);
        }
    }
}

fn create_map(paths:&Vec<WirePath>, map:&mut WireMap) {
    let mut wire_id = 1;
    for path in paths.iter() {
        map_wire(wire_id, path, map);
        wire_id += 1;
    }
}

fn find_intersections(wire_map:&WireMap) -> WireMap {
    let mut ret = WireMap::new();
    for (coords, wiring) in wire_map {
        let wire_crossings = wiring.iter().map(|w| { w.wire }).collect::<HashSet<u8>>().len();
        if wire_crossings > 1 && ! (coords.x == 0 && coords.y == 0) {
            ret.insert(*coords, wiring.to_vec());
        }
    }

    ret
}

fn first_puzzle(wire_paths:&Vec<WirePath>) -> Option<usize> {
    let mut wire_map:WireMap = BTreeMap::new();

    create_map(&wire_paths, &mut wire_map);
    let intersections = find_intersections(&wire_map);

    match intersections.iter().next() {
        Some((c, _)) => Some((i32::abs(c.x) + i32::abs(c.y)) as usize),
        _            => None,
    }
}

fn second_puzzle(wire_paths:&Vec<WirePath>) -> Option<usize> {
    let mut wire_map:WireMap = BTreeMap::new();

    create_map(&wire_paths, &mut wire_map);
    let intersections = find_intersections(&wire_map);

    let lengths : Vec<usize> = intersections.iter().map(|(_, wiring)| {
        wiring.iter().map(|w| { w.steps }).sum()
    }).collect();

    lengths.into_iter().min()
}

fn main() {
    let wire_paths = read_input();

    let first = first_puzzle(&wire_paths);
    match first {
        Some(s) => println!("Solution to first part: {}.", s),
        _       => println!("No solution found for first part."),
    }

    let second = second_puzzle(&wire_paths);
    match second {
        Some(s) => println!("Solution to second part: {}.", s),
        _       => println!("No solution found for second part."),
    }
}