Function advent_of_code_2021::day_23::build_states

fn build_states(burrow: &Burrow) -> Vec<(usize, Burrow)>

This handles building the possible next states respecting the limits on Amphipod movement returning a list of the possible states and the cost for each.

• For each hallway cell:
  • If there is an Amphipod there walk towards its desired tunnel, aborting if there is a non-empty cell in the way. Track the distance, 0 -> 1 or 6 -> 5 are 1 distance, all others are 2 to account for the unrepresented cells the Amphipod can’t stop in.
  • Then walk down the the tunnel, until a non-empty cell, or the bottom. Note the position of and distance to the final empty cell. Continue to increment the distance, the first step is worth an extra 1 as the Amphipod first steps into the cell adjacent to the tunnel that is not represented.
  • Continue through any remaining cells, if any have an Amphipod that wants to be in a different tunnel, abort.
  • If the move is valid, use Burrow::swap to copy the burrow with that move applied, and calculate the cost. Add these to the output Vec.
• For each tunnel:
  • Walk down it until you reach a non-empty cell.
  • Starting at the cell left of the top of this tunnel, i.e. the first one the Amphipod can stop at, check if the cell is empty, and, if so use Burrow::swap to copy the burrow with that move applied, and calculate the cost. Add these to the output Vec.
  • Keep stepping leftwards until a non-empty cell, or the end of the hallway (0) is reached.
  • Repeat for the cell to the right, stepping rightwards.