Add day03, 2019

Implemented with the wire map as a newtype based on BTreeMap.
Not necessarily the best choice, but it was fun to write.

1 files changed, 148 insertions, 0 deletions

diff --git a/2019/rust/day03/src/main.rs b/2019/rust/day03/src/main.rs
new file mode 100644
index 0000000..fa26cac
--- /dev/null
+++ b/2019/rust/day03/src/main.rs
@@ -0,0 +1,148 @@
+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."),
+    }
+}