Day 9

Advent of Code: Worked Solutions

Setup

Import libraries:

library(tidyverse)

Disable scientific formatting when displaying large numbers:

options(scipen = 999)

Read input from file into a vector of integers:

input <- read_lines("../input/day09.txt") |> 
  str_split_1("") |> 
  as.integer()

Part 1

Define a function to move the file blocks:

move_files <- function(filesys) {
  repeat {
    first_blank <- min(which(is.na(filesys)))
    last_file   <- max(which(!is.na(filesys)))
    
    # If all files have been compressed, exit
    if (first_blank > last_file) break
    
    # Otherwise, move the last file into the first blank location
    filesys[first_blank] <- filesys[last_file]
    filesys[last_file]   <- NA_integer_
  }
  filesys
}

Define a function to compute the checksum of the file system:

checksum <- function(filesys) {
  filesys |> 
    imap_int(\(x, idx) if_else(is.na(x), 0, x * (idx - 1))) |> 
    sum()
}

Uncompress the given file layout, interpreting even entries as files and odd entries as spaces:

filesys <- input|> 
  imap(function(x, idx) {
    file_id <- if_else(idx %% 2 == 1, floor(idx / 2), NA_integer_)
    rep(file_id, x)
  }) |> 
  unlist()

Move the files and compute the checksum:

filesys |> 
  move_files() |> 
  checksum()

Part 2

Update the compression function:

move_blocks <- function(filesys) {
  for (file_id in max(na.omit(filesys)):1) {
    
    # Pull the location and length of the file block for the current ID
    file_block <- which(filesys == file_id)
    n <- length(file_block)
    
    # Pull indices of all empty values before the current file block
    empty_idx <- which(is.na(filesys[1:min(file_block)]))
    
    # Pull all valid starting indices of empty blocks of the right length
    if (n == 1) {
      valid_idx <- empty_idx
    } else {
      valid_block <- replace_na(lead(empty_idx, n - 1) - empty_idx == n - 1, FALSE)
      valid_idx <- empty_idx[valid_block]
    }
    
    # If valid indices exist, move the file block to the first valid location
    if (length(valid_idx) > 0) {
      idx_start <- min(valid_idx)
      filesys[idx_start:(idx_start + n - 1)] <- file_id
      filesys[file_block] <- NA_integer_
    }
  }
  
  filesys
}

Re-run input with new compression function:

filesys |> 
  move_blocks() |> 
  checksum()