2023: Day 4 - Scratchcards

R
Published

December 4, 2023

Setup

The original challenge

My data

Part 1

There are a bunch of cards, which get points based on how many winning numbers do they have. I have to calculate how many points are the cards worth in total.

Card 1: 41 48 83 86 17 | 83 86  6 31 17  9 48 53
Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19
Card 3:  1 21 53 59 44 | 69 82 63 72 16 21 14  1
Card 4: 41 92 73 84 69 | 59 84 76 51 58  5 54 83
Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36
Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11

Numbers to the right of the vertical bar | are the winning numbers. The first winning number to the left of the bar makes the card worth 1 point, and each sucesive winning number doubles the points the card is worth.

library(tidyverse)
library(here)

Reading the input as a vector

input <- read_lines(here("2023/day/4/input"))
input[1:10]
 [1] "Card   1: 69 12 75 19 83 56 73 53 52 91 | 83 63 56 30 77 94 12 81 42 69 52 70  6 97 20 43 61 22 75 19 73 32 74 53 91"
 [2] "Card   2: 23 55 24 84 90 10 87 73 74 45 | 20 66 51 78  9 76 86 96 72 70 84 35 74 90 56 55 23 38 58 45 87  2 80  8 10"
 [3] "Card   3: 70 32 38 23 86 54 26 16  9  1 | 67 50 39 70 59 77 63 30  3 45 23 16 72  1 86  7  9 32 26 68 38 54 65 34 64"
 [4] "Card   4: 33 50 19 63 92  1 58 34 84  8 | 35 61 49 86 40 20 22 71 84 51 64 62 33 85 45  3 54 83  1 29 82 19 92  8 11"
 [5] "Card   5: 74  9 54 83 22 15 81 64 47 70 | 21 74 59 85 17 36  5 79 87  7 13 23 47 45 96 29 68 65  3 22  4 34 46 90 40"
 [6] "Card   6: 29 55 56 13 58 71 36 30 15 11 | 99 17 90 29 22 68 61 55 11 13 37 94 30 60 56 92 44 71 42 31  8 26 14 51 35"
 [7] "Card   7: 92 70 97 62 33 45 85 59 82 73 | 92 35 11 49 88 14 85 42 40 41 69 51 82 73  5 87 60 62 33 97 70 16 59 13 45"
 [8] "Card   8:  5 22 64 46 32 90 57 83 37 38 | 87 47 91 35 39 64 73 83 71 22 10 45  1 76 37 13 20 66 67 21 86 92 38 12 52"
 [9] "Card   9:  7 49 62 79 37 91  3 58 74 19 | 17  7 58  2 53 95 52 62 83 41 42 36  4 94 64 97 20 32  3 73 81 22 57 37  9"
[10] "Card  10: 84 33 81 45 99 96 76 97 40  2 | 81 26 11 34 83 25 45 76  2 85 33 64 57 99 93 75 96  8 84 44 79 87 97 40 70"

Trying to parse the input as tidy data:

card_data <- tibble(
  input = input
) %>%
  separate(
    input,
    into = c("id", "data"),
    sep = ": "
  ) %>%
  mutate(
    id = as.integer(str_extract(id, "\\d+"))
  )

card_data
# A tibble: 212 × 2
      id data                                                                   
   <int> <chr>                                                                  
 1     1 "69 12 75 19 83 56 73 53 52 91 | 83 63 56 30 77 94 12 81 42 69 52 70  …
 2     2 "23 55 24 84 90 10 87 73 74 45 | 20 66 51 78  9 76 86 96 72 70 84 35 7…
 3     3 "70 32 38 23 86 54 26 16  9  1 | 67 50 39 70 59 77 63 30  3 45 23 16 7…
 4     4 "33 50 19 63 92  1 58 34 84  8 | 35 61 49 86 40 20 22 71 84 51 64 62 3…
 5     5 "74  9 54 83 22 15 81 64 47 70 | 21 74 59 85 17 36  5 79 87  7 13 23 4…
 6     6 "29 55 56 13 58 71 36 30 15 11 | 99 17 90 29 22 68 61 55 11 13 37 94 3…
 7     7 "92 70 97 62 33 45 85 59 82 73 | 92 35 11 49 88 14 85 42 40 41 69 51 8…
 8     8 " 5 22 64 46 32 90 57 83 37 38 | 87 47 91 35 39 64 73 83 71 22 10 45  …
 9     9 " 7 49 62 79 37 91  3 58 74 19 | 17  7 58  2 53 95 52 62 83 41 42 36  …
10    10 "84 33 81 45 99 96 76 97 40  2 | 81 26 11 34 83 25 45 76  2 85 33 64 5…
# ℹ 202 more rows
card_data_split <- card_data %>%
  separate(
    data,
    into = c("my_numbers", "winning_numbers"),
    sep = " \\| "
  )

card_data_split
# A tibble: 212 × 3
      id my_numbers                      winning_numbers                        
   <int> <chr>                           <chr>                                  
 1     1 "69 12 75 19 83 56 73 53 52 91" 83 63 56 30 77 94 12 81 42 69 52 70  6…
 2     2 "23 55 24 84 90 10 87 73 74 45" 20 66 51 78  9 76 86 96 72 70 84 35 74…
 3     3 "70 32 38 23 86 54 26 16  9  1" 67 50 39 70 59 77 63 30  3 45 23 16 72…
 4     4 "33 50 19 63 92  1 58 34 84  8" 35 61 49 86 40 20 22 71 84 51 64 62 33…
 5     5 "74  9 54 83 22 15 81 64 47 70" 21 74 59 85 17 36  5 79 87  7 13 23 47…
 6     6 "29 55 56 13 58 71 36 30 15 11" 99 17 90 29 22 68 61 55 11 13 37 94 30…
 7     7 "92 70 97 62 33 45 85 59 82 73" 92 35 11 49 88 14 85 42 40 41 69 51 82…
 8     8 " 5 22 64 46 32 90 57 83 37 38" 87 47 91 35 39 64 73 83 71 22 10 45  1…
 9     9 " 7 49 62 79 37 91  3 58 74 19" 17  7 58  2 53 95 52 62 83 41 42 36  4…
10    10 "84 33 81 45 99 96 76 97 40  2" 81 26 11 34 83 25 45 76  2 85 33 64 57…
# ℹ 202 more rows

Creating a function that parses the sequences of numbers as numeric vectors:

to_numbers <- function(x) {
  str_extract_all(x, "\\d+") %>%
  map(as.numeric)
}

Function that takes two vectors and calcultes how many elements from the first one are in the second one:

calculate_n_winning <- function(x, y) {
  keep(x, ~magrittr::is_in(., y)) %>%
  length()
}
card_data_processed <-
  card_data_split %>%
  mutate(across(c(my_numbers, winning_numbers), to_numbers)) %>%
  mutate(n_winning = map2_dbl(my_numbers, winning_numbers, calculate_n_winning))

card_data_processed
# A tibble: 212 × 4
      id my_numbers winning_numbers n_winning
   <int> <list>     <list>              <dbl>
 1     1 <dbl [10]> <dbl [25]>             10
 2     2 <dbl [10]> <dbl [25]>              8
 3     3 <dbl [10]> <dbl [25]>             10
 4     4 <dbl [10]> <dbl [25]>              6
 5     5 <dbl [10]> <dbl [25]>              3
 6     6 <dbl [10]> <dbl [25]>              7
 7     7 <dbl [10]> <dbl [25]>             10
 8     8 <dbl [10]> <dbl [25]>              5
 9     9 <dbl [10]> <dbl [25]>              5
10    10 <dbl [10]> <dbl [25]>             10
# ℹ 202 more rows

Now I need a function that doubles its output for each integer greater than 1. Specifically, the function should behave as follows:

  • f(0) = 0
  • f(1) = 1
  • f(2) = 2
  • f(3) = 4
  • f(4) = 8
calculate_points <- function(x) {
  if (x == 0) {
    return(0)
  } else {
    return(2^(x-1))
  }
}

Applying the function to calculate how many points the cards are worth:

card_data_processed %>%
  mutate(points = map_dbl(n_winning, calculate_points)) %>%
  count(wt = points)
# A tibble: 1 × 1
      n
  <dbl>
1 25231

The solution is correct 🥳

Part 2

Here I think I need to use some form of recursion:

“you win copies of the scratchcards below the winning card equal to the number of matches. So, if card 10 were to have 5 matching numbers, you would win one copy each of cards 11, 12, 13, 14, and 15.”

“Copies of scratchcards are scored like normal scratchcards and have the same card number as the card they copied. So, if you win a copy of card 10 and it has 5 matching numbers, it would then win a copy of the same cards that the original card 10 won: cards 11, 12, 13, 14, and 15. This process repeats until none of the copies cause you to win any more cards. (Cards will never make you copy a card past the end of the table.)”

It seems that the only column I need is n_winning, along with a new column to keep track of how many copies of the cards I have. I’ll store the data in a matrix to access and modify it using indices.

card_data_pt2 <-
  card_data_processed %>%
  transmute(
    n_matches = n_winning,
    count = 1
  ) %>%
  as.matrix()

card_data_pt2[1:10]
 [1] 10  8 10  6  3  7 10  5  5 10

Now I need to code a procedure that captures the logic described in the prompt:

n_original_cards <- nrow(card_data_pt2)

for (i in 1:n_original_cards) {
  n_matches_i <- card_data_pt2[i, 1]
  count_i <- card_data_pt2[i, 2]

  if (n_matches_i == 0) next

  # If I have N copies of the current card, I'll win copies of the cards below N times
  for (n in 1:count_i) {
    for (j in 1:n_matches_i) {
      if (i+j <= n_original_cards) {
        # Adding one copy of each of the j cards below
        card_data_pt2[i+j, 2] = card_data_pt2[i+j, 2] + 1
      }
    }
  } 
}

Adding up the scratchcards using the count column:

sum(card_data_pt2[,2])
[1] 9721255