# 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

# 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[]$name]] <- unmatched_tiles[]
unmatched_tiles <- 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[]$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, target_ind])) { # 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, target_ind] <- 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]
)


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
mc <- arr_ind

# 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, x] == '#'))
}

# 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
mc <- arr_ind

# 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!