Day 18: Operation Order

public override string SolvePart1()
{
	using (var fs = new StreamReader(Inputs.Year2020.Inputs2020.Input18))
	{
		string line;
		var results = new List<long>();
		while ((line = fs.ReadLine()) != null)
		{
			var toShunt = line.Where(c => c != ' ').Select(c => new Token(c)).ToList();
			var outputQueue = new Queue<Token>();
			var shuntStack = new Stack<Token>();
			for (int i = 0; i < toShunt.Count; i++)
			{
				switch (toShunt[i].Type)
				{
					case Token.TokenType.NUMBER:
						outputQueue.Enqueue(toShunt[i]);
						break;
					case Token.TokenType.PAREN:
						if (toShunt[i].Paren == Token.ParenType.LEFT)
						{
							shuntStack.Push(toShunt[i]);
						}
						else
						{
							//pop until paren, dispose
							while (shuntStack.Peek().Type != Token.TokenType.PAREN)
							{
								outputQueue.Enqueue(shuntStack.Pop());
							}
							shuntStack.Pop();
						}
						break;
					case Token.TokenType.OPERATOR:
						while (shuntStack.Count > 0 && shuntStack.Peek().Type == Token.TokenType.OPERATOR)
						{
							outputQueue.Enqueue(shuntStack.Pop());
						}
						shuntStack.Push(toShunt[i]);
						break;
					default:
						throw new Exception("malformed token");
				}
			}
			while (shuntStack.Count > 0)
			{
				outputQueue.Enqueue(shuntStack.Pop());
			}

			var mathStack = new Stack<long>();
			while (outputQueue.Count > 0)
			{
				var next = outputQueue.Dequeue();
				if (next.Type == Token.TokenType.NUMBER)
				{
					mathStack.Push(next.Value);
				}
				else
				{
					var opA = mathStack.Pop();
					var opB = mathStack.Pop();
					if (next.Operator == Token.OperatorType.PLUS)
					{
						mathStack.Push(opA + opB);
					}
					else
					{
						mathStack.Push(opA * opB);
					}
						
				}
			}

			results.Add(mathStack.Pop());
			if (mathStack.Count != 0)
			{
				throw new Exception("misparsed");
			}

		}

		return $"Total sum is {results.Sum()}";
	}
}

public override string SolvePart2()
{
	using (var fs = new StreamReader(Inputs.Year2020.Inputs2020.Input18))
	{
		string line;
		var results = new List<long>();
		while ((line = fs.ReadLine()) != null)
		{
			var toShunt = line.Where(c => c != ' ').Select(c => new Token(c)).ToList();
			var outputQueue = new Queue<Token>();
			var shuntStack = new Stack<Token>();
			for (int i = 0; i < toShunt.Count; i++)
			{
				switch (toShunt[i].Type)
				{
					case Token.TokenType.NUMBER:
						outputQueue.Enqueue(toShunt[i]);
						break;
					case Token.TokenType.PAREN:
						if (toShunt[i].Paren == Token.ParenType.LEFT)
						{
							shuntStack.Push(toShunt[i]);
						}
						else
						{
							//pop until paren, dispose
							while (shuntStack.Peek().Type != Token.TokenType.PAREN)
							{
								outputQueue.Enqueue(shuntStack.Pop());
							}
							shuntStack.Pop();
						}
						break;
					case Token.TokenType.OPERATOR:
						while (shuntStack.Count > 0 && shuntStack.Peek().Type == Token.TokenType.OPERATOR
							&& (shuntStack.Peek().Operator >= toShunt[i].Operator))
						{
							outputQueue.Enqueue(shuntStack.Pop());
						}
						shuntStack.Push(toShunt[i]);
						break;
					default:
						throw new Exception("malformed token");
				}
			}
			while (shuntStack.Count > 0)
			{
				outputQueue.Enqueue(shuntStack.Pop());
			}

			var mathStack = new Stack<long>();
			while (outputQueue.Count > 0)
			{
				var next = outputQueue.Dequeue();
				if (next.Type == Token.TokenType.NUMBER)
				{
					mathStack.Push(next.Value);
				}
				else
				{
					var opA = mathStack.Pop();
					var opB = mathStack.Pop();
					if (next.Operator == Token.OperatorType.PLUS)
					{
						mathStack.Push(opA + opB);
					}
					else
					{
						mathStack.Push(opA * opB);
					}
						
				}
			}

			results.Add(mathStack.Pop());
			if (mathStack.Count != 0)
			{
				throw new Exception("misparsed");
			}

		}

		return $"Total sum is {results.Sum()}";
	}
}

public class Token
{
	public enum TokenType
	{
		NUMBER,
		OPERATOR,
		PAREN
	}

	public enum OperatorType
	{
		PLUS = 1,
		TIMES = 0
	}

	public enum ParenType
	{
		LEFT,
		RIGHT
	}
	
	public TokenType Type { get; }
	public long Value { get; }
	public OperatorType Operator { get; }
	public ParenType Paren { get; }

	public Token(char c)
	{
		switch (c)
		{
			case '(':
				Type = TokenType.PAREN;
				Paren = ParenType.LEFT;
				break;
			case ')':
				Type = TokenType.PAREN;
				Paren = ParenType.RIGHT;
				break;
			case '+':
				Type = TokenType.OPERATOR;
				Operator = OperatorType.PLUS;
				break;
			case '*':
				Type = TokenType.OPERATOR;
				Operator = OperatorType.TIMES;
				break;
			default:
				Type = TokenType.NUMBER;
				Value = c - '0';
				break;
		}
	}
}

Today was another day of having a better part 2 leaderboard ranking than part 1, which I'm always proud of.

Basically I run my parenthesis method on every row. What parenthesis does is it looks for pairs of parenthesis and then sends the internals over to my string_solve method, which handles reading through a string using the new order of operations. Then it swaps in the the solution in place of the old parenthesis and checks again. It keeps going like that until there are no more parenthesis.

Once all the parenthesis have been dealt with, it sends all the remaining parts to string_solve one last time, and that's the answer

Basically everything finds a small portion of the equation that it knows how to deal with, the it simplifies it and runs replace to swap the more complex version out for the simpler version

The bug that was taking forever to solve was that my 'replace' functions didn't have the 'DO THIS ONLY ONCE' command, so in some rare cases (4, I counted). It would swap out multiple portions of the equation... which fucked up the result but didn't cause any errors.

import re

#data = test_data.split('\n')
data = input_data.split('\n')

pattern = re.compile('\((.+)\)')
pattern2 = re.compile('\(([\d+*\s]+)\)')
pattern3 = re.compile('(\d+)\s([+*])\s(\d+)')

def parenthesis(equation):
    while True:
        matches = pattern2.findall(equation)
        if len(matches) > 0:
            for match in matches:
                equation = equation.replace('(' + match + ')', string_solve(match),1)
        else:
            equation = string_solve(equation)
            break
    return equation

def string_solve(equation): 
    while True:
        match = pattern3.search(equation)
        if match is not None:
            left = match.group(1)
            right = match.group(3)
            symbol = match.group(2)
            if symbol == '+':
                equation = equation.replace(str(match.group(0)), str(int(left) + int(right)),1)
            elif symbol == '*':
                equation = equation.replace(str(match.group(0)), str(int(left) * int(right)),1)
            else:
                print('Something fucked up')
        else:
            break
    return equation
    
running_sum = 0
for row in data:
    running_sum = running_sum + int(parenthesis(row))
print(running_sum)

This basically works the same way as part A, but I add a new regex pattern and do all the '+'s before the '*'s in string_solve

import re

#data = test_data.split('\n')
data = input_data.split('\n')

pattern = re.compile('\((.+)\)')
pattern2 = re.compile('\(([\d+*\s]+)\)')
pattern3 = re.compile('(\d+)\s([+])\s(\d+)')
pattern4 = re.compile('(\d+)\s([*])\s(\d+)')

def parenthesis(equation):
    while True:
        matches = pattern2.findall(equation)
        if len(matches) > 0:
            for match in matches:
                equation = equation.replace('(' + match + ')', string_solve(match),1)
        else:
            equation = string_solve(equation)
            break
    return equation

def string_solve(equation): 
    while True:
        match = pattern3.search(equation)
        if match is not None:
            left = match.group(1)
            right = match.group(3)
            equation = equation.replace(str(match.group(0)), str(int(left) + int(right)),1)
        else:
            break
    while True:
        match = pattern4.search(equation)
        if match is not None:
            left = match.group(1)
            right = match.group(3)
            equation = equation.replace(str(match.group(0)), str(int(left) * int(right)),1)
        else:
            break
    return equation
    
running_sum = 0
for row in data:
    #print(int(parenthesis(row)), '=', row)
    running_sum = running_sum + int(parenthesis(row))
print(running_sum)

• There are very simple (minimal code required, as opposed to easy) ways to solve this one, if you take advantage of some of the built in functions for your preferred language

• You may have an easier time if you subdivide the tasks of 'dealing with parenthesis' and 'doing the actual math'

• If you're having trouble with your results, it may help to compare to a 'known good'. For example, some of my equations weren't active properly, but I couldn't figure out which ones, because all the ones I validated by hand came back correct. So I used someone else's method to calculate all the individual equations and compared it to my results. That helped me isolate the few equations that were giving me trouble. This method can be extremely viable in the 'real world' but that depends on the nature of the work you're doing

• If you end up swapping around portions of your equations using something like python's replace method, be careful that you're only swapping out what you want to, and not grabbing anything extra by mistake. For example, one of my equations looked like this:

2 + 2 + 8 * 4 + (4 + 4) * 5
2 + 2 + 8 * 4 + 8 * 5
4 + 8 * 4 + 8 * 5
12 * 12 * 5
144 * 5
720

When it should have looked like this:

2 + 2 + 8 * 4 + (4 + 4) * 5
2 + 2 + 8 * 4 + 8 * 5
4 + 8 * 4 + 8 * 5
12 * 4 + 8 * 5
48 + 8 * 5
56 * 5
280

• When you're in the testing phase, you may find it helpful to print out the trace of your equation, to help make sure it's behaving properly

This took me a lot longer than I had hoped... I started off by doing a recursive descent parser and a recursive evaluator and that worked fine for Part 1 and can be seen here. Unfortunately, Part 2 requires precedence and I didn't know how to do that with recursive descent...

So after hours of trying all sorts of random things, I took the hint from @JRandomHacker and looked up the Shunting-yard algorithm and decided to go with that since I do know how to evaluate RPN expressions. So long story short, I use the algorithm to convert the infix expression into an RPN/postfix expression and then evaluate it.

import sys

# Constants

OPERATORS = ('+', '*')
PARENS    = ('(', ')')

# Functions

def parse_expression(tokens):
    ''' Parse expression from infix to RPN '''
    queue = []
    stack = []

    while tokens:
        token = tokens.pop(0)

        if token.isdigit():
            queue.append(int(token))
        elif token == '(':
            stack.append(token)
        elif token == ')':
            while stack[-1] not in PARENS:
                queue.append(stack.pop())
            stack.pop()
        elif token in OPERATORS:
            while stack and stack[-1] in OPERATORS:
                queue.append(stack.pop())
            stack.append(token)

    while stack and stack[-1] in OPERATORS:
        queue.append(stack.pop())

    return queue

def evaluate(expression):
    ''' Evaluate RPN expression '''
    stack = []

    while expression:
        token = expression.pop(0)
        if token in OPERATORS:
            operand2 = stack.pop()
            operand1 = stack.pop()
            result   = operand1 + operand2 if token == '+' else operand1 * operand2
        else:
            result   = token
            
        stack.append(result)

    return stack[0]

# Main Execution

def main():
    total = 0
    for line in sys.stdin:
        tokens     = [token for token in line if not token.isspace()]
        expression = parse_expression(tokens)
        evaluation = evaluate(expression)
        total     += evaluation

    print(total)

if __name__ == '__main__':
    main()

Once the Shunting-yard algorithm was in place, all I had to do for Part 2 was add an additional condition to ensure I move operators from the operators stack only if they have greater or equal precedence to the current token. Fortunately for me, '+' > '*', so I didn't have to anything special for this comparison.

--- day18-A.py	2020-12-18 10:05:31.793332016 -0500
+++ day18-B.py	2020-12-18 10:06:02.304385426 -0500
@@ -26,7 +26,7 @@
                 queue.append(stack.pop())
             stack.pop()
         elif token in OPERATORS:
-            while stack and stack[-1] in OPERATORS:
+            while stack and stack[-1] in OPERATORS and stack[-1] >= token:
                 queue.append(stack.pop())
             stack.append(token)

After getting some sleep, I decided to lookup how to handle operator precedence and association with recursive descent and found that an Operator-precedence parser isn't too bad (I just didn't know about it). Below is a working solution for Part 1 and 2 using this approach.

import collections
import sys

# Constants

PRECEDENCE = {
    '+' : 1,
    '*' : 1,
}

# Structures

Node = collections.namedtuple('Node', 'op lhs rhs')

# Functions

def parse_primary(tokens):
    if tokens[0] == '(':
        tokens.pop(0)
        primary = parse_expression(tokens)
        tokens.pop(0)
    else:
        primary = tokens.pop(0)

    return primary

def parse_expression(tokens, precedence=0):
    lhs = parse_primary(tokens)

    while tokens and PRECEDENCE.get(tokens[0], -1) >= precedence:
        op  = tokens.pop(0)
        rhs = parse_expression(tokens, PRECEDENCE[op] + 1)
        lhs = Node(op, lhs, rhs)

    return lhs

def evaluate(expression):
    if isinstance(expression, str):
        return int(expression)

    if expression.op == '+':
        return evaluate(expression.lhs) + evaluate(expression.rhs)
    else:
        return evaluate(expression.lhs) * evaluate(expression.rhs)

# Main Execution

def main():
    total = 0
    for line in sys.stdin:
        tokens     = [token for token in line if not token.isspace()]
        expression = parse_expression(tokens)
        evaluation = evaluate(expression)
        total     += evaluation

    print(total)

if __name__ == '__main__':
    main()

Once again, Part 2 was just a minor change. In this case, I just made '+' a higher precedence in the table and the algorithm does the rest!

--- day18-A-RD.py       2020-12-18 10:54:10.350018800 -0500
+++ day18-B-RD.py       2020-12-18 10:54:18.862029743 -0500
@@ -6,7 +6,7 @@
 # Constants
 
 PRECEDENCE = {
-    '+' : 1,
+    '+' : 2,
     '*' : 1,
 }

import re

with open("input.txt") as input_file:
    expressions = [re.findall(r'(\d|\+|\*|\(|\))', expression)
                   for expression in input_file.read().split("\n")]


def operation(a, b, operator):
    if operator == "+":
        return int(a) + int(b)
    if operator == "*":
        return int(a) * int(b)


def calculate(expression, plus_before_minus):

    open_parentheses = 0
    closed_parantheses = 0
    sub_expression = []

    operator = ""
    results = [0] * 10
    block = 0
    for part in expression:

        if open_parentheses > 0:
            # while stuck in a parenthesis block
            if part == ")":
                closed_parantheses += 1
            if open_parentheses == closed_parantheses:
                open_parentheses = 0
                closed_parantheses = 0
                if not results[block]:
                    results[block] = calculate(
                        sub_expression, plus_before_minus)
                else:
                    results[block] = operation(results[block],
                                               calculate(sub_expression, plus_before_minus), operator)
                sub_expression = []
            else:
                sub_expression += [part]
        elif part.isnumeric():
            # if not in parenthesis hell
            if not results[block]:
                results[block] = int(part)
            else:
                results[block] = operation(results[block], part, operator)

        elif part == "+" or part == "*":
            operator = part

            # split result in blocks to multiply at the end
            if plus_before_minus and operator == "*":
                block += 1
        if part == "(":
            open_parentheses += 1

    # multiply blocks
    product = 1
    for result in results:
        if result:
            product *= result
    return product


def calculate_all(expressions, plus_before_minus):
    results = 0
    for expression in expressions:
        results += calculate(expression, plus_before_minus)
    return results


print("Without precedence:", calculate_all(expressions, False))
print("With precedence:", calculate_all(expressions, True))

function main()

    input = []
    open("Day18/input.txt") do fp
        input = clean_input.(readlines(fp))
    end

    println(sum(eval_expression.(input)))

end

function clean_input(line)
    return_line = Array{Any}([letter for letter in line if letter != ' '])
    for idx = 1:length(return_line)
        if match(r"[()+*]", string(return_line[idx])) == nothing
            return_line[idx] = parse(Int, return_line[idx])
        end
    end
    return return_line
end

function eval_expression(line)
    if length(line) < 3
        return line[1]
    elseif line[1] == '('
        close = find_paren_match(line[2:end], 0)
        return eval_expression([eval_expression(line[2:close])...,
                                line[close+2:end]...])
    elseif line[3] == '('
        close = find_paren_match(line[4:end], 2)
        return eval_expression([line[1:2]...,
                                eval_expression(line[4:close])...,
                                line[close+2:end]...])
    elseif line[2] == '+'
        return eval_expression([line[1] + line[3], line[4:end]...])
    elseif line[2] == '*'
        return eval_expression([line[1] * line[3], line[4:end]...])
    end
end

function find_paren_match(line, offset)
    paren_count = 1
    for (idx,character) in enumerate(line)
        if character == '('
            paren_count += 1
        elseif character == ')'
            paren_count -= 1
        end

        if paren_count == 0
            return idx + offset
        end
    end
end
 

main()

@@ -7,6 +7,8 @@ function main()
 
     println(sum(eval_expression.(input)))
 
+    println(sum(eval_expression2.(input)))
+
 end
 
 function clean_input(line)
@@ -38,6 +40,27 @@ function eval_expression(line)
     end
 end
 
+function eval_expression2(line)
+    if length(line) < 3
+        return line[1]
+    elseif line[1] == '('
+        close = find_paren_match(line[2:end], 0)
+        return eval_expression2([eval_expression2(line[2:close])...,
+                                line[close+2:end]...])
+    elseif line[3] == '('
+        close = find_paren_match(line[4:end], 2)
+        return eval_expression2([line[1:2]...,
+                                eval_expression2(line[4:close])...,
+                                line[close+2:end]...])
+    elseif line[2] == '+'
+        return eval_expression2([line[1] + line[3], line[4:end]...])
+    elseif line[2] == '*' && length(line) >= 4 && line[4] != '+'
+        return eval_expression2([line[1] * line[3], line[4:end]...])
+    else
+        return line[1] * eval_expression2(line[3:end])
+    end
+end
+
 function find_paren_match(line, offset)
     paren_count = 1
     for (idx,character) in enumerate(line)

defmodule AdventOfCode.Day18 do
  def part1(args) do
    args
    |> parse_input()
    |> Enum.map(&evaluate(&1, :p1))
    |> Enum.sum()
  end

  def part2(args) do
    args
    |> parse_input()
    |> Enum.map(&evaluate(&1, :p2))
    |> Enum.sum()
  end

  defp parse_input(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.map(&String.replace(&1, " ", ""))
    |> Enum.map(&String.to_charlist/1)
    |> Enum.map(&nest_quantities/1)
  end

  defp nest_quantities(expr, acc \\ [])

  defp nest_quantities([], acc), do: Enum.reverse(acc)

  defp nest_quantities([?) | rest], acc) do
    {Enum.reverse(acc), rest}
  end

  defp nest_quantities([?( | rest], acc) do
    {quantity, rest} = nest_quantities(rest)

    nest_quantities(rest, [quantity | acc])
  end

  defp nest_quantities([char | rest], acc) do
    nest_quantities(rest, [char | acc])
  end

  ###

  defp evaluate(expr, acc \\ {0, &+/2}, p_flag)

  defp evaluate([n | expr], {l, op}, p_flag) when n in ?0..?9 do
    evaluate(expr, {op.(l, n - ?0), nil}, p_flag)
  end

  defp evaluate([?+ | expr], {l, _}, p_flag) do
    evaluate(expr, {l, &+/2}, p_flag)
  end

  defp evaluate([?* | expr], {l, _}, :p1) do
    evaluate(expr, {l, &*/2}, :p1)
  end

  defp evaluate([?* | expr], {l, _}, :p2) do
    l * evaluate(expr, :p2)
  end

  defp evaluate([quantity | expr], {l, op}, p_flag) when is_list(quantity) do
    evaluate(expr, {op.(l, evaluate(quantity, p_flag)), nil}, p_flag)
  end

  defp evaluate([], {n, _}, _), do: n
end