day_10.Rmd

# Adapter Array

```{r setup, include=FALSE}
knitr::opts_chunk$set(echo = TRUE)
options(crayon.enabled = NULL)
library(tidyverse)

START_TIME <- Sys.time()
```

This is my attempt to solve [Day 10](https://adventofcode.com/2020/day/10).

```{r load data}
sample <- read_lines("samples/day_10_sample.txt") %>% as.numeric()
actual <- read_lines("inputs/day_10_input.txt") %>% as.numeric()
```

## Part 1

We can solve part 1 pretty easily using base R functions. First, sort the input. We can then use `diff()` to calculate
the differences between each successive pairs of values, then we can use `table()` to count how many of each value
appears. We can then multiply the values using the `prod()` (product) function.

We just need to remember to add "0" to our input, and the value that is 3 greater than the maximum value in the input.

```{r}
part_1 <- function(input) {
  c(0, input, max(input + 3)) %>%
    sort() %>%
    diff() %>%
    table() %>%
    prod()
}
```

We can now test our function on the sample:

```{r part 1 sample test}
part_1(sample) == 22 * 10
```

And we can run the function with the actual data:

```{r part 1 actual}
part_1(actual)
```

## Part 2

Part 2 can be solved with [Dynamic Programming](https://en.wikipedia.org/wiki/Dynamic_programming). We will start at the
beginning of the sorted input, and iterate over each item in turn. At each item we find which other items can be
reached and increase their counts by the current items count. Once we reach the end of the list we have the answer.

```{r part 2 function}
part_2 <- function(input) {
  # ensure input is sorted
  input <- sort(input)
  # create a list of values for our counts, initialise to 0
  t <- rep(0, length(input))
  # set all of the items that can be reached from "0" to 1
  t[input <= 3] <- 1
  
  # iterate over the input
  for (i in seq_along(input)) {
    # get the current item in the input
    x <- input[[i]]
    # get the indexes of the items that can be reached from the current item
    r <- input > x & input <= x + 3
    # update the items that can be reached
    t[r] <- t[[i]] + t[r]
  }
  
  # return just the final value
  tail(t, 1)
}
```

We can test our part 2 function on the sample data:

```{r part 2 sample test}
part_2(sample) == 19208
```

We know that the actual solution will be a giant number, so make sure R doesn't format the number in scientific
notation by setting the `scipen` option.

```{r part 2 actual}
options(scipen = 999)
part_2(actual)
```

---

*Elapsed Time: `r round(Sys.time() - START_TIME, 3)`s*