Task 17

2025-09-21

1 Setup

1.1 Libraries

library(httr)
library(xml2)
library(magrittr)
library(dplyr)
library(purrr)
library(stringr)
library(withr)

1.2 Retrieve Data from `AoC`

local_envvar(list("PKG_LIBS" = "-lcrypto -lcrypt32 -lws2_32 -lz")) %>% 
  suppressMessages()
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 
}

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

2 Puzzle Day 17

2.1 Part 1

2.1.1 Description

— Day 17: Two Steps Forward —

You’re trying to access a secure vault protected by a 4x4 grid of small rooms connected by doors. You start in the top-left room (marked S), and you can access the vault (marked V) once you reach the bottom-right room:

#########
#S| | | #
#-#-#-#-#
# | | | #
#-#-#-#-#
# | | | #
#-#-#-#-#
# | | |  
####### V

Fixed walls are marked with #, and doors are marked with - or |.

The doors in your current room are either open or closed (and locked) based on the hexadecimal MD5 hash of a passcode (your puzzle input) followed by a sequence of uppercase characters representing the path you have taken so far (U for up, D for down, L for left, and R for right).

Only the first four characters of the hash are used; they represent, respectively, the doors up, down, left, and right from your current position. Any b, c, d, e, or f means that the corresponding door is open; any other character (any number or a) means that the corresponding door is closed and locked.

To access the vault, all you need to do is reach the bottom-right room; reaching this room opens the vault and all doors in the maze.

For example, suppose the passcode is hijkl. Initially, you have taken no steps, and so your path is empty: you simply find the MD5 hash of hijkl alone. The first four characters of this hash are ced9, which indicate that up is open (c), down is open (e), left is open (d), and right is closed and locked (9). Because you start in the top-left corner, there are no “up” or “left” doors to be open, so your only choice is down.

Next, having gone only one step (down, or D), you find the hash of hijklD. This produces f2bc, which indicates that you can go back up, left (but that’s a wall), or right. Going right means hashing hijklDR to get 5745 - all doors closed and locked. However, going up instead is worthwhile: even though it returns you to the room you started in, your path would then be DU, opening a different set of doors.

After going DU (and then hashing hijklDU to get 528e), only the right door is open; after going DUR, all doors lock. (Fortunately, your actual passcode is not hijkl).

Passcodes actually used by Easter Bunny Vault Security do allow access to the vault if you know the right path. For example:

If your passcode were ihgpwlah, the shortest path would be DDRRRD.
With kglvqrro, the shortest path would be DDUDRLRRUDRD.
With ulqzkmiv, the shortest would be DRURDRUDDLLDLUURRDULRLDUUDDDRR.

Given your vault’s passcode, what is the shortest path (the actual path, not just the length) to reach the vault?

2.1.2 Solution

We implement an A Star search algorithm with the Manhatten distance as heuristic plus the actual costs.

#ifndef STANDALONE
#include <Rcpp.h>
using namespace Rcpp;
#else
#include <iostream>
#endif

#include <iomanip>
#include <openssl/evp.h>
#include <queue>
#include <regex>
#include <sstream>
#include <string>
#include <unordered_map>

std::string get_md5(const std::string& input) {
  EVP_MD_CTX* mdctx = EVP_MD_CTX_new();
  const EVP_MD* md = EVP_md5();
  unsigned char md_value[EVP_MAX_MD_SIZE];
  unsigned int md_len;

  EVP_DigestInit_ex(mdctx, md, NULL);
  EVP_DigestUpdate(mdctx, input.c_str(), input.size());
  EVP_DigestFinal_ex(mdctx, md_value, &md_len);

  std::ostringstream oss;
  for (size_t i = 0; i < md_len; ++i) {
    oss << std::hex << std::setw(2) << std::setfill('0') << static_cast<int>(md_value[i]);
  }

  EVP_MD_CTX_free(mdctx);
  return oss.str();
}

constexpr int ROOMS_ROWS = 4;
constexpr int ROOMS_COLS = 4;

class Maze {
  private:
    int row;
    int col;
    std::string passkey;
    std::vector<char> path;

    std::string get_current_passkey() const;
    bool is_wall(char dir) const;

  public:
    Maze(const std::string);

    bool is_done() const { return row == ROOMS_ROWS - 1 && col == ROOMS_COLS - 1; };
    int score() const { return ROOMS_ROWS - 1 - row + ROOMS_COLS - 1 - col + path.size(); };
    std::string get_path() const;

    Maze move(char dir) const;

    std::vector<char> get_valid_neighbors() const;
};

struct MazeComparator {
  public:
    bool operator()(const Maze& a, const Maze& b) const {
      return a.score() > b.score(); // lower score = better
    }
};

Maze::Maze(const std::string key)
    : row(0)
    , col(0)
    , passkey(key) { }

std::string Maze::get_path() const {
  return std::string(path.data(), path.size());
}

Maze Maze::move(char dir) const {
  static const std::unordered_map<char, std::pair<int, int>> DELTAS = {
      {'U', {-1, 0}}, {'R', {0, 1}}, {'D', {1, 0}}, {'L', {0, -1}}};

  Maze next_room = *this;
  auto delta = DELTAS.at(dir);
  next_room.row += delta.first;
  next_room.col += delta.second;
  next_room.path.push_back(dir);
  return next_room;
}

std::vector<char> Maze::get_valid_neighbors() const {
  if (is_done()) {
    return {};
  }
  std::vector<char> dirs = {'U', 'D', 'L', 'R'};
  std::vector<char> valid_dirs;
  std::string code = get_md5(get_current_passkey());
  for (int i = 0; i < dirs.size(); ++i) {
    char c = code[i];
    if ((c >= 'b' && c <= 'f') && !is_wall(dirs[i])) {
      valid_dirs.push_back(dirs[i]);
    }
  }
  return valid_dirs;
}

bool Maze::is_wall(char dir) const {
  bool res;
  if (dir == 'U') {
    res = row == 0;
  } else if (dir == 'R') {
    res = col == ROOMS_COLS - 1;
  } else if (dir == 'D') {
    res = row == ROOMS_ROWS - 1;
  } else if (dir == 'L') {
    res = col == 0;
  }
  return res;
}

std::string Maze::get_current_passkey() const {
  return passkey + get_path();
}

// [[Rcpp::export]]
std::string get_shortest_path(std::string passcode) {
  std::string shortest_path;
  std::priority_queue<Maze, std::vector<Maze>, MazeComparator> walk;
  Maze start(passcode);
  walk.push(start);
  while (!walk.empty()) {
    Maze pos = walk.top();
    walk.pop();
    if (pos.is_done()) {
      shortest_path = pos.get_path();
      break;
    }
    std::vector<char> nbs = pos.get_valid_neighbors();
    for (char dir : nbs) {
      walk.push(pos.move(dir));
    }
  }
  return shortest_path;
}

// [[Rcpp::export]]
int get_longest_path(std::string passcode) {
  int longest_path = 0;
  std::queue<Maze> walk;
  Maze start(passcode);
  walk.push(start);

  while (!walk.empty()) {
    Maze pos = walk.front();
    walk.pop();
    if (pos.is_done()) {
      if (pos.get_path().size() > longest_path) {
        longest_path = pos.get_path().size();
      }
    }
    std::vector<char> nbs = pos.get_valid_neighbors();
    for (char dir : nbs) {
      walk.push(pos.move(dir));
    }
  }
  return longest_path;
}

#ifdef STANDALONE
int main() {
  std::cout << get_shortest_path("ihgpwlah") << std::endl
            << get_shortest_path("kglvqrro") << std::endl
            << get_shortest_path("ulqzkmiv") << std::endl;
  std::cout << get_longest_path("ihgpwlah") << std::endl
            << get_longest_path("kglvqrro") << std::endl
            << get_longest_path("ulqzkmiv") << std::endl;
}
#endif

get_shortest_path(puzzle_data)

## [1] "DUDRLRRDDR"

2.2 Part 2

2.2.1 Description

— Part Two —

You’re curious how robust this security solution really is, and so you decide to find longer and longer paths which still provide access to the vault. You remember that paths always end the first time they reach the bottom-right room (that is, they can never pass through it, only end in it).

For example:

If your passcode were ihgpwlah, the longest path would take 370 steps.
With kglvqrro, the longest path would be 492 steps long.
With ulqzkmiv, the longest path would be 830 steps long.

What is the length of the longest path that reaches the vault?

2.2.2 Solution

For teh longest path we do not stop after finding the first path, but exhaust the full search space.

get_longest_path(puzzle_data)

## [1] 788