day20.Rmd

---
title: "--- Day 20: Jurassic Jigsaw ---"
author: Fleur Kelpin
date: Dec 20, 2020
output: github_document
---

```{r message=FALSE, warning=FALSE}
library(tidyverse)
options(digits = 22)
input <- read_file("day20.txt") %>%
  str_split("\\n\\n") %>%
  unlist() %>%
  {
    tibble(line = .)
  } %>%
  extract(line, c("id", "tile", NA), "Tile (\\d+):\\n((.|\\n)*)$", convert = T) %>%
  mutate(num = row_number())
input
```
```{r}
n <- 10
tiles <- array(FALSE, dim = c(n, n, nrow(input)))
for (i in 1:nrow(input)) {
  tiles[, , i] <- input$tile[[i]] %>%
    str_split("\n") %>%
    unlist() %>%
    map(~ str_split(., "")) %>%
    unlist() %>%
    map_lgl(~ . == "#") %>%
    matrix(nrow = n, byrow = T)
}
tiles[, , 1]
```
```{r}
edges <- function(x) {
  c(
    tiles[1, , x],
    tiles[, 1, x],
    tiles[10, , x],
    tiles[, 10, x],
    tiles[1, 10:1, x],
    tiles[10:1, 1, x],
    tiles[10, 10:1, x],
    tiles[10:1, 10, x]
  ) %>%
    matrix(ncol = n, byrow = T)
}
edges(2)
```
```{r}
matches <- function(i, j) {
  matrix(t(c(t(edges(i)), t(edges(j)))), ncol = n, byrow = T) %>%
    duplicated() %>%
    any()
}
num_matches <- function(i) {
  result <- 0
  for (j in 1:nrow(input)) {
    if (j != i && matches(i, j)) {
      result <- result + 1
    }
  }
  result
}
corners <- input %>%
  rowwise() %>%
  filter(num_matches(num) == 2) %>%
  ungroup()

summarise(corners, prod(id))
```
# Part 2
```{r}
neighbors <- matrix(FALSE, nrow = nrow(input), ncol = nrow(input))
for (i in 1:nrow(input)) {
  for (j in 1:nrow(input)) {
    neighbors[i, j] <- i != j & matches(i, j)
  }
}
```
```{r}
input <- input %>%
  rowwise() %>%
  mutate(nb <- list(which(neighbors[num, ])))
input
```
There are a lot of possible ways to lay this puzzle. Once we pick the top left
and the tile to the right of that, we can figure out the layout of the whole
grid
```{r}
m <- sqrt(nrow(input))
puzzle <- matrix(NA_integer_, nrow = m, ncol = m)
puzzle[1, 1] <- corners$num[[1]]
puzzle[1, 2] <- which(neighbors[puzzle[1, 1], ])[[1]]
for (j in 3:m) {
  candidates <- which(neighbors[puzzle[1, j - 1], ])
  edge <- map_lgl(candidates, ~ num_matches(.) < 4 & !. %in% puzzle)
  puzzle[1, j] <- candidates[which(edge)[[1]]]
}
for (i in 2:m) {
  candidates <- which(neighbors[puzzle[i - 1, 1], ])
  edge <- map_lgl(candidates, ~ num_matches(.) < 4 & !. %in% puzzle)
  puzzle[i, 1] <- candidates[which(edge)[[1]]]
  for (j in 2:m) {
    left <- puzzle[i, j - 1]
    top <- puzzle[i - 1, j]
    candidates <- which(neighbors[left, ] & neighbors[top, ])
    puzzle[i, j] <- candidates[!(candidates %in% puzzle)][[1]]
  }
}
puzzle
```
Flip them tiles!
```{r}
flip <- function(tile) {
  n <- dim(tile)[[1]]
  result <- array(dim = c(n, n, 8))
  result[, , 1] <- tile
  result[, , 2] <- t(tile)
  result[, , 3] <- tile[, n:1]
  result[, , 4] <- t(tile[, n:1])
  result[, , 5] <- tile[n:1, ]
  result[, , 6] <- t(tile[n:1, ])
  result[, , 7] <- tile[n:1, n:1]
  result[, , 8] <- t(tile[n:1, n:1])
  result
}
```

```{r}
shared_edges <- function(i, j) {
  e <- matrix(t(c(t(edges(i)), t(edges(j)))), ncol = n, byrow = T)
  e[duplicated(e), ]
}
shared_edges(123, 120)
orientation_rb <- function(i, j) {
  piece <- puzzle[i, j]
  right <- puzzle[i, j + 1]
  bottom <- puzzle[i + 1, j]
  right_edges <- shared_edges(piece, right)
  bottom_edges <- shared_edges(piece, bottom)
  tile <- tiles[, , piece]
  flips <- flip(tile)
  right_edge_flips <- t(flips[, 10, ])
  bottom_edge_flips <- t(flips[10, , ])
  flip_index <- which(map_lgl(1:8, ~
  (all(right_edge_flips[., ] == right_edges[1, ]) |
    all(right_edge_flips[., ] == right_edges[2, ])) &
    (all(bottom_edge_flips[., ] == bottom_edges[1, ]) |
      all(bottom_edge_flips[., ] == bottom_edges[2, ]))))
  flips[, , flip_index]
}
orientation_rb(1, 1)
```
```{r}
orientation_l <- function(i, j, left_edge) {
  piece <- puzzle[i, j]
  left <- puzzle[i, j - 1]
  left_edges <- shared_edges(piece, left)
  tile <- tiles[, , piece]
  flips <- flip(tile)
  left_edge_flips <- t(flips[, 1, ])
  flip_index <- which(map_lgl(1:8, ~ all(left_edge_flips[., ] == left_edge)))
  flips[, , flip_index]
}
orientation_t <- function(i, j, top_edge) {
  piece <- puzzle[i, j]
  top <- puzzle[i - 1, j]
  top_edges <- shared_edges(piece, top)
  tile <- tiles[, , piece]
  flips <- flip(tile)
  top_edge_flips <- t(flips[1, , ])
  flip_index <- which(map_lgl(1:8, ~ all(top_edge_flips[., ] == top_edge)))
  flips[, , flip_index]
}
```
```{r}
map_with_stitches <- matrix(nrow = m * (n - 1) + 1, ncol = m * (n - 1) + 1)
for (i in 1:m) {
  for (j in 1:m) {
    top_left <- c((i - 1) * 9, (j - 1) * 9)
    if (j < m & i < m) {
      tile <- orientation_rb(i, j)
    } else if (j == m & i < m) {
      left_edge <- map_with_stitches[1:10 + top_left[[1]], 1 + top_left[[2]]]
      tile <- orientation_l(i, j, left_edge)
    } else {
      top_edge <- map_with_stitches[1 + top_left[[1]], 1:10 + top_left[[2]]]
      tile <- orientation_t(i, j, top_edge)
    }
    map_with_stitches[1:10 + top_left[[1]], 1:10 + top_left[[2]]] <- tile
  }
}
map <- matrix(nrow = m * (n - 2), ncol = m * (n - 2))
for (i in 1:m) {
  for (j in 1:m) {
    top_left_from <- c((i - 1) * 9, (j - 1) * 9)
    top_left_to <- c((i - 1) * 8, (j - 1) * 8)
    map[
      1:8 + top_left_to[[1]],
      1:8 + top_left_to[[2]]
    ] <-
      map_with_stitches[
        2:9 + top_left_from[[1]],
        2:9 + top_left_from[[2]]
      ]
  }
}
```
Now go hunting for the monsters!
```{r}
monster <- read_lines("day20-monster.txt") %>%
  map(~ str_split(., "")) %>%
  unlist() %>%
  map_lgl(~ . == "#") %>%
  matrix(nrow = 3, byrow = T)
```

```{r}
remove_monster <- function(i, j, map) {
  if (all((map[
    i + 1:nrow(monster) - 1,
    j + 1:ncol(monster) - 1
  ] & monster) == monster)) {
    map[i + 1:nrow(monster) - 1, j + 1:ncol(monster) - 1] <-
      map[i + 1:nrow(monster) - 1, j + 1:ncol(monster) - 1] & !monster
    TRUE
  } else {
    FALSE
  }
}
```
```{r}
flipped_maps <- flip(map)
for (k in 1:8) {
  found_monsters <- FALSE
  for (i in 1:(dim(flipped_maps)[[1]] - dim(monster)[[1]])) {
    for (j in 1:(dim(flipped_maps)[[2]] - dim(monster)[[2]])) {
      if (all((flipped_maps[
        i + 1:nrow(monster) - 1,
        j + 1:ncol(monster) - 1,
        k
      ] & monster) == monster)) {
        flipped_maps[i + 1:nrow(monster) - 1, j + 1:ncol(monster) - 1, k] <-
          flipped_maps[i + 1:nrow(monster) - 1, j + 1:ncol(monster) - 1, k] & !monster
        found_monsters <- TRUE
      }
    }
  }
  if (found_monsters) {
    print(k)
    print(sum(flipped_maps[, , k]))
  }
}
```