GÄr att se denna som ett 1D-problem, i alla fall sÄ lÀnge som rummen har en relativ begrÀnsad storlek (i mitt fall fungerar det ha ha upp till 9 st i varje rum, 19 st och man utökar storleken pÄ tillstÄndet frÄn 32-bitar per position till 64-bitar).
Testade först, likt mÄnga andra, med Dijkstra dÄ det "rimligen borde vara mer effektivt". Fungerade, men för mig var en DFS betydligt snabbare + en sÄdan Àr lÀttare att sprida över flera kÀrnor.
Ihop med DFS körs en memoize för att eliminera kombinationer av samma lösning.
GÄr att köra pÄ ~90 ms pÄ M1 och ~65 ms pÄ 5950X. Men Àr inte precis den kortaste lösningen... Givet att kÀrnorna lastas rÀtt nÀra 100 % Àr det brutalt ineffektiv anvÀndning av kÀrnor, inte miljöklassad... Tar ca 150 ms att lösa pÄ en trÄd pÄ M1, bl.a. fungerar memoize-delen betydligt bÀttre ju fÀrre trÄdar man anvÀnder.
use crate::solution::Solution;
use fnv::FnvHashSet;
use rayon::prelude::*;
struct Day23 {
initial_state: State,
}
impl Solution for Day23 {
fn part1(&mut self) -> String {
self.organize().to_string()
}
fn part2(&mut self) -> String {
for (i, a) in [(4, 4), (3, 2), (2, 1), (1, 3)].iter().enumerate() {
let mut loc = self.initial_state.map[i * 2 + 2];
let p4 = (loc >> 6) & 0x7;
loc &= !0xffc0;
loc |= (p4 << 12) + (a.1 << 9) + (a.0 << 6);
loc += 0x2_0000;
self.initial_state.map[i * 2 + 2] = loc;
}
self.organize().to_string()
}
}
impl Day23 {
fn organize(&self) -> u32 {
let mut start_states = Vec::new();
for i in 0..11 {
if let Some(new_state) = self.initial_state.try_move_to_final_pos(i) {
start_states.push(new_state);
} else if is_room(i) {
for new_state in self.initial_state.hallway_moves(i) {
start_states.push(new_state);
}
}
}
start_states.par_iter().map(sub_organize).min().unwrap()
}
}
fn sub_organize(start_state: &State) -> u32 {
let mut memoize = FnvHashSet::default();
let mut stack = vec![*start_state];
let mut min_energy = u32::MAX;
while let Some(state) = stack.pop() {
if state.energy >= min_energy {
continue;
}
if state.is_done() {
min_energy = state.energy;
} else {
memoize.insert(state);
}
for i in 0..11 {
if let Some(new_state) = state.try_move_to_final_pos(i) {
if !memoize.contains(&new_state) {
stack.push(new_state);
}
} else if is_room(i) {
for new_state in state.hallway_moves(i) {
if !memoize.contains(&new_state) {
stack.push(new_state);
}
}
}
}
}
min_energy
}
pub fn new(input: &str) -> Box<dyn Solution> {
let start_pos = input
.chars()
.filter(|ch| ch.is_alphabetic())
.map(|ch| (ch as u8 - b'A' + 1) as u32)
.collect::<Vec<_>>();
Box::new(Day23 {
initial_state: State::new(&start_pos),
})
}
// Each slot has this format | 16-bit A | 1-bit unused | 5x 3-bit B |
// A is always 0 for hallways, number of slots available in burrows for the "right" amphipod type
// B is amphipod type (3-bits, 1-4 and 0 means empty). Which of the slots determine "depth"
// hallways only use depth 0 and rooms only use depth 1-4
type Map = [u32; 11];
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
struct State {
map: Map,
energy: u32,
}
impl State {
fn new(start_pos: &[u32]) -> Self {
let mut d = State {
map: [0; 11],
energy: 0,
};
for i in 0..4 {
let r0 = start_pos[i];
let r1 = start_pos[i + 4];
if r1 == i as u32 + 1 {
if r0 == i as u32 + 1 {
d.map[2 * (i + 1)] = 0;
} else {
d.map[2 * (i + 1)] = (1 << 16) + (r0 << 3);
}
} else {
d.map[2 * (i + 1)] = (2 << 16) + (r0 << 3) + (r1 << 6);
}
}
d
}
fn is_done(&self) -> bool {
(self.map[2] == 0) & (self.map[4] == 0) & (self.map[6] == 0) & (self.map[8] == 0)
}
fn try_move_to_final_pos(&self, map_idx: usize) -> Option<State> {
let loc = self.map[map_idx];
if location_is_empty(loc) {
return None;
}
let (amphipod_type, depth) = if is_room(map_idx) {
outermost_amphipod_in_room(loc)
} else {
(loc, 0)
};
if let Some(steps) = self.steps_to_home_burrow(amphipod_type, map_idx) {
let mut map = self.map;
remove_amphipod(&mut map, map_idx, depth);
add_amphipod_to_home_burrow(&mut map, amphipod_type);
Some(State {
map,
energy: self.energy + (depth + steps) * step_cost(amphipod_type),
})
} else {
None
}
}
fn steps_to_home_burrow(&self, amphipod_type: u32, map_idx: usize) -> Option<u32> {
let home_idx = home_burrow_idx(amphipod_type);
let home_loc = self.map[home_idx];
if !location_is_empty(home_loc) {
// Something of wrong type in home burrow
return None;
}
let (from, to) = if home_idx > map_idx {
(map_idx, home_idx)
} else {
(home_idx, map_idx)
};
for i in (from + 1)..to {
if (self.map[i] & 0x7) != 0 {
return None;
}
}
Some((to - from) as u32 + (home_loc >> 16))
}
fn hallway_moves(&self, room_idx: usize) -> impl Iterator<Item = State> {
let loc = self.map[room_idx];
if location_is_empty(loc) {
return vec![].into_iter();
}
let (amphipod_type, depth) = outermost_amphipod_in_room(loc);
let mut new_state = *self;
remove_amphipod(&mut new_state.map, room_idx, depth);
let start = (room_idx >> 1) + 1;
let mut moves = Vec::new();
add_moves(
&mut moves,
&new_state,
(0..start).rev(),
amphipod_type,
depth,
room_idx,
);
add_moves(
&mut moves,
&new_state,
start..7,
amphipod_type,
depth,
room_idx,
);
moves.into_iter()
}
}
fn add_moves<I>(
moves: &mut Vec<State>,
state: &State,
idxs: I,
amphipod_type: u32,
depth: u32,
room_idx: usize,
) where
I: Iterator<Item = usize>,
{
const HALLWAY_IDXS: [usize; 7] = [0, 1, 3, 5, 7, 9, 10];
for i in idxs {
let map_idx = HALLWAY_IDXS[i];
let l = state.map[map_idx];
if l != 0 {
break;
}
let move_cost =
(depth + (map_idx as i32 - room_idx as i32).abs() as u32) * step_cost(amphipod_type);
let mut new_state = *state;
new_state.map[map_idx] = amphipod_type;
new_state.energy += move_cost;
moves.push(new_state);
}
}
fn is_room(idx: usize) -> bool {
(idx == 2) | (idx == 4) | (idx == 6) | (idx == 8)
}
fn location_is_empty(loc: u32) -> bool {
(loc & 0xffff) == 0
}
fn home_burrow_idx(amphipod_type: u32) -> usize {
(amphipod_type * 2) as usize
}
fn remove_amphipod(map: &mut Map, room_idx: usize, depth: u32) {
map[room_idx] &= !(0x7 << (depth * 3));
}
fn add_amphipod_to_home_burrow(map: &mut Map, amphipod_type: u32) {
map[home_burrow_idx(amphipod_type)] -= 0x1_0000;
}
fn step_cost(amphipod_type: u32) -> u32 {
const ENERGY_PER_STEP: [u32; 4] = [1, 10, 100, 1000];
ENERGY_PER_STEP[(amphipod_type - 1) as usize]
}
fn outermost_amphipod_in_room(loc: u32) -> (u32, u32) {
let mut depth = 1;
loop {
let amphipod_type = (loc >> (3 * depth)) & 0x7;
if amphipod_type != 0 {
break (amphipod_type, depth);
}
depth += 1;
}
}
