This topic is about Day 18 of the Advent of Code 2020 .
Thanks to @egze, we have a private leaderboard:
https://adventofcode.com/2020/leaderboard/private/view/39276
The join code is:
39276-eeb74f9a
Right out of the gate, I wanted to build something like an AST. Problem is, I’ve never done that before, so it took me about 1.5 hours. Little bit messy, but I don’t want to spend any more time on this today.
1 Like
I spent most of the time in part 1 trying to get the recursive descent parser to make the evaluating order left-to-right. When I solved that part 2 was easy.
Here is my solution.
3 Likes
Hacked with elixir quoted expression, this can be called cheating I guess 
Since the input is a valid elixir expression, getting AST is just treating input as elixir code, we dont even have to care about the brackets.
defmodule Advent2020.Day18 do
def input do
File.read!(Path.expand("day18.txt", :code.priv_dir(:advent_2020)))
|> String.split("\n", trim: true)
end
defp replace(str, []), do: str
defp replace(str, [{match, replacement} | rest]),
do: String.replace(str, match, replacement) |> replace(rest)
def parse_with_replcement(line, replace) do
{:ok, quoted} = replace(line, replace) |> Code.string_to_quoted()
quoted
end
defp replace_operation(num, _replacement) when is_integer(num), do: num
defp replace_operation({operator, metadata, [a, b]}, replace) do
{replace[operator] || operator, metadata,
[replace_operation(a, replace), replace_operation(b, replace)]}
end
def run(replace) do
revert = Enum.map(replace, fn {m, r} -> {String.to_atom(r), String.to_atom(m)} end)
Enum.map(input(), fn line ->
{result, []} =
parse_with_replcement(line, replace)
|> replace_operation(revert)
|> Code.eval_quoted()
result
end)
|> Enum.sum()
end
def part_one, do: run([{"*", "-"}])
def part_two, do: run([{"*", "-"}, {"+", "/"}])
end
4 Likes
Well, if it gets the job done… Nice trick! 
2 Likes
defmodule D18 do
def parse(text) do
text
|> String.split("\n", trim: true)
|> Enum.map(fn line ->
line
|> String.replace("(", " ( ")
|> String.replace(")", " ) ")
|> String.split(" ", trim: true)
|> parse_line([])
end)
end
defp parse_line([], acc) do
Enum.reverse(acc)
end
defp parse_line(["(" | rest], acc) do
{block, rest} = parse_line(rest, [])
parse_line(rest, [block | acc])
end
defp parse_line([")" | rest], acc) do
{Enum.reverse(acc), rest}
end
defp parse_line([other | rest], acc) do
parse_line(rest, [
case Integer.parse(other) do
:error -> other
{int, ""} -> int
end
| acc
])
end
def p1([a, "+", b | rest]) do
p1([p1(a) + p1(b) | rest])
end
def p1([a, "*", b | rest]) do
p1([p1(a) * p1(b) | rest])
end
def p1(x) when is_integer(x) do
x
end
def p1([x]) when is_integer(x) do
x
end
def p2([a, "+", b | rest]) do
p2([p2(a) + p2(b) | rest])
end
def p2([a, "*", b | rest]) do
p2(a) * p2([p2(b) | rest])
end
def p2(x) when is_integer(x) do
x
end
def p2([x]) when is_integer(x) do
x
end
end
INPUT |> D18.parse() |> Enum.map(&D18.p1/1) |> Enum.sum() |> IO.inspect()
INPUT |> D18.parse() |> Enum.map(&D18.p2/1) |> Enum.sum() |> IO.inspect()
2 Likes
defmodule Day18 do
def readinput() do
# |> split()
File.read!("18.input.txt")
|> String.split("\n", trim: true)
|> Enum.map(&split/1)
end
def split(s) do
s
|> String.replace("(", "( ")
|> String.replace(")", " )")
|> String.split()
end
def part1(input \\ readinput()) do
Enum.reduce(input, 0, fn line, acc -> acc + parse(line, &eval1/2) end)
end
def part2(input \\ readinput()) do
Enum.reduce(input, 0, fn line, acc -> acc + parse(line, &eval2/2) end)
end
######## parse
def parse(input, evalfn, result \\ [])
def parse([], evalfn, result), do: evalfn.(Enum.reverse(result), nil)
def parse(["+" | rest], evalfn, result), do: parse(rest, evalfn, [:add | result])
def parse(["*" | rest], evalfn, result), do: parse(rest, evalfn, [:mult | result])
def parse(["(" | rest], evalfn, result) do
{unprocessed, inner} = parse(rest, evalfn)
parse(unprocessed, evalfn, [inner | result])
end
def parse([")" | rest], evalfn, result) do
{rest, evalfn.(Enum.reverse(result), nil)}
end
def parse([term | rest], evalfn, result),
do: parse(rest, evalfn, [String.to_integer(term) | result])
######## eval for part 1
def eval1(terms, op, out \\ 0)
def eval1([], _, out), do: out
def eval1([number | rest], :add, out), do: eval1(rest, nil, number + out)
def eval1([number | rest], :mult, out), do: eval1(rest, nil, number * out)
def eval1([term | rest], nil, out) do
case term do
:add -> eval1(rest, :add, out)
:mult -> eval1(rest, :mult, out)
_ -> eval1(rest, nil, term)
end
end
######## eval for part 2
def eval2(terms, op, out \\ [])
def eval2([], _, out), do: mult(out)
def eval2([term | rest], :add, [first | left]) do
eval2(rest, nil, [mult(first) + mult(term) | left])
end
def eval2([term | rest], nil, left) do
case term do
:add -> eval2(rest, :add, left)
_ -> eval2(rest, nil, [term | left])
end
end
def mult(thing) when is_number(thing), do: thing
def mult(thing) when is_list(thing) do
Enum.reject(thing, &(&1 == :mult))
|> Enum.reduce(1, &Kernel.*/2)
end
end
What a fun day, first I tried overloading operator in Ruby, something like :
class Integer
def -(b)
self * b
end
end
puts 2 + 1 - 2
6
Since it seems to do the trick I start exploring Elixir’s AST (quite new for me) and after die and retry (thanks to the helpful error messages when a function parameter does not match a pattern), I find my way out !
The key thing is to replace the input to match operator precedence, let Elixir do the parsing and work the AST to put back the original operator is needed.
1 Like
First I tried to see if there was a way to change operator precedence, but, finding nothing, I just redefined some operators with the same precedence in part 1, and with precedence lower than +/- for part 2. Then I just replace the operators in the input string and pass everything through eval. (I’ve also redefined / and - because I didn’t realize they weren’t in the input).
defmodule AdventOfCode.Day18 do
def part1(input) do
input
|> change_operators()
|> String.split("\n", trim: true)
|> Enum.map(fn expr ->
{res, _} = expr |> Code.string_to_quoted!() |> in_module(SimpleOperators) |> Code.eval_quoted()
res
end)
|> Enum.sum()
end
def part2(input) do
input
|> change_operators_2()
|> String.split("\n", trim: true)
|> Enum.map(fn expr ->
{res, _} = expr |> Code.string_to_quoted!() |> in_module(AdvancedOperators) |> Code.eval_quoted()
res
end)
|> Enum.sum()
end
def in_module(ast, mod) do
quote do
import unquote(mod)
import Kernel, only: []
unquote(ast)
end
end
def change_operators(input) do
input
|> String.replace("+", ">>>")
|> String.replace("-", "<<<")
|> String.replace("*", "~>>")
|> String.replace("/", "<<~")
end
def change_operators_2(input) do
input
|> String.replace("*", "~>>")
|> String.replace("/", "<<~")
end
end
defmodule SimpleOperators do
def a >>> b, do: a + b
def a <<< b, do: a - b
def a ~>> b, do: a * b
def a <<~ b, do: div(a, b)
end
defmodule AdvancedOperators do
# needed because i remove the imports in `in_module`
import Kernel, except: [+: 2, -: 2]
def a + b, do: Kernel.+(a, b)
def a - b, do: Kernel.-(a, b)
def a ~>> b, do: a * b
def a <<~ b, do: div(a, b)
end
1 Like
I defined two custom operator <<< and >>> for + and *, replace string + * with them. Then let elixir calculate sum.
Part 2, only replace *, + then has higher precedence.
Same idea of operator overriding.
2 Likes
Such a pragmatic solution 
, I was so tired when tackling this and spent more-time-than-I-want-to-admit solving for merging the numbers back after splitting with String.graphemes() due to those parenthesis without whitespace 
3 Likes
I originally parsed each equation into an expression tree to evaluate them - which worked, but then I saw on reddit someone mention the shunting yard algorithm - did a bunch of reading on operator precedence parsing and stack based calculators and was able to refactor my code in a really satisfying way. The implementation of the algorithm and the evaluator could use some clean up, but it works, and it works about 10 times faster then the expression tree approach
4 Likes
Honestly, I’m a bit blown away by people cracking open the AST and evaluating the expressions in Elixir. Once advent of code is complete I feel like I need to go back through the days and really try to grock everyone’s code. Lot’s of good stuff that I haven’t had the chance to look at.
I had a much more mundane, tree based approach. My solution to part 2 was just to wrap addition in some parens.
defmodule Day18 do
def part_1, do: load() |> Enum.map(&interpret/1) |> Enum.sum()
def part_2, do: load() |> Enum.map(&interpret2/1) |> Enum.sum()
def interpret(text), do: text |> lex() |> parse() |> eval()
def interpret2(text), do: text |> lex() |> parse() |> wrap() |> eval()
def lex(""), do: []
def lex(" " <> rest), do: lex(rest)
def lex(<<n::bytes-size(1)>> <> rest) when n in ["(", ")", "+", "*"], do: [n|lex(rest)]
def lex(<<n::bytes-size(1)>> <> rest), do: [String.to_integer(n)|lex(rest)]
def parse(tokens=["("|_]), do: parse(match_parens(tokens, []))
def parse([n|rest]), do: [parse(n)|parse(rest)]
def parse(n), do: n
def match_parens(["("|t], stack), do: match_parens(t, [[]|stack])
def match_parens([")"|t], [c,p|rest]), do: match_parens(t, [[parse(Enum.reverse(c))|p]|rest])
def match_parens([")"|rest], [group]), do: [Enum.reverse(group)|rest]
def match_parens([n|t], [group|rest]), do: match_parens(t, [[n|group]|rest])
def wrap([]), do: []
def wrap([left, "+", right|rest]), do: wrap([[wrap(left), "+", wrap(right)]|rest])
def wrap([left, "*", right|rest]), do: [wrap(left), "*"| wrap([wrap(right)|rest])]
def wrap([n]), do: [n]
def wrap(n), do: n
def eval(prev, []), do: prev
def eval(prev, ["+", n|rest]), do: eval(prev + eval(n), rest)
def eval(prev, ["*", n|rest]), do: eval(prev * eval(n), rest)
def eval([n, "+", m|rest]), do: eval(eval(n) + eval(m), rest)
def eval([n, "*", m|rest]), do: eval(eval(n) * eval(m), rest)
def eval([l=[_|_]]), do: eval(l)
def eval(n), do: n
def load, do: File.read!("day-18.input") |> String.split("\n", trim: true)
end
That’s what I also ended up doing but my code was a lot messier. Tried reimplementing it using the Shunting Yard algorithm suggested by @camilleryr which made it a lot nicer and easier to change as part 2 would have been a simple change of:
def precedence(operator) do
case operator do
"+" -> 3
"*" -> 2
end
end
Was a fun exercise!
The code if anyone is interested.
And the code from this morning
I tried to do that in Elixir tonight, it works. Of course, it is absolutely terrible. But it works 
I still like my first solution better though.
defmodule NoPrecedence do
import Kernel, except: [-: 2]
def a - b, do: a * b
def eval(expression) do
env = Map.update!(__ENV__, :functions, &[{__MODULE__, -: 2} | &1])
expression
|> String.replace("*", "-")
|> Code.eval_string([], env)
|> elem(0)
end
end
defmodule AdditionPrecedence do
import Kernel, except: [-: 2, /: 2]
def a / b, do: a + b
def a - b, do: a * b
def eval(expression) do
env = Map.update!(__ENV__, :functions, &[{__MODULE__, -: 2}, {__MODULE__, "/": 2} | &1])
expression
|> String.replace("+", "/")
|> String.replace("*", "-")
|> Code.eval_string([], env)
|> elem(0)
end
end
for line <- File.stream!("../src/adventofcode/priv/input/2020/day-18.inp") do
NoPrecedence.eval(line)
end
|> Enum.sum()
|> IO.inspect(label: "part 1")
for line <- File.stream!("../src/adventofcode/priv/input/2020/day-18.inp"), reduce: 0 do
sum -> sum + AdditionPrecedence.eval(line)
end
|> IO.inspect(label: "part 2")
Slower pace now so I only just got around to finishing this.
I noticed Part 1 could be optimised to just walk the string, using recursion for the parentheses. Unfortunately, that meant I had to effectively start again for Part 2. Here’s an excerpt from Part 1:
def evaluate(command), do: evaluate(command, nil, 0)
def evaluate([], nil, acc), do: acc
def evaluate(["*" | rest], nil, acc), do: evaluate(rest, "*", acc)
def evaluate(["+" | rest], nil, acc), do: evaluate(rest, "+", acc)
def evaluate(["(" | rest], op, acc), do: evaluate(rest) |> evaluate(op, acc)
def evaluate([")" | rest], nil, acc), do: [acc | rest]
def evaluate([num | rest], "*", acc), do: evaluate(rest, nil, acc * num)
def evaluate([num | rest], "+", acc), do: evaluate(rest, nil, acc + num)
def evaluate([num | rest], nil, 0), do: evaluate(rest, nil, num)
I also went the AST route for Part 2, first building up a tree and then evaluating it. I spent more time that I care to admit on that fixing silly bugs and staring at logging output, and the end result is not exactly pretty either. I wasn’t sure how to parse the precedence correctly. I decided to do it in two passes: first construct the + operations, then go back and pick up any * operations left - although it felt pretty awkward.
I wanted to do the AST, so it was a good exercise, but I wish I’d come up with @princemaple’s elegant solution.
This seemed like a good time to try out NimbleParsec, it worked out pretty well:
I still don’t have a great mental model for what adding wrap() does, but some experimentation got me through.
I’m curious what somebody who knows the library better would do…
