🏡 index : ~doyle/aoc.git

d23c210e63a139a4a70d02d0bd0be48159174e16 [patch]

e7f43b4510ae4cc7377cddbd1cf53555132861bb

2dfdbfc11b3256b72ea35773f6d5540e1b6b19a7

d23c210e63a139a4a70d02d0bd0be48159174e16.tar.gz

Add day 17

Diff

 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()
}