Day 4: Giant Squid

Click for Problem Statement

Back to 2021

library(tidyverse)
library(here)
path_data <- here("2021/inputs/04-input.txt")
input <- tibble(x = read_lines(path_data))

In this one we’re playing bingo with a giant squid, and we’re going to do it with dataframes! Let’s go…

Part 1

We need to essentially play bingo, find the first board that wins, and then do some fancy calculations on the winning board. So, we need to first get the boards organized. This turns out to be the toughest part.

Unpacking the Input

The input provides us with both the list of numbers drawn and the bingo boards, so we need to separate those.

First the numbers to draw: we can take the first row of input and split it up and convert into numbers. There: a nice vector of drawn numbers.

# get vector of the drawing numbers
draw_numbers <- input[[1, "x"]] %>% str_split(pattern = ",")
draw_numbers <- as.numeric(draw_numbers[[1]])

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

Now we can tackle the boards. We will:

  • Get the boards from the input, removing the empty strings
  • Since all boards are the same size, we can make a column to count the boards and then make each row one board
  • Let’s also clean up the strings, making every number two characters
# let's convert the boards into vectors and define tests for each type

# just the board input section, no delimiters
raw <- 
  input %>% 
  slice(3:nrow(.)) %>% 
  filter(x != "")

# df of raw board strings
raw_boards <- raw %>%   
  # count boards
  mutate(board = (row_number() - 1) %/% 5) %>% 
  # for each board
  group_by(board) %>% 
  # make each number two chars
  mutate(board_string = paste(x, collapse = " ")) %>% 
  mutate(board_string = str_replace_all(board_string, "  ", " 0"),
         board_string = str_replace_all(board_string, "^ ([0-9])", "\\1")) %>% 
  # unique board strings
  select(-x) %>% 
  distinct()

raw_boards
## # A tibble: 100 × 2
## # Groups:   board [100]
##    board board_string                                                              
##    <dbl> <chr>                                                                     
##  1     0 31 93 46 11 30 02 45 40 69 33 82 21 37 99 86 57 16 34 94 85 60 49 28 14 65
##  2     1 96 02 20 41 24 29 15 27 83 48 07 93 99 82 26 03 91 66 35 85 62 78 67 04 22
##  3     2 10 87 50 84 40 78 05 17 59 44 38 88 15 46 32 08 72 74 90 23 64 93 49 39 20
##  4     3 25 41 32 30 39 06 66 38 95 05 31 13 56 67 34 69 18 64 44 96 75 14 88 97 40
##  5     4 39 62 50 10 68 18 07 95 72 82 83 23 19 70 71 11 64 30 08 03 06 81 27 34 99
##  6     5 40 52 66 20 49 93 74 16 35 29 97 88 06 98 81 62 55 99 47 12 83 76 57 75 22
##  7     6 52 76 43 86 99 58 26 61 36 42 11 69 65 03 49 33 07 71 08 25 50 82 32 16 64
##  8     7 45 38 88 96 08 22 17 05 60 66 87 12 61 59 02 00 37 18 15 98 07 62 23 56 92
##  9     8 20 07 12 26 69 81 63 89 57 19 18 44 61 64 53 47 27 08 30 00 60 99 28 06 96
## 10     9 70 50 63 56 26 55 97 65 05 96 72 68 29 91 61 34 00 14 28 04 45 53 78 80 47
## # … with 90 more rows

Now we can convert these strings into a dataframe of boards. We want a tidy representation of them, meaning:

  • board
  • place_on_board
  • number_at_that_place

We can get there from our raw strings:

  • Separate each board string into twenty-five columns, split by spaces
  • Pivot the result to get long version like we want
  • Do some fiddling: convert to numbers and zero-index the place values
# df of all boards
boards <- raw_boards %>% 
  # split up the board strings
  separate(board_string, sep = " ", into = as.character(seq(1, 25))) %>% 
  # pivot, baby!
  pivot_longer(cols = -board, names_to = "place", values_to = "num") %>% 
  # tough to parse with all the parens, but a lovely trick!
  mutate(across(where(is.character), as.numeric)) %>% 
  # zero index number places
  mutate(place = place - 1) 

boards
## # A tibble: 2,500 × 3
## # Groups:   board [100]
##    board place   num
##    <dbl> <dbl> <dbl>
##  1     0     0    31
##  2     0     1    93
##  3     0     2    46
##  4     0     3    11
##  5     0     4    30
##  6     0     5     2
##  7     0     6    45
##  8     0     7    40
##  9     0     8    69
## 10     0     9    33
## # … with 2,490 more rows

We now have a dataframe of all boards, with every number and where they go. Sweeeeet. Let’s play bingo!

Hang on…

Getting the Game Ready

Here’s what our board layout looks like:

# what a board looks like, numbers are places
test_board <- matrix(0:24, nrow = 5, byrow = TRUE)
test_board
##      [,1] [,2] [,3] [,4] [,5]
## [1,]    0    1    2    3    4
## [2,]    5    6    7    8    9
## [3,]   10   11   12   13   14
## [4,]   15   16   17   18   19
## [5,]   20   21   22   23   24

To check for a bingo, we need to track whether a number is marked and whether someone has won. First, we should add to our boards dataframe to specify which row and column each number is a part of. Which means…math shows up!

From the test board above, we can use the place values to define what each row and column are:

  • Each row is the numbers one to twenty-five, chunked by fives. So we can do a floor division to get that.
  • Each column is some starting value, then increase by steps of five. We can use modulo to get this.

And we will set all of the boards to have no marks. Our bingo game is now setup.

# setup bingo df
bingo <- boards %>% 
  mutate(row = place %/% 5,
         col = place %% 5,
         marked = FALSE)

bingo
## # A tibble: 2,500 × 6
## # Groups:   board [100]
##    board place   num   row   col marked
##    <dbl> <dbl> <dbl> <dbl> <dbl> <lgl> 
##  1     0     0    31     0     0 FALSE 
##  2     0     1    93     0     1 FALSE 
##  3     0     2    46     0     2 FALSE 
##  4     0     3    11     0     3 FALSE 
##  5     0     4    30     0     4 FALSE 
##  6     0     5     2     1     0 FALSE 
##  7     0     6    45     1     1 FALSE 
##  8     0     7    40     1     2 FALSE 
##  9     0     8    69     1     3 FALSE 
## 10     0     9    33     1     4 FALSE 
## # … with 2,490 more rows

Playing Bingo

Now we need to take our bingo setup and play! But we will need a way to check if anyone has won. To do this, we can group by each board and count the number of marked values on each board, for all rows and all columns. If any total ever hits five, we know someone has won.

get_totals <- function(df) {
  # total for the rows
  rows <- df %>% 
    group_by(board, row) %>% 
    summarise(total = sum(marked)) %>% 
    ungroup() %>% 
    select(-row) %>% 
    mutate(type = "row")

  # total for the columns
  cols <- df %>% 
    group_by(board, col) %>% 
    summarise(total = sum(marked)) %>% 
    ungroup() %>% 
    select(-col) %>% 
    mutate(type = "col")

  # combine
  totals <- bind_rows(rows, cols) %>% 
    select(board, type, total)
  
  return(totals)
}

To play the game, we can loop through a selection of numbers (our “basket” of numbers), updating our bingo dataframe each time. Once all numbers are drawn, we can find use the results to find the totals and see the status of the game.

play_bingo <- function(number_basket) {
  # start fresh
  curr_bingo <- bingo
  
  # if you have the number, mark it, otherwise leave it
  for (draw_num in number_basket) {
    curr_bingo <- curr_bingo %>% 
      mutate(marked = ifelse(num == draw_num, TRUE, marked))
  }
  
  return(curr_bingo)
}

Phew, okay. Let’s finally play some bingo!

Part 1 (no really)

Find First Winner

We will keep playing bingo with more and more numbers till someone wins (we see a five in our totals)

# an example of playing bingo, no one has won yet (no 5s under total)
play_bingo(draw_numbers[1:12]) %>% 
  get_totals() %>% 
  arrange(desc(total))
## # A tibble: 1,000 × 3
##    board type  total
##    <dbl> <chr> <int>
##  1    59 row       4
##  2    69 row       4
##  3    16 row       3
##  4    21 row       3
##  5    35 row       3
##  6    42 row       3
##  7    64 row       3
##  8    36 col       3
##  9    68 col       3
## 10    82 col       3
## # … with 990 more rows

But as soon we draw the 23rd number…BINGO!

# congrats, you won!
play_bingo(draw_numbers[1:23]) %>% 
  get_totals() %>% 
  arrange(desc(total)) %>% 
  head(3)
## # A tibble: 3 × 3
##   board type  total
##   <dbl> <chr> <int>
## 1    79 col       5
## 2    27 row       4
## 3    35 row       4

And it’s board 79! Let’s tally their score!

Get the Score

Let’s get the results of board 79 after they have won:

# winning board is 79
winning_board_1 <- play_bingo(draw_numbers[1:23]) %>% 
  filter(board == 79)

To get the score, we:

  • Sum all of the unmarked numbers (marked == FALSE)
  • Multiply the result by the number that was just called (the 23rd number)
# calculating score

# sum of all unmarked numbers
winning_unmarked_sum_1 <- winning_board_1 %>% 
  filter(!marked) %>% 
  summarise(total = sum(num)) %>% 
  pull(total)
# number that was just called
just_called_1 <- draw_numbers[23]

# final score
winning_unmarked_sum_1 * just_called_1
## [1] 29440

Well played! But what if we play the long game?

Part 2

Now we want to know the board that is the last to win. Same idea, but we will add a filter to just look for the boards that haven’t won yet. As soon as we are left with just one board (in this case, ten rows of totals), we have the last player.

# an example of playing bingo, checking for players still in the game
# Notice the dimensions: we will fiddle till we only have ten rows (one board)
play_bingo(draw_numbers[1:60]) %>% 
  get_totals() %>% 
  arrange(desc(total)) %>% 
  group_by(board) %>% 
  filter(all(total < 5))
## # A tibble: 540 × 3
## # Groups:   board [54]
##    board type  total
##    <dbl> <chr> <int>
##  1     2 row       4
##  2     2 row       4
##  3     4 row       4
##  4     6 row       4
##  5     6 row       4
##  6     7 row       4
##  7     8 row       4
##  8     9 row       4
##  9    10 row       4
## 10    11 row       4
## # … with 530 more rows

And after the 83rd number is drawn, there is only one player remaining:

# earliest number drawn to return only one board
play_bingo(draw_numbers[1:83]) %>% 
  get_totals() %>% 
  arrange(desc(total)) %>% 
  group_by(board) %>% 
  filter(all(total < 5))
## # A tibble: 10 × 3
## # Groups:   board [1]
##    board type  total
##    <dbl> <chr> <int>
##  1    32 row       4
##  2    32 row       4
##  3    32 row       4
##  4    32 col       4
##  5    32 col       4
##  6    32 col       4
##  7    32 row       3
##  8    32 row       3
##  9    32 col       3
## 10    32 col       3

So board 32 is the last one still in the game. Let’s let them win already! With the 84th number they are still playing, but once we draw the 85th number, they finally get a bingo. So now we take their winning board:

# get 32's winning board
winning_board_2 <- play_bingo(draw_numbers[1:85]) %>% 
  filter(board == 32)
winning_board_2
## # A tibble: 25 × 6
## # Groups:   board [1]
##    board place   num   row   col marked
##    <dbl> <dbl> <dbl> <dbl> <dbl> <lgl> 
##  1    32     0    52     0     0 TRUE  
##  2    32     1    35     0     1 TRUE  
##  3    32     2    43     0     2 TRUE  
##  4    32     3    77     0     3 TRUE  
##  5    32     4    79     0     4 TRUE  
##  6    32     5    53     1     0 FALSE 
##  7    32     6    56     1     1 TRUE  
##  8    32     7    93     1     2 TRUE  
##  9    32     8    92     1     3 TRUE  
## 10    32     9    12     1     4 TRUE  
## # … with 15 more rows

And figure out their score:

# calculate score

# sum of all unmarked numbers
winning_unmarked_sum_2 <- winning_board_2 %>% 
  filter(!marked) %>% 
  summarise(total = sum(num)) %>% 
  pull(total)
# number that was just called
just_called_2 <- draw_numbers[85]

# final score
winning_unmarked_sum_2 * just_called_2
## [1] 13884

And there we go! We have played bingo with a giant squid!

🦑

All Done!

Phew! That was a lot. Hope you learned something!

How would you do it? What’s your shortcut? Please share!

Till next time!