commit 2fea9d7c7acdc304f11ebee3fa89362763607388
parent 4c9b5e23a5330203177f7a5902396859f5cfe4db
Author: Louis Burda <quent.burda@gmail.com>
Date: Wed, 19 Apr 2023 15:12:44 +0200
[Day 23] Calc moved_in and moved_out implicitly
Diffstat:
| M | src/23/src/main.rs | | | 123 | ++++++++++++++++++++++++++++++++++++++++++------------------------------------- |
1 file changed, 66 insertions(+), 57 deletions(-)
diff --git a/src/23/src/main.rs b/src/23/src/main.rs
@@ -13,16 +13,9 @@ struct Pos {
y: isize
}
-#[derive(PartialEq,Eq,Hash,Clone,Copy)]
-struct DJKAgentState {
- moved_out: bool,
- moved_in: bool,
- pos: Pos
-}
-
#[derive(PartialEq,Eq,Hash,Clone)]
struct DJKState {
- agents: [Vec<DJKAgentState>; 4]
+ agents: [Vec<Pos>; 4]
}
#[derive(Clone)]
@@ -37,6 +30,8 @@ struct MapConfig {
hallway: Range,
slot_x: Range,
slot_y: Range,
+ initial: DJKState,
+ fixed: [Vec<bool>; 4]
}
static AGENT_SYMBS: [char; 4] = ['A', 'B', 'C', 'D'];
@@ -50,6 +45,18 @@ impl Pos {
}
impl DJKState {
+ fn moved_in(&self, at: usize, ai: usize, cfg: &MapConfig) -> bool {
+ if self.agents[at][ai] == cfg.initial.agents[at][ai] {
+ return cfg.fixed[at][ai];
+ } else {
+ return self.agents[at][ai].x == idx2slot!(cfg, at);
+ }
+ }
+
+ fn moved_out(&self, at: usize, ai: usize, cfg: &MapConfig) -> bool {
+ return self.agents[at][ai].y == cfg.hallway_y;
+ }
+
fn print(&self, map: &HashMap<Pos,char>) {
let maxx = map.iter().map(|(p,_)| p.x).max().unwrap();
let maxy = map.iter().map(|(p,_)| p.y).max().unwrap();
@@ -62,7 +69,7 @@ impl DJKState {
nc = if *c.unwrap() == '#' { '#' } else { ' ' };
for t in 0..4 {
for agent in &self.agents[t] {
- if p == agent.pos {
+ if &p == agent {
nc = AGENT_SYMBS[t];
break;
}
@@ -93,7 +100,9 @@ fn parse_input(input: &str) -> (HashMap<Pos,char>, MapConfig) {
hallway_y: 1,
hallway: Range { min: 1, max: 12 },
slot_x: Range { min: 3, max: 10 },
- slot_y: Range { min: 1, max: y - 1 }
+ slot_y: Range { min: 1, max: y - 1 },
+ initial: DJKState { agents: [ vec![], vec![], vec![], vec![] ] },
+ fixed: [ vec![], vec![], vec![], vec![] ],
};
return (map, cfg);
@@ -104,8 +113,8 @@ fn heuristic(cfg: &MapConfig, state: &DJKState) -> isize {
for t in 0..4 {
for agent in &state.agents[t] {
let slot_x = idx2slot!(cfg, t);
- if agent.pos.x != slot_x {
- cost += agent.pos.dist_to(&Pos { x: slot_x, y: cfg.hallway_y });
+ if agent.x != slot_x {
+ cost += agent.dist_to(&Pos { x: slot_x, y: cfg.hallway_y });
}
}
}
@@ -124,13 +133,13 @@ fn try_move_out(map: &HashMap<Pos,char>, cfg: &MapConfig,
for (i,agent) in state.agents[t].iter().enumerate() {
if t == at && i == ai { continue; }
- if agent.pos.x == cur.pos.x && agent.pos.y < cur.pos.y { return; }
+ if agent.x == cur.x && agent.y < cur.y { return; }
- if agent.pos.y == cfg.hallway_y {
- if agent.pos.x > cur.pos.x {
- maxx = isize::min(maxx, agent.pos.x);
+ if agent.y == cfg.hallway_y {
+ if agent.x > cur.x {
+ maxx = isize::min(maxx, agent.x);
} else {
- minx = isize::max(minx, agent.pos.x + 1);
+ minx = isize::max(minx, agent.x + 1);
}
}
}
@@ -142,11 +151,10 @@ fn try_move_out(map: &HashMap<Pos,char>, cfg: &MapConfig,
&& ((x - cfg.slot_x.min) % 2 == 0) { continue; }
let mut nstate = state.clone();
- nstate.agents[at][ai].pos.x = x;
- nstate.agents[at][ai].pos.y = cfg.hallway_y;
- nstate.agents[at][ai].moved_out = true;
+ nstate.agents[at][ai].x = x;
+ nstate.agents[at][ai].y = cfg.hallway_y;
let ncost_g = cost + MOVE_COST[at]
- * state.agents[at][ai].pos.dist_to(&nstate.agents[at][ai].pos);
+ * state.agents[at][ai].dist_to(&nstate.agents[at][ai]);
let ncost_f = ncost_g + heuristic(cfg, &nstate);
let res = costmap.get_mut(&nstate);
@@ -173,26 +181,25 @@ fn try_move_in(map: &HashMap<Pos,char>, cfg: &MapConfig,
for (i,agent) in state.agents[t].iter().enumerate() {
if t == at && i == ai { continue; }
- if agent.pos.y == cfg.hallway_y {
+ if agent.y == cfg.hallway_y {
/* another agent is in the way */
- if agent.pos.x > state.agents[at][ai].pos.x {
- if idx2slot!(cfg, at) > agent.pos.x { return; }
+ if agent.x > state.agents[at][ai].x {
+ if idx2slot!(cfg, at) > agent.x { return; }
} else {
- if idx2slot!(cfg, at) < agent.pos.x { return; }
+ if idx2slot!(cfg, at) < agent.x { return; }
}
- } else if agent.pos.x == idx2slot!(cfg, at) {
- slot_free_y = isize::min(slot_free_y, agent.pos.y - 1);
+ } 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; }
}
}
}
let mut nstate = state.clone();
- nstate.agents[at][ai].pos.x = idx2slot!(cfg, at);
- nstate.agents[at][ai].pos.y = slot_free_y;
- nstate.agents[at][ai].moved_in = true;
+ nstate.agents[at][ai].x = idx2slot!(cfg, at);
+ nstate.agents[at][ai].y = slot_free_y;
let ncost_g = cost + MOVE_COST[at]
- * state.agents[at][ai].pos.dist_to(&nstate.agents[at][ai].pos);
+ * state.agents[at][ai].dist_to(&nstate.agents[at][ai]);
let ncost_f = ncost_g + heuristic(cfg, &nstate);
let res = costmap.get_mut(&nstate);
@@ -212,41 +219,43 @@ fn try_move(map: &HashMap<Pos,char>, cfg: &MapConfig,
costmap: &mut HashMap<DJKState,isize>,
active: &mut PriorityQueue<DJKState,isize>,
state: &DJKState, cost: isize, at: usize, ai: usize) -> bool {
- if !state.agents[at][ai].moved_out {
- try_move_out(map, cfg, costmap, active, state, cost, at, ai);
- return false;
- } else if !state.agents[at][ai].moved_in {
- try_move_in(map, cfg, costmap, active, state, cost, at, ai);
+ if !state.moved_in(at, ai, cfg) {
+ if !state.moved_out(at, ai, cfg) {
+ try_move_out(map, cfg, costmap, active, state, cost, at, ai);
+ } else {
+ try_move_in(map, cfg, costmap, active, state, cost, at, ai);
+ }
return false;
} else {
- return state.agents.iter().all(|v| v.iter().all(|a| a.moved_in));
+ for t in 0..4 {
+ for i in 0..state.agents[t].len() {
+ if !state.moved_in(t, i, cfg) { return false; }
+ }
+ }
+ return true;
}
}
-fn organize(map: &HashMap<Pos,char>, cfg: &MapConfig) -> Option<usize> {
- let mut active: PriorityQueue<DJKState,isize> = PriorityQueue::new();
- let mut costmap: HashMap<DJKState,isize> = HashMap::new();
+fn organize(map: &HashMap<Pos,char>, cfg: &mut MapConfig) -> Option<usize> {
+ let mut active: PriorityQueue<DJKState,isize> = PriorityQueue::with_capacity(100000);
+ let mut costmap: HashMap<DJKState,isize> = HashMap::with_capacity(100000);
- let mut initial = DJKState { agents: [vec![], vec![], vec![], vec![]] };
for (p,c) in map.iter() {
let idx = AGENT_SYMBS.iter().position(|sc| sc == c);
if idx.is_some() {
- let mut agent = DJKAgentState {
- moved_out: false,
- moved_in: false,
- pos: p.clone()
- };
- if p.x == cfg.slot_x.min + 2 * idx.unwrap() as isize {
+ if p.x == idx2slot!(cfg, idx.unwrap()) {
let fixed = (p.y+1..cfg.slot_y.max)
.all(|y| map.get(&Pos { x: p.x, y }).unwrap() == c);
- agent.moved_out = fixed;
- agent.moved_in = fixed;
+ aoc::debugln!("{} {} {} -> {}", p.x, p.y, c, fixed);
+ cfg.fixed[idx.unwrap()].push(fixed);
+ } else {
+ cfg.fixed[idx.unwrap()].push(false);
}
- initial.agents[idx.unwrap()].push(agent);
+ cfg.initial.agents[idx.unwrap()].push(p.clone());
}
}
- active.push(initial.clone(), -heuristic(&cfg, &initial));
- costmap.insert(initial, 0);
+ active.push(cfg.initial.clone(), -heuristic(&cfg, &cfg.initial));
+ costmap.insert(cfg.initial.clone(), 0);
let mut advanced: usize = 0;
while !active.is_empty() {
@@ -307,16 +316,16 @@ fn extend_map(s_map: &HashMap<Pos,char>, s_cfg: &MapConfig)
}
fn part1(aoc: &mut aoc::Info) {
- let (map,cfg) = parse_input(&aoc.input);
- let answer = organize(&map, &cfg);
+ let (map, mut cfg) = parse_input(&aoc.input);
+ let answer = organize(&map, &mut cfg);
aoc.answer = Some(format!("{}", answer.unwrap()));
aoc.solution = Some("15385");
}
fn part2(aoc: &mut aoc::Info) {
- let (s_map,s_cfg) = parse_input(&aoc.input);
- let (map,cfg) = extend_map(&s_map, &s_cfg);
- let answer = organize(&map, &cfg);
+ 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()));
}
