commit af7aee76aea2b6a7bfd2f2d49d9c1f2487672c92
parent 67a315a49eb5f6a607c23a7c2af5116914ad1bc1
Author: Louis Burda <quent.burda@gmail.com>
Date: Wed, 19 Apr 2023 16:46:29 +0200
[Day 23] Enable optimizations and use binaryheap pq
Diffstat:
2 files changed, 142 insertions(+), 60 deletions(-)
diff --git a/src/23/src/main.rs b/src/23/src/main.rs
@@ -1,5 +1,5 @@
-use priority_queue::PriorityQueue;
-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 ) => {
@@ -13,9 +13,11 @@ struct Pos {
y: isize
}
-#[derive(PartialEq,Eq,Hash,Clone)]
+#[derive(Clone)]
struct DJKState {
- agents: [[Pos; 4]; 4]
+ agents: [[Pos; 4]; 4],
+ cost: usize,
+ total: usize
}
#[derive(Clone)]
@@ -36,13 +38,66 @@ struct MapConfig {
fixed: [[bool; 4]; 4]
}
+// struct FastHasher(u64);
+
static AGENT_SYMBS: [char; 4] = ['A', 'B', 'C', 'D'];
-static MOVE_COST: [isize; 4] = [1, 10, 100, 1000];
+static MOVE_COST: [usize; 4] = [1, 10, 100, 1000];
+
+// impl Default for FastHasher {
+// fn default() -> Self {
+// return FastHasher(0xcbf29ce484222325);
+// }
+// }
+//
+// impl Hasher for FastHasher {
+// #[inline]
+// fn finish(&self) -> u64 {
+// self.0
+// }
+//
+// #[inline]
+// fn write(&mut self, bytes: &[u8]) {
+// let FastHasher(mut hash) = *self;
+//
+// for byte in bytes.iter() {
+// hash = hash ^ (*byte as u64);
+// hash = hash.wrapping_mul(0x100000001b3);
+// }
+//
+// *self = FastHasher(hash);
+// }
+// }
impl Pos {
- fn dist_to(&self, other: &Self) -> isize {
- return isize::abs(self.x - other.x)
- + isize::abs(self.y - other.y);
+ fn dist_to(&self, other: &Self) -> usize {
+ return (isize::abs(self.x - other.x)
+ + isize::abs(self.y - other.y)) as usize;
+ }
+}
+
+impl Eq for DJKState { }
+
+impl PartialEq for DJKState {
+ fn eq(&self, other: &Self) -> bool {
+ return self.total == other.total;
+ }
+}
+
+impl Ord for DJKState {
+ fn cmp(&self, other: &Self) -> std::cmp::Ordering {
+ Reverse(self.total).cmp(&Reverse(other.total))
+ }
+}
+
+impl PartialOrd for DJKState {
+ fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
+ Some(Reverse(self.total).cmp(&Reverse(other.total)))
+ }
+}
+
+impl Hash for DJKState {
+ fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
+ self.agents.hash(state)
}
}
@@ -105,15 +160,15 @@ fn parse_input(input: &str) -> (HashMap<Pos,char>, MapConfig) {
slot_y: Range { min: 1, max: y - 1 },
agent_cnt: (y - 3) as usize,
type_cnt: 4,
- initial: DJKState { agents: [ [Pos { x: 0, y: 0 }; 4]; 4 ] },
+ initial: DJKState { agents: [ [Pos { x: 0, y: 0 }; 4]; 4 ], cost: 0, total: 0 },
fixed: [ [false; 4]; 4 ],
};
return (map, cfg);
}
-fn heuristic(cfg: &MapConfig, state: &DJKState) -> isize {
- let mut cost: isize = 0;
+fn heuristic(cfg: &MapConfig, state: &DJKState) -> usize {
+ let mut cost: usize = 0;
for t in 0..cfg.type_cnt {
for i in 0..cfg.agent_cnt {
let agent = state.agents[t][i];
@@ -127,9 +182,9 @@ fn heuristic(cfg: &MapConfig, state: &DJKState) -> isize {
}
fn try_move_out(map: &HashMap<Pos,char>, cfg: &MapConfig,
- costmap: &mut HashMap<DJKState,isize>,
- active: &mut PriorityQueue<DJKState,isize>,
- state: &DJKState, cost: isize, at: usize, ai: usize) {
+ costmap: &mut HashMap<[[Pos; 4]; 4],usize>,
+ active: &mut BinaryHeap<DJKState>,
+ state: &DJKState, at: usize, ai: usize) {
let cur = &state.agents[at][ai];
let mut minx: isize = cfg.hallway.min;
@@ -159,28 +214,34 @@ fn try_move_out(map: &HashMap<Pos,char>, cfg: &MapConfig,
let mut nstate = state.clone();
nstate.agents[at][ai].x = x;
nstate.agents[at][ai].y = cfg.hallway_y;
- let ncost_g = cost + MOVE_COST[at]
+ nstate.cost = state.cost + MOVE_COST[at]
* state.agents[at][ai].dist_to(&nstate.agents[at][ai]);
- let ncost_f = ncost_g + heuristic(cfg, &nstate);
- let res = costmap.get_mut(&nstate);
- if res.is_none() || *res.unwrap() > ncost_g {
+ let res = costmap.get_mut(&nstate.agents);
+ if res.is_none() || **res.as_ref().unwrap() > nstate.cost {
+ nstate.total = nstate.cost + heuristic(cfg, &nstate);
+
if aoc::get_debug() > 1 {
- aoc::debugln!("MOVE OUT {} {}", ncost_g, ncost_f);
+ aoc::debugln!("MOVE OUT {} {}", nstate.cost, nstate.total);
nstate.print(cfg, map);
aoc::debugln!("");
}
- costmap.insert(nstate.clone(), ncost_g);
- active.push_increase(nstate, -ncost_f);
+ if res.is_none() {
+ costmap.insert(nstate.agents.clone(), nstate.cost);
+ } else {
+ *res.unwrap() = nstate.cost;
+ }
+
+ active.push(nstate);
}
}
}
fn try_move_in(map: &HashMap<Pos,char>, cfg: &MapConfig,
- costmap: &mut HashMap<DJKState,isize>,
- active: &mut PriorityQueue<DJKState,isize>,
- state: &DJKState, cost: isize, at: usize, ai: usize) {
+ costmap: &mut HashMap<[[Pos; 4]; 4],usize>,
+ 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 {
@@ -205,47 +266,54 @@ fn try_move_in(map: &HashMap<Pos,char>, cfg: &MapConfig,
let mut nstate = state.clone();
nstate.agents[at][ai].x = idx2slot!(cfg, at);
nstate.agents[at][ai].y = slot_free_y;
- let ncost_g = cost + MOVE_COST[at]
+ nstate.cost = state.cost + MOVE_COST[at]
* state.agents[at][ai].dist_to(&nstate.agents[at][ai]);
- let ncost_f = ncost_g + heuristic(cfg, &nstate);
- let res = costmap.get_mut(&nstate);
- if res.is_none() || *res.unwrap() > ncost_g {
+ let res = costmap.get_mut(&nstate.agents);
+ if res.is_none() || **res.as_ref().unwrap() > nstate.cost {
+ nstate.total = nstate.cost + heuristic(cfg, &nstate);
+
if aoc::get_debug() > 1 {
- aoc::debugln!("MOVE IN {} {}", ncost_g, ncost_f);
+ aoc::debugln!("MOVE IN {} {}", nstate.cost, nstate.total);
nstate.print(cfg, map);
aoc::debugln!("");
}
- costmap.insert(nstate.clone(), ncost_g);
- active.push_increase(nstate, -ncost_f);
+ if res.is_none() {
+ costmap.insert(nstate.agents.clone(), nstate.cost);
+ } else {
+ *res.unwrap() = nstate.cost;
+ }
+
+ active.push(nstate);
}
}
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 {
+ costmap: &mut HashMap<[[Pos; 4]; 4],usize>,
+ active: &mut BinaryHeap<DJKState>,
+ state: &DJKState, at: usize, ai: usize) {
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);
+ try_move_out(map, cfg, costmap, active, state, at, ai);
} else {
- try_move_in(map, cfg, costmap, active, state, cost, at, ai);
+ try_move_in(map, cfg, costmap, active, state, at, ai);
}
- return false;
- } else {
- for t in 0..cfg.type_cnt {
- for i in 0..cfg.agent_cnt {
- if !state.moved_in(t, i, cfg) { return false; }
- }
+ }
+}
+
+fn all_moved_in(state: &DJKState, cfg: &MapConfig) -> bool {
+ for t in 0..cfg.type_cnt {
+ for i in 0..cfg.agent_cnt {
+ if !state.moved_in(t, i, cfg) { return false; }
}
- return true;
}
+ return true;
}
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 active = BinaryHeap::with_capacity(10000000);
+ let mut costmap: HashMap<[[Pos; 4]; 4],usize> = HashMap::with_capacity(10000000);
let mut counts: [usize; 4] = [0; 4];
for (p,c) in map.iter() {
@@ -262,13 +330,14 @@ fn organize(map: &HashMap<Pos,char>, cfg: &mut MapConfig) -> Option<usize> {
counts[t] += 1;
}
}
- active.push(cfg.initial.clone(), -heuristic(&cfg, &cfg.initial));
- costmap.insert(cfg.initial.clone(), 0);
+ 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();
- let cost_g = *costmap.get(&state).unwrap();
+ let state = active.pop().unwrap();
advanced += 1;
@@ -278,16 +347,16 @@ fn organize(map: &HashMap<Pos,char>, cfg: &mut MapConfig) -> Option<usize> {
state.print(&cfg, &map);
aoc::debugln!("");
}
- aoc::debugln!("{}", cost_g);
+ 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 {
- 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);
- }
+ try_move(&map, &cfg, &mut costmap,
+ &mut active, &state, t, i);
}
}
}
@@ -304,13 +373,13 @@ fn extend_map(s_map: &HashMap<Pos,char>, s_cfg: &MapConfig)
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) };
+ let p = Pos { x: x as isize, y: s_cfg.hallway_y + 2 + (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 {
+ && p.y > s_cfg.hallway_y + 1 {
map.insert(Pos { x: p.x, y: p.y + 2 }, c);
} else {
map.insert(p.clone(), c);
@@ -319,6 +388,7 @@ fn extend_map(s_map: &HashMap<Pos,char>, s_cfg: &MapConfig)
let mut cfg = s_cfg.clone();
cfg.slot_y.max += 2;
+ cfg.agent_cnt += 2;
return (map, cfg);
}
diff --git a/src/Makefile b/src/Makefile
@@ -12,8 +12,20 @@ clean:: $1/clean
.PHONY: $1/run $1/clean
-$1/main: $1/src/main.rs
- cd $1 && cargo build && cp ./target/debug/day$1 main
+$1/target/debug/day$1: $1/src/main.rs
+ @cd $1 && cargo build
+
+$1/target/release/day$1: $1/src/main.rs
+ @cd $1 && cargo build -r
+
+$1/main: $1/target/release/day$1
+ @cp $1/target/release/day$1 $1/main
+
+$1/debug1: $1/target/debug/day$1
+ @cd $1 && time ./target/debug/day$1 1
+
+$1/debug2: $1/target/debug/day$1
+ @cd $1 && time ./target/debug/day$1 2
$1/run1: $1/main
@cd $1 && time ./main 1
