Advent of Code 2020 - Day 18

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 :slight_smile:

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! :grinning:

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

Hi there
I went for a massive regex/replace approach :slight_smile:

Part1 / Part2

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 :slight_smile:, 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 :blush:

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

3 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 :wink: 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…