commit ea68649cfcea407905507dfbe57a06b86a20e17a
parent 1d67fd6bc08d9c69565e043bcf7d80c4737003a6
Author: Louis Burda <quent.burda@gmail.com>
Date: Wed, 19 Apr 2023 02:03:30 +0200
[Day 23] Simplify state graph
Diffstat:
| A | src/23/part2 | | | 230 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | src/23/src/main.rs | | | 224 | +++++++++++++++++++++++++++++++++++++++++-------------------------------------- |
2 files changed, 345 insertions(+), 109 deletions(-)
diff --git a/src/23/part2 b/src/23/part2
@@ -0,0 +1,230 @@
+--- Part Two ---
+
+As you prepare to give the amphipods your solution, you notice that the diagram they handed you was
+actually folded up. As you unfold it, you discover an extra part of the diagram.
+
+Between the first and second lines of text that contain amphipod starting positions, insert the
+following lines:
+
+ #D#C#B#A#
+ #D#B#A#C#
+
+So, the above example now becomes:
+
+#############
+#...........#
+###B#C#B#D###
+ [1m[97m#D#C#B#A#
+ #D#B#A#C#[0m
+ #A#D#C#A#
+ #########
+
+The amphipods still want to be organized into rooms similar to before:
+
+#############
+#...........#
+###A#B#C#D###
+ #A#B#C#D#
+ #A#B#C#D#
+ #A#B#C#D#
+ #########
+
+In this updated example, the least energy required to organize these amphipods is
+[1m[97m44169[0m:
+
+#############
+#...........#
+###B#C#B#D###
+ #D#C#B#A#
+ #D#B#A#C#
+ #A#D#C#A#
+ #########
+
+#############
+#..........D#
+###B#C#B#.###
+ #D#C#B#A#
+ #D#B#A#C#
+ #A#D#C#A#
+ #########
+
+#############
+#A.........D#
+###B#C#B#.###
+ #D#C#B#.#
+ #D#B#A#C#
+ #A#D#C#A#
+ #########
+
+#############
+#A........BD#
+###B#C#.#.###
+ #D#C#B#.#
+ #D#B#A#C#
+ #A#D#C#A#
+ #########
+
+#############
+#A......B.BD#
+###B#C#.#.###
+ #D#C#.#.#
+ #D#B#A#C#
+ #A#D#C#A#
+ #########
+
+#############
+#AA.....B.BD#
+###B#C#.#.###
+ #D#C#.#.#
+ #D#B#.#C#
+ #A#D#C#A#
+ #########
+
+#############
+#AA.....B.BD#
+###B#.#.#.###
+ #D#C#.#.#
+ #D#B#C#C#
+ #A#D#C#A#
+ #########
+
+#############
+#AA.....B.BD#
+###B#.#.#.###
+ #D#.#C#.#
+ #D#B#C#C#
+ #A#D#C#A#
+ #########
+
+#############
+#AA...B.B.BD#
+###B#.#.#.###
+ #D#.#C#.#
+ #D#.#C#C#
+ #A#D#C#A#
+ #########
+
+#############
+#AA.D.B.B.BD#
+###B#.#.#.###
+ #D#.#C#.#
+ #D#.#C#C#
+ #A#.#C#A#
+ #########
+
+#############
+#AA.D...B.BD#
+###B#.#.#.###
+ #D#.#C#.#
+ #D#.#C#C#
+ #A#B#C#A#
+ #########
+
+#############
+#AA.D.....BD#
+###B#.#.#.###
+ #D#.#C#.#
+ #D#B#C#C#
+ #A#B#C#A#
+ #########
+
+#############
+#AA.D......D#
+###B#.#.#.###
+ #D#B#C#.#
+ #D#B#C#C#
+ #A#B#C#A#
+ #########
+
+#############
+#AA.D......D#
+###B#.#C#.###
+ #D#B#C#.#
+ #D#B#C#.#
+ #A#B#C#A#
+ #########
+
+#############
+#AA.D.....AD#
+###B#.#C#.###
+ #D#B#C#.#
+ #D#B#C#.#
+ #A#B#C#.#
+ #########
+
+#############
+#AA.......AD#
+###B#.#C#.###
+ #D#B#C#.#
+ #D#B#C#.#
+ #A#B#C#D#
+ #########
+
+#############
+#AA.......AD#
+###.#B#C#.###
+ #D#B#C#.#
+ #D#B#C#.#
+ #A#B#C#D#
+ #########
+
+#############
+#AA.......AD#
+###.#B#C#.###
+ #.#B#C#.#
+ #D#B#C#D#
+ #A#B#C#D#
+ #########
+
+#############
+#AA.D.....AD#
+###.#B#C#.###
+ #.#B#C#.#
+ #.#B#C#D#
+ #A#B#C#D#
+ #########
+
+#############
+#A..D.....AD#
+###.#B#C#.###
+ #.#B#C#.#
+ #A#B#C#D#
+ #A#B#C#D#
+ #########
+
+#############
+#...D.....AD#
+###.#B#C#.###
+ #A#B#C#.#
+ #A#B#C#D#
+ #A#B#C#D#
+ #########
+
+#############
+#.........AD#
+###.#B#C#.###
+ #A#B#C#D#
+ #A#B#C#D#
+ #A#B#C#D#
+ #########
+
+#############
+#..........D#
+###A#B#C#.###
+ #A#B#C#D#
+ #A#B#C#D#
+ #A#B#C#D#
+ #########
+
+#############
+#...........#
+###A#B#C#D###
+ #A#B#C#D#
+ #A#B#C#D#
+ #A#B#C#D#
+ #########
+
+Using the initial configuration from the full diagram, [1m[97mwhat is the least energy required to organize
+the amphipods?[0m
+
+
diff --git a/src/23/src/main.rs b/src/23/src/main.rs
@@ -1,6 +1,24 @@
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
+// }
+//}
+
+macro_rules! idx2slot {
+ ( $x:expr ) => {
+ SLOTS_BEGIN + ($x * 2) as isize
+ }
+}
+
#[derive(PartialEq,Eq,Hash,Clone,Copy)]
struct Pos {
x: isize,
@@ -9,19 +27,15 @@ struct Pos {
#[derive(PartialEq,Eq,Hash,Clone,Copy)]
struct DJKState {
- moving: [bool; 8],
moved_out: [bool; 8],
moved_in: [bool; 8],
pos: [Pos; 8]
}
impl Pos {
- fn add(&self, other: &Self) -> Pos {
- return Pos { x: self.x + other.x, y: self.y + other.y };
- }
-
- fn adj(&self, i: usize) -> Self {
- return self.add(&ADJ[i]);
+ fn dist_to(&self, other: &Self) -> isize {
+ return isize::abs(self.x - other.x)
+ + isize::abs(self.y - other.y);
}
}
@@ -50,18 +64,17 @@ impl DJKState {
}
}
-static ADJ: [Pos; 4] = [
- Pos { x: 0, y: -1 },
- Pos { x: 1, y: 0 },
- Pos { x: 0, y: 1 },
- Pos { x: -1, y: 0 }
-];
-
+static SLOTS_BEGIN: isize = 3;
+static SLOTS_END: isize = 10;
static SLOTS: [isize; 4] = [3, 5, 7, 9];
-static SPOTS: [isize; 7] = [1, 2, 4, 6, 8, 10, 11];
+
+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_BEGIN: isize = 2;
-static SLOT_END: isize = 3;
+static SLOT_UPPER: isize = 2;
+static SLOT_LOWER: isize = 3;
static SYMB: [char; 4] = ['A', 'B', 'C', 'D'];
@@ -93,76 +106,113 @@ fn find_pos(map: &HashMap<Pos,char>, sc: char) -> [Pos; 2] {
fn in_slot(state: &DJKState, agent: usize) -> bool {
if state.pos[agent].x == SLOTS[agent / 2] {
- if state.pos[agent].y == SLOT_END {
+ if state.pos[agent].y == SLOT_LOWER {
return true;
}
- if state.pos[agent].y == SLOT_BEGIN {
+ 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_END;
+ && state.pos[other].y == SLOT_LOWER;
}
}
return false;
}
-fn try_move(map: &HashMap<Pos,char>, costmap: &mut HashMap<DJKState,isize>,
- active: &mut PriorityQueue<DJKState,isize>,
- state: &DJKState, cost: isize, agent: usize) -> bool {
- let mut moved = false;
+fn try_move_out(map: &HashMap<Pos,char>,
+ 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; }
- for dir in 0..4 {
- let npos = state.pos[agent].adj(dir);
- let ncost = cost + MOVE_COST[agent / 2];
+ if state.pos[i].x == state.pos[agent].x
+ && state.pos[i].y < state.pos[agent].y { return; }
- /* is the adjacent space open? */
- let res = map.get(&npos);
- if res.is_none() || *res.unwrap() == '#' { continue; }
+ 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);
+ }
+ }
+ }
- /* is another agent already in that space? */
- if state.pos.iter().enumerate()
- .filter(|(i,&p)| *i != agent && p == npos)
- .next().is_some() { continue; }
+ for x in minx..maxx {
+ /* skip spots over slots */
+ if on_slot!(x) { continue; }
- /* is moving from hallway into slot not their own */
- if state.pos[agent].y == HALLWAY && npos.y != HALLWAY
- && npos.x != SLOTS[agent / 2] { 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());
+ }
+}
- /* is moving into slot but there is still a foreign agent in slot */
- if state.pos[agent].y == HALLWAY && npos.y != HALLWAY
- && state.pos.iter().enumerate()
- .filter(|(i,p)| i / 2 != agent / 2 && p.x == SLOTS[agent / 2])
- .next().is_some() { continue; }
+fn try_move_in(map: &HashMap<Pos,char>,
+ 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; }
- let mut nstate = state.clone();
- nstate.pos[agent] = npos;
- nstate.moving[agent] = true;
+ 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; }
+ }
+ } else if state.pos[i].x == idx2slot!(agent / 2) {
+ /* upper slot taken */
+ if state.pos[i].y == SLOT_UPPER { return; }
- /* has this state been visited already? */
- let res = costmap.get(&nstate);
- if res.is_some() && -*res.unwrap() <= ncost { continue; }
+ /* agent of other type in slot */
+ if i / 2 != agent / 2 { return }
- aoc::debugln!("PUSH {}", ncost);
- if aoc::get_debug() > 1 {
- nstate.print(map);
+ lower_taken = true;
}
- active.push(nstate, -ncost);
- moved = true;
}
- return moved;
+ 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());
+}
+
+fn try_move(map: &HashMap<Pos,char>,
+ 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);
+ return false;
+ } else if !state.moved_in[agent] {
+ try_move_in(map, active, state, cost, agent);
+ return false;
+ } else {
+ return state.moved_in.iter().all(|b| *b);
+ }
}
fn part1(aoc: &mut aoc::Info) {
let map = parse_input(&aoc.input);
- let mut costmap: HashMap<DJKState,isize> = HashMap::new();
let mut active: PriorityQueue<DJKState,isize> = PriorityQueue::new();
let mut initial = DJKState {
- moving: [false, false, false, false, false, false, false, false],
- moved_out: [false, false, false, false, false, false, false, false],
- moved_in: [false, false, false, false, false, false, false, false],
+ 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],
@@ -179,13 +229,11 @@ fn part1(aoc: &mut aoc::Info) {
let mut answer: Option<usize> = None;
let mut advanced: usize = 0;
while !active.is_empty() && answer.is_none() {
- let (mut state, mut cost) = active.pop().unwrap();
+ let (state, mut cost) = active.pop().unwrap();
cost = -cost; /* inverted for correct priority */
advanced += 1;
- costmap.insert(state.clone(), -cost);
-
aoc::debugln!("-----------------");
aoc::debugln!("{}", cost);
aoc::debugln!("LEN {}", active.len());
@@ -194,55 +242,13 @@ fn part1(aoc: &mut aoc::Info) {
aoc::debugln!("");
}
- assert!(state.moving.iter().filter(|b| **b).count() <= 1);
- let moving = state.moving.iter().enumerate().filter(|(_,b)| **b).next();
- if moving.is_some() {
- let i = moving.unwrap().0;
- aoc::debugln!("MOVING {}", i / 2);
- try_move(&map, &mut costmap, &mut active, &state, cost, i);
-
- /* try stopping agent */
- state.moving[i] = false;
- if state.pos[i].y == HALLWAY {
- /* cant end in hallway */
- if state.moved_out[i] { continue; }
-
- /* dont stop over a slot */
- if SLOTS.iter().filter(|x| state.pos[i].x == **x)
- .next().is_some() { continue; }
- } else {
- /* must fill up the slot to end */
- if !in_slot(&state, i) { continue; }
- }
-
- if state.pos[i].y != HALLWAY {
- aoc::debugln!("MOVED IN");
- state.moved_out[i] = true;
- state.moved_in[i] = true;
-
- if state.moved_in.iter().all(|b| *b) {
- answer = Some(cost as usize);
- break;
- }
- } else {
- aoc::debugln!("MOVED OUT");
- state.moved_out[i] = true;
- }
-
- costmap.insert(state, cost);
- }
-
- /* start moving other agent or end */
for i in 0..8 {
- if state.moved_in[i] { continue; }
-
- /* dont try to start moving agents into their slot if it
- * is still occupied by agents of other type */
- if state.moved_out[i] && state.pos.iter().enumerate()
- .filter(|(k,p)| *k/2 != i/2 && p.x == SLOTS[i / 2])
- .next().is_some() { continue; }
-
- try_move(&map, &mut costmap, &mut active, &state, cost, i);
+ let done = try_move(&map, &mut active, &state, cost, i);
+ if done {
+ aoc::debugln!("ANSWER?");
+ answer = Some(cost as usize);
+ break;
+ }
}
}
