Advent of Code 2020 - Day 20

By Eric Burden | December 21, 2020

In the spirit of the holidays (and programming), I’ll be posting my solutions to the Advent of Code 2020 puzzles here, at least one day after they’re posted (no spoilers!). I’ll be implementing the solutions in R because, well, that’s what I like! What I won’t be doing is posting any of the actual answers, just the reasoning behind them.

Also, as a general convention, whenever the puzzle has downloadable input, I’m saving it in a file named input.txt.

Day 20 - Jurassic Jigsaw

Find the problem description HERE.

Part One - Try Increasing the Resolution

The challenge here is to flip and rotate square images manipulate matrices until you identify a configuration where each smaller image matrix matches edges with the images matrices next to it to form a larger image square matrix. Probably the best thing we did here was in the rotate() and flip() functions, and in using R with it’s first-class support for matrices. We’ve also successfully managed to avoid relying on the stringr package for text manipulation functions, too, which is kind of freeing. Don’t be thrown off, I refer to each individual input square/matrix as a ‘tile’ in the code comments and code. It made sense at the time.

# Input ------------------------------------------------------------------------

test_input <- readLines('test_input.txt')  # Definitely not re-typing all that
real_input <- readLines('input.txt')


# Functions --------------------------------------------------------------------

# Helper function, parses the input lines into a list of 'tiles', lists 
# containing a name and a matrix of characters representing image contents
input_to_tiles <- function(input) {
  current_tile <- 0  # Index of the tile to add lines to
  tiles <- list()    # Empty list for tiles
  
  # For each line in the input file...
  for (line in input) {
    if (line =='') { next }  # Skip blank lines
    
    # If the line contains a tile title, add an empty character vector
    # to `tiles` named according to the tile id
    if (grepl('Tile \\d+:', line)) {
      current_tile <- current_tile + 1
      current_tile_name <- regmatches(line, regexpr('\\d+', line))
      tiles[[current_tile_name]]$name <- current_tile_name
      tiles[[current_tile_name]]$tile <- character(0)
      next
    }
    
    # For all other lines, split the line into characters and add it to
    # the `tiles` list to the tile currently being added to
    tiles[[current_tile_name]]$tile <- c(
      tiles[[current_tile_name]]$tile, 
      strsplit(line, '')
    )
  }
  
  # Convert each element in the tiles list to a matrix
  for (tile_name in names(tiles)) {
    tiles[[tile_name]]$tile <- do.call(rbind, tiles[[tile_name]]$tile )
  }
  tiles
}

# Helper function, rotates a matrix 90' clockwise
rotate <- function(tile_tile) {
  t(apply(tile_tile, 2, rev))
}

# Helper function, flips a matrix vertically
flip <- function(tile_tile) {
  apply(tile_tile, 2, rev)
}

# Helper function, given a string indicating a side of a tile matrix `side` and
# the tile matrix, returns the characters that make up that side of the tile
# matrix
get_side <- function(side, tile) {
  if (side == 'top') { 
    tile$tile[1,] 
  } else if (side == 'right') { 
    tile$tile[, ncol(tile$tile)] 
  } else if (side == 'bottom') { 
    tile$tile[nrow(tile$tile),] 
  } else if (side == 'left') { 
    tile$tile[,1] 
  } else {
    stop(paste(side, 'is not a valid argument for `side`'))
  }
}

# Helper function, given a pattern from the side of a tile matrix `pattern`, a
# string indicating which side it came from `side`, and a tile to test that
# pattern against `test_tile`, flip and rotate the `test_tile` into the 
# orientation that matches the pattern for the given side. Return the 
# `test_tile` in the identified orientation if it can be achieved. Otherwise, 
# return NULL. Note, `side` here references the base tile being matched against, 
# not the `test_tile`. A 'right' `side` will match the `test_tile`'s left-hand 
# side, for example.
check_tile_match <- function(pattern, side, test_tile) {
  
  # For each possible permutation of `test_tile`...
  for (i in 1:8) {
    
    # Get the side pattern from the appropriate side of the `test_tile` to 
    # compare to `pattern`
    test_pattern <- if (side == 'top') { 
      get_side('bottom', test_tile) 
    } else if (side == 'right') { 
      get_side('left', test_tile) 
    } else if (side == 'bottom') { 
      get_side('top', test_tile)
    } else if (side == 'left') { 
      get_side('right', test_tile) 
    } else {
      stop(paste(side, 'is not a valid argument for `side`'))
    }
    
    # If they match, return the test tile. Otherwise, flip/rotate the 
    # `test_tile` and try again. Flip on the 5th try, rotate on all others
    if (identical(pattern, test_pattern)) { return(test_tile) }
    test_tile$tile <- if (i == 5) { flip(test_tile$tile) } else { rotate(test_tile$tile) }
  }
}

# Helper function, given a tile `base_tile`, a string indicating which side of
# the base tile to match on `side`, and a set of tiles to search for a match
# `tiles`, flip and rotate the tiles in `tiles` to find the one that matches
# side `side` of `base_tile`. If one is found, return it in the matching
# orientation, otherwise return NULL
match_side <- function(base_tile, side, tiles) {
  side_pattern <- get_side(side, base_tile)
  for (test_tile in tiles) {
    test_result <- check_tile_match(side_pattern, side, test_tile)
    if (!is.null(test_result)) { return(test_result) }
  }
}


# Processing ------------------------------------------------------------------

unmatched_tiles <- input_to_tiles(real_input)  # All tiles, to start
tile_count <- length(unmatched_tiles)          # How many tiles?
matched_tiles <- list()                        # Move tiles here once matched

# Move the first tile in `unmatched_tiles` to the `matched_tiles` list
matched_tiles[[unmatched_tiles[[1]]$name]] <- unmatched_tiles[[1]]
unmatched_tiles[1] <- NULL

# The matrix used for arranging the tiles must be large enough that any square
# containing `tile_count` elements starting from the center index cannot exceed
# the bounds of the matrix.
map_dim <- (sqrt(tile_count) * 2) + 1          
tile_arrangement <- matrix(NA, ncol = map_dim, nrow = map_dim)

# Put the one tile in `matched_tiles` into the center of the `tile_arrangement`
# matrix. We will add the other tiles to it, sort of like domino's.
tile_arrangement[((map_dim %/% 2)+1), ((map_dim %/% 2)+1)] <- matched_tiles[[1]]$name

# Single number indices for the `tile_arrangement` matrix
arrangement_indices <- slice.index(tile_arrangement, c(1, 2))


# Until all the tiles have been moved from `unmatched_tiles` to `matched_tiles`...
checked_indices <- numeric(0)
while (length(unmatched_tiles) > 0) {
  
  # Get the indices for all the tiles that have been added to `tile_arrangement`,
  # except for the ones that have been matched against already. Each iteration,
  # this will yield the newly matched tile indices
  occupied_indices <- arrangement_indices[!is.na(tile_arrangement)]
  indices_to_check <- setdiff(occupied_indices, checked_indices)
  
  # For each newly added tile...
  for (i in indices_to_check) {
    
    # Get the array index from the single number index
    arr_ind <- which(arrangement_indices == i, arr.ind = T)
    current_tile <- matched_tiles[[tile_arrangement[i]]]  # Tile to match against
    
    # For each side of the tile to match against...
    for (side in c('top', 'right', 'bottom', 'left')) {
      
      # Calculate the index for the space to the top, right, bottom, or left
      # of the tile being matched against
      target_ind <- if (side == 'top') { 
        arr_ind + c(-1, 0) 
      } else if (side == 'right') { 
        arr_ind + c(0, 1) 
      } else if (side == 'bottom') { 
        arr_ind + c(1, 0) 
      } else if (side == 'left') { 
        arr_ind + c(0, -1) 
      }
      
      # If there's not already a tile in that space...
      if (is.na(tile_arrangement[target_ind[1], target_ind[2]])) {
        
        # Check if there is an unmatched tile that could fit in that space. If
        # so, move that tile from `unmatched_tiles` to `matched_tiles`, and add
        # its name to `tile_arrangement` in the appropriate position
        matching_tile <- match_side(current_tile, side, unmatched_tiles)
        if (!is.null(matching_tile)) {
          unmatched_tiles[[matching_tile$name]] <- NULL
          matched_tiles[[matching_tile$name]] <- matching_tile
          tile_arrangement[target_ind[1], target_ind[2]] <- matching_tile$name
        }
      }
    }
    
    # Keep up with checked indices to avoid trying to match against the same
    # tile again
    checked_indices <- c(checked_indices, i) 
  }
}

# Get the spaces in `tile_arrangement` that have tile names in them, 'crop' 
# `tile_arrangement` to just those indices, get the tile name (id) from each
# corner, and multiply them together.
occupied_indices <- arrangement_indices[!is.na(tile_arrangement)]
tiles_dim <- sqrt(tile_count)
cropped_arrangement <- matrix(tile_arrangement[occupied_indices], nrow = tiles_dim)
corners <- c(
  cropped_arrangement[1, 1], 
  cropped_arrangement[1, tiles_dim], 
  cropped_arrangement[tiles_dim, 1], 
  cropped_arrangement[tiles_dim, tiles_dim]
)
answer1 <- prod(as.numeric(corners))

Note that the tile_arrangement matrix needed to be big enough to accommodate the case where the starting tile (placed at the center) were a corner tile.

Part Two - Somehwere There Be Monsters

Turns out, if we remove the inner ‘borders’ from each ‘tile’, there really is an image there! Neat. We just need to flip/rotate some more until we can identify a ‘sea monster’ pattern, count the number of ‘sea monster’s we can find, then subtract out their #’s from the overall result.

# Setup ------------------------------------------------------------------------

source('exercise_1.R')


# Functions --------------------------------------------------------------------

# Helper function, given a single number index to a matrix `i` and the 
# matrix `full_image`, checks that index to determine if it is attached
# to a sea monster, returns TRUE if so
is_sea_monster <- function(i, full_image) {
  
  # Convert single numeric index ('1') to array index ([1, 1])
  arr_ind <- which(slice.index(full_image, c(1, 2)) == i, arr.ind = T)
  mr <- arr_ind[1]
  mc <- arr_ind[2]
  
  # Starting with the tip of the sea monster's tail [mr, mc], a mapping
  # of the indices that need to contain a '#' in order to signify a
  # sea monster
  monster_indices <- list(
    c(mr, mc),     c(mr+1, mc+1),  c(mr+1, mc+4),  c(mr, mc+5),
    c(mr, mc+6),   c(mr+1, mc+7),  c(mr+1, mc+10), c(mr, mc+11),
    c(mr, mc+12),  c(mr+1, mc+13), c(mr+1, mc+16), c(mr, mc+17),
    c(mr-1, mc+18), c(mr, mc+18),  c(mr, mc+19)
  )
  
  # Do all the `monster_indices` contain a '#'?
  all(sapply(monster_indices, function(x) full_image[x[1], x[2]] == '#'))
}

# Processing -------------------------------------------------------------------


# The full image size will be the length/width of the `tile_arrangement` times
# 8, since each image square tile is an 8x8 matrix once the outer layer is 
# removed
img_dim <- sqrt(length(matched_tiles)) * 8
full_image <- matrix(NA_character_, nrow = img_dim, ncol = img_dim)

# `spacing` provides a list to pull the top left indices of each image tile
# in the full image. The first tile will have a top left corner at [1, 1]. 
# Moving across it's [1, 9], [1, 17], etc.
spacing <- seq(1, img_dim, 8)

# Fill in the empty `full_image` matrix with the characters from each tile. Use
# the `tile_arrangement` matrix to identify where in the `full_image` to place
# each tile's characters
for (i in slice.index(cropped_arrangement, c(1, 2))) {
  
  # Convert single numeric index ('1') to array index ([1, 1])
  arr_ind <- which(cropped_arrangement == cropped_arrangement[i], arr.ind = T)
  mr <- arr_ind[1]
  mc <- arr_ind[2]
  
  # Get the tile contents to add to the `full_image`, minus the outer layer
  tile_name <- cropped_arrangement[i]
  tile <- matched_tiles[[tile_name]]
  tile_contents <- tile$tile[2:9,2:9]
  
  # Add tile contents to the appropriate section of `full_image`
  img_row_range <- spacing[mr]:(spacing[mr]+7)
  img_col_range <- spacing[mc]:(spacing[mc]+7)
  full_image[(img_row_range),(img_col_range)] <- tile_contents
}

# Flip and rotate the image until a sea monster appears. The 
# `monster_check_range` is a subset of the `full_image`, accounting for the
# valid spaces where the tip of a sea monster's tail could be and preventing
# 'index out of bounds' errors.
monster_check_range <- slice.index(full_image, c(1, 2))[2:(img_dim-1), 1:(img_dim-19)]

# For each permutation of `full_image`...
for (t in 1:8) {
  found_it <- FALSE
  
  # Check each index in `monster_check_range` for a sea monster. If found,
  # break out of both 'for' loops, leaving the `full_image` in the state where
  # a sea monster was found.
  for (i in monster_check_range) {
    if (is_sea_monster(i, full_image)) { found_it <- TRUE; break }
  }
  if (found_it) { break }
  full_image <- if (t == 5) { flip(full_image) } else { rotate(full_image) }
}

# Now that we know `full_image` is in the proper orientation, count the sea
# monsters
sea_monsters <- 0
for (i in monster_check_range) {
  if (is_sea_monster(i, full_image)) { sea_monsters <- sea_monsters + 1 }
}

# Each sea monster contains 15 hashes, so the number of non-sea-monster hashes
# must be the total number of hashes minus the number of hashes in sea monsters
hash_count <- sum(full_image == '#')
answer2 <- hash_count - (sea_monsters * 15)

The annoying bit was screenshotting the ‘sea monster’ example then counting up the offsets from the tail for each #, getting the count off by one somewhere, then going back to fix it.

Wrap-Up

These puzzles have been on a roll, especially the last few days. I’ve needed to write a fair bit of code for them (especially once I get my comments in there), but they’ve all been fairly methodical implementations of the described problem space with a rewarding finish. I take back all my ‘chinese remainder theorem’-inspired grumbling.

If you found a different solution (or spotted a mistake in one of mine), please drop me a line!

comments powered by Disqus