From 5a09744b94d58001921ec623369c43e6e14661a3 Mon Sep 17 00:00:00 2001 From: Irene Knapp Date: Thu, 23 Dec 2021 02:28:25 -0800 Subject: 23 --- 23/src/main.rs | 837 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 837 insertions(+) create mode 100644 23/src/main.rs (limited to '23/src') diff --git a/23/src/main.rs b/23/src/main.rs new file mode 100644 index 0000000..636337c --- /dev/null +++ b/23/src/main.rs @@ -0,0 +1,837 @@ +use advent_lib::prelude::*; + +use std::collections::BinaryHeap; +use std::collections::HashMap; +use std::cmp::Reverse; + + +#[derive(Debug,Clone,Copy,Eq,PartialEq,Hash)] +enum Amphipod { + A, + B, + C, + D, +} + +#[derive(Debug,Clone,Eq,PartialEq)] +enum Place { + Room(usize), + Hallway(usize), +} + +#[derive(Debug,Clone,Eq,PartialEq)] +struct Parameters { + room_size: usize, +} + +#[derive(Debug,Clone,Eq)] +struct State { + expense_so_far: usize, + hallway: Vec>, + rooms: Vec>, + last_destination: Option, +} + +#[derive(Debug,Clone,Eq,PartialEq,Hash)] +struct StaticState { + hallway: Vec>, + rooms: Vec>, +} + +impl Ord for State { + fn cmp(&self, other: &Self) -> std::cmp::Ordering { + Reverse(&self.expense_so_far).cmp(&Reverse(&other.expense_so_far)) + } +} + +impl PartialOrd for State { + fn partial_cmp(&self, other: &Self) -> Option { + Some(Reverse(&self.expense_so_far).cmp(&Reverse(&other.expense_so_far))) + } +} + +impl PartialEq for State { + fn eq(&self, other: &Self) -> bool { + self.expense_so_far == other.expense_so_far + } +} + + +fn main() -> Result<()> { + let mut args = std::env::args(); + if args.len() != 2 { + eprintln!("Usage: advent input"); + } + let _ = args.next(); + let filename = args.next().unwrap(); + + let input = advent_lib::read_lines_file(&filename)?; + + let mut hallway = Vec::new(); + for _ in 0 .. 11 { + hallway.push(None); + } + + let mut rooms = Vec::new(); + for i in 0 .. 4 { + let mut room = Vec::new(); + let x = 3 + 2 * i; + for j in 0 .. 2 { + let y = 3 - j; + let c = input[y].chars().nth(x).unwrap(); + let amphipod = match c { + 'A' => Amphipod::A, + 'B' => Amphipod::B, + 'C' => Amphipod::C, + 'D' => Amphipod::D, + _ => { panic!("Unexpected character."); } + }; + room.push(amphipod); + } + rooms.push(room); + } + + let initial_state = State { + expense_so_far: 0, + hallway, + rooms, + last_destination: None, + }; + + let expense = find_steps(&Parameters { room_size: 2 }, &initial_state); + println!("{}", expense); + + let mut harder_rooms = Vec::new(); + for i in 0 .. 4 { + let mut harder_room = Vec::new(); + harder_room.push(initial_state.rooms[i][0]); + match i { + 0 => { + harder_room.push(Amphipod::D); + harder_room.push(Amphipod::D); + } + 1 => { + harder_room.push(Amphipod::B); + harder_room.push(Amphipod::C); + } + 2 => { + harder_room.push(Amphipod::A); + harder_room.push(Amphipod::B); + } + 3 => { + harder_room.push(Amphipod::C); + harder_room.push(Amphipod::A); + } + _ => { } + } + harder_room.push(initial_state.rooms[i][1]); + harder_rooms.push(harder_room); + } + let harder_initial_state = State { + expense_so_far: 0, + hallway: initial_state.hallway.clone(), + rooms: harder_rooms, + last_destination: None, + }; + + let harder_expense = find_steps(&Parameters { room_size: 4 }, + &harder_initial_state); + println!("{}", harder_expense); + + Ok(()) +} + + +fn find_steps(parameters: &Parameters, initial_state: &State) -> usize { + let mut exploration_queue = BinaryHeap::new(); + exploration_queue.push(initial_state.clone()); + + let mut visited_states = HashMap::new(); + + //let mut i = 0; + loop { + let state = match exploration_queue.pop() { + None => { panic!("insoluble"); } + Some(state) => { state } + }; + + if is_solved(parameters, &state) { + return state.expense_so_far; + } + + let static_state = StaticState { + hallway: state.hallway.clone(), + rooms: state.rooms.clone(), + }; + + match visited_states.get(&static_state) { + None => { } + Some(_) => { continue; } + } + + visited_states.insert(static_state, state.expense_so_far); + + //i += 1; + //if (parameters.room_size == 4) && (i % 10000 == 0) { + // println!("iteration {}, cost {}", i, state.expense_so_far); + // debug_state(parameters, &state); + //} + + // This is where we would call is_unsolvable() if it worked. + + // All moves that start in a room. + for start_room in 0 .. 4 { + if state.rooms[start_room].len() > 0 { + let start_room_occupancy = state.rooms[start_room].len(); + let amphipod = state.rooms[start_room][start_room_occupancy-1]; + let distance = 1 + parameters.room_size - start_room_occupancy; + + // Don't consider moves that begin at the most recent destination. + match state.last_destination { + Some(Place::Room(last_room)) => { + if start_room == last_room { + continue; + } + } + _ => { } + } + + // It only makes sense to move an amphipod out of their destination + // room if there are amphipods that don't want to be there below + // them. + if amphipod_destination_room(&hipod) == start_room { + let mut should_skip = true; + for i in 0 .. start_room_occupancy { + let occupant = state.rooms[start_room][i]; + if occupant != amphipod { + should_skip = false; + break; + } + } + if should_skip { + continue; + } + } + + { + // All *leftward* moves that start in a room. + let mut hallway = hallway_left_of_room(start_room); + let mut distance = distance + 1; + + loop { + if state.hallway[hallway].is_some() { + break; + } + + // At each step along the hallway, enqueue a search state that + // has the amphipod stopped at that location. + enqueue_move_to_hallway(&state, &hipod, Place::Room(start_room), + hallway, distance, &mut exploration_queue, &visited_states); + + match adjacent_room_left_of_hallway(hallway) { + None => { }, + Some(end_room) => { + enqueue_move_to_room(parameters, &state, &hipod, + Place::Room(start_room), end_room, distance, + &mut exploration_queue, &visited_states); + } + } + + match hallway_left_of_hallway(hallway) { + None => { break; }, + Some(new_hallway) => { + distance += hallway - new_hallway; + hallway = new_hallway; + } + } + } + } + + { + // All *rightward* moves that start in a room. + let mut hallway = hallway_right_of_room(start_room); + let mut distance = distance + 1; + + loop { + if state.hallway[hallway].is_some() { + break; + } + + // At each step along the hallway, enqueue a search state that + // has the amphipod stopped at that location. + enqueue_move_to_hallway(&state, &hipod, Place::Room(start_room), + hallway, distance, &mut exploration_queue, &visited_states); + + match adjacent_room_right_of_hallway(hallway) { + None => { }, + Some(end_room) => { + enqueue_move_to_room(parameters, &state, &hipod, + Place::Room(start_room), end_room, distance, + &mut exploration_queue, &visited_states); + } + } + + match hallway_right_of_hallway(hallway) { + None => { break; }, + Some(new_hallway) => { + distance += new_hallway - hallway; + hallway = new_hallway; + } + } + } + } + } + } + + // All moves that start in a hallway. + for start_hallway in 0 .. 11 { + // Don't consider moves that begin at the most recent destination. + match state.last_destination { + Some(Place::Hallway(last_hallway)) => { + if start_hallway == last_hallway { + continue; + } + } + _ => { } + } + + match state.hallway[start_hallway] { + None => { } + Some(amphipod) => { + let distance = 0; + + { + // All *leftward* moves that start in a hallway. + let mut hallway = start_hallway; + let mut distance = distance; + + loop { + match adjacent_room_left_of_hallway(hallway) { + None => { }, + Some(end_room) => { + enqueue_move_to_room(parameters, &state, &hipod, + Place::Hallway(start_hallway), end_room, distance, + &mut exploration_queue, &visited_states); + } + } + + match hallway_left_of_hallway(hallway) { + None => { break; }, + Some(new_hallway) => { + if state.hallway[new_hallway].is_some() { + break; + } + + distance += hallway - new_hallway; + hallway = new_hallway; + } + } + } + } + + { + // All *rightward* moves that start in a hallway. + let mut hallway = start_hallway; + let mut distance = distance; + + loop { + match adjacent_room_right_of_hallway(hallway) { + None => { }, + Some(end_room) => { + enqueue_move_to_room(parameters, &state, &hipod, + Place::Hallway(start_hallway), end_room, distance, + &mut exploration_queue, &visited_states); + } + } + + match hallway_right_of_hallway(hallway) { + None => { break; }, + Some(new_hallway) => { + if state.hallway[new_hallway].is_some() { + break; + } + + distance += new_hallway - hallway; + hallway = new_hallway; + } + } + } + } + } + } + } + } +} + + +fn enqueue_move_to_room(parameters: &Parameters, state: &State, + amphipod: &Amphipod, start: Place, end_room: usize, distance: usize, + exploration_queue: &mut BinaryHeap, + visited_states: &HashMap) +{ + if room_is_viable_destination(parameters, state, amphipod, end_room) { + let end_room_occupancy = state.rooms[end_room].len(); + let mut new_state = state.clone(); + + match start { + Place::Hallway(start_hallway) => { + new_state.hallway[start_hallway] = None; + } + Place::Room(start_room) => { + let _ = new_state.rooms[start_room].pop(); + } + } + + new_state.rooms[end_room].push(*amphipod); + let distance = distance + 1 + parameters.room_size - end_room_occupancy; + new_state.expense_so_far += amphipod_expense(&hipod, distance); + new_state.last_destination = Some(Place::Room(end_room)); + + enqueue_state(new_state, exploration_queue, visited_states); + } +} + + +fn enqueue_move_to_hallway(state: &State, amphipod: &Amphipod, start: Place, + end_hallway: usize, distance: usize, + exploration_queue: &mut BinaryHeap, + visited_states: &HashMap) +{ + let mut new_state = state.clone(); + match start { + Place::Room(start_room) => { + let _ = new_state.rooms[start_room].pop(); + } + _ => { } + } + new_state.hallway[end_hallway] = Some(*amphipod); + new_state.expense_so_far += amphipod_expense(&hipod, distance); + new_state.last_destination = Some(Place::Hallway(end_hallway)); + + enqueue_state(new_state, exploration_queue, visited_states); +} + + +fn enqueue_state(state: State, exploration_queue: &mut BinaryHeap, + visited_states: &HashMap) +{ + let should_enqueue = match visited_states.get(&StaticState { + hallway: state.hallway.clone(), + rooms: state.rooms.clone(), + }) { + None => { true } + Some(already_tried_expense) => { + state.expense_so_far < *already_tried_expense + } + }; + + if should_enqueue { + exploration_queue.push(state); + } +} + + +fn room_is_viable_destination(parameters: &Parameters, state: &State, + amphipod: &Amphipod, end_room: usize) + -> bool +{ + let end_room_occupancy = state.rooms[end_room].len(); + + if end_room_occupancy == parameters.room_size { + return false; + } + + if amphipod_destination_room(&hipod) != end_room { + return false; + } + + for existing_occupant in &state.rooms[end_room] { + if amphipod != existing_occupant { + return false; + } + } + + true +} + + +fn is_solved(parameters: &Parameters, state: &State) -> bool { + for hallway in 0 .. 11 { + if state.hallway[hallway].is_some() { + return false; + } + } + + for room in 0 .. 4 { + let occupants = &state.rooms[room]; + if occupants.len() != parameters.room_size { + return false; + } + for occupant in occupants { + if amphipod_destination_room(occupant) != room { + return false; + } + } + } + + true +} + + +#[allow(dead_code)] +// This function does not work - it returns true in cases that are still +// solvable. It is retained as a salve to my ego. +fn is_unsolvable(state: &State) -> bool { + // Consider pieces which are in rooms other than their destinations. There + // are certain scenarios in which we can prove that these pieces can never + // reach their destinations. + for start_room in 0 .. 4 { + for occupant in &state.rooms[start_room] { + let end_room = amphipod_destination_room(occupant); + + // Break this into two cases, one in which we search left and an + // almost-identical one in which we search right. + if start_room > end_room { + // First, check whether there is an available stash space to the + // right. If there is, we can't prove anything useful, so keep + // searching. + let stash_hallway = hallway_right_of_room(start_room); + match state.hallway[stash_hallway] { + None => { + continue; + }, + Some(_) => { }, + } + + // Now that we know there is no stash space, check whether we and an + // amphipod in the hallway will block each other. + let mut hallway = hallway_left_of_room(start_room); + loop { + match state.hallway[hallway] { + None => { }, + Some(blocker) => { + if amphipod_destination_room(&blocker) == start_room { + return true; + } + } + } + + match adjacent_room_left_of_hallway(hallway) { + None => { }, + Some(intermediate_room) => { + if intermediate_room == end_room { + break; + } + } + } + + match hallway_left_of_hallway(hallway) { + None => { + break; + }, + Some(new_hallway) => { + hallway = new_hallway; + } + } + } + } else if start_room < end_room { + // First, check whether there is an available stash space to the + // left. If there is, we can't prove anything useful, so keep + // searching. + let stash_hallway = hallway_left_of_room(start_room); + match state.hallway[stash_hallway] { + None => { + continue; + }, + Some(_) => { }, + } + + // Now that we know there is no stash space, check whether we and an + // amphipod in the hallway will block each other. + let mut hallway = hallway_right_of_room(start_room); + loop { + match state.hallway[hallway] { + None => { }, + Some(blocker) => { + if amphipod_destination_room(&blocker) == start_room { + return true; + } + } + } + + match adjacent_room_right_of_hallway(hallway) { + None => { } + Some(intermediate_room) => { + if intermediate_room == end_room { + break; + } + } + } + + match hallway_right_of_hallway(hallway) { + None => { + break; + }, + Some(new_hallway) => { + hallway = new_hallway; + } + } + } + } + } + } + + // Consider pieces which are in the hallway. There are certain cases in + // which these pieces can never reach their destinations. + for start_hallway in 0 .. 11 { + match state.hallway[start_hallway] { + None => { } + Some(amphipod) => { + let end_room = amphipod_destination_room(&hipod); + + if is_room_left_of_hallway(end_room, start_hallway) { + // This amphipod must move left to reach its destination. + let mut hallway = start_hallway; + + loop { + match adjacent_room_left_of_hallway(hallway) { + None => { }, + Some(new_room) => { + if new_room == end_room { + break; + } + } + } + + match hallway_left_of_hallway(hallway) { + None => { + break; + } + Some(new_hallway) => { + match state.hallway[new_hallway] { + None => { } + Some(blocker) => { + // If the blocker needs to go somewhere that's on the + // far side of the start point, the configuration is + // unsolvable. + let blocker_destination = + amphipod_destination_room(&blocker); + if is_room_right_of_hallway( + blocker_destination, start_hallway) + { + return true; + } + } + } + + hallway = new_hallway; + } + } + } + } else { + // This amphipod must move right to reach its destination. + let mut hallway = start_hallway; + + loop { + match adjacent_room_right_of_hallway(hallway) { + None => { }, + Some(new_room) => { + if new_room == end_room { + break; + } + } + } + + match hallway_right_of_hallway(hallway) { + None => { + break; + } + Some(new_hallway) => { + match state.hallway[new_hallway] { + None => { } + Some(blocker) => { + // If the blocker needs to go somewhere that's on the + // far side of the start point, the configuration is + // unsolvable. + let blocker_destination = + amphipod_destination_room(&blocker); + if is_room_left_of_hallway( + blocker_destination, start_hallway) + { + return true; + } + } + } + + hallway = new_hallway; + } + } + } + } + } + } + } + + false +} + + +fn amphipod_expense(amphipod: &Amphipod, distance: usize) -> usize { + distance * match amphipod { + Amphipod::A => 1, + Amphipod::B => 10, + Amphipod::C => 100, + Amphipod::D => 1000, + } +} + + +fn hallway_left_of_room(room_index: usize) -> usize { + 1 + room_index * 2 +} + +fn hallway_right_of_room(room_index: usize) -> usize { + 3 + room_index * 2 +} + +fn hallway_left_of_hallway(hallway_index: usize) -> Option { + if hallway_index == 0 { + None + } else if hallway_index == 1 { + Some(0) + } else if hallway_index == 3 { + Some(1) + } else if hallway_index == 5 { + Some(3) + } else if hallway_index == 7 { + Some(5) + } else if hallway_index == 9 { + Some(7) + } else if hallway_index == 10 { + Some(9) + } else { + panic!("Invalid hallway index {}", hallway_index); + } +} + +fn hallway_right_of_hallway(hallway_index: usize) -> Option { + if hallway_index == 0 { + Some(1) + } else if hallway_index == 1 { + Some(3) + } else if hallway_index == 3 { + Some(5) + } else if hallway_index == 5 { + Some(7) + } else if hallway_index == 7 { + Some(9) + } else if hallway_index == 9 { + Some(10) + } else if hallway_index == 10 { + None + } else { + panic!("Invalid hallway index {}", hallway_index); + } +} + +fn adjacent_room_right_of_hallway(hallway_index: usize) -> Option { + if hallway_index == 1 { + Some(0) + } else if hallway_index == 3 { + Some(1) + } else if hallway_index == 5 { + Some(2) + } else if hallway_index == 7 { + Some(3) + } else { + None + } +} + +fn adjacent_room_left_of_hallway(hallway_index: usize) -> Option { + if hallway_index == 9 { + Some(3) + } else if hallway_index == 7 { + Some(2) + } else if hallway_index == 5 { + Some(1) + } else if hallway_index == 3 { + Some(0) + } else { + None + } +} + +fn is_room_left_of_hallway(room_index: usize, hallway_index: usize) -> bool { + hallway_right_of_room(room_index) <= hallway_index +} + +fn is_room_right_of_hallway(room_index: usize, hallway_index: usize) -> bool { + hallway_left_of_room(room_index) >= hallway_index +} + + +fn amphipod_destination_room(amphipod: &Amphipod) -> usize { + match amphipod { + Amphipod::A => 0, + Amphipod::B => 1, + Amphipod::C => 2, + Amphipod::D => 3, + } +} + + +#[allow(dead_code)] +fn debug_state(parameters: &Parameters, state: &State) { + println!("#############"); + + print!("#"); + for hallway in 0 .. 11 { + match state.hallway[hallway] { + None => { print!("."); } + Some(amphipod) => { debug_amphipod(&hipod); } + } + } + println!("#"); + + print!("###"); + for room in 0 .. 4 { + if state.rooms[room].len() == parameters.room_size { + debug_amphipod(&state.rooms[room][parameters.room_size - 1]); + } else { + print!("."); + } + print!("#"); + } + println!("##"); + + for i in 0 .. parameters.room_size - 1 { + print!(" #"); + for room in 0 .. 4 { + let index = parameters.room_size - 2 - i; + if state.rooms[room].len() >= index + 1 { + debug_amphipod(&state.rooms[room][index]); + } else { + print!("."); + } + print!("#"); + } + println!(""); + } + + println!(" #########"); + + println!(""); +} + + +#[allow(dead_code)] +fn debug_amphipod(amphipod: &Amphipod) { + match amphipod { + Amphipod::A => { print!("A"); } + Amphipod::B => { print!("B"); } + Amphipod::C => { print!("C"); } + Amphipod::D => { print!("D"); } + } +} + -- cgit 1.4.1