diff options
| -rw-r--r-- | 2023/day17.rs | 169 |
1 files changed, 114 insertions, 55 deletions
diff --git a/2023/day17.rs b/2023/day17.rs index 37aff45..57a4577 100644 --- a/2023/day17.rs +++ b/2023/day17.rs @@ -5,86 +5,145 @@ use num::complex::Complex as c; use num::Complex; use std::cmp::min; use std::collections::HashMap; +use std::collections::HashSet; use std::fs::File; use std::io::Read; type Matrix<T> = Vec<Vec<T>>; -fn rec( - pos: Complex<i32>, - dir: Complex<i32>, - conti: u32, - mut hl: i32, - s: &mut HashMap<(Complex<i32>, Complex<i32>, u32), i32>, - m: &Matrix<i32>, -) -> i32 { - if !(0 <= pos.re && pos.re < m[0].len() as i32 && 0 <= pos.im && pos.im < m.len() as i32) { - return 999999999; - } - hl += m[pos.im as usize][pos.re as usize]; - - if conti > 3 { - return 999999999; - } - - // println!("{}", pos); - if let Some(hl_) = s.get(&(pos, dir, conti)) { - if hl_ <= &hl { - return 999999999; +fn bfs1(m: &Matrix<u32>) -> u32 { + let mut s: HashMap<(Complex<i32>, Complex<i32>, u32), u32> = HashMap::new(); + let mut hs: HashSet<(Complex<i32>, Complex<i32>, u32, u32)> = HashSet::new(); + let mut hs_next: HashSet<(Complex<i32>, Complex<i32>, u32, u32)> = HashSet::new(); + + hs.insert((c::new(0, 0), c::new(1, 0), 0, 0)); + + let mut res: Vec<u32> = Vec::new(); + while hs.len() > 0 { + for (pos, dir, conti, mut hl) in hs { + if conti > 2 { + continue; + } + + if !(0 <= pos.re + && pos.re < m[0].len() as i32 + && 0 <= pos.im + && pos.im < m.len() as i32) + { + continue; + } + + hl += m[pos.im as usize][pos.re as usize]; + + if pos == c::new(m[0].len() as i32 - 1, m.len() as i32 - 1) { + res.push(hl); + continue; + } + + if let Some(hl_) = s.get(&(pos, dir, conti)) { + if hl_ <= &hl { + continue; + } + } + s.insert((pos, dir, conti), hl); + + let new_dir = dir; + let new_pos = pos + new_dir; + hs_next.insert((new_pos, new_dir, conti + 1, hl)); + + let new_dir = dir * c::i(); + let new_pos = pos + new_dir; + hs_next.insert((new_pos, new_dir, 0, hl)); + + let new_dir = dir * (-c::i()); + let new_pos = pos + new_dir; + hs_next.insert((new_pos, new_dir, 0, hl)); } + hs = hs_next; + hs_next = HashSet::new(); } - s.insert((pos, dir, conti), hl); + return res.into_iter().fold(999999999, min) - m[0][0]; +} - if pos == c::new(m[0].len() as i32 - 1, m.len() as i32 - 1) { - return hl; +fn bfs2(m: &Matrix<u32>) -> u32 { + let mut s: HashMap<(Complex<i32>, Complex<i32>, u32), u32> = HashMap::new(); + let mut hs: HashSet<(Complex<i32>, Complex<i32>, u32, u32)> = HashSet::new(); + let mut hs_next: HashSet<(Complex<i32>, Complex<i32>, u32, u32)> = HashSet::new(); + + hs.insert((c::new(0, 0), c::new(1, 0), 0, 0)); + + let mut res: Vec<u32> = Vec::new(); + while hs.len() > 0 { + for (pos, dir, conti, mut hl) in hs { + if conti > 9 { + continue; + } + + if !(0 <= pos.re + && pos.re < m[0].len() as i32 + && 0 <= pos.im + && pos.im < m.len() as i32) + { + continue; + } + + hl += m[pos.im as usize][pos.re as usize]; + + if conti > 2 && pos == c::new(m[0].len() as i32 - 1, m.len() as i32 - 1) { + res.push(hl); + continue; + } + + if let Some(hl_) = s.get(&(pos, dir, conti)) { + if hl_ <= &hl { + continue; + } + } + s.insert((pos, dir, conti), hl); + + let new_dir = dir; + let new_pos = pos + new_dir; + hs_next.insert((new_pos, new_dir, conti + 1, hl)); + + if conti > 2 { + let new_dir = dir * c::i(); + let new_pos = pos + new_dir; + hs_next.insert((new_pos, new_dir, 0, hl)); + + let new_dir = dir * (-c::i()); + let new_pos = pos + new_dir; + hs_next.insert((new_pos, new_dir, 0, hl)); + } + } + hs = hs_next; + hs_next = HashSet::new(); } - - let mut ret = 999999999; - let new_pos = pos + dir; - let new_dir = dir; - ret = min(ret, rec(new_pos, new_dir, conti + 1, hl, s, m)); - - let new_pos = pos + dir; - let new_dir = dir * c::i(); - ret = min(ret, rec(new_pos, new_dir, 0, hl, s, m)); - - let new_pos = pos + dir; - let new_dir = dir * (-c::i()); - ret = min(ret, rec(new_pos, new_dir, 0, hl, s, m)); - - return ret; + return res.into_iter().fold(999999999, min) - m[0][0]; } fn main() { - let filename = "in/day17.ref"; - // let filename = "in/day17.pzl"; + // let filename = "in/day17.ref"; + let filename = "in/day17.pzl"; let mut f = File::open(filename).expect("cannot open file"); let mut content = String::new(); f.read_to_string(&mut content).expect("cannot read file"); let lines = content.trim_end().split('\n'); - // println!("{:?}", lines); - let mut m: Matrix<i32> = Vec::new(); + let mut m: Matrix<u32> = Vec::new(); for line in lines { - let mut mr: Vec<i32> = Vec::new(); + let mut mr: Vec<u32> = Vec::new(); for c in line.chars() { - mr.push(c.to_digit(10).unwrap() as i32); + mr.push(c.to_digit(10).unwrap()); } m.push(mr); } - // println!("{:?}", m); - - let mut state: HashMap<(Complex<i32>, Complex<i32>, u32), i32> = HashMap::new(); - let mut pos = c::new(0, 0); - let mut dir = c::new(1, 0); - - let res1 = rec(pos, dir, 0, 0, &mut state, &m); - // println!("{:?}", state); - let mut res2 = 0; + let res1 = bfs1(&m); + let res2 = bfs2(&m); println!("res1: {}", res1); println!("res2: {}", res2); + assert_eq!(res1, 635); + assert_eq!(res2, 734); } -// 612 too low |