diff options
Diffstat (limited to '23')
| -rw-r--r-- | 23/Cargo.toml | 11 | ||||
| -rw-r--r-- | 23/input | 5 | ||||
| -rw-r--r-- | 23/small | 136 | ||||
| -rw-r--r-- | 23/src/main.rs | 837 | ||||
| -rw-r--r-- | 23/tests/main.rs | 17 |
5 files changed, 1006 insertions, 0 deletions
diff --git a/23/Cargo.toml b/23/Cargo.toml new file mode 100644 index 0000000..28383e3 --- /dev/null +++ b/23/Cargo.toml @@ -0,0 +1,11 @@ +[package] +name = "advent_23" +version = "0.1.0" +authors = ["Irene Knapp <ireneista@gmail.com>"] +edition = "2018" + +[dependencies] +advent_lib = { path = "../lib" } + +[dev-dependencies] +assert_cmd = "0.10" diff --git a/23/input b/23/input new file mode 100644 index 0000000..3c41777 --- /dev/null +++ b/23/input @@ -0,0 +1,5 @@ +############# +#...........# +###A#D#B#C### + #B#C#D#A# + ######### diff --git a/23/small b/23/small new file mode 100644 index 0000000..4e496e9 --- /dev/null +++ b/23/small @@ -0,0 +1,136 @@ +--- scanner 0 --- +404,-588,-901 +528,-643,409 +-838,591,734 +390,-675,-793 +-537,-823,-458 +-485,-357,347 +-345,-311,381 +-661,-816,-575 +-876,649,763 +-618,-824,-621 +553,345,-567 +474,580,667 +-447,-329,318 +-584,868,-557 +544,-627,-890 +564,392,-477 +455,729,728 +-892,524,684 +-689,845,-530 +423,-701,434 +7,-33,-71 +630,319,-379 +443,580,662 +-789,900,-551 +459,-707,401 + +--- scanner 1 --- +686,422,578 +605,423,415 +515,917,-361 +-336,658,858 +95,138,22 +-476,619,847 +-340,-569,-846 +567,-361,727 +-460,603,-452 +669,-402,600 +729,430,532 +-500,-761,534 +-322,571,750 +-466,-666,-811 +-429,-592,574 +-355,545,-477 +703,-491,-529 +-328,-685,520 +413,935,-424 +-391,539,-444 +586,-435,557 +-364,-763,-893 +807,-499,-711 +755,-354,-619 +553,889,-390 + +--- scanner 2 --- +649,640,665 +682,-795,504 +-784,533,-524 +-644,584,-595 +-588,-843,648 +-30,6,44 +-674,560,763 +500,723,-460 +609,671,-379 +-555,-800,653 +-675,-892,-343 +697,-426,-610 +578,704,681 +493,664,-388 +-671,-858,530 +-667,343,800 +571,-461,-707 +-138,-166,112 +-889,563,-600 +646,-828,498 +640,759,510 +-630,509,768 +-681,-892,-333 +673,-379,-804 +-742,-814,-386 +577,-820,562 + +--- scanner 3 --- +-589,542,597 +605,-692,669 +-500,565,-823 +-660,373,557 +-458,-679,-417 +-488,449,543 +-626,468,-788 +338,-750,-386 +528,-832,-391 +562,-778,733 +-938,-730,414 +543,643,-506 +-524,371,-870 +407,773,750 +-104,29,83 +378,-903,-323 +-778,-728,485 +426,699,580 +-438,-605,-362 +-469,-447,-387 +509,732,623 +647,635,-688 +-868,-804,481 +614,-800,639 +595,780,-596 + +--- scanner 4 --- +727,592,562 +-293,-554,779 +441,611,-461 +-714,465,-776 +-743,427,-804 +-660,-479,-426 +832,-632,460 +927,-485,-438 +408,393,-506 +466,436,-512 +110,16,151 +-258,-428,682 +-393,719,612 +-211,-452,876 +808,-476,-593 +-575,615,604 +-485,667,467 +-680,325,-822 +-627,-443,-432 +872,-547,-609 +833,512,582 +807,604,487 +839,-516,451 +891,-625,532 +-652,-548,-490 +30,-46,-14 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<Option<Amphipod>>, + rooms: Vec<Vec<Amphipod>>, + last_destination: Option<Place>, +} + +#[derive(Debug,Clone,Eq,PartialEq,Hash)] +struct StaticState { + hallway: Vec<Option<Amphipod>>, + rooms: Vec<Vec<Amphipod>>, +} + +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<std::cmp::Ordering> { + 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<State>, + visited_states: &HashMap<StaticState,usize>) +{ + 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<State>, + visited_states: &HashMap<StaticState,usize>) +{ + 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<State>, + visited_states: &HashMap<StaticState,usize>) +{ + 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<usize> { + 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<usize> { + 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<usize> { + 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<usize> { + 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"); } + } +} + diff --git a/23/tests/main.rs b/23/tests/main.rs new file mode 100644 index 0000000..6f37464 --- /dev/null +++ b/23/tests/main.rs @@ -0,0 +1,17 @@ +use assert_cmd::prelude::*; +//use predicates::prelude::*; +use std::process::Command; + + +#[test] +fn personal_input() -> Result<(), Box<dyn std::error::Error>> { + let mut command = Command::cargo_bin("advent_23")?; + + command.arg("input"); + command.assert().success().stdout( + "13336\n\ + 53308\n"); + + Ok(()) +} + |