From 17d08716aa4f016a8cef1589c755d5a25472c758 Mon Sep 17 00:00:00 2001 From: alex <> Date: Mon, 16 Dec 2024 16:27:48 +0100 Subject: [PATCH] Day16 - part 1 (wip: answer too high) --- src/day16.rs | 181 +++++++++++++++++++++++++++++++++++++++++++++++++++ src/main.rs | 2 + 2 files changed, 183 insertions(+) create mode 100644 src/day16.rs diff --git a/src/day16.rs b/src/day16.rs new file mode 100644 index 0000000..fb9facc --- /dev/null +++ b/src/day16.rs @@ -0,0 +1,181 @@ +use std::error::Error; +use std::path::Path; +use std::collections::HashMap; + +const INFINITE_SCORE: u64 = u64::MAX; + +#[derive(Copy, Clone, Debug)] +struct Tile { + score: u64, + dir: (isize, isize), +} + +impl Tile { + pub fn new(score: u64, dir: (isize, isize)) -> Self { + Self { score, dir } + } +} + +struct Puzzle { + map: HashMap<(isize, isize), u8>, + start: (isize, isize), + end: (isize, isize), +} + +impl Puzzle { + pub fn new(input: &str) -> Self { + let mut map: HashMap<(isize, isize), u8> = HashMap::new(); + let mut start = (-1, -1); + let mut end = (-1, -1); + input.lines().enumerate() + .for_each(|(row, line)| { + line.as_bytes().into_iter().enumerate() + .for_each(|(col, &value)| { + let (row, col) = (row as isize, col as isize); + match value { + b'#' => {}, + _ => { map.insert((row, col), value); } + } + if value == b'S' { + start = (row, col); + } + else if value == b'E' { + end = (row, col); + } + }); + }); + Self { map, start, end } + } + + fn solve(&self) -> u64 { + // (pos) -> (score, dir) <=> (x, y) -> (s, (dx, dy)) + let mut score: HashMap<(isize, isize), Tile> = HashMap::new(); + self.map.iter() + .for_each(|(&pos, &value)| { + match value { + b'S' => score.insert(pos, Tile::new(0, (0, 1))), + _ => score.insert(pos, Tile::new(INFINITE_SCORE, (0, 0))), + }; + }); + + let mut next: Vec<(isize, isize)> = Vec::new(); + next.push(self.start); + println!("start={:?}, end={:?}", self.start, self.end); + while let Some(pos) = next.pop() { + if pos == self.end { + break; + } + let tile = *score.get(&pos).unwrap(); + let score_curr = tile.score; + let dir_curr = tile.dir; + let dir_opp = (-dir_curr.0, -dir_curr.1); + //println!(" pos={:?} score={:?}", pos, score_curr); + [(-1, 0), (0, 1), (1, 0), (0, -1)].into_iter() + .filter(|d| *d != dir_opp) + .filter(|d| self.map.contains_key(&(pos.0 + d.0, pos.1 + d.1))) + .for_each(|dir| { + let pos_new = (pos.0 + dir.0, pos.1 + dir.1); + if self.map.contains_key(&pos_new) { + let tile_new = score.get_mut(&pos_new).unwrap(); + let mut score_new = score_curr + 1; + if dir != dir_curr { + score_new += 1000; + } + if tile_new.score == INFINITE_SCORE || score_new < tile_new.score { + tile_new.score = score_new; + tile_new.dir = dir; + next.push(pos_new); + } + } + }); + // the minimal score should be at the end of "next" + next.sort_by(|a, b| { + let t1 = score.get(a).unwrap(); + let t2 = score.get(b).unwrap(); + t2.score.cmp(&t1.score) + }); + //println!(" next={:?}", next); + } + + (*score.get(&self.end).unwrap()).score + } +} + +fn run_part1(input: &str) -> Result> { + println!("Running {} - part 1", get_day()); + + let puzzle = Puzzle::new(input); + Ok(puzzle.solve()) +} + +fn run_part2(input: &str) -> Result> { + println!("Running {} - part 2", get_day()); + + Ok(0) +} + +pub fn run(input: &str) -> Result<(), Box> { + let res = run_part1(input)?; + println!("{res}"); + + let res = run_part2(input)?; + println!("{res}"); + + Ok(()) +} + +fn get_day() -> String { + let filename = file!(); + Path::new(filename).file_stem().unwrap().to_str().unwrap().to_string() +} + +#[cfg(test)] +mod tests { + use super::*; + + static TEXT_INPUT_0: &str = "\ +############### +#.......#....E# +#.#.###.#.###.# +#.....#.#...#.# +#.###.#####.#.# +#.#.#.......#.# +#.#.#####.###.# +#...........#.# +###.#.#####.#.# +#...#.....#.#.# +#.#.#.###.#.#.# +#.....#...#.#.# +#.###.#.#.#.#.# +#S..#.....#...# +###############"; + static TEXT_INPUT_1: &str = "\ +################# +#...#...#...#..E# +#.#.#.#.#.#.#.#.# +#.#.#.#...#...#.# +#.#.#.#.###.#.#.# +#...#.#.#.....#.# +#.#.#.#.#.#####.# +#.#...#.#.#.....# +#.#.#####.#.###.# +#.#.#.......#...# +#.#.###.#####.### +#.#.#...#.....#.# +#.#.#.#####.###.# +#.#.#.........#.# +#.#.#.#########.# +#S#.............# +#################"; + + #[test] + fn test_part1() { + assert_eq!(7036, run_part1(TEXT_INPUT_0).unwrap()); + assert_eq!(11048, run_part1(TEXT_INPUT_1).unwrap()); + } + + #[test] + fn test_part2() { + assert_eq!(0, run_part2(TEXT_INPUT_0).unwrap()); + } +} diff --git a/src/main.rs b/src/main.rs index 89da6e6..55d2ac4 100644 --- a/src/main.rs +++ b/src/main.rs @@ -19,6 +19,7 @@ pub mod day12; pub mod day13; pub mod day14; pub mod day15; +pub mod day16; fn main() { let args: Vec = env::args().collect(); @@ -56,6 +57,7 @@ fn run(day: &str, input_file: &str) -> Result<(), Box> { "day13" => day13::run(&input)?, "day14" => day14::run(&input)?, "day15" => day15::run(&input)?, + "day16" => day16::run(&input)?, _ => return Err(format!("unknown or unimplemented day \"{day}\"").into()), } Ok(()) -- 2.39.5