From d23c210e63a139a4a70d02d0bd0be48159174e16 Mon Sep 17 00:00:00 2001
From: Jordan Doyle <jordan@doyle.la>
Date: Fri, 22 Dec 2023 21:41:27 +0000
Subject: [PATCH] Add day 17

---
 Cargo.toml |   4 ++++
 2023/17.rs | 201 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 205 insertions(+)

diff --git a/Cargo.toml b/Cargo.toml
index c4ce73e..81e5c71 100644
--- a/Cargo.toml
+++ a/Cargo.toml
@@ -11,6 +11,10 @@
 itertools = "0.12"
 
 [[bin]]
+name = "aoc2023-17"
+path = "2023/17.rs"
+
+[[bin]]
 name = "aoc2023-12"
 path = "2023/12.rs"
 
diff --git a/2023/17.rs b/2023/17.rs
new file mode 100644
index 0000000..79dd8f3 100644
--- /dev/null
+++ a/2023/17.rs
@@ -1,0 +1,201 @@
+use std::{
+    cmp::Reverse,
+    collections::{BinaryHeap, HashMap},
+    io::Read,
+};
+
+fn main() {
+    let mut input = Vec::new();
+    std::io::stdin().lock().read_to_end(&mut input).unwrap();
+    let input = parse_input(&input);
+
+    part1(&input);
+    println!();
+    part2(&input);
+}
+
+fn part1(input: &[Vec<u8>]) {
+    let start = (0, 0);
+    let end = (input[0].len() - 1, input.len() - 1);
+
+    let (distance, path) = dijkstra(input, start, end, 0, 3).unwrap();
+
+    print_grid(input, path);
+    eprintln!("part 1: {:?}", distance);
+}
+
+fn part2(input: &[Vec<u8>]) {
+    let start = (0, 0);
+    let end = (input[0].len() - 1, input.len() - 1);
+
+    let (distance, path) = dijkstra(input, start, end, 4, 10).unwrap();
+
+    print_grid(input, path);
+    eprintln!("part 1: {:?}", distance);
+}
+
+fn dijkstra(
+    input: &[Vec<u8>],
+    start: (usize, usize),
+    end: (usize, usize),
+    min_distance: u32,
+    max_distance: u32,
+) -> Option<(u32, HashMap<(usize, usize), Direction>)> {
+    let mut min_cost: HashMap<((usize, usize), Direction, u32), u32> = HashMap::new();
+    let mut queue = BinaryHeap::new();
+
+    queue.push(Reverse(NodeInfo {
+        node: start,
+        cost: 0,
+        step_count: 0,
+        last_direction: Direction::None,
+        path: HashMap::new(),
+    }));
+
+    while let Some(Reverse(NodeInfo {
+        node: node @ (x, y),
+        cost,
+        step_count,
+        last_direction,
+        path,
+    })) = queue.pop()
+    {
+        if node == end && step_count >= min_distance {
+            return Some((cost, path));
+        }
+
+        if cost
+            > *min_cost
+                .get(&(node, last_direction, step_count))
+                .unwrap_or(&u32::MAX)
+        {
+            continue;
+        }
+
+        for (neighbour_pos @ (neighbour_x, neighbour_y), direction) in [
+            ((x + 1, y), Direction::Right),
+            ((x.wrapping_sub(1), y), Direction::Left),
+            ((x, y.wrapping_sub(1)), Direction::Up),
+            ((x, y + 1), Direction::Down),
+        ] {
+            if direction.invert() == last_direction {
+                continue;
+            }
+
+            if step_count == max_distance && direction == last_direction {
+                continue;
+            }
+
+            if step_count < min_distance
+                && direction != last_direction
+                && last_direction != Direction::None
+            {
+                continue;
+            }
+
+            let Some(next_cost) = input.get(neighbour_y).and_then(|x| x.get(neighbour_x)) else {
+                continue;
+            };
+
+            let step_count = if direction == last_direction {
+                step_count + 1
+            } else {
+                1
+            };
+
+            let next = NodeInfo {
+                node: neighbour_pos,
+                cost: cost + u32::from(*next_cost),
+                step_count,
+                last_direction: direction,
+                path: {
+                    let mut p = path.clone();
+                    p.insert(neighbour_pos, direction);
+                    p
+                },
+            };
+
+            if next.cost
+                < *min_cost
+                    .get(&(neighbour_pos, direction, step_count))
+                    .unwrap_or(&u32::MAX)
+            {
+                min_cost.insert((neighbour_pos, direction, step_count), next.cost);
+                queue.push(Reverse(next));
+            }
+        }
+    }
+
+    None
+}
+
+fn print_grid(input: &[Vec<u8>], visited: HashMap<(usize, usize), Direction>) {
+    for (y, a) in input.iter().enumerate() {
+        for (x, v) in a.iter().enumerate() {
+            match visited.get(&(x, y)) {
+                Some(Direction::Up) => print!("^"),
+                Some(Direction::Down) => print!("v"),
+                Some(Direction::Left) => print!("<"),
+                Some(Direction::Right) => print!(">"),
+                Some(Direction::None) => print!("*"),
+                None => print!("{}", v),
+            }
+        }
+
+        println!();
+    }
+}
+
+#[derive(Eq, PartialEq, Debug)]
+struct NodeInfo {
+    node: (usize, usize),
+    cost: u32,
+    step_count: u32,
+    last_direction: Direction,
+    path: HashMap<(usize, usize), Direction>,
+}
+
+impl Ord for NodeInfo {
+    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
+        self.cost.cmp(&other.cost)
+    }
+}
+
+impl PartialOrd for NodeInfo {
+    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
+        self.cost.partial_cmp(&other.cost)
+    }
+}
+
+#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
+pub enum Direction {
+    Up,
+    Down,
+    Left,
+    Right,
+    None,
+}
+
+impl Direction {
+    fn invert(self) -> Self {
+        match self {
+            Self::Up => Self::Down,
+            Self::Down => Self::Up,
+            Self::Left => Self::Right,
+            Self::Right => Self::Left,
+            Self::None => Self::None,
+        }
+    }
+}
+
+fn parse_input(input: &[u8]) -> Vec<Vec<u8>> {
+    std::str::from_utf8(&input)
+        .unwrap()
+        .split("\n")
+        .map(|v| {
+            v.chars()
+                .map(|c| u8::try_from(c.to_digit(10).unwrap()).unwrap())
+                .collect()
+        })
+        .collect()
+}
--
rgit 0.1.5