commit 06eb0a03a1382b10fa495dd388804713ef9e931a
parent af7aee76aea2b6a7bfd2f2d49d9c1f2487672c92
Author: Louis Burda <quent.burda@gmail.com>
Date: Wed, 19 Apr 2023 18:25:06 +0200
[Day 23] Try bruteforce search with caching
Diffstat:
| M | src/23/src/main.rs | | | 122 | +++++++++++++++++++++++++++++++++++++++++++++---------------------------------- |
1 file changed, 69 insertions(+), 53 deletions(-)
diff --git a/src/23/src/main.rs b/src/23/src/main.rs
@@ -1,5 +1,5 @@
+use std::{collections::HashMap, hash::Hash};
use std::cmp::Reverse;
-use std::{collections::HashMap, collections::BinaryHeap, hash::Hash};
macro_rules! idx2slot {
( $cfg:expr, $t:expr ) => {
@@ -38,6 +38,8 @@ struct MapConfig {
fixed: [[bool; 4]; 4]
}
+struct Min(Option<usize>);
+
// struct FastHasher(u64);
static AGENT_SYMBS: [char; 4] = ['A', 'B', 'C', 'D'];
@@ -68,6 +70,20 @@ static MOVE_COST: [usize; 4] = [1, 10, 100, 1000];
// }
// }
+impl Min {
+ fn update_min(&mut self, other: &Self) {
+ if other.0.is_some() {
+ self.update(&other.0.unwrap());
+ }
+ }
+
+ fn update(&mut self, other: &usize) {
+ if self.0.is_none() || &self.0.unwrap() > other {
+ self.0 = Some(*other);
+ }
+ }
+}
+
impl Pos {
fn dist_to(&self, other: &Self) -> usize {
return (isize::abs(self.x - other.x)
@@ -181,10 +197,9 @@ fn heuristic(cfg: &MapConfig, state: &DJKState) -> usize {
return cost;
}
-fn try_move_out(map: &HashMap<Pos,char>, cfg: &MapConfig,
+fn lowest_cost_move_out(map: &HashMap<Pos,char>, cfg: &MapConfig,
costmap: &mut HashMap<[[Pos; 4]; 4],usize>,
- active: &mut BinaryHeap<DJKState>,
- state: &DJKState, at: usize, ai: usize) {
+ state: &DJKState, at: usize, ai: usize) -> Min {
let cur = &state.agents[at][ai];
let mut minx: isize = cfg.hallway.min;
@@ -194,7 +209,7 @@ fn try_move_out(map: &HashMap<Pos,char>, cfg: &MapConfig,
if t == at && i == ai { continue; }
let agent = state.agents[t][i];
- if agent.x == cur.x && agent.y < cur.y { return; }
+ if agent.x == cur.x && agent.y < cur.y { return Min(None); }
if agent.y == cfg.hallway_y {
if agent.x > cur.x {
@@ -206,6 +221,7 @@ fn try_move_out(map: &HashMap<Pos,char>, cfg: &MapConfig,
}
}
+ let mut min_cost = Min(None);
for x in minx..maxx {
/* skip spots over slots */
if x >= cfg.slot_x.min && x < cfg.slot_x.max
@@ -233,15 +249,17 @@ fn try_move_out(map: &HashMap<Pos,char>, cfg: &MapConfig,
*res.unwrap() = nstate.cost;
}
- active.push(nstate);
+ let cost = lowest_cost(map, cfg, costmap, &nstate);
+ min_cost.update_min(&cost);
}
}
+
+ return min_cost;
}
-fn try_move_in(map: &HashMap<Pos,char>, cfg: &MapConfig,
+fn lowest_cost_move_in(map: &HashMap<Pos,char>, cfg: &MapConfig,
costmap: &mut HashMap<[[Pos; 4]; 4],usize>,
- active: &mut BinaryHeap<DJKState>,
- state: &DJKState, at: usize, ai: usize) {
+ state: &DJKState, at: usize, ai: usize) -> Min {
let mut slot_free_y = cfg.slot_y.max-1;
for t in 0..cfg.type_cnt {
@@ -252,13 +270,13 @@ fn try_move_in(map: &HashMap<Pos,char>, cfg: &MapConfig,
if agent.y == cfg.hallway_y {
/* another agent is in the way */
if agent.x > state.agents[at][ai].x {
- if idx2slot!(cfg, at) > agent.x { return; }
+ if idx2slot!(cfg, at) > agent.x { return Min(None); }
} else {
- if idx2slot!(cfg, at) < agent.x { return; }
+ if idx2slot!(cfg, at) < agent.x { return Min(None); }
}
} else if agent.x == idx2slot!(cfg, at) {
slot_free_y = isize::min(slot_free_y, agent.y - 1);
- if slot_free_y == cfg.hallway_y { return; }
+ if slot_free_y == cfg.hallway_y { return Min(None); }
}
}
}
@@ -285,20 +303,23 @@ fn try_move_in(map: &HashMap<Pos,char>, cfg: &MapConfig,
*res.unwrap() = nstate.cost;
}
- active.push(nstate);
+ return lowest_cost(map, cfg, costmap, &nstate);
+ } else {
+ return Min(None);
}
}
-fn try_move(map: &HashMap<Pos,char>, cfg: &MapConfig,
+fn lowest_cost_move(map: &HashMap<Pos,char>, cfg: &MapConfig,
costmap: &mut HashMap<[[Pos; 4]; 4],usize>,
- active: &mut BinaryHeap<DJKState>,
- state: &DJKState, at: usize, ai: usize) {
- if !state.moved_in(at, ai, cfg) {
+ state: &DJKState, at: usize, ai: usize) -> Min {
+ if !state.moved_in(at, ai, cfg) {
if !state.moved_out(at, ai, cfg) {
- try_move_out(map, cfg, costmap, active, state, at, ai);
+ return lowest_cost_move_out(map, cfg, costmap, state, at, ai);
} else {
- try_move_in(map, cfg, costmap, active, state, at, ai);
+ return lowest_cost_move_in(map, cfg, costmap, state, at, ai);
}
+ } else {
+ return Min(None);
}
}
@@ -311,8 +332,31 @@ fn all_moved_in(state: &DJKState, cfg: &MapConfig) -> bool {
return true;
}
-fn organize(map: &HashMap<Pos,char>, cfg: &mut MapConfig) -> Option<usize> {
- let mut active = BinaryHeap::with_capacity(10000000);
+fn lowest_cost(map: &HashMap<Pos,char>, cfg: &MapConfig,
+ costmap: &mut HashMap<[[Pos; 4]; 4],usize>, prev: &DJKState) -> Min {
+
+ if aoc::get_debug() > 1 {
+ aoc::debugln!("----");
+ prev.print(&cfg, &map);
+ aoc::debugln!("");
+ }
+
+ if all_moved_in(&prev, cfg) {
+ return Min(Some(prev.cost as usize));
+ }
+
+ let mut min_cost = Min(None);
+ for t in 0..cfg.type_cnt {
+ for i in 0..cfg.agent_cnt {
+ let cost = lowest_cost_move(&map, &cfg, costmap, &prev, t, i);
+ min_cost.update_min(&cost);
+ }
+ }
+
+ return min_cost;
+}
+
+fn organize(map: &HashMap<Pos,char>, cfg: &mut MapConfig) -> Min {
let mut costmap: HashMap<[[Pos; 4]; 4],usize> = HashMap::with_capacity(10000000);
let mut counts: [usize; 4] = [0; 4];
@@ -332,38 +376,9 @@ fn organize(map: &HashMap<Pos,char>, cfg: &mut MapConfig) -> Option<usize> {
}
cfg.initial.cost = 0;
cfg.initial.total = heuristic(&cfg, &cfg.initial);
- active.push(cfg.initial.clone());
costmap.insert(cfg.initial.agents.clone(), 0);
- let mut advanced: usize = 0;
- while !active.is_empty() {
- let state = active.pop().unwrap();
-
- advanced += 1;
-
- if aoc::get_debug() > 1 {
- aoc::debugln!("-----------------");
- aoc::debugln!("LEN {}", active.len());
- state.print(&cfg, &map);
- aoc::debugln!("");
- }
- aoc::debugln!("{}", state.cost);
-
- if all_moved_in(&state, cfg) {
- return Some(state.cost as usize);
- }
-
- for t in 0..cfg.type_cnt {
- for i in 0..cfg.agent_cnt {
- try_move(&map, &cfg, &mut costmap,
- &mut active, &state, t, i);
- }
- }
- }
-
- aoc::debugln!("Advanced {} states", advanced);
-
- return None;
+ return lowest_cost(map, cfg, &mut costmap, &cfg.initial);
}
fn extend_map(s_map: &HashMap<Pos,char>, s_cfg: &MapConfig)
@@ -396,7 +411,7 @@ fn extend_map(s_map: &HashMap<Pos,char>, s_cfg: &MapConfig)
fn part1(aoc: &mut aoc::Info) {
let (map, mut cfg) = parse_input(&aoc.input);
let answer = organize(&map, &mut cfg);
- aoc.answer = Some(format!("{}", answer.unwrap()));
+ aoc.answer = Some(format!("{}", answer.0.unwrap()));
aoc.solution = Some("15385");
}
@@ -404,7 +419,8 @@ fn part2(aoc: &mut aoc::Info) {
let (s_map, s_cfg) = parse_input(&aoc.input);
let (map, mut cfg) = extend_map(&s_map, &s_cfg);
let answer = organize(&map, &mut cfg);
- aoc.answer = Some(format!("{}", answer.unwrap()));
+ aoc.answer = Some(format!("{}", answer.0.unwrap()));
+ aoc.solution = Some("49803")
}
fn main() {
