commit 4c9b5e23a5330203177f7a5902396859f5cfe4db
parent ea68649cfcea407905507dfbe57a06b86a20e17a
Author: Louis Burda <quent.burda@gmail.com>
Date: Wed, 19 Apr 2023 04:29:36 +0200
[Day 23] Add cost heuristic (A*)
Diffstat:
4 files changed, 223 insertions(+), 153 deletions(-)
diff --git a/src/.gitignore b/src/.gitignore
@@ -3,3 +3,4 @@ Cargo.lock
template
compile_commands.json
main
+perf.*
diff --git a/src/23/src/main.rs b/src/23/src/main.rs
@@ -1,21 +1,9 @@
use priority_queue::PriorityQueue;
-use std::collections::HashMap;
-
-macro_rules! on_slot {
- ( $x:expr ) => {
- $x >= SLOTS_BEGIN && $x < SLOTS_END && (($x - SLOTS_BEGIN) % 2 == 0)
- }
-}
-
-//macro_rules! slot2idx {
-// ( $x:expr ) => {
-// (($x - SLOTS_BEGIN) / 2) as usize
-// }
-//}
+use std::{collections::HashMap, hash::Hash};
macro_rules! idx2slot {
- ( $x:expr ) => {
- SLOTS_BEGIN + ($x * 2) as isize
+ ( $cfg:expr, $t:expr ) => {
+ $cfg.slot_x.min + ($t * 2) as isize
}
}
@@ -26,12 +14,34 @@ struct Pos {
}
#[derive(PartialEq,Eq,Hash,Clone,Copy)]
+struct DJKAgentState {
+ moved_out: bool,
+ moved_in: bool,
+ pos: Pos
+}
+
+#[derive(PartialEq,Eq,Hash,Clone)]
struct DJKState {
- moved_out: [bool; 8],
- moved_in: [bool; 8],
- pos: [Pos; 8]
+ agents: [Vec<DJKAgentState>; 4]
+}
+
+#[derive(Clone)]
+struct Range {
+ min: isize,
+ max: isize
}
+#[derive(Clone)]
+struct MapConfig {
+ hallway_y: isize,
+ hallway: Range,
+ slot_x: Range,
+ slot_y: Range,
+}
+
+static AGENT_SYMBS: [char; 4] = ['A', 'B', 'C', 'D'];
+static MOVE_COST: [isize; 4] = [1, 10, 100, 1000];
+
impl Pos {
fn dist_to(&self, other: &Self) -> isize {
return isize::abs(self.x - other.x)
@@ -50,10 +60,12 @@ impl DJKState {
let mut nc = ' ';
if c.is_some() {
nc = if *c.unwrap() == '#' { '#' } else { ' ' };
- for i in 0..8 {
- if p == self.pos[i] {
- nc = SYMB[i/2];
- break;
+ for t in 0..4 {
+ for agent in &self.agents[t] {
+ if p == agent.pos {
+ nc = AGENT_SYMBS[t];
+ break;
+ }
}
}
}
@@ -64,25 +76,10 @@ impl DJKState {
}
}
-static SLOTS_BEGIN: isize = 3;
-static SLOTS_END: isize = 10;
-static SLOTS: [isize; 4] = [3, 5, 7, 9];
-
-static SPOTS_BEGIN: isize = 1;
-static SPOTS_END: isize = 12;
-//static SPOTS: [isize; 7] = [1, 2, 4, 6, 8, 10, 11];
-
-static HALLWAY: isize = 1;
-static SLOT_UPPER: isize = 2;
-static SLOT_LOWER: isize = 3;
-
-static SYMB: [char; 4] = ['A', 'B', 'C', 'D'];
-
-static MOVE_COST: [isize; 4] = [1, 10, 100, 1000];
-
-fn parse_input(input: &str) -> HashMap<Pos,char> {
+fn parse_input(input: &str) -> (HashMap<Pos,char>, MapConfig) {
let mut map: HashMap<Pos,char> = HashMap::new();
- let mut y: usize = 0;
+
+ let mut y: isize = 0;
for line in input.lines() {
if line.is_empty() { continue; }
for (x,c) in line.chars().enumerate() {
@@ -91,173 +88,236 @@ fn parse_input(input: &str) -> HashMap<Pos,char> {
}
y += 1;
}
- return map;
-}
-fn find_pos(map: &HashMap<Pos,char>, sc: char) -> [Pos; 2] {
- let mut agents: Vec<Pos> = Vec::new();
- for (p,c) in map.iter() {
- if *c == sc {
- agents.push(p.clone());
- }
- }
- return agents.try_into().unwrap_or_else(|_| panic!());
-}
+ let cfg = 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 }
+ };
-fn in_slot(state: &DJKState, agent: usize) -> bool {
- if state.pos[agent].x == SLOTS[agent / 2] {
- if state.pos[agent].y == SLOT_LOWER {
- return true;
- }
+ return (map, cfg);
+}
- if state.pos[agent].y == SLOT_UPPER {
- let other = if agent % 2 == 0 { agent + 1 } else { agent - 1 };
- return state.pos[other].x == SLOTS[other / 2]
- && state.pos[other].y == SLOT_LOWER;
+fn heuristic(cfg: &MapConfig, state: &DJKState) -> isize {
+ let mut cost: isize = 0;
+ 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 });
+ }
}
}
- return false;
+ return cost;
}
-fn try_move_out(map: &HashMap<Pos,char>,
+fn try_move_out(map: &HashMap<Pos,char>, cfg: &MapConfig,
+ costmap: &mut HashMap<DJKState,isize>,
active: &mut PriorityQueue<DJKState,isize>,
- state: &DJKState, cost: isize, agent: usize) {
- let mut minx: isize = SPOTS_BEGIN;
- let mut maxx: isize = SPOTS_END;
- for i in 0..8 {
- if i == agent { continue; }
-
- if state.pos[i].x == state.pos[agent].x
- && state.pos[i].y < state.pos[agent].y { return; }
-
- if state.pos[i].y == HALLWAY {
- if state.pos[i].x > state.pos[agent].x {
- maxx = isize::min(maxx, state.pos[i].x);
- } else {
- minx = isize::max(minx, state.pos[i].x+1);
+ state: &DJKState, cost: isize, at: usize, ai: usize) {
+ let cur = &state.agents[at][ai];
+
+ let mut minx: isize = cfg.hallway.min;
+ let mut maxx: isize = cfg.hallway.max;
+ for t in 0..4 {
+ 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.pos.y == cfg.hallway_y {
+ if agent.pos.x > cur.pos.x {
+ maxx = isize::min(maxx, agent.pos.x);
+ } else {
+ minx = isize::max(minx, agent.pos.x + 1);
+ }
}
}
}
for x in minx..maxx {
/* skip spots over slots */
- if on_slot!(x) { continue; }
+ if x >= cfg.slot_x.min && x < cfg.slot_x.max
+ && ((x - cfg.slot_x.min) % 2 == 0) { continue; }
let mut nstate = state.clone();
- nstate.pos[agent].x = x;
- nstate.pos[agent].y = HALLWAY;
- nstate.moved_out[agent] = true;
- let ncost = cost + MOVE_COST[agent / 2]
- * state.pos[agent].dist_to(&nstate.pos[agent]);
- nstate.print(&map);
- active.push_increase(nstate, -ncost);
- aoc::debugln!("MOVE OUT {} {}", ncost, active.len());
+ nstate.agents[at][ai].pos.x = x;
+ nstate.agents[at][ai].pos.y = cfg.hallway_y;
+ nstate.agents[at][ai].moved_out = true;
+ let ncost_g = cost + MOVE_COST[at]
+ * state.agents[at][ai].pos.dist_to(&nstate.agents[at][ai].pos);
+ let ncost_f = ncost_g + heuristic(cfg, &nstate);
+
+ let res = costmap.get_mut(&nstate);
+ if res.is_none() || *res.unwrap() > ncost_g {
+ if aoc::get_debug() > 1 {
+ aoc::debugln!("MOVE OUT {} {}", ncost_g, ncost_f);
+ nstate.print(&map);
+ aoc::debugln!("");
+ }
+
+ costmap.insert(nstate.clone(), ncost_g);
+ active.push_increase(nstate, -ncost_f);
+ }
}
}
-fn try_move_in(map: &HashMap<Pos,char>,
+fn try_move_in(map: &HashMap<Pos,char>, cfg: &MapConfig,
+ costmap: &mut HashMap<DJKState,isize>,
active: &mut PriorityQueue<DJKState,isize>,
- state: &DJKState, cost: isize, agent: usize) {
- let mut lower_taken = false;
- for i in 0..8 {
- if i == agent { continue; }
-
- if state.pos[i].y == HALLWAY {
- /* another agent is in the way */
- if state.pos[i].x > state.pos[agent].x {
- if idx2slot!(agent / 2) > state.pos[i].x { return; }
- } else {
- if idx2slot!(agent / 2) < state.pos[i].x { return; }
+ state: &DJKState, cost: isize, at: usize, ai: usize) {
+
+ let mut slot_free_y = cfg.slot_y.max-1;
+ for t in 0..4 {
+ for (i,agent) in state.agents[t].iter().enumerate() {
+ if t == at && i == ai { continue; }
+
+ if agent.pos.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; }
+ } else {
+ if idx2slot!(cfg, at) < agent.pos.x { return; }
+ }
+ } else if agent.pos.x == idx2slot!(cfg, at) {
+ slot_free_y = isize::min(slot_free_y, agent.pos.y - 1);
+ if slot_free_y == cfg.hallway_y { return; }
}
- } else if state.pos[i].x == idx2slot!(agent / 2) {
- /* upper slot taken */
- if state.pos[i].y == SLOT_UPPER { return; }
-
- /* agent of other type in slot */
- if i / 2 != agent / 2 { return }
-
- lower_taken = true;
}
}
- let y = if lower_taken { SLOT_UPPER } else { SLOT_LOWER };
let mut nstate = state.clone();
- nstate.pos[agent].x = idx2slot!(agent / 2);
- nstate.pos[agent].y = y;
- nstate.moved_in[agent] = true;
- let ncost = cost + MOVE_COST[agent / 2]
- * state.pos[agent].dist_to(&nstate.pos[agent]);
- nstate.print(map);
- active.push_increase(nstate, -ncost);
- aoc::debugln!("MOVE IN {} {}", ncost, active.len());
+ 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;
+ let ncost_g = cost + MOVE_COST[at]
+ * state.agents[at][ai].pos.dist_to(&nstate.agents[at][ai].pos);
+ let ncost_f = ncost_g + heuristic(cfg, &nstate);
+
+ let res = costmap.get_mut(&nstate);
+ if res.is_none() || *res.unwrap() > ncost_g {
+ if aoc::get_debug() > 1 {
+ aoc::debugln!("MOVE IN {} {}", ncost_g, ncost_f);
+ nstate.print(map);
+ aoc::debugln!("");
+ }
+
+ costmap.insert(nstate.clone(), ncost_g);
+ active.push_increase(nstate, -ncost_f);
+ }
}
-fn try_move(map: &HashMap<Pos,char>,
+fn try_move(map: &HashMap<Pos,char>, cfg: &MapConfig,
+ costmap: &mut HashMap<DJKState,isize>,
active: &mut PriorityQueue<DJKState,isize>,
- state: &DJKState, cost: isize, agent: usize) -> bool {
- if !state.moved_out[agent] {
- try_move_out(map, active, state, cost, agent);
+ 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.moved_in[agent] {
- try_move_in(map, active, state, cost, agent);
+ } else if !state.agents[at][ai].moved_in {
+ try_move_in(map, cfg, costmap, active, state, cost, at, ai);
return false;
} else {
- return state.moved_in.iter().all(|b| *b);
+ return state.agents.iter().all(|v| v.iter().all(|a| a.moved_in));
}
}
-fn part1(aoc: &mut aoc::Info) {
- let map = parse_input(&aoc.input);
-
+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();
- let mut initial = DJKState {
- moved_out: [false; 8], moved_in: [false; 8],
- pos: [find_pos(&map, 'A')[0], find_pos(&map, 'A')[1],
- find_pos(&map, 'B')[0], find_pos(&map, 'B')[1],
- find_pos(&map, 'C')[0], find_pos(&map, 'C')[1],
- find_pos(&map, 'D')[0], find_pos(&map, 'D')[1]]
- };
- for i in 0..8 {
- if in_slot(&initial, i) {
- initial.moved_in[i] = true;
- initial.moved_out[i] = true;
+ 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 {
+ 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;
+ }
+ initial.agents[idx.unwrap()].push(agent);
}
}
- active.push(initial, 0);
+ active.push(initial.clone(), -heuristic(&cfg, &initial));
+ costmap.insert(initial, 0);
- let mut answer: Option<usize> = None;
let mut advanced: usize = 0;
- while !active.is_empty() && answer.is_none() {
- let (state, mut cost) = active.pop().unwrap();
- cost = -cost; /* inverted for correct priority */
+ while !active.is_empty() {
+ let (state, _) = active.pop().unwrap();
+ let cost_g = *costmap.get(&state).unwrap();
advanced += 1;
- aoc::debugln!("-----------------");
- aoc::debugln!("{}", cost);
- aoc::debugln!("LEN {}", active.len());
if aoc::get_debug() > 1 {
+ aoc::debugln!("-----------------");
+ aoc::debugln!("LEN {}", active.len());
state.print(&map);
aoc::debugln!("");
}
-
- for i in 0..8 {
- let done = try_move(&map, &mut active, &state, cost, i);
- if done {
- aoc::debugln!("ANSWER?");
- answer = Some(cost as usize);
- break;
+ aoc::debugln!("{}", cost_g);
+
+ for t in 0..4 {
+ for i in 0..state.agents[t].len() {
+ let done = try_move(&map, &cfg, &mut costmap,
+ &mut active, &state, cost_g, t, i);
+ if done {
+ aoc::debugln!("ANSWER?");
+ return Some(cost_g as usize);
+ }
}
}
}
aoc::debugln!("Advanced {} states", advanced);
+ return None;
+}
+
+fn extend_map(s_map: &HashMap<Pos,char>, s_cfg: &MapConfig)
+ -> (HashMap<Pos,char>, MapConfig) {
+ let insert: [&str; 2] = [" #D#C#B#A# ", " #D#B#A#C# "];
+
+ let mut map: HashMap<Pos,char> = HashMap::new();
+ for (y,l) in insert.iter().enumerate() {
+ for (x,c) in l.chars().enumerate() {
+ let p = Pos { x: x as isize, y: s_cfg.hallway_y + 1 + (y as isize) };
+ map.insert(p, c);
+ }
+ }
+ for (p,&c) in s_map.iter() {
+ if p.x >= s_cfg.slot_x.min - 1 && p.x < s_cfg.slot_x.max + 1
+ && p.y >= s_cfg.hallway_y + 1 {
+ map.insert(Pos { x: p.x, y: p.y + 2 }, c);
+ } else {
+ map.insert(p.clone(), c);
+ }
+ }
+
+ let mut cfg = s_cfg.clone();
+ cfg.slot_y.max += 2;
+
+ return (map, cfg);
+}
+
+fn part1(aoc: &mut aoc::Info) {
+ let (map,cfg) = parse_input(&aoc.input);
+ let answer = organize(&map, &cfg);
aoc.answer = Some(format!("{}", answer.unwrap()));
+ aoc.solution = Some("15385");
}
-fn part2(_aoc: &mut aoc::Info) {
+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);
+ aoc.answer = Some(format!("{}", answer.unwrap()));
}
fn main() {
diff --git a/src/23/test2 b/src/23/test2
@@ -1,6 +1,6 @@
#############
#...........#
-###B#A#C#D###
- #A#B#C#D#
+###.#C#B#D###
+ #A#B#A#D#
#########
diff --git a/src/23/test3 b/src/23/test3
@@ -0,0 +1,9 @@
+
+
+#############
+#...........#
+###.#C#B#D###
+ #A#B#A#D#
+ #A#B#C#D#
+ #A#B#C#D#
+ #########
