Day 20

Advent of Code: Worked Solutions

Setup

# Libraries
library(tidyverse)

# Read input from file
input <- read_table("../input/day20.txt", col_names = "char") |> 
  mutate(
    row = row_number(),
    char = str_split(char, "")
  ) |> 
  unnest_longer(char, indices_to = "col")

Part 1

Extract the sequence of tiles in the original path:

# Compute coordinates of each tile and extract the path sequence, ignoring walls
df <- input |> 
  filter(row > 1 & row < max(row) & col > 1 & col < max(col)) |> 
  mutate(
    id = row_number(),
    row = row - 1, 
    col = col - 1
  ) |> 
  filter(char %in% c("S", "E", ".")) |> 
  arrange(col, row)

# Re-number the tiles on the path by their ordering from start to finish
path_seq <- df |> 
  filter(char == "S") |> 
  pull(id)

while (length(path_seq) < nrow(df)) {
  path_seq <- c(
    path_seq, 
    df |> 
      filter(id == tail(path_seq, 1)) |> 
      cross_join(df) |> 
      filter(
        (abs(col.x - col.y) == 1 & abs(row.x - row.y) == 0) |
        (abs(col.x - col.y) == 0 & abs(row.x - row.y) == 1)
      ) |> 
      filter(!(id.y %in% path_seq)) |> 
      pull(id.y)
  )
}

# Attach path order onto the list of path tiles with their coordinates
df_path <- left_join(
  df, 
  enframe(path_seq, name = "path_idx", value = "id"), 
  join_by(id)
) |> 
  select(path_idx, row, col) |> 
  arrange(path_idx)

Count the total seconds saved when collision is disabled for n seconds. Possible cheat end locations, and the time it takes to arrive there, can be calculated using Manhattan distance.

manhattan_dist <- function(a_row, a_col, b_row, b_col) {
  abs(a_row - b_row) + abs(a_col - b_col)
}

count_cheats <- function(cheat_length) {

  df_path |> 
    # Find all possible time-saving cheats if collision is disabled for n secs
    left_join(df_path, join_by(x$path_idx < y$path_idx)) |> 
    mutate(dist = manhattan_dist(row.x, col.x, row.y, col.y)) |> 
    filter(dist <= cheat_length) |> 
    mutate(saved = path_idx.y - path_idx.x - dist) |> 
    summarize(n = n(), .by = saved) |> 
    arrange(saved) |> 
    
    # Count the total number of cheats that save at least 100 seconds
    filter(saved >= 100) |> 
    pull(n) |>
    sum()
  
}

Run on puzzle input:

count_cheats(2)

[1] 1417

Part 2

count_cheats(20)

[1] 1014683