Advent of Code 2020: Day 18

, 10 min read
advent of code 2020

Part 1

As you look out the window and notice a heavily-forested continent slowly appear over the horizon, you are interrupted by the child sitting next to you. They’re curious if you could help them with their math homework.

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

The homework (your puzzle input) consists of a series of expressions that consist of addition (+), multiplication (*), and parentheses ((…)). Just like normal math, parentheses indicate that the expression inside must be evaluated before it can be used by the surrounding expression. Addition still finds the sum of the numbers on both sides of the operator, and multiplication still finds the product.

However, the rules of operator precedence have changed. Rather than evaluating multiplication before addition, the operators have the same precedence and are evaluated left-to-right regardless of the order in which they appear.

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

You can read the full text here. Ok! Well today is fun, we are basically writing a part of parser.

What we need to do is take an expression, e.g.,

1
1 + (2 * 3) + (4 * (5 + 6))

And evaluate it such that the “*” and “+” operator have the same priority; however, the bracket has a higher priority than both of them. I am sort of vaguely aware that this can be done either using a tree or using the Shunting-yard algorithm. I will attach a python solution which utilises a tree at the bottom of this post. However, for our C++ solution, we are going to use a recursive approach.

BIDMAS
The elf teaching BIDMAS

So, we loop through and look for the first set of open and closed brackets, in the example above we would find,

1
(2 * 3)

Then, for part 1 at least, we just need to loop through from left to right and process the operators as they appear. Then we can inject the result of this back into the initial expression, e.g.

1
1 + (2 * 3) + (4 * (5 + 6))

becomes

1
2
1 + (2 * 3) + (4 * (5 + 6))
1 + 6 + (4 * (5 + 6))

We can repeat this.

1
2
3
1 + (2 * 3) + (4 * (5 + 6))
1 + 6 + (4 * 11)
1 + 6 + 44

Finally, there are no brackets left, thus we can just put the whole line into the same function that was processing the brackets and we have the answer. Great! So what does the code look like? First of all,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
long int process_brackets(std::string subline, int part){
    // We are in a substring (..) where there are no brackets
    // except the start and end
    long int val = 0;
    long int num = 0;
    int mode = 0;
    int subindex = 0;
    char op =  '+';
    for(size_t subletter=0; subletter<subline.size(); subletter++){
        // Process number
        int ascii = int(subline[subletter]);
        if ((ascii >= 48) && (ascii <= 59)){
            if (mode == 0){
                subindex = subletter;
                mode = 1;
            }
        }
        else if (mode == 1){
            num = std::stol(
                    subline.substr(subindex, subletter-subindex));
            if (op == '+')
                val += num;
            else if (op == '*')
                val *= num;
            mode = 0;
        }

        if ((subline[subletter] == '+') ||
                (subline[subletter] == '*')){
            op = subline[subletter];
        }
    }

    return val;
}

All this function does is loop through the string in a single pass identifying numbers and operators. We grab multi-digit numbers and identify the last operator before the number. We then apply the operator with the current number. This function never needs to worry about brackets because we know they don’t matter in this substring.

Now we need to loop through each expression identifying parts with brackets, and evaluating what is inside the brackets, repeatedly until there are no more brackets. We can do this with the following code,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
long int process_line(std::string line){
    size_t letter = 0;
    int index = 0;
    // Loop through the line replacing the brackets
    while(letter < line.size()){
        if (line[letter] == '('){
            index = letter;
        }
        else if (line[letter] == ')'){
            // Identify subline as (...)
            std::string subline = line.substr(index, letter-index+1);

            // Process subline
            long int val = process_brackets(subline);

            // Replace the (...) with the number we have calcualted
            std::string nline = line.substr(0, index);
            nline += std::to_string(val);
            if (letter != line.size()-1)
                nline += line.substr(letter+1, line.size()-letter-1);
            line = nline;

            // We've removed the brackets and replaced with value inside, now
            // we start again at the beginning of the line until it has no
            // brackets
            letter = -1;
        }
        letter++;
    }
    line += " ";
    // Finally we have a line with no brackets, no we do all the steps in order
    long int val = process_brackets(line);
    return val;
}

This looks very ugly, and maybe daunting. But it is just identifying substrings of the form “(…)”, evaluating the expression in the brackets and injecting that value into the original term.

We just pass over every value in the input,

1
2
3
4
5
6
7
8
std::fstream myfile("input", std::ios_base::in);
std::string line;

while(std::getline(myfile, line)){
    long int val1 = process_line(line);
    ans1 += val1;
}
myfile.close();

and we have the first ⭐! Note: remember to use a long int, because the numbers get pretty big!

The full code can be found on github

Part 2

You manage to answer the child’s questions, and they finish part 1 of their homework, but get stuck when they reach the next section: advanced math.

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

You can read the full text here. Well now part 2 has mixed it up! Now we care of the plus and multiplication. We must do all the additions, and then we can go through and do all the multiplications.

Fortunately, we have written our code so that we only care about the operators in a single function. For part 1, we loop through a subsequence, free from brackets, and apply the operators in the order they appear.

1
2
3
4
5
// Part 1 just process in order
if (op == '+')
    val += num;
else if (op == '*')
    val *= num;

However, now instead of performing the operator we’re going to make a stack of numbers and operators,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
std::list<char> ops = {'+'};
std::list<long int> nums = {0};
for(size_t subletter=0; subletter<subline.size(); subletter++){
    // Process number
    int ascii = int(subline[subletter]);
    if ((ascii >= 48) && (ascii <= 59)){
        if (mode == 0){
            subindex = subletter;
            mode = 1;
        }
    }
    else if (mode == 1){
        num = std::stol(
                subline.substr(subindex, subletter-subindex));
        // Part 2, store ops and process at the end, as we must do the
        // adds first!
        nums.push_back(num);
        ops.push_back(op);
        mode = 0;
    }
    if ((subline[subletter] == '+') ||
            (subline[subletter] == '*')){
        op = subline[subletter];
    }
}

This is just a minor change to our process_brackets function. Now we loop through the stack of numbers and operators and perform all of the additions, whilst ignoring the multiplications.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
std::list<char>::iterator op_it = ops.begin();
std::list<long int>::iterator num_it = nums.begin();
std::list<long int> products = {0};
while(op_it != ops.end()){
    long int num1 = *num_it;
    op = *op_it;
    num_it = std::next(num_it);
    op_it = std::next(op_it);
    if (op == '*'){
        products.push_back(num1);
    }
    else{
        products.back() += num1;
    }
}

So we have new list of numbers which all need to be multiplied together. Thus, the total value for this subsequence is,

1
2
3
4
val = 1;
for(auto v: products)
    if (v > 0)
        val *= v;

Then we pass over all the expressions as in part 1, and we are done, ⭐⭐.

The full code can be found on github

Reflections

My code today is very imperative and quite inefficient because of all my string modification. I would guess that my code is very slow compared to more efficient solutions with tree structures, or the previously mentioned Shunting-yard algorithm.

In general, both parts of the code scale as O(N)-time and space where N is the number of expressions. Furthermore, the time dependency of my algorithm will also scale with the number of operations, M in each expression. I think the complexity of the code is not too bad, it’s just that the implementation is not particularly readable or expressive.

Tree algorithm

Below is a python snippet which solves the same problem by generating a tree structure:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class Integer:
    def __init__(self, value):
        self.value = int(value)


class Node:
    def __init__(self, lhs, operator, rhs):
        self.operator = operator
        self.lhs = lhs
        self.rhs = rhs
        self.value = 0
        self.parse_children()

    def split_op(self, expr):
        # Split at operator
        brackets = 0
        split = None

        #ops = [['*'], ['+'],]
        ops = [['*', '+'],]
        for equal_ops in ops:
            for i, c in enumerate(expr[::-1]):
                brackets += (c == '(')
                brackets -= (c == ')')

                if (c in equal_ops) and (brackets == 0):
                    split = i
                    break

            if split is not None:
                break

        if split is not None:
            split = len(expr)-1-split

        return split

    def parse(self, expr):
        if expr is None:
            return None

        # Do we have brackets?
        split = self.split_op(expr)

        # Do we have matching outer brackets?
        if split is None:
            if expr[0] == "(":
                expr = expr[1:-1]
                split = self.split_op(expr)

        # Did we find more things to split
        if split is not None:
            operator = expr[split]
            lhs = expr[:split]
            rhs = expr[split+1:]

            return Node(lhs, operator, rhs)
        else:
            return Integer(expr)

    def parse_children(self):
        self.lhs = self.parse(self.lhs)
        self.rhs = self.parse(self.rhs)
        self.calculate()

    def calculate(self):
        self.value = self.lhs.value
        self.operate()

    def operate(self):
        if self.operator is None:
            return

        rhs = self.rhs.value
        if self.operator == "+":
            self.value += rhs
        elif self.operator == "*":
            self.value *= rhs


express = "((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2"

expr = Node(express.replace(" ", ""), None, None)
print(expr.value)

This implementation is much more general, and the only change between part 1 and part 2 is operation precedence, e.g.,

1
 ops = [['*', '+'],]

to

1
 ops = [['*'], ['+'],]

All operators in the same sublist have the same priority.

. . . .

I have no affiliation with AoC. I’m just a fan of the programming puzzles. If you enjoy them too, please feel free to join in and support the creators

Back to my advent calendar

Comments

Back to all posts