commit d6043a35398d885b348e6b30f19c5da9c7d9da1d
parent 06eb0a03a1382b10fa495dd388804713ef9e931a
Author: Louis Burda <quent.burda@gmail.com>
Date: Wed, 19 Apr 2023 18:25:11 +0200
Revert "[Day 23] Try bruteforce search with caching"
This reverts commit ff41f04c776049c242954804122c7254ab4e33a9.
Diffstat:
| M | src/23/src/main.rs | | | 122 | ++++++++++++++++++++++++++++++++++--------------------------------------------- |
1 file changed, 53 insertions(+), 69 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,8 +38,6 @@ struct MapConfig {
fixed: [[bool; 4]; 4]
}
-struct Min(Option<usize>);
-
// struct FastHasher(u64);
static AGENT_SYMBS: [char; 4] = ['A', 'B', 'C', 'D'];
@@ -70,20 +68,6 @@ 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)
@@ -197,9 +181,10 @@ fn heuristic(cfg: &MapConfig, state: &DJKState) -> usize {
return cost;
}
-fn lowest_cost_move_out(map: &HashMap<Pos,char>, cfg: &MapConfig,
+fn try_move_out(map: &HashMap<Pos,char>, cfg: &MapConfig,
costmap: &mut HashMap<[[Pos; 4]; 4],usize>,
- state: &DJKState, at: usize, ai: usize) -> Min {
+ active: &mut BinaryHeap<DJKState>,
+ state: &DJKState, at: usize, ai: usize) {
let cur = &state.agents[at][ai];
let mut minx: isize = cfg.hallway.min;
@@ -209,7 +194,7 @@ fn lowest_cost_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 Min(None); }
+ if agent.x == cur.x && agent.y < cur.y { return; }
if agent.y == cfg.hallway_y {
if agent.x > cur.x {
@@ -221,7 +206,6 @@ fn lowest_cost_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
@@ -249,17 +233,15 @@ fn lowest_cost_move_out(map: &HashMap<Pos,char>, cfg: &MapConfig,
*res.unwrap() = nstate.cost;
}
- let cost = lowest_cost(map, cfg, costmap, &nstate);
- min_cost.update_min(&cost);
+ active.push(nstate);
}
}
-
- return min_cost;
}
-fn lowest_cost_move_in(map: &HashMap<Pos,char>, cfg: &MapConfig,
+fn try_move_in(map: &HashMap<Pos,char>, cfg: &MapConfig,
costmap: &mut HashMap<[[Pos; 4]; 4],usize>,
- state: &DJKState, at: usize, ai: usize) -> Min {
+ active: &mut BinaryHeap<DJKState>,
+ state: &DJKState, at: usize, ai: usize) {
let mut slot_free_y = cfg.slot_y.max-1;
for t in 0..cfg.type_cnt {
@@ -270,13 +252,13 @@ fn lowest_cost_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 Min(None); }
+ if idx2slot!(cfg, at) > agent.x { return; }
} else {
- if idx2slot!(cfg, at) < agent.x { return Min(None); }
+ if idx2slot!(cfg, at) < agent.x { return; }
}
} 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 Min(None); }
+ if slot_free_y == cfg.hallway_y { return; }
}
}
}
@@ -303,23 +285,20 @@ fn lowest_cost_move_in(map: &HashMap<Pos,char>, cfg: &MapConfig,
*res.unwrap() = nstate.cost;
}
- return lowest_cost(map, cfg, costmap, &nstate);
- } else {
- return Min(None);
+ active.push(nstate);
}
}
-fn lowest_cost_move(map: &HashMap<Pos,char>, cfg: &MapConfig,
+fn try_move(map: &HashMap<Pos,char>, cfg: &MapConfig,
costmap: &mut HashMap<[[Pos; 4]; 4],usize>,
- state: &DJKState, at: usize, ai: usize) -> Min {
- if !state.moved_in(at, ai, cfg) {
+ active: &mut BinaryHeap<DJKState>,
+ state: &DJKState, at: usize, ai: usize) {
+ if !state.moved_in(at, ai, cfg) {
if !state.moved_out(at, ai, cfg) {
- return lowest_cost_move_out(map, cfg, costmap, state, at, ai);
+ try_move_out(map, cfg, costmap, active, state, at, ai);
} else {
- return lowest_cost_move_in(map, cfg, costmap, state, at, ai);
+ try_move_in(map, cfg, costmap, active, state, at, ai);
}
- } else {
- return Min(None);
}
}
@@ -332,31 +311,8 @@ fn all_moved_in(state: &DJKState, cfg: &MapConfig) -> bool {
return true;
}
-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 {
+fn organize(map: &HashMap<Pos,char>, cfg: &mut MapConfig) -> Option<usize> {
+ let mut active = BinaryHeap::with_capacity(10000000);
let mut costmap: HashMap<[[Pos; 4]; 4],usize> = HashMap::with_capacity(10000000);
let mut counts: [usize; 4] = [0; 4];
@@ -376,9 +332,38 @@ fn organize(map: &HashMap<Pos,char>, cfg: &mut MapConfig) -> Min {
}
cfg.initial.cost = 0;
cfg.initial.total = heuristic(&cfg, &cfg.initial);
+ active.push(cfg.initial.clone());
costmap.insert(cfg.initial.agents.clone(), 0);
- return lowest_cost(map, cfg, &mut costmap, &cfg.initial);
+ 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;
}
fn extend_map(s_map: &HashMap<Pos,char>, s_cfg: &MapConfig)
@@ -411,7 +396,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.0.unwrap()));
+ aoc.answer = Some(format!("{}", answer.unwrap()));
aoc.solution = Some("15385");
}
@@ -419,8 +404,7 @@ 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.0.unwrap()));
- aoc.solution = Some("49803")
+ aoc.answer = Some(format!("{}", answer.unwrap()));
}
fn main() {
