R/day05.R

In tjmahr/adventofcode21:

#' Day 05: Hydrothermal Venture
#'
#' [Hydrothermal Venture](https://adventofcode.com/2021/day/5)
#'
#' @name day05
#' @rdname day05
#' @details
#'
#' **Part One**
#'
#' You come across a field of [hydrothermal
#' vents](https://en.wikipedia.org/wiki/Hydrothermal_vent) on the ocean
#' floor! These vents constantly produce large, opaque clouds, so it would
#' be best to avoid them if possible.
#'
#' They tend to form in *lines*; the submarine helpfully produces a list of
#' nearby [lines of vents]{title="Maybe they're Bresenham vents."} (your
#' puzzle input) for you to review. For example:
#'
#'     0,9 -> 5,9
#'     8,0 -> 0,8
#'     9,4 -> 3,4
#'     2,2 -> 2,1
#'     7,0 -> 7,4
#'     6,4 -> 2,0
#'     0,9 -> 2,9
#'     3,4 -> 1,4
#'     0,0 -> 8,8
#'     5,5 -> 8,2
#'
#' Each line of vents is given as a line segment in the format
#' `x1,y1 -> x2,y2` where `x1`,`y1` are the coordinates of one end the line
#' segment and `x2`,`y2` are the coordinates of the other end. These line
#' segments include the points at both ends. In other words:
#'
#' -   An entry like `1,1 -> 1,3` covers points `1,1`, `1,2`, and `1,3`.
#' -   An entry like `9,7 -> 7,7` covers points `9,7`, `8,7`, and `7,7`.
#'
#' For now, *only consider horizontal and vertical lines*: lines where
#' either `x1 = x2` or `y1 = y2`.
#'
#' So, the horizontal and vertical lines from the above list would produce
#' the following diagram:
#'
#'     .......1..
#'     ..1....1..
#'     ..1....1..
#'     .......1..
#'     .112111211
#'     ..........
#'     ..........
#'     ..........
#'     ..........
#'     222111....
#'
#' In this diagram, the top left corner is `0,0` and the bottom right
#' corner is `9,9`. Each position is shown as *the number of lines which
#' cover that point* or `.` if no line covers that point. The top-left pair
#' of `1`s, for example, comes from `2,2 -> 2,1`; the very bottom row is
#' formed by the overlapping lines `0,9 -> 5,9` and `0,9 -> 2,9`.
#'
#' To avoid the most dangerous areas, you need to determine *the number of
#' points where at least two lines overlap*. In the above example, this is
#' anywhere in the diagram with a `2` or larger - a total of `5` points.
#'
#' Consider only horizontal and vertical lines. *At how many points do at
#' least two lines overlap?*
#'
#' **Part Two**
#'
#' Unfortunately, considering only horizontal and vertical lines doesn\'t
#' give you the full picture; you need to also consider *diagonal lines*.
#'
#' Because of the limits of the hydrothermal vent mapping system, the lines
#' in your list will only ever be horizontal, vertical, or a diagonal line
#' at exactly 45 degrees. In other words:
#'
#' -   An entry like `1,1 -> 3,3` covers points `1,1`, `2,2`, and `3,3`.
#' -   An entry like `9,7 -> 7,9` covers points `9,7`, `8,8`, and `7,9`.
#'
#' Considering all lines from the above example would now produce the
#' following diagram:
#'
#'     1.1....11.
#'     .111...2..
#'     ..2.1.111.
#'     ...1.2.2..
#'     .112313211
#'     ...1.2....
#'     ..1...1...
#'     .1.....1..
#'     1.......1.
#'     222111....
#'
#' You still need to determine *the number of points where at least two
#' lines overlap*. In the above example, this is still anywhere in the
#' diagram with a `2` or larger - now a total of `12` points.
#'
#' Consider all of the lines. *At how many points do at least two lines
#' overlap?*
#'
#' @param x some data
#' @param include_diagonals whether to include diagonal lines
#' @return For Part One and Part Two, `f05a_count_intersections(x)` returns the
#'   number of intersecting points.
#' @export
#' @examples
#' f05a_count_intersections(example_data_05())
#' f05a_count_intersections(example_data_05(), include_diagonals = TRUE)
f05a_count_intersections <- function(x, include_diagonals = FALSE) {
  # strategy: split-apply-combine
  is_vertical <- function(x) x[["x1"]] == x[["x2"]]
  is_horizontal <- function(x) x[["y1"]] == x[["y2"]]
  is_line <- if (include_diagonals) {
    function(x) TRUE
  } else {
    function(x) is_vertical(x) || is_horizontal(x)
  }
  unpack_line <- function(l) {
    data.frame(
      id = l[["id"]],
      x = seq(l[["x1"]], l[["x2"]]),
      y = seq(l[["y1"]], l[["y2"]])
    )
  }

  x <- x |>
    f05_parse_lines() |>
    split(~ id) |>
    f_filter(is_line) |>
    lapply(unpack_line) |>
    f_reduce(rbind)

  # ha it even makes a grid
  counts <- table(x[["x"]], x[["y"]])
  sum(counts > 1)
}

f05_parse_lines <- function(x) {
  # x <- example_data_05()
  x_frame <- x |>
    strsplit(split = "(,| -> )") |>
    simplify2array() |>
    t() |>
    as.data.frame() |>
    stats::setNames(c("x1", "y1", "x2", "y2"))

  x_frame[["id"]] <- seq_along(x)
  x_frame
}

#' @param example Which example data to use (by position or name). Defaults to
#'   1.
#' @rdname day05
#' @export
example_data_05 <- function(example = 1) {
  l <- list(
    a = c(
      "0,9 -> 5,9",
      "8,0 -> 0,8",
      "9,4 -> 3,4",
      "2,2 -> 2,1",
      "7,0 -> 7,4",
      "6,4 -> 2,0",
      "0,9 -> 2,9",
      "3,4 -> 1,4",
      "0,0 -> 8,8",
      "5,5 -> 8,2"
    )
  )
  l[[example]]
}