AOC_Day3_P1.R

# Advent of Code Day 3 Puzzle 1
# Team Reindeer! (Tom and Mable)
#
# Read the puzzle first: https://adventofcode.com/2018/day/3
# Then to understand how this solution works, it is best
# to start with the last function in this file and work up!
# The example_claim_vector is the same example as from the
# puzzle website.

library(stringr)
library(readr)

# Examples to use in the functions below
example_claim <- "#1 @ 2,0: 2x3"
example_claim_vector <- c('#1 @ 1,3: 4x4', '#2 @ 3,1: 4x4', '#3 @ 5,5: 2x2')
example_fabric_size <- c(7,7)

# Load in claims data from a .txt file and work out the
# corresponding solution to the puzzle.
# Test this by saving your puzzle input somewhere, and then using
# that path as the argument to this function.
count_overlaps_from_file <- function(path = 'TW_input_day3_p1.txt') {
  claim_data <- read_lines(file = path)
  count_overlaps(claim_data)
}

# Given a list or vector of claims, calculate the number
# of squares with overlapping claims (the solution to the puzzle)
# Test this by running:
# > count_overlaps(claim_list = example_claim_list)
count_overlaps <- function(claim_list) {
  fabric_size = fabric_size_needed(claim_list)
  # get the number of claims covering each square
  coverage_matrix <- claims_covering_each_square(claim_list, fabric_size)
  
  # now identify elements of the matrix with more than one claim
  overlaps_matrix <- coverage_matrix > 1
  
  # count how many squares have more than one claim
  sum(overlaps_matrix)
}

# Given a list of claims, return a matrix showing the number of claims
# from the list covering each square
# Test this by running:
# > claims_covering_each_square(claim_list = example_claim_list, fabric_size = example_fabric_size)
claims_covering_each_square <- function(claim_list, fabric_size) {
  list_of_coverage_matrices <- lapply(claim_list, squares_covered_by_claim, fabric_size = fabric_size)
  Reduce('+', list_of_coverage_matrices)
}

# Function to work out minimum fabric (and hence matrix) size
# needed for a given list of claims
# Test this by running:
# > fabric_size_needed(claim_list = example_claim_list)
fabric_size_needed <- function(claim_list) {
  
  # convert each claim to numerical data
  claim_vectors <- lapply(claim_list, get_claim_spec_info)
  
  # get the bottom right coordinates (furthest from origin) of each claim
  x_coords_bottom_right <- lapply(claim_vectors, function(x) {x[2]+x[4]})
  y_coords_bottom_right <- lapply(claim_vectors, function(x) {x[3]+x[5]})
  
  # work out the largest x and y coordinates of all the
  # bottom-right corners of the claims - this gives the
  # dimensions of the fabric (and hence matrices) needed
  # to represent the claims
  c(max(unlist(x_coords_bottom_right)),
    max(unlist(y_coords_bottom_right))
  )
}

# For a given claim, make a matrix whose [i,j]th element is
# 1 if the [i,j]th square is covered by the claim, and 0 if not
# Test this by running:
# > example_claim
# > squares_covered_by_claim(claim_spec = example_claim, fabric_size = example_fabric_size)
squares_covered_by_claim <- function(claim_spec, fabric_size) {
  numeric_claim_spec <- get_claim_spec_info(claim_spec)
  claim_matrix <- matrix(rep(0,fabric_size[1]*fabric_size[2]), nrow = fabric_size[1])
  a <- numeric_claim_spec[2]
  b <- numeric_claim_spec[3]
  c <- a + numeric_claim_spec[4]
  d <- b + numeric_claim_spec[5]
  
  # Loop over all elements of claim_matrix, setting to 1 if the square
  # is part of the claim, and 0 if not.
  # This method is too slow however!
  # R loops are VERY SLOW! So we need to look for another
  # way to define this matrix...
  #for (i in 1:fabric_size[1]) {
  #  for (j in 1:fabric_size[2]) {
  #    claim_matrix[i,j] = ifelse(i > a && i <= c && j > b && j <= d , 1, 0)
  #  }
  #}
  
  # It turns out we can form the matrix using the built in
  # base R function "outer"
  X <- c(1:fabric_size[1]) > a & c(1:fabric_size[1]) <= c
  Y <- c(1:fabric_size[2]) > b & c(1:fabric_size[2]) <= d
  claim_matrix <- outer(X,Y, FUN = "&")
  
  claim_matrix
}

# Convert the string claim specification into a vector of 5 numbers:
# 1) the claim ID
# 2) the x-coordinate of the top left corner, 3) the y-coordinate
# 4) the width and 5) the height
# Test this by running:
# > example_claim
# > get_claim_spec_info(claim_spec = example_claim)
get_claim_spec_info <- function(claim_spec) {
  extracted_strings <- str_extract_all(claim_spec, '[0-9]+')
  vector_spec <- as.numeric(extracted_strings[[1]])
  vector_spec
}