Task 23

Thorn Thaler - <

2025-07-25

1 Setup

1.1 Libraries

library(httr)
library(xml2)
library(tibble)
library(magrittr)
library(dplyr)
library(purrr)
library(stringr)
library(stringi)
library(knitr)
library(cli)
library(bit64)
library(igraph)

1.2 Retrieve Data from AoC

session_cookie <- set_cookies(session = keyring::key_get("AoC-GitHub-Cookie"))
base_url <- paste0("https://adventofcode.com/", params$year, "/day/", params$task_nr)
puzzle <- GET(base_url,
              session_cookie) %>% 
  content(encoding = "UTF-8") %>% 
  xml_find_all("///article") %>% 
  lapply(as.character)

parse_puzzle_data <- function(text_block = readClipboard()) {
  if (length(text_block) == 1L) {
    text_block <- text_block %>% 
      str_split("\n") %>% 
      extract2(1L) %>% 
      keep(nzchar)
  }
  text_block %>% 
    str_subset("[ABCD]") %>% 
    str_extract_all("[ABCD]") %>% 
    list_transpose()
}

puzzle_data <- local({
  GET(paste0(base_url, "/input"),
      session_cookie) %>% 
    content(encoding = "UTF-8") %>% 
    parse_puzzle_data()
})

2 Puzzle Day 23

2.1 Part 1

2.1.1 Description

— Day 23: Amphipod —

A group of amphipods notice your fancy submarine and flag you down. “With such an impressive shell,” one amphipod says, “surely you can help us with a question that has stumped our best scientists.”

They go on to explain that a group of timid, stubborn amphipods live in a nearby burrow. Four types of amphipods live there: Amber (A), Bronze (B), Copper (C), and Desert (D). They live in a burrow that consists of a hallway and four side rooms. The side rooms are initially full of amphipods, and the hallway is initially empty.

They give you a diagram of the situation (your puzzle input), including locations of each amphipod (A, B, C, or D, each of which is occupying an otherwise open space), walls (#), and open space (.).

For example: 

#############
#...........#
###B#C#B#D###
  #A#D#C#A#
  #########

The amphipods would like a method to organize every amphipod into side rooms so that each side room contains one type of amphipod and the types are sorted A-D going left to right, like this: 

#############
#...........#
###A#B#C#D###
  #A#B#C#D#
  #########

Amphipods can move up, down, left, or right so long as they are moving into an unoccupied open space. Each type of amphipod requires a different amount of energy to move one step: Amber amphipods require 1 energy per step, Bronze amphipods require 10 energy, Copper amphipods require 100, and Desert ones require 1000. The amphipods would like you to find a way to organize the amphipods that requires the least total energy.

However, because they are timid and stubborn, the amphipods have some extra rules:

  • Amphipods will never stop on the space immediately outside any room. They can move into that space so long as they immediately continue moving. (Specifically, this refers to the four open spaces in the hallway that are directly above an amphipod starting position.)
  • Amphipods will never move from the hallway into a room unless that room is their destination room and that room contains no amphipods which do not also have that room as their own destination. If an amphipod’s starting room is not its destination room, it can stay in that room until it leaves the room. (For example, an Amber amphipod will not move from the hallway into the right three rooms, and will only move into the leftmost room if that room is empty or if it only contains other Amber amphipods.)
  • Once an amphipod stops moving in the hallway, it will stay in that spot until it can move into a room. (That is, once any amphipod starts moving, any other amphipods currently in the hallway are locked in place and will not move again until they can move fully into a room.)

In the above example, the amphipods can be organized using a minimum of 12521 energy. One way to do this is shown below.

Starting configuration: 

#############
#...........#
###B#C#B#D###
  #A#D#C#A#
  #########

One Bronze amphipod moves into the hallway, taking 4 steps and using 40 energy: 

#############
#...B.......#
###B#C#.#D###
  #A#D#C#A#
  #########

The only Copper amphipod not in its side room moves there, taking 4 steps and using 400 energy: 

#############
#...B.......#
###B#.#C#D###
  #A#D#C#A#
  #########

A Desert amphipod moves out of the way, taking 3 steps and using 3000 energy, and then the Bronze amphipod takes its place, taking 3 steps and using 30 energy: 

#############
#.....D.....#
###B#.#C#D###
  #A#B#C#A#
  #########

The leftmost Bronze amphipod moves to its room using 40 energy: 

#############
#.....D.....#
###.#B#C#D###
  #A#B#C#A#
  #########

Both amphipods in the rightmost room move into the hallway, using 2003 energy in total: 

#############
#.....D.D.A.#
###.#B#C#.###
  #A#B#C#.#
  #########

Both Desert amphipods move into the rightmost room using 7000 energy: 

#############
#.........A.#
###.#B#C#D###
  #A#B#C#D#
  #########

Finally, the last Amber amphipod moves into its room, using 8 energy: 

#############
#...........#
###A#B#C#D###
  #A#B#C#D#
  #########

What is the least energy required to organize the amphipods?

2.1.2 Solution

We use a brute-force appraoch, where we simply try out all potential moevments. We could improve the code by carefully reflecting on smart moving strategies to avoid exploring the while space. However, the problem seems to be small enough that such improvements seem unnecessary.

However, we had to fall back to C++ code for efficiency reasons, as in R we have copy on modifcation semantics, which is, in eahc recursion we are copying lists, which significantly slows down the code.

The idea of the C++ is as follows:

  1. We define a State class, which maintains the bots on the hallway and the bots in the rooms. The former is implemented as an std::array<char, 11> and the latter as a std::array<std::stack<char>, 4>.
  2. The class defines functions for moving bots in and out, checking if a path is free and returning all movable bots in both the rooms and the hallway.
  3. It provides a get_map_id() function, which gives a condensed textual representation of the current state, which later will serve as a key for the has map, where we maintain the costs of any given mpa already calculated (to avoid re-calculating known costs).
  4. The main function solve is a recursive function, which
  5. Checks if we have a final state, and returns cost zero (no more movements needed)
  6. Checks if a certain satet was already calculated in the past and returns the cached value in this case.
  7. Move all bots from the hallway home and recalls itself wiht this new state and sums the costs.
  8. Tries each possible space for a bot currently sitting in its false room and keeps the cheapest solution in each recursion.
#ifndef STANDALONE
#include <Rcpp.h>
using namespace Rcpp;
#endif

#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>
#include <limits>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <vector>

constexpr unsigned int MAX_COST = std::numeric_limits<unsigned int>::max();

class State {
  public:
    State(const std::vector<std::vector<char>>&);

    std::string get_map_id() const;
    std::vector<unsigned int> get_hallbots() const;
    std::unordered_map<unsigned int, std::vector<unsigned int>> get_homebots() const;

    unsigned int move_home(unsigned int);
    unsigned int move_out(unsigned int, unsigned int);
    bool is_done() const;

  private:
    const unsigned int room_size;

    const std::array<char, 4> room_labels = {'A', 'B', 'C', 'D'};
    const std::array<unsigned int, 4> moving_costs = {1, 10, 100, 1000};
    const std::array<unsigned int, 4> room_pos = {2, 4, 6, 8};

    std::array<std::stack<char>, 4> rooms;
    std::array<char, 11> hallway;

    bool validate_layout(const std::vector<std::vector<char>>&) const;
    bool can_get_home(unsigned int) const;
    bool can_move(unsigned int, unsigned int) const;

    unsigned int get_bot_idx(char) const;
    unsigned int get_cost(unsigned int, unsigned int, unsigned int) const;

    friend std::ostream& operator<<(std::ostream&, const State&);
};

State::State(const std::vector<std::vector<char>>& initial_layout)
    : room_size(initial_layout[0].size())
    , rooms()
    , hallway() {
  if (!validate_layout(initial_layout)) {
    throw std::runtime_error("all elements of 'initial_input' must have the same length");
  }
  hallway.fill('.');
  size_t i = 0;
  for (const auto& l : initial_layout) {
    std::stack<char> room;
    std::vector<char> room_layout = l;
    for (auto j = room_layout.end() - 1; j >= room_layout.begin(); --j) {
      room.push(*j);
    }
    rooms[i++] = room;
  }
};

std::string State::get_map_id() const {
  std::ostringstream key_stream;
  std::string key;
  for (const auto s : hallway) {
    key_stream << s;
  }
  for (auto room : rooms) {
    while (room.size() != room_size) {
      room.push('.');
    }
    while (!room.empty()) {
      key_stream << room.top();
      room.pop();
    }
  }
  return key_stream.str();
}

std::vector<unsigned int> State::get_hallbots() const {
  std::vector<unsigned int> bot_idx;
  for (size_t i = 0; i < hallway.size(); ++i) {
    if (hallway[i] != '.') {
      if (can_get_home(i)) {
        bot_idx.push_back(i);
      }
    }
  }
  return bot_idx;
}

std::unordered_map<unsigned int, std::vector<unsigned int>> State::get_homebots() const {
  std::unordered_map<unsigned int, std::vector<unsigned int>> bot_idx;
  for (size_t i = 0; i < rooms.size(); ++i) {
    std::stack<char> room = rooms[i];
    std::vector<unsigned int> free_spaces;
    while (!room.empty()) {
      if (room.top() == room_labels[i]) {
        room.pop();
      } else {
        for (size_t j = 0; j < hallway.size(); ++j) {
          if (can_move(j, i) &&
              std::find(std::begin(room_pos), std::end(room_pos), j) == std::end(room_pos)) {
            free_spaces.push_back(j);
          }
        }
        if (!free_spaces.empty()) {
          bot_idx[i] = free_spaces;
        }
        break;
      }
    }
  }
  return bot_idx;
}

bool State::validate_layout(const std::vector<std::vector<char>>& initial_layout) const {
  bool result = true;
  for (const auto& l : initial_layout) {
    result = result && (l.size() == room_size);
  }
  return result;
}

bool State::can_get_home(unsigned int hall_pos) const {
  char bot = hallway[hall_pos];
  unsigned int home_idx = get_bot_idx(bot);
  // need an offset b/c we do not want to test the starting field
  int offset = (hall_pos < room_pos[home_idx]) ? 1 : -1;
  std::stack<char> room = rooms[home_idx];
  bool result = can_move(hall_pos + offset, home_idx) && room.size() != room_size;
  while (!room.empty() && result) {
    result = result && (room.top() == bot);
    room.pop();
  }
  return result;
}

bool State::can_move(unsigned int hall_pos, unsigned int room_idx) const {
  bool result = true;
  int step = hall_pos < room_pos[room_idx] ? 1 : -1;
  for (size_t i = hall_pos; i != room_pos[room_idx]; i += step) {
    result = result && (hallway[i] == '.');
    if (!result) {
      break;
    }
  }
  return result;
}

bool State::is_done() const {
  bool result;
  for (size_t i = 0; i < rooms.size(); i++) {
    std::stack<char> room = rooms[i];
    result = room.size() == room_size;
    while (!room.empty() && result) {
      result = result && (room.top() == room_labels[i]);
      room.pop();
    }
    if (!result) {
      break;
    }
  }
  return result;
}

unsigned int State::get_bot_idx(char bot) const {
  /* bot -'A' maps A => 0, B => 1, C => 2 and D => 3*/
  return bot - 'A';
}

unsigned int State::get_cost(unsigned int hall_pos,
                             unsigned int room_idx,
                             unsigned int bot_idx) const {
  unsigned int distance = abs(static_cast<int>(hall_pos) -
                              static_cast<int>(room_pos[room_idx])) + // horizontal distance
      (room_size - rooms[room_idx].size()) + // vertical distance
      // if we move out we need to count the last step
      (hallway[hall_pos] == '.' ? 1 : 0);
  return distance * moving_costs[bot_idx];
}

unsigned int State::move_home(unsigned int hall_pos) {
  char bot = hallway[hall_pos];
  unsigned int bot_idx = get_bot_idx(bot);
  unsigned int moving_costs = get_cost(hall_pos, bot_idx, bot_idx);
  hallway[hall_pos] = '.';
  rooms[bot_idx].push(bot);
  return moving_costs;
}

unsigned int State::move_out(unsigned int room_idx, unsigned int hall_pos) {
  char bot = rooms[room_idx].top();
  unsigned int moving_costs = get_cost(hall_pos, room_idx, get_bot_idx(bot));
  rooms[room_idx].pop();
  hallway[hall_pos] = bot;
  return moving_costs;
}

std::ostream& operator<<(std::ostream& stream, const State& x) {
  size_t col, row, n_col, n_row;
  std::fill_n(std::ostream_iterator<char>(stream), x.hallway.size() + 2, '#');
  stream << std::endl << '#';
  for (const auto& s : x.hallway) {
    stream << s;
  }
  stream << '#' << std::endl;
  n_col = x.rooms.size();
  n_row = x.room_size;
  char rooms_str[n_row][n_col];
  for (col = 0; col < n_col; col++) {
    std::stack<char> room = x.rooms[col];
    row = n_row - room.size();
    for (size_t i = 0; i < row; i++) {
      rooms_str[i][col] = '.';
    }
    while (!room.empty()) {
      rooms_str[row++][col] = room.top();
      room.pop();
    }
  }
  for (row = 0; row < n_row; row++) {
    char filler = row == 0 ? '#' : ' ';
    std::fill_n(std::ostream_iterator<char>(stream), 2, filler);
    stream << '#';
    for (col = 0; col < n_col; col++) {
      stream << rooms_str[row][col] << '#';
    }
    std::fill_n(std::ostream_iterator<char>(stream), 2, filler);
    stream << std::endl;
  }
  stream << "  ";
  std::fill_n(std::ostream_iterator<char>(stream), x.hallway.size() - 2, '#');
  stream << "  " << std::endl;
  return stream;
}

unsigned int solve(State state) {
  static std::unordered_map<std::string, unsigned int> hash;
  unsigned int costs, moving_costs, branch_costs;
  std::string id = state.get_map_id();
  if (state.is_done()) {
    return 0;
  }
  if (hash.find(id) != hash.end()) {
    return hash[id];
  }
  for (const auto hall_pos : state.get_hallbots()) {
    moving_costs = state.move_home(hall_pos);
    costs = solve(state);
    if (costs <= MAX_COST - moving_costs) {
      return moving_costs + costs;
    } else {
      return MAX_COST;
    }
  }
  branch_costs = MAX_COST;
  for (const auto& [home_pos, cand_pos] : state.get_homebots()) {
    for (const auto hall_pos : cand_pos) {
      State new_state(state);
      moving_costs = new_state.move_out(home_pos, hall_pos);
      costs = solve(new_state);
      if (costs <= MAX_COST - moving_costs) {
        branch_costs = std::min(branch_costs, costs + moving_costs);
      }
    }
  }
  costs = branch_costs;
  hash[id] = costs;
  return costs;
}

#ifndef STANDALONE
// [[Rcpp::export]]
unsigned int bring_bots_home(const List& initial_layout) {
  std::vector<std::vector<char>> layout;
  for (const auto& l : initial_layout) {
    CharacterVector room_layout = l;
    std::vector<char> room;
    for (auto j = room_layout.begin(); j < room_layout.end(); ++j) {
      room.push_back(as<char>(*j));
    }
    layout.push_back(room);
    room.clear();
  }
  State state(layout);
  return solve(state);
}
#else
int main() {
  std::vector<std::vector<char>> initial_layout = {{'B', 'A'}, {'C', 'D'}, {'B', 'C'}, {'D', 'A'}};
  State state(initial_layout);
  std::cout << "Least amount of Energy:" << solve(state) << std::endl;
  return 0;
}
#endif
bring_bots_home(puzzle_data)
## [1] 13336

2.2 Part 2

2.2.1 Description

— Part Two —

As you prepare to give the amphipods your solution, you notice that the diagram they handed you was actually folded up. As you unfold it, you discover an extra part of the diagram.

Between the first and second lines of text that contain amphipod starting positions, insert the following lines: 

  #D#C#B#A#
  #D#B#A#C#

So, the above example now becomes: 

#############
#...........#
###B#C#B#D###
  #D#C#B#A#
  #D#B#A#C#
  #A#D#C#A#
  #########

The amphipods still want to be organized into rooms similar to before: 

#############
#...........#
###A#B#C#D###
  #A#B#C#D#
  #A#B#C#D#
  #A#B#C#D#
  #########

In this updated example, the least energy required to organize these amphipods is 44169: 

#############
#...........#
###B#C#B#D###
  #D#C#B#A#
  #D#B#A#C#
  #A#D#C#A#
  #########

#############
#..........D#
###B#C#B#.###
  #D#C#B#A#
  #D#B#A#C#
  #A#D#C#A#
  #########

#############
#A.........D#
###B#C#B#.###
  #D#C#B#.#
  #D#B#A#C#
  #A#D#C#A#
  #########

#############
#A........BD#
###B#C#.#.###
  #D#C#B#.#
  #D#B#A#C#
  #A#D#C#A#
  #########

#############
#A......B.BD#
###B#C#.#.###
  #D#C#.#.#
  #D#B#A#C#
  #A#D#C#A#
  #########

#############
#AA.....B.BD#
###B#C#.#.###
  #D#C#.#.#
  #D#B#.#C#
  #A#D#C#A#
  #########

#############
#AA.....B.BD#
###B#.#.#.###
  #D#C#.#.#
  #D#B#C#C#
  #A#D#C#A#
  #########

#############
#AA.....B.BD#
###B#.#.#.###
  #D#.#C#.#
  #D#B#C#C#
  #A#D#C#A#
  #########

#############
#AA...B.B.BD#
###B#.#.#.###
  #D#.#C#.#
  #D#.#C#C#
  #A#D#C#A#
  #########

#############
#AA.D.B.B.BD#
###B#.#.#.###
  #D#.#C#.#
  #D#.#C#C#
  #A#.#C#A#
  #########

#############
#AA.D...B.BD#
###B#.#.#.###
  #D#.#C#.#
  #D#.#C#C#
  #A#B#C#A#
  #########

#############
#AA.D.....BD#
###B#.#.#.###
  #D#.#C#.#
  #D#B#C#C#
  #A#B#C#A#
  #########

#############
#AA.D......D#
###B#.#.#.###
  #D#B#C#.#
  #D#B#C#C#
  #A#B#C#A#
  #########

#############
#AA.D......D#
###B#.#C#.###
  #D#B#C#.#
  #D#B#C#.#
  #A#B#C#A#
  #########

#############
#AA.D.....AD#
###B#.#C#.###
  #D#B#C#.#
  #D#B#C#.#
  #A#B#C#.#
  #########

#############
#AA.......AD#
###B#.#C#.###
  #D#B#C#.#
  #D#B#C#.#
  #A#B#C#D#
  #########

#############
#AA.......AD#
###.#B#C#.###
  #D#B#C#.#
  #D#B#C#.#
  #A#B#C#D#
  #########

#############
#AA.......AD#
###.#B#C#.###
  #.#B#C#.#
  #D#B#C#D#
  #A#B#C#D#
  #########

#############
#AA.D.....AD#
###.#B#C#.###
  #.#B#C#.#
  #.#B#C#D#
  #A#B#C#D#
  #########

#############
#A..D.....AD#
###.#B#C#.###
  #.#B#C#.#
  #A#B#C#D#
  #A#B#C#D#
  #########

#############
#...D.....AD#
###.#B#C#.###
  #A#B#C#.#
  #A#B#C#D#
  #A#B#C#D#
  #########

#############
#.........AD#
###.#B#C#.###
  #A#B#C#D#
  #A#B#C#D#
  #A#B#C#D#
  #########

#############
#..........D#
###A#B#C#.###
  #A#B#C#D#
  #A#B#C#D#
  #A#B#C#D#
  #########

#############
#...........#
###A#B#C#D###
  #A#B#C#D#
  #A#B#C#D#
  #A#B#C#D#
  #########

Using the initial configuration from the full diagram, what is the least energy required to organize the amphipods?

2.2.2 Solution

We simply call bring_bots_home with the extended rooms.

new_rooms<- list(
  c("A", "D", "D", "B"), 
  c("D", "C", "B", "C"), 
  c("B", "B", "A", "D"), 
  c("C", "A", "C", "A")
  ) 
bring_bots_home(new_rooms)
## [1] 53308

3 R Legacy Solution

For the sake of completeness, here’s the previous R codes, which is, however, due to the copy on change semantic not really performing well:

encode_map <- function(data) {
  hall <- data[2L, seq(2L, ncol(data) - 1L)]
  rooms <- map(4L + 2L * 0:3, ~ data[seq(3L, nrow(data) - 1L), .x]) %>% 
    set_names(LETTERS[1:4])
  list(hall = hall, rooms = rooms)
}

get_map_id <- function(state) {
  unlist(state) %>% 
    paste(collapse = "")
}

is_done <- function(state) {
  rooms <- state$rooms
  reduce(names(rooms), function(res, room_id) {
    res && all(rooms[[room_id]] == room_id)
  }, .init = TRUE)
}

is_path_blocked <- function(bot, hall_pos, room_pos, hall) {
  !all(hall[seq(hall_pos, room_pos)][-1L] %in% c(".", "x"))
}

get_cost <- function(bot, in_room_pos, room_pos, hall_pos) {
  room_idx <- match(bot, LETTERS[1:4]) - 1L
  vertical <- in_room_pos
  horizontal <- abs(hall_pos - room_pos)
  cost <- 10 ^ room_idx
  (vertical + horizontal) * cost
}

get_new_position <- function(hall_pos, state, room_id = NA, dir = c("home", "out")) {
  dir <- match.arg(dir)
  hall <- state$hall
  if (dir == "home") {
    bot <- hall[hall_pos]
    room_id <- bot
    room <- state$rooms[[room_id]]
    room_pos <- (match(bot, LETTERS) - 1L) * 2L + 3L
  } else if (dir == "out") {
    ## invariant: we do not call this function in the out direction with an empty room
    stopifnot(!is.na(room_id))
    room <- state$rooms[[room_id]]
    bot <- room[which(room != ".")[1L]]
    room_pos <- (match(room_id, LETTERS) - 1L) * 2L + 3L
  }
  room_size <- length(room)
  if (is_path_blocked(bot, hall_pos, room_pos, hall)) {
    in_room_pos <- NA
  } else if (dir == "home") {
    ## bot wants to move from hall to room
    new_roomie <- bot
    new_idler <- "."
    cand <- which(room == ".")
    if (length(cand) == 0L) {
      ## no empty spaces
      in_room_pos <- NA
    } else if (length(cand) == room_size) {
      ## all empty spaces
      in_room_pos <- room_size
    } else {
      ## room has already some inhabitants
      neighbors <- tail(room, room_size - max(cand))
      if (all(neighbors == bot)) {
        ## all inhabitants are of same type
        in_room_pos <- max(cand)
      } else {
        in_room_pos <- NA
      }
    }
  } else if (dir == "out") {
    ## bot wants to move from room to hall
    new_roomie <- "."
    new_idler <- bot
    if (hall[hall_pos] != ".") {
      in_room_pos <- NA
    } else {
      in_room_pos <- which(room == bot)[1L]
    }
  }
  if (!is.na(in_room_pos)) {
    room[in_room_pos] <- new_roomie
    hall[hall_pos] <- new_idler
    state$rooms[[room_id]] <- room
    state$hall <- hall
    res <- list(
      is_free = TRUE,
      cost = get_cost(bot, in_room_pos, room_pos, hall_pos),
      state = state
    )
  } else {
    res <- list(
      is_free = FALSE,
      cost = NA_integer_,
      state = list()
    )
  }
  res
}

get_top_bot <- function(room) {
  room_id <- names(room)
  room <- room[[1L]]
  if (all(room %in% c(".", room_id))) {
    res <- NA_integer_
  } else {
    ## there is at least one wrong bot in here
    res <- which(room != ".")[1L]
  }
  res
}

bring_bots_home <- function(initial_state) {
  hash_list <- list()
  i <- 1
  move_bots <- function(state) {
    if (i %% 1000 == 0) print(i)
    i <<- i + 1
    id <- get_map_id(state)
    if (is_done(state)) {
      return(0L)
    }
    if (!is.null(hash_list[[id]])) {
      return(hash_list[[id]])
    }
    ## first move all hall bots home
    hall <- state$hall
    rooms <- state$rooms
    for (hall_pos in seq_along(hall)) {
      bot <- hall[hall_pos]
      if (!bot %in% c(".", "x")) {
        move_attempt <- get_new_position(hall_pos, state, dir = "home")
        if (move_attempt$is_free) {
          return(move_attempt$cost + Recall(move_attempt$state))
        }
      }
    }
    min_costs <- Inf
    for (room_id in names(rooms)) {
      top_bot_idx <- get_top_bot(rooms[room_id])
      if (!is.na(top_bot_idx)) {
        ## we can move a bot from this room
         for (hall_pos in seq_along(hall)) {
           move_attempt <- get_new_position(hall_pos, state, room_id, "out")
           if (move_attempt$is_free) {
             min_costs <- min(min_costs, move_attempt$cost + Recall(move_attempt$state))
           }
         }
      }
    }
    hash_list[[id]] <<- min_costs
    min_costs
  }
  
  move_bots(initial_state)
}

initial_state <- encode_map(puzzle_data)
bring_bots_home(initial_state)

initial_state2 <- initial_state
initial_state2$rooms <- list(A = c("A", "D", "D", "B"), 
                             B = c("D", "C", "B", "C"),
                             C = c("B", "B", "A", "D"), 
                             D = c("C", "A", "C", "A"))
bring_bots_home(initial_state2)