1 files changed, 137 insertions, 0 deletions
diff --git a/2021/src/bin/day_5.rs b/2021/src/bin/day_5.rs
new file mode 100644
index 0000000..08eaecd
--- /dev/null
+++ b/2021/src/bin/day_5.rs
@@ -0,0 +1,137 @@
+use nom::{
+    bytes::complete::tag,
+    character::complete::{char as nom_char, line_ending, u32 as nom_u32},
+    combinator::map,
+    multi::separated_list1,
+    sequence::tuple,
+    IResult,
+};
+use std::{collections::BTreeMap, fs};
+
+fn main() -> Result<(), Box<dyn std::error::Error>> {
+    let input = fs::read_to_string("inputs/day_5.txt")?;
+    let lines = parse_lines(&input).unwrap().1;
+    {
+        let mut map_simple = Bitmap::default();
+        for line in &lines {
+            map_simple.mark_line_only_simple(line);
+        }
+        dbg!(map_simple.count_overlapped_points());
+    }
+    {
+        let mut map = Bitmap::default();
+        for line in &lines {
+            map.mark_line(line);
+        }
+        dbg!(map.count_overlapped_points());
+    }
+
+    Ok(())
+}
+
+#[derive(Default)]
+struct Bitmap(BTreeMap<Point, usize>);
+impl Bitmap {
+    fn mark_line_only_simple(&mut self, l: &Line) {
+        if l.is_horizontal() {
+            for x in l.a.x..=l.b.x {
+                self.mark_point(&Point { x, y: l.a.y });
+            }
+        } else if l.is_vertical() {
+            for y in l.a.y..=l.b.y {
+                self.mark_point(&Point { x: l.a.x, y });
+            }
+        } else {
+        }
+    }
+
+    fn mark_line(&mut self, l: &Line) {
+        if l.is_horizontal() {
+            for x in l.a.x..=l.b.x {
+                self.mark_point(&Point { x, y: l.a.y });
+            }
+        } else if l.is_vertical() {
+            for y in l.a.y..=l.b.y {
+                self.mark_point(&Point { x: l.a.x, y });
+            }
+        } else if l.is_diagonal_up() {
+            for delta in 0..=(l.b.x - l.a.x) {
+                self.mark_point(&Point {
+                    x: l.a.x + delta,
+                    y: l.a.y + delta,
+                });
+            }
+        } else if l.is_diagonal_down() {
+            for delta in 0..=(l.b.x - l.a.x) {
+                let reverse_delta = l.b.x - l.a.x - delta;
+                self.mark_point(&Point {
+                    x: l.a.x + delta,
+                    y: l.b.y + reverse_delta,
+                });
+            }
+        } else {
+            panic!("There shouldn't be other cases...")
+        }
+    }
+
+    fn mark_point(&mut self, p: &Point) {
+        *self.0.entry(p.clone()).or_insert(0) += 1;
+    }
+
+    fn count_overlapped_points(&self) -> usize {
+        self.0.values().filter(|v| **v > 1).count()
+    }
+}
+
+#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)]
+struct Point {
+    x: u32,
+    y: u32,
+}
+
+#[derive(Debug)]
+struct Line {
+    a: Point,
+    b: Point,
+}
+
+impl Line {
+    fn is_horizontal(&self) -> bool {
+        self.a.y == self.b.y
+    }
+
+    fn is_vertical(&self) -> bool {
+        self.a.x == self.b.x
+    }
+
+    fn is_diagonal_up(&self) -> bool {
+        self.a.x < self.b.x && self.a.y < self.b.y
+    }
+
+    fn is_diagonal_down(&self) -> bool {
+        self.a.x < self.b.x && self.a.y > self.b.y
+    }
+}
+
+fn parse_lines(input: &str) -> IResult<&str, Vec<Line>> {
+    separated_list1(line_ending, parse_line)(input)
+}
+
+fn parse_line(input: &str) -> IResult<&str, Line> {
+    map(
+        tuple((parse_point, tag(" -> "), parse_point)),
+        |(a, _, b)| {
+            if a < b {
+                Line { a, b }
+            } else {
+                Line { a: b, b: a }
+            }
+        },
+    )(input)
+}
+
+fn parse_point(input: &str) -> IResult<&str, Point> {
+    map(tuple((nom_u32, nom_char(','), nom_u32)), |(x, _, y)| {
+        Point { x, y }
+    })(input)
+}