AoC Day 18 – Operation Order

This is a solution to Advent of Code 2020 day 18, written in Raku.

https://adventofcode.com/2020/day/18

Part One

Unfortunately, it seems like this "math" follows different rules than you remember.

Before you can help with the homework, you need to understand it yourself. Evaluate the expression on each line of the homework; what is the sum of the resulting values?

Raku

Part one calls for a left-associative calculator with equal precendence for add and multiply and support for parens. I have chosen to write a Raku grammar with actions that perform the calculation, so the result is returned by the Grammar.parse method.

  unit module Day18;

  grammar L-to-R-Calc {
      rule TOP { <expr> }
      rule expr { <l=.valexp> [ <oper> <r=.valexp> ]+ }
      rule valexp { <val=.num> | <val=.paren> }
      rule paren { '(' <expr> ')' }
      rule oper { <op=.add> | <op=.mul> }
      token add { '+' }
      token mul { '*' }
      token num { \d+ }

      class Actions {
          method TOP($/) { make $<expr>.made }
          method expr($/) {
              my $t = $<l>.made;
              for $<oper> Z $<r> -> ($op, $r) {
                  $t = &($op.made)($t, $r.made)
              }
              make $t
          }
          method valexp($/) { make $<val>.made }
          method paren($/) { make $<expr>.made }
          method oper($/) { make $<op>.made }
          method add($/) { make -> $l, $r { $l + $r } }
          method mul($/) { make -> $l, $r { $l * $r } }
          method num($/) { make +$/ }
      }

      method parse(|c) { nextwith(actions => Actions, |c); }
      method subparse(|c) { nextwith(actions => Actions, |c); }
  }

  sub calculate(Str $expression) is export {
      L-to-R-Calc.parse($expression).made;
  }

Tests

  use Test;
  use lib '.';
  use Day18;

  is calculate('2 * 3 + (4 * 5)'), 26;
  is calculate('5 + (8 * 3 + 9 + 3 * 4 * 3)'), 437;
  is calculate('5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4))'), 12240;
  is calculate('((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2'), 13632;

ok 1 - 
ok 2 - 
ok 3 - 
ok 4 -

Solution

The solution to part one is the sum of all the expressions provided in the input.

use lib '.';
use Day18;

my @input = '18-input.txt'.IO.lines;

say 'Part One';
say [+] @input.map(-> $line { calculate($line) } );
say 'Took ' ~ (now - ENTER now) ~ ' seconds';

Part One
1408133923393
Took 0.311358 seconds

Part Two

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

What do you get if you add up the results of evaluating the homework problems using these new rules?

For part two I have modified the grammar rules to produce a parse tree which evaluates the addition expressions before the multiplication expressions.

  unit module Day18Part2;

  grammar Sum-Mul-Calc {
      rule TOP { <value=.prodexp> }
      rule prodexp { <values=.sumexp>+ %% '*' }
      rule sumexp { <values=.valexp>+ %% '+' }
      rule valexp { <value=.num> | <value=.paren> }
      rule paren { '(' <value=.prodexp> ')' }
      token num { \d+ }

      class Actions {
          method TOP($/) { make $<value>.made }
          method prodexp($/) { make [*] $<values>>>.made }
          method sumexp($/) { make [+] $<values>>>.made }
          method valexp($/) { make $<value>.made }
          method paren($/) { make $<value>.made }
          method num($/) { make +$/ }
      }

      method parse(|c) { nextwith(actions => Actions, |c); }
      method subparse(|c) { nextwith(actions => Actions, |c); }
  }

  sub calculate(Str $expression) is export {
      Sum-Mul-Calc.parse($expression).made;
  }

Tests

  use Test;
  use lib '.';
  use Day18Part2;

  is calculate('2 * 3 + (4 * 5)'), 46;
  is calculate('5 + (8 * 3 + 9 + 3 * 4 * 3)'), 1445;
  is calculate('5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4))'), 669060;
  is calculate('((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2'), 23340;

ok 1 - 
ok 2 - 
ok 3 - 
ok 4 -

Solution

The solution to part two is the sum of all the same expressions provided in the input, using the new precedence rules.

use lib '.';
use Day18Part2;

my @input = '18-input.txt'.IO.lines;

say 'Part Two';
say [+] @input.map(-> $line { calculate($line) } );
say 'Took ' ~ (now - ENTER now) ~ ' seconds';

Part Two
314455761823725
Took 0.34398185 seconds

raku