Advent of Code 2020 - Day 18

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.

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.

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

Well, if it gets the job done… Nice trick!

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()

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

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.

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

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.