Task 11

2025-07-25

1 Setup

1.1 Libraries

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

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 
}

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

2 Puzzle Day 11

2.1 Part 1

2.1.1 Description

— Day 11: Corporate Policy —

Santa’s previous password expired, and he needs help choosing a new one.

To help him remember his new password after the old one expires, Santa has devised a method of coming up with a password based on the previous one. Corporate policy dictates that passwords must be exactly eight lowercase letters (for security reasons), so he finds his new password by incrementing his old password string repeatedly until it is valid.

Incrementing is just like counting with numbers: xx, xy, xz, ya, yb, and so on. Increase the rightmost letter one step; if it was z, it wraps around to a, and repeat with the next letter to the left until one doesn’t wrap around.

Unfortunately for Santa, a new Security-Elf recently started, and he has imposed some additional password requirements:

Passwords must include one increasing straight of at least three letters, like abc, bcd, cde, and so on, up to xyz. They cannot skip letters; abd doesn’t count.
Passwords may not contain the letters i, o, or l, as these letters can be mistaken for other characters and are therefore confusing.
Passwords must contain at least two different, non-overlapping pairs of letters, like aa, bb, or zz.

For example:

hijklmmn meets the first requirement (because it contains the straight hij) but fails the second requirement requirement (because it contains i and l).
abbceffg meets the third requirement (because it repeats bb and ff) but fails the first requirement.
abbcegjk fails the third requirement, because it only has one double letter (bb).
The next password after abcdefgh is abcdffaa.
The next password after ghijklmn is ghjaabcc, because you eventually skip all the passwords that start with ghi…, since i is not allowed.

Given Santa’s current password (your puzzle input), what should his next password be?

2.1.2 Solution

We work with letter positions rather than the letters themselves as it makes calculation way easier.

We use a function to validate a given password and another to increment it. We then increment the password until we reach a valid password.

The solution was first implemented in R, but was slow-ish (it took more than 2 minutes to calculate the password). Hence, we re-implemented it using C++.

The algorithm could be tremendously improved by not increasing passwords by one step at a time, but jumping invalid passwords right away.

However, the C++ solution was blasting fast anyways, so we did not bother to further improve the solution.

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

#include <algorithm>
#include <array>
#include <string>

bool validate_pw(const std::array<unsigned int, 8>& code) {
  bool test_passed = false;
  for (size_t i = 0; i < code.size() - 2; ++i) {
    if (code[i] + 1 == code[i + 1] && code[i + 1] + 1 == code[i + 2]) {
      test_passed = true;
      break;
    }
  }
  if (!test_passed) {
    return false;
  }
  test_passed = !std::any_of(
      code.begin(), code.end(), [](unsigned int n) { return n == 9 || n == 12 || n == 15; });
  if (!test_passed) {
    return false;
  }
  int pairCount = 0;
  for (size_t i = 0; i < code.size() - 1; ++i) {
    if (code[i] == code[i + 1]) {
      ++pairCount;
      ++i;
    }
  }
  test_passed = pairCount >= 2;
  return test_passed;
}

void increment_pw(std::array<unsigned int, 8>& code) {
  size_t i, n;
  unsigned int new_digit;
  bool done = false;
  n = code.size();
  i = n - 1;
  while (!done) {
    new_digit = std::max<unsigned int>((code[i] + 1) % 27, 1);
    done = new_digit != 1;
    code[i] = new_digit;
    if (i == 0) {
      i = n - 1;
    } else {
      i--;
    }
  }
}

// [[Rcpp::export]]
std::string find_next_password(std::string pw) {
  std::array<unsigned int, 8> code;
  size_t i = 0;
  for (auto const& c : pw) {
    code[i++] = static_cast<char>(c) - 'a' + 1;
  }
  bool done = false;
  i = 0;
  while (!done) {
    increment_pw(code);
    done = validate_pw(code);
    i++;
  }
  auto stringify {[](const std::array<unsigned int, 8>& code) {
    std::string result;
    for (auto d : code) {
      char letter = 'a' + (d - 1);
      result += letter;
    }
    return result;
  }};
  return stringify(code);
}

#ifdef STANDALONE
int main() {
  std::string password = "ghijklmn";
  std::string next_password = find_next_password(password);
  std::cout << "Original password: " << password << " Next password: " << next_password
            << std::endl;
  return 0;
}
#endif // STANDALONE

(res <- find_next_password(puzzle_data))

## [1] "cqjxxyzz"

2.2 Part 2

2.2.1 Description

— Part Two —

Santa’s password expired again. What’s the next one?

2.2.2 Solution

All we need to do is to apply the same function to the previously generated password.

 find_next_password(res)

## [1] "cqkaabcc"

3 R Legacy Solution

validate_password <- function(code) {
  distance <- diff(code)
  rld <- rle(distance)
  rl <- rle(code)
  idx_iol <- match(c("i", "o", "l"), letters)
  any(rld$values == 1L & rld$lengths >= 2L) && ## 3 consecutive
    !any(idx_iol %in% code) && ## no i, o or l
    (any(rl$lengths >= 4) || sum(rl$lengths >= 2) >= 2) ## at least 2 pairs
}

increment_password <- function(code) {
  n <- i <- length(code)
  done <- FALSE
  while (!done) {
    new_digit <- max((code[i] + 1L) %% 27L, 1L)
    done <- new_digit != 1L
    code[i] <- new_digit
    i <- if_else(i - 1 == 0, n, i - 1)
  }
  code
}

find_next_valid_password <- function(password) {
  cli_progress_bar("Looking for valid passwords")
  code <- str_split(password, "") %>% 
    extract2(1L) %>% 
    match(letters)
  is_invalid <- TRUE
  n <- length(code)
  idx_iol <- match(c("i", "o", "l"), letters)
  while (is_invalid) {
    cli_progress_update()
    i <- n
    done <- FALSE
    ## increment
    while (!done) {
      new_digit <- max((code[i] + 1L) %% 27L, 1L)
      done <- new_digit != 1L
      code[i] <- new_digit
      i <- if_else(i - 1L == 0L, n, i - 1L)
    }
    ## check
    distance <- diff(code)
    rld <- rle(distance)
    rl <- rle(code)
    is_invalid <- !(
      any(rld$values == 1L & rld$lengths >= 2L) && ## 3 consecutive
      !any(idx_iol %in% code) && ## no i, o or l
      (any(rl$lengths >= 4) || sum(rl$lengths >= 2) >= 2) ## at least 2 pairs
    )
  }
  cli_progress_done()
  letters[code] %>% 
    paste(collapse = "")
}

find_next_valid_password(puzzle_data)