commit 1d67fd6bc08d9c69565e043bcf7d80c4737003a6
parent 95974eb642bd04068de20e0021c42019b53b3e7b
Author: Louis Burda <quent.burda@gmail.com>
Date: Wed, 19 Apr 2023 00:08:12 +0200
[day 23] Implement grid-based djkstra
Diffstat:
6 files changed, 411 insertions(+), 0 deletions(-)
diff --git a/src/23/Cargo.toml b/src/23/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "day23"
+version = "0.1.0"
+edition = "2021"
+
+[dependencies]
+aoc = { path = "../common/aoc" }
+priority-queue = "1.3.1"
diff --git a/src/23/input b/src/23/input
@@ -0,0 +1,6 @@
+#############
+#...........#
+###A#D#A#C###
+ #C#D#B#B#
+ #########
+
diff --git a/src/23/part1 b/src/23/part1
@@ -0,0 +1,126 @@
+--- Day 23: Amphipod ---
+
+A group of amphipods notice your fancy submarine and flag you down. "With such an impressive shell,"
+one amphipod says, "surely you can help us with a question that has stumped our best scientists."
+
+They go on to explain that a group of timid, stubborn amphipods live in a nearby burrow. Four types
+of amphipods live there: [1m[97mAmber[0m (A), [1m[97mBronze[0m (B), [1m[97mCopper[0m (C), and [1m[97mDesert[0m (D). They live in a burrow
+that consists of a [1m[97mhallway[0m and four [1m[97mside rooms[0m. The side rooms are initially full of amphipods, and
+the hallway is initially empty.
+
+They give you a [1m[97mdiagram of the situation[0m (your puzzle input), including locations of each amphipod
+(A, B, C, or D, each of which is occupying an otherwise open space), walls (#), and open space (.).
+
+For example:
+
+#############
+#...........#
+###B#C#B#D###
+ #A#D#C#A#
+ #########
+
+The amphipods would like a method to organize every amphipod into side rooms so that each side room
+contains one type of amphipod and the types are sorted A-D going left to right, like this:
+
+#############
+#...........#
+###A#B#C#D###
+ #A#B#C#D#
+ #########
+
+Amphipods can move up, down, left, or right so long as they are moving into an unoccupied open
+space. Each type of amphipod requires a different amount of [1m[97menergy[0m to move one step: Amber amphipods
+require 1 energy per step, Bronze amphipods require 10 energy, Copper amphipods require 100, and
+Desert ones require 1000. The amphipods would like you to find a way to organize the amphipods that
+requires the [1m[97mleast total energy[0m.
+
+However, because they are timid and stubborn, the amphipods have some extra rules:
+
+
+ - Amphipods will never [1m[97mstop on the space immediately outside any room[0m. They can move into that
+space so long as they immediately continue moving. (Specifically, this refers to the four open
+spaces in the hallway that are directly above an amphipod starting position.)
+
+ - Amphipods will never [1m[97mmove from the hallway into a room[0m unless that room is their destination room
+[1m[97mand[0m that room contains no amphipods which do not also have that room as their own destination. If an
+amphipod's starting room is not its destination room, it can stay in that room until it leaves the
+room. (For example, an Amber amphipod will not move from the hallway into the right three rooms, and
+will only move into the leftmost room if that room is empty or if it only contains other Amber
+amphipods.)
+
+ - Once an amphipod stops moving in the hallway, [1m[97mit will stay in that spot until it can move into a
+room[0m. (That is, once any amphipod starts moving, any other amphipods currently in the hallway are
+locked in place and will not move again until they can move fully into a room.)
+
+
+In the above example, the amphipods can be organized using a minimum of [1m[97m12521[0m energy. One way to do
+this is shown below.
+
+Starting configuration:
+
+#############
+#...........#
+###B#C#B#D###
+ #A#D#C#A#
+ #########
+
+One Bronze amphipod moves into the hallway, taking 4 steps and using 40 energy:
+
+#############
+#...B.......#
+###B#C#.#D###
+ #A#D#C#A#
+ #########
+
+The only Copper amphipod not in its side room moves there, taking 4 steps and using 400 energy:
+
+#############
+#...B.......#
+###B#.#C#D###
+ #A#D#C#A#
+ #########
+
+A Desert amphipod moves out of the way, taking 3 steps and using 3000 energy, and then the Bronze
+amphipod takes its place, taking 3 steps and using 30 energy:
+
+#############
+#.....D.....#
+###B#.#C#D###
+ #A#B#C#A#
+ #########
+
+The leftmost Bronze amphipod moves to its room using 40 energy:
+
+#############
+#.....D.....#
+###.#B#C#D###
+ #A#B#C#A#
+ #########
+
+Both amphipods in the rightmost room move into the hallway, using 2003 energy in total:
+
+#############
+#.....D.D.A.#
+###.#B#C#.###
+ #A#B#C#.#
+ #########
+
+Both Desert amphipods move into the rightmost room using 7000 energy:
+
+#############
+#.........A.#
+###.#B#C#D###
+ #A#B#C#D#
+ #########
+
+Finally, the last Amber amphipod moves into its room, using 8 energy:
+
+#############
+#...........#
+###A#B#C#D###
+ #A#B#C#D#
+ #########
+
+[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
@@ -0,0 +1,260 @@
+use priority_queue::PriorityQueue;
+use std::collections::HashMap;
+
+#[derive(PartialEq,Eq,Hash,Clone,Copy)]
+struct Pos {
+ x: isize,
+ y: isize
+}
+
+#[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]);
+ }
+}
+
+impl DJKState {
+ 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();
+ for y in 0..maxy+1 {
+ for x in 0..maxx+1 {
+ let p = Pos { x, y };
+ let c = map.get(&p);
+ 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;
+ }
+ }
+ }
+ aoc::debug!("{}", nc);
+ }
+ aoc::debugln!("");
+ }
+ }
+}
+
+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: [isize; 4] = [3, 5, 7, 9];
+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 SYMB: [char; 4] = ['A', 'B', 'C', 'D'];
+
+static MOVE_COST: [isize; 4] = [1, 10, 100, 1000];
+
+fn parse_input(input: &str) -> HashMap<Pos,char> {
+ let mut map: HashMap<Pos,char> = HashMap::new();
+ let mut y: usize = 0;
+ for line in input.lines() {
+ if line.is_empty() { continue; }
+ for (x,c) in line.chars().enumerate() {
+ let pos = Pos { x: x as isize, y: y as isize };
+ map.insert(pos, c);
+ }
+ 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!());
+}
+
+fn in_slot(state: &DJKState, agent: usize) -> bool {
+ if state.pos[agent].x == SLOTS[agent / 2] {
+ if state.pos[agent].y == SLOT_END {
+ return true;
+ }
+
+ if state.pos[agent].y == SLOT_BEGIN {
+ 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;
+ }
+ }
+ 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;
+
+ for dir in 0..4 {
+ let npos = state.pos[agent].adj(dir);
+ let ncost = cost + MOVE_COST[agent / 2];
+
+ /* is the adjacent space open? */
+ let res = map.get(&npos);
+ if res.is_none() || *res.unwrap() == '#' { continue; }
+
+ /* is another agent already in that space? */
+ if state.pos.iter().enumerate()
+ .filter(|(i,&p)| *i != agent && p == npos)
+ .next().is_some() { 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; }
+
+ /* 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; }
+
+ let mut nstate = state.clone();
+ nstate.pos[agent] = npos;
+ nstate.moving[agent] = true;
+
+ /* has this state been visited already? */
+ let res = costmap.get(&nstate);
+ if res.is_some() && -*res.unwrap() <= ncost { continue; }
+
+ aoc::debugln!("PUSH {}", ncost);
+ if aoc::get_debug() > 1 {
+ nstate.print(map);
+ }
+ active.push(nstate, -ncost);
+ moved = true;
+ }
+
+ return moved;
+}
+
+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],
+ 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;
+ }
+ }
+ active.push(initial, 0);
+
+ 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();
+ cost = -cost; /* inverted for correct priority */
+
+ advanced += 1;
+
+ costmap.insert(state.clone(), -cost);
+
+ aoc::debugln!("-----------------");
+ aoc::debugln!("{}", cost);
+ aoc::debugln!("LEN {}", active.len());
+ if aoc::get_debug() > 1 {
+ state.print(&map);
+ 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);
+ }
+ }
+
+ aoc::debugln!("Advanced {} states", advanced);
+
+ aoc.answer = Some(format!("{}", answer.unwrap()));
+}
+
+fn part2(_aoc: &mut aoc::Info) {
+}
+
+fn main() {
+ aoc::run(part1, part2);
+}
+
diff --git a/src/23/test1 b/src/23/test1
@@ -0,0 +1,5 @@
+#############
+#...........#
+###B#C#B#D###
+ #A#D#C#A#
+ #########
diff --git a/src/23/test2 b/src/23/test2
@@ -0,0 +1,6 @@
+
+#############
+#...........#
+###B#A#C#D###
+ #A#B#C#D#
+ #########
