Efficient BFS in Rust
About a year ago, I discovered Advent of Code, an annual series of coding challenges that commence each December. Eager to deepen my programming prowess, I embarked on a unique challenge: tackling each year's problems in a different programming language.
For my inaugural year, I opted for Julia—a language I found appealing due to its simplicity and resemblance to Python, a language I've long been proficient in. Julia's native support for matrices and ranges, coupled with its concise type system and 1-based indexing, made it an ideal choice for crafting straightforward procedural code.
Recently, through collaboration on an open-source project in Rust, I delved into this elegant and robust language. Its expressive syntax and powerful features swiftly captivated me, making Rust an obvious contender for my second Advent of Code challenge.
In this article, I aim to share insights from a particularly intriguing challenge: Day 11 of Advent of Code 2016, and my approach to solving it. We'll delve into the realms of BFS versus DFS strategies, efficient state management, and the importance of pruning unused data. But first, let's explore the problem at hand.
A River Crossing Puzzle
You may be familiar with river crossing puzzles. A classic example involves a farmer tasked with transporting a wolf, a goat, and a cabbage across a river. The challenge lies in the constraints: the farmer's boat can only carry one item at a time, and if left unsupervised, the wolf will devour the goat, and the goat will consume the cabbage.
The puzzle's solution hinges on the farmer's ability to shuttle items back and forth across the river. To resolve it, the farmer first transports the goat across the river, returns alone, then takes the wolf across. After safely depositing the wolf, the farmer returns with the goat. Next, the farmer takes the cabbage across, leaves it with the wolf, and finally returns to retrieve the goat, ensuring all three items safely reach the other side.
A More Advanced Puzzle
Advent of Code elevates the classic river crossing puzzle to a new level with a challenging scenario set in a four-floor facility, where you begin on the first floor. Spread across the first three floors are Radioisotope Thermoelectric Generators (RTGs) and specially-paired Microchips.
There are five types of RTGs and corresponding Microchips. In the second part of the puzzle two more types are introduced.
You may use an elevator to move up or down one floor at a time. Afterwards it takes some time to recharge. To operate the elevator, you must have at least one RTG or Microchip with you. You can carry at most two items. A Microchip is considered paired if its corresponding RTG is on the same floor or both are in the elevator. If a Microchip is not paired and another RTG is present, the Microchip will be fried.
To solve the puzzle, all five RTGs and Microchips (or seven in the second part) must be transported to the top floor with the fewest possible steps.
It might seem that solving this puzzle by hand is easier than doing it programmatically but you might realise it isn't quite that easy if you actually try to solve it. With the puzzle input given it takes at least 33 steps to solve the puzzle:
The first floor contains a promethium generator and a promethium-compatible microchip.
The second floor contains a cobalt generator, a curium generator, a ruthenium generator, and a plutonium generator.
The third floor contains a cobalt-compatible microchip, a curium-compatible microchip, a ruthenium-compatible microchip, and a plutonium-compatible microchip.
The fourth floor contains nothing relevant.
For part two of the puzzle the following constraints were added resulting in a minimum of 57 steps to solve the puzzle:
Upon entering the isolated containment area, however, you notice some extra parts on the first floor that weren't listed on the record outside:
- An elerium generator.
- An elerium-compatible microchip.
- A dilithium generator.
- A dilithium-compatible microchip.
Breaking Down the Puzzle
This puzzle may initially appear daunting, but it is indeed solvable. My approach to tackling almost any puzzle begins with modelling the problem domain. This step provides a clear understanding of the data involved and how it evolves throughout the puzzle-solving process.
The next step is transforming the puzzle input into structured data.
This puzzle as many others is solved as a series of steps and for each you need to consider the current state, so we need to implement state transition. This can be broken down further into discovering all possible state transitions, actually deriving a new state and evaluating it. To solve the puzzle we need to discover state transitions that end up in a completed state, in our case with all items on the top floor. But we also need to consider the constraints, so we should differentiate between valid and invalid state. An invalid state effectively means that a path is abandoned and will not be explored any further.
To summarise the approach:
Modelling the Domain
Let's begin with an overview of the facility. It comprises four floors. The elevator is stopped on one of them. We don't need to model states where the elevator is in motion. We're also interested in the items present on any floor, that is the RTGs (from now on called Generators) and Microchips.
struct Area {
elevator_stop: Floor,
first_floor: HashSet<Item>,
second_floor: HashSet<Item>,
third_floor: HashSet<Item>,
fourth_floor: HashSet<Item>,
}
The floor the elevator is on can be represented as an enum. I prefer it over an integer because I don't have to consider out of bounds values. The actual item is another representation and as items on each floor are unordered but will move around over time we can use a HashSet to store them in.
Let's model the item next. We know it's either a Generator or a Microchip and it is of one of seven distinct elements.
struct Item {
element: Element,
item_type: Type
}
Now let's define some enums. Let's add one to represent the elevator moving up or down. And while we're at it, let's define a status for our state, we'll use it soon.
enum Floor { F1, F2, F3, F4 }
enum Element { Cobalt, Curium, Dilithium, Elerium, Plutonium, Promethium, Ruthenium }
enum Type { Generator, Microchip }
enum Direction { Up, Down }
enum Status { Valid, Invalid, Completed }
The area modelled earlier is part of our state. But the state should also include a list of past transitions and the evaluated status.
struct State {
area: Area,
actions: Vec<Action>,
status: Status,
}
Transitions are described as actions and an action involves the elevator moving one floor up or down. Remember we need an item to operate the elevator but we can also take a second, optional, item with us.
struct Action {
direction: Direction,
item: Item,
optional_item: Option<Item>
}
Convert the Puzzle Input into State
This step is rather straightforward, so I'll only mention the most relevant parts. First we initialise the area before we populate it with items. The elevator is initially located on the first floor where we enter.
let mut area = Area {
elevator_stop: F1,
first_floor: HashSet::with_capacity(14),
second_floor: HashSet::with_capacity(14),
third_floor: HashSet::with_capacity(14),
fourth_floor: HashSet::with_capacity(14),
};
We can apply regular expressions to extract the respective floors and items from the input, parsing it line by line. We can then apply pattern matching to transform the captured strings to the area properties respectively element enum constants. These are the regular expressions I have used.
let re_floor = Regex::new(r"The (first|second|third|fourth) floor.*").unwrap();
match re_floor.captures(line) {
Some(capture) => set_ref = match capture.get(1).unwrap().as_str() {
"first" => &mut area.first_floor,
...
let re_items = Regex::new(r"(\w+)(-compatible microchip| generator)").unwrap();
for cap in re_items.captures_iter(line) {
set_ref.insert(Item {
element: match cap[1].to_string().as_str() {
"cobalt" => Cobalt,
...
Finally we can create an initial state from it, with an empty history of actions and of valid status.
State {
area,
actions: vec![],
status: Valid,
}
Let's talk about DFS vs. BFS
While we can continue implementing parts of the algorithm, there's an important choice to be made.
The entire sequence, starting from the initial state and culminating in a completed state with minimal actions, can be visualised as a tree.
The initial state serves as the root of this tree. At first, starting from floor one, the elevator can only ascend. In the more challenging second part of the puzzle, there are already six items present and we're allowed to transport one or two items per trip. Opting for one item creates six distinct paths leading to the next state, while choosing two items expands this to eleven paths. The number of potential paths increases further on floors two and three, where the elevator can move in both directions.
There are two primary approaches to traversing a tree for paths. Depth-first search (DFS) methodically follows a path until reaching either a completed or invalid state. If a path fails to solve the puzzle, backtracking occurs. Typically, this is managed through recursion. By passing the entire state by value and keeping it on the stack, backtracking naturally continues from the correct state by design.
领英推荐
Breadth-first search (BFS) examines all nodes at the current level of the tree before advancing to the next level. Unlike DFS, this approach does not involve backtracking or recursion. However, BFS requires storing the state of all paths in memory simultaneously.
What is the right approach to solve this problem? Well we cannot say for certain how long the minimal path to solving this problem may be.
DFS is typically suitable when the length of the path is well-defined and manageable, such as in solving or generating a sudoku puzzle where there are a fixed number of steps related to the grid size and pre-filled content.
However, for our river crossing puzzle, the path length can potentially extend indefinitely - especially when items are repeatedly moved up and down floors without progress towards the solution. It’s challenging to determine if a particular move brings us closer to the solution or further away.
Since our goal is to find the shortest path, discovering just one successful path using DFS doesn’t guarantee it’s the shortest. To ensure we find the shortest path, we would need to explore all paths shorter than the currently found path length, which can be computationally expensive and inefficient.
Given these considerations, BFS emerges as the preferred choice over DFS for this puzzle. BFS systematically explores all possible paths level by level, ensuring that the shortest path to the solution is found first.
However, even with BFS, careful management of states is critical to prevent inefficiencies. An inefficient BFS implementation could run for days while my Rust solution for part one completes in under two seconds and part two takes a little over 27 seconds on my computer.
Discovering State Transitions
This step is relatively straightforward. We iterate over possible directions and combinations of primary and secondary items, ensuring we avoid invalid moves. Additionally, we could make some initial assumptions. For instance, if no items remain on the first floor, we may decide never to return to that floor. Similarly, if both the first and second floors are empty, we might assume we won't revisit the second floor. However, it's essential to consider potential edge cases where depositing items on the second floor might be necessary to prevent frying a Microchip. It might be best to add these optimisations after the algorithm is finished to observe whether they change the result or considerably improve performance.
for direction in DIRECTIONS {
if state.area.elevator_stop == F1 && direction == Down {
continue;
} else if state.area.elevator_stop == F4 && direction == Up {
continue;
}
for item in items.iter() {
for optional_item in items.iter() {
if item == optional_item {
continue
}
...
Instead of creating a directions array on the spot you can declare it as a (immutable) global structure to be reused, saving some cpu cycles. I did the same with the elements later on.
static DIRECTIONS: [Direction; 2] = [Up, Down];
Deriving the Next State
To deduce the next state you can copy the current state and then apply elevator movement, removing the items you took with you in the elevator and adding them to the target floor. Most importantly you need to evaluate the status so you can abandon a path quickly if any Microchips are fried due to moving them or Generators between floors.
fn create_next_state(state: &mut State, next_action: Action) -> State {
state.area.current_floor().retain(|&item| item != next_action.item);
state.area.next_floor(&next_action.direction).insert(next_action.item);
if let Some(second_item) = next_action.optional_item {
state.area.current_floor().retain(|&item| item != second_item);
state.area.next_floor(&next_action.direction).insert(second_item);
}
state.status = if has_fried_chip(&state.area) { Invalid } else { Valid };
if state.is_valid() && state.area.first_floor.is_empty() && state.area.second_floor.is_empty() && state.area.third_floor.is_empty() {
state.status = Completed;
}
state.area.move_elevator(next_action.direction);
state.actions.push(next_action.to_owned());
state.to_owned()
}
The "has fried chip" logic is absolutely crucial since it is evaluated so many times. I really have chosen performance over beauty here.
fn has_fried_chip(area: &Area) -> bool {
area.first_floor.iter().any(|&item| is_fried_chip(&item, &area.first_floor))
|| area.second_floor.iter().any(|&item| is_fried_chip(&item, &area.second_floor))
|| area.third_floor.iter().any(|&item| is_fried_chip(&item, &area.third_floor))
|| area.fourth_floor.iter().any(|&item| is_fried_chip(&item, &area.fourth_floor))
}
fn is_fried_chip(item: &Item, floor_items: &HashSet<Item>) -> bool {
if item.item_type == Microchip {
let corresponding_generator = floor_items.iter().find(|&&other| {
other.item_type == Generator && other.element == item.element
});
match corresponding_generator {
Some(_gen) => false,
None => floor_items.iter().any(|&other| other.item_type == Generator),
}
} else {
false
}
}
I have also added some convenience functions to my area struct. Pattern matching works very well here.
impl Area {
fn move_elevator(&mut self, direction: Direction) {
match direction {
Up => match self.elevator_stop {
F1 => self.elevator_stop = F2,
F2 => self.elevator_stop = F3,
F3 => self.elevator_stop = F4,
F4 => panic!("can't go up from top floor"),
},
Down => match self.elevator_stop {
F1 => panic!("can't go down from ground floor"),
F2 => self.elevator_stop = F1,
F3 => self.elevator_stop = F2,
F4 => self.elevator_stop = F3,
},
}
}
...
Memorise Visited State
Due to the numerous potential states and the elevator's ability to move up and down while carrying up to two items each time, paths often lead to revisiting previously encountered states. With BFS, we inevitably visit each state as early as possible, necessitating the abandonment of paths that revisit states.
Effective management of memorised states is pivotal to the algorithm's success. If all states remain in memory until a solution is discovered, the algorithm could feasibly run for an extended period - potentially exceeding a month, no exaggeration.
Let's consider what information we actually need to retain in memory.
To compute the next level of possible states, we must remember the current states - specifically those that are deemed valid. We do not require memory of the preceding level of states for this purpose.
We do however need to keep track of visited states, but we only need to store a subset of the state's information. Specifically, we are interested in the location of each element. What truly matters is the floor locations of each pair consisting of a Generator and a Microchip belonging to an element. The arrangement where a Generator is on one floor and its corresponding Microchip is on another is distinctly different from the reverse arrangement because Generators can potentially fry Microchips from other elements when they are on the same floor, while Microchips themselves do not pose such a risk to one another.
Coding Distribution Patterns
After careful consideration, I devised an efficient representation for the distribution of Generators and Microchips across floors. Each element can be situated on any of floors 1 through 4, allowing for 16 potential combinations per element. By calculating and sorting these values, distributions that differ only in specific element swaps are identified as known distributions.
Similar to the default hashCode() implementation in Java that modern IDEs generate, I propose creating a unique hash value by multiplying the hash value by a number greater than the number of possible combinations before adding the combination. This process is repeated for all elements. In part one of the puzzle, the resulting hash value fits into a u32, while in part two, it fits into a u64.
fn code(&self) -> u64 {
let mut combinations: Vec<u8> = Vec::new();
for element in ELEMENTS {
let mut combination: u8 = self.find_pos(element, Microchip);
combination += self.find_pos(element, Generator) * 10;
combinations.push(match combination {
11 => 0,
12 => 1,
...
43 => 14,
44 => 15,
_ => panic!("unexpected combination: {}", combination)
});
}
let prime_base: u64 = 17;
let mut hash: u64 = 0;
combinations.sort_unstable();
combinations.iter().for_each(|c| hash = hash * prime_base + *c as u64);
hash = hash * prime_base + match self.elevator_stop {
F1 => 1,
F2 => 2,
F3 => 3,
F4 => 4,
};
hash
}
The function find_pos used here is another convenience function in the implementation of the area struct that returns the floor number for an item by searching through the HashSets representing the floors.
Without this optimisation it seems almost impossible to produce the solution in under a minute.
State Pruning
Now that we separated visited distributions from the state that we need to transition to the next level we can optimise our memory usage of this state.
An obvious option is to pop elements from our state vector until it is empty while collecting derived states for the next level.
fn find_solution(state: State) -> State {
let mut area_codes: HashSet<u64> = HashSet::new();
let mut states: Vec<State> = Vec::new();
states.push(state);
loop {
let mut next_states: Vec<State> = Vec::new();
while let Some(state) = states.pop() {
...
After all states of the current level are processed we filter the already evaluated next states and add them to both our global state and the known distribution patterns which I named area codes here.
for state in next_states.iter() {
let ac = state.area.code();
let contains = area_codes.iter().any(|c| c == &ac);
if !contains {
area_codes.insert(ac);
states.push(state.to_owned());
}
};
And that's it - all the magic behind solving Advent of Code 2016 Day 11 Part 2 in under 30 seconds.
Conclusion
Solving this coding challenge was an extremely satisfying experience and taught me a lot about the critical difference between BFS and DFS and how to efficiently manage state and take care that the most often parts of your algorithm don't become bottlenecks.
This was the most interesting puzzle in the Advent of Code series for me so far and I'm looking forward to all the challenges to come.
I was considering to do the next year in Haskell but I have no idea how I would have solved this puzzle with it in an acceptable amount of time to be honest. Maybe I'll take a more straightforward language like Go first.
My solution to part 2 of Advent of Code Day 11, which only adds a few lines of code compared to part 1, is available on GitHub as well as any other solutions and my personal puzzle inputs: https://github.com/christianpflugradt/advent-of-code/blob/main/2016/2016-11-2.rs
The Advent of Code puzzle can be found here: https://adventofcode.com/2016/day/11
Now go and write some code. ??