day18.Rmd

---
title: "--- Day 18: Operation Order ---"
author: Fleur Kelpin
date: Dec 18, 2020
output: github_document
---

```{r message=FALSE, warning=FALSE}
library(tidyverse)
library(Ramble)
input <- readLines("day18.txt") %>%
  map_chr(~ str_remove_all(., "\\s"))
tibble(input)
```
# Part 1

Evaluate the expression on each line of the homework; what is the sum of the
resulting values?

Writing a grammar for this is trickier than I thought, because associativity
matters and it's easy to get circular references and infinite recursion.
```
expr: block (plusOrTimes block)*
block: number | '(' expr ')'
```
Then when resolving the expressions, we'll get a list of integers and operators.
```{r}
resolve <- function(x) {
  result <- as.numeric(x[[1]])
  if (length(x) <= 2) {
    return(result)
  }
  for (i in seq(from = 2, to = length(x), by = 2)) {
    result <- switch(x[[i]],
      "+" = result + as.numeric(x[[i + 1]]),
      "*" = result * as.numeric(x[[i + 1]])
    )
  }
  result
}
resolve(c("2", "+", "4", "*", "4"))
```
Now we can use this resolve function in a parser combinator:
```{r}
library(Ramble)

pPlusOrTimes <- symbol("+") %alt% symbol("*")
pExpr <- (pBlock %then% many(pPlusOrTimes %then% pBlock)) %using%
  function(x) {
    resolve(unlist(c(x)))
  }
pBlock <- (natural() %using% function(x) {
  as.numeric(unlist(c(x)))
}) %alt%
  ((symbol("(") %then%
    pExpr %then%
    symbol(")")) %using% function(x) {
    unlist(c(x))[[2]]
  })

pExpr("1+(2+4*4)")
```
And finally compute the answer
```{r}
input %>%
  map_dbl(~ pExpr(.)$result) %>%
  sum() %>%
  format(scientific = F)
```

# Part 2

Now, addition and multiplication have different precedence levels, but they're
not the ones you're familiar with. Instead, addition is evaluated before
multiplication.

That should actually be easier cause associativity no longer matters and we can
evaluate everything eagerly.

```
expr :: = factor * expr | factor
factor :: = term + expr | term
term :: = (expr) | digit+
```

```{r}
pExpr <- ((pFactor %then%
  symbol("*") %then%
  pExpr %using% function(x) {
    prod(as.numeric(unlist(c(x))[c(1, 3)]))
  }) %alt% pFactor)
pFactor <- ((pTerm %then%
  symbol("+") %then%
  pFactor %using% function(x) {
    sum(as.numeric(unlist(c(x))[c(1, 3)]))
  }) %alt% pTerm)
pTerm <- ((symbol("(") %then%
  pExpr %then%
  symbol(")") %using% function(x) {
    return(as.numeric(unlist(c(x))[2]))
  }) %alt% natural())
pExpr("4*4*(8+4*2*3+(6+6*7+6)+(7+4*9*7+2))")
```
And the answer
```{r}
input %>%
  map_dbl(~ pExpr(.)$result) %>%
  sum() %>%
  format(scientific = F)
```