Task 17

2025-03-21

1 Setup

1.1 Libraries

library(httr)
library(xml2)
library(magrittr)
library(dplyr)
library(purrr)
library(stringr)

1.2 Retrieve Data from `AoC`

session_cookie <- set_cookies(session = keyring::key_get("AoC-GitHub-Cookie"))
base_url <- paste0("https://adventofcode.com/", params$year, "/day/", params$task_nr)
puzzle <- GET(base_url,
              session_cookie) %>% 
  content(encoding = "UTF-8") %>% 
  xml_find_all("///article") %>% 
  lapply(as.character)

parse_puzzle_data <- function(text_block = readClipboard()) {
  if (length(text_block) == 1L) {
    text_block <- text_block %>% 
      str_split("\n") %>% 
      extract2(1L) %>% 
      keep(nzchar)
  }
  as.integer(text_block)
}

puzzle_data <- local({
  GET(paste0(base_url, "/input"),
      session_cookie) %>% 
    content(encoding = "UTF-8") %>% 
    parse_puzzle_data()
})

2 Puzzle Day 17

2.1 Part 1

2.1.1 Description

— Day 17: No Such Thing as Too Much —

The elves bought too much eggnog again - 150 liters this time. To fit it all into your refrigerator, you’ll need to move it into smaller containers. You take an inventory of the capacities of the available containers.

For example, suppose you have containers of size 20, 15, 10, 5, and 5 liters. If you need to store 25 liters, there are four ways to do it:

15 and 10
20 and 5 (the first 5)
20 and 5 (the second 5)
15, 5, and 5

Filling all containers entirely, how many different combinations of containers can exactly fit all 150 liters of eggnog?

2.1.2 Solution

We solve this puzzle via dynamic programming. We create a vector where each entry represents the amount of ways to reach a sum equal to the index. That is z₀ indicates the amount of ways to build a sum equal 0. We set z₀ to 1 (there is only one way to build the sum 0, namely by adding no numbers as all numbers are greater than 0).

We then use two loops, the first iterates over each number, the second loops from the maximum capacity down to the current number. Let’s assume that x_i denotes the current number from the list. Now to count the number of ways to reach a sum of y, we simply have to add the number of ways how we reach y − x_i to get the proper count.

count_sums <- function(numbers, capacity) {
  nr_ways <- vector("integer", capacity + 1L)
  nr_ways[1L] <- 1L
  walk(numbers, function(nr) {
    for (i in capacity:nr) {
      ## idea: 
      ## 1. res[i + 1L] counts the number of ways we can build the sum `i` (the plus one
      ##    is there because R is 1-based)
      ## 2. Likewise res[i - nr + 1L] counts the number of ways we can build sum `i - nr`
      ## 3. We are currently examining summand `nr`, thus we can add `nr` to `i - nr` to
      ##    end up at `i`. Hence, we simply add the number of ways to reach `i - nr` to
      ##    the number of ways we reached `i` (in earlier iterations) 
      nr_ways[i + 1L] <<- nr_ways[i + 1L] + nr_ways[i - nr + 1L] 
    }
  })
  tail(nr_ways, 1L)
}
count_sums(puzzle_data, 150)

## [1] 654

2.2 Part 2

2.2.1 Description

— Part Two —

While playing with all the containers in the kitchen, another load of eggnog arrives! The shipping and receiving department is requesting as many containers as you can spare.

Find the minimum number of containers that can exactly fit all 150 liters of eggnog. How many different ways can you fill that number of containers and still hold exactly 150 litres?

In the example above, the minimum number of containers was two. There were three ways to use that many containers, and so the answer there would be 3.

2.2.2 Solution

This time we need also to keep track about the amount of summands. The algorithm follows largely the same ideas as before, but this time we check if the previous sum was reached with less then current number of operands plus one, if so, we take this number of ways as new minimum and update teh values accordingly. If we are already on the track of smallest number of summands, we update the number of ways as before by adding the value of the partial sum.

count_min_sums <- function(numbers, capacity) {
  nr_operands <- rep(Inf, capacity + 1L)
  nr_ways <- rep(0L, capacity + 1L) 
  
  nr_operands[1L] <- 0L
  nr_ways[1L] <- 1L
  walk(numbers, function(nr) {
    for (i in capacity:nr) {
      if (nr_operands[i - nr + 1L] + 1L < nr_operands[i + 1L]) {
        ## we got `i - nr` with less summands minus one (the one we would be adding now)
        ## update teh numebr of operands (one more) and overwrite the number of ways 
        ## (we want to count only the minumum, hence not adding but simply overwriting)
        nr_operands[i + 1L] <<- nr_operands[i - nr + 1L] + 1L
        nr_ways[i + 1L] <<- nr_ways[i - nr + 1L]
      } else if (nr_operands[i - nr + 1L] + 1L == nr_operands[i + 1L]) {
        ## same as before if we are on the track of smallest number of operands
        nr_ways[i + 1L] <<- nr_ways[i + 1L] + nr_ways[i - nr + 1L]
      }
    }
  }
  )
  list(min_count = nr_operands[capacity + 1L], min_ways = nr_ways[capacity + 1L])
}
count_min_sums(puzzle_data, 150L)

## $min_count
## [1] 4
## 
## $min_ways
## [1] 57