96 Zeilen
2,9 KiB
Rust
96 Zeilen
2,9 KiB
Rust
use std::{cmp::Ordering, collections::HashMap, u32};
|
|
|
|
use advent_of_code::{
|
|
find_character,
|
|
strings::{convert_to_array, line_to_char},
|
|
Kartesian, KartesianDirection, Map, KD,
|
|
};
|
|
use advent_of_code_macros::include_aoc;
|
|
|
|
include_aoc!(DATA 2024 16);
|
|
|
|
const START: Option<char> = Some('S');
|
|
const WALL: Option<char> = Some('#');
|
|
const END: Option<char> = Some('E');
|
|
const SPACE: Option<char> = Some('.');
|
|
|
|
fn new_score(old_score: u32, old: KD, new: KD) -> u32 {
|
|
old_score
|
|
+ if new == old {
|
|
1
|
|
} else if old == new.neg() {
|
|
2001
|
|
} else {
|
|
1001
|
|
}
|
|
}
|
|
|
|
fn sorter(a: &(Kartesian<usize>, KartesianDirection, u32), b: &(Kartesian<usize>, KartesianDirection, u32)) -> Ordering {
|
|
a.2.cmp(&b.2).reverse()
|
|
}
|
|
|
|
fn search_end(map: &Map<char>, startpos: Kartesian<usize>, last_dir: KartesianDirection) -> u32 {
|
|
let mut posmap: HashMap<Kartesian<usize>, u32> = HashMap::new();
|
|
let mut branches = Vec::with_capacity(200);
|
|
branches.push((startpos, last_dir, 0));
|
|
let mut vmap = map.clone();
|
|
let mut best = u32::MAX;
|
|
loop {
|
|
let (newpos, old_dir, score) = match branches.pop() {
|
|
Some(b) => b,
|
|
None => break,
|
|
};
|
|
if !posmap.contains_key(&newpos) {
|
|
posmap.insert(newpos, score);
|
|
} else {
|
|
if score > *posmap.get(&newpos).unwrap() {
|
|
continue;
|
|
}
|
|
posmap.insert(newpos, score);
|
|
}
|
|
println!("moved {} with increased score {}", old_dir, score);
|
|
vmap.set(
|
|
newpos,
|
|
match old_dir {
|
|
KartesianDirection::Left => '←',
|
|
KartesianDirection::Top => '↑',
|
|
KartesianDirection::Right => '→',
|
|
KartesianDirection::Bottom => '↓',
|
|
_ => unreachable!(),
|
|
},
|
|
);
|
|
for dir in KD::iter(false, false, true) {
|
|
let after_move = newpos.move_dir(dir.vector(), dir).unwrap();
|
|
match map.get(after_move) {
|
|
WALL => {},
|
|
END => {
|
|
if best > new_score(score, old_dir, dir) {
|
|
best = new_score(score, old_dir, dir);
|
|
}
|
|
break;
|
|
},
|
|
SPACE | START => {
|
|
let added = new_score(score, old_dir, dir);
|
|
branches.push((after_move, dir, added));
|
|
},
|
|
_ => unreachable!(),
|
|
}
|
|
}
|
|
branches.sort_by(sorter);
|
|
}
|
|
print!("{}", vmap);
|
|
best
|
|
}
|
|
|
|
fn main() {
|
|
let map = Map::from(convert_to_array::<_, _, '\n'>(DATA, line_to_char));
|
|
//println!("Startmap: \n{}", map);
|
|
let deer = find_character(&map, 'S');
|
|
let best = search_end(&map, deer, KartesianDirection::East);
|
|
println!("Best Score is: {}", best)
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod test {
|
|
use super::*;
|
|
}
|