DEV Community

Cover image for Advent of Code 2020 Solution Megathread - Day 18: Operation Order
Ryan Palo
Ryan Palo

Posted on

Advent of Code 2020 Solution Megathread - Day 18: Operation Order

#adventofcode #challenge

One more week until Christmas! Hopefully all of the code is leaving you extra jolly rather than grinchy. Let's take today to meditate on all of the blessings in our lives. 😊 Also, fun fact: Haskell was the top submitted language yesterday! Go functional languages!

The Puzzle

In today’s puzzle, is all about math. Side note: I 100% knew what the video linked in the beginning of the instructions was going to be before I clicked on it. Math is math! Why would they change math!? Well, today, it's no longer "Please Excuse My Dear Aunt Sally." It's "Left to Right No Matter What. P.S. Suck It."

I'm excited to write this parser. Let's get to it!

The Leaderboards

As always, this is the spot where I’ll plug any leaderboard codes shared from the community.

Ryan's Leaderboard: 224198-25048a19
Enter fullscreen mode Exit fullscreen mode

If you want to generate your own leaderboard and signal boost it a little bit, send it to me either in a DEV message or in a comment on one of these posts and I'll add it to the list above.

Yesterday’s Languages

Updated 07:43AM 12/18/2020 PST.

Language Count
Haskell 2
Perl 1
Ruby 1
Python 1
JavaScript 1

Merry Coding!

Top comments (10)

Collapse
 
cappe987 profile image
Casper •

My Haskell solution. It uses the shunting-yard algorithm to convert it to a postfix string and then evals the postfix string. Today's part 2 was obvious the moment I read part 1 so I went for this approach. So to solve part 2 I only had to change a 2 to a 3. Took 24 seconds from submitting the answer to part 1 to submitting the answer to part 2.

import Data.Char
import Data.Bifunctor as Bf

precedence :: Char -> Int -- Change precedence level of + to 2 for part 1
precedence c = case c of '+' -> 3; '*' -> 2; '(' -> 1; ')' -> 1;

shouldPopStack :: Char -> Char -> Bool
shouldPopStack x top = precedence x <= precedence top && top /= '('

popWhile :: Char -> (String, String) -> (String, String)
popWhile c (out, []) = (out, []) 
popWhile c (out, x:stack) = 
  if shouldPopStack c x then popWhile c (x:out, stack) else (out, x:stack)

shunting :: String -> (String, String) -> String
shunting [] (out, stack) = reverse stack ++ out
shunting ('(':xs) (out, stack) = shunting xs (out, '(':stack)
shunting (')':xs) (out, stack) = 
  let (ops, rest) = span (/= '(') stack
  in shunting xs (reverse ops ++ out, tail rest)
shunting ('+':xs) yard = shunting xs (Bf.second ('+':) $ popWhile '+' yard)
shunting ('*':xs) yard = shunting xs (Bf.second ('*':) $ popWhile '*' yard)
shunting (x  :xs) (out, stack) = shunting xs (x:out, stack)

evalPostfix :: String -> (Int, String)
evalPostfix ('+':xs) = 
  let (left, rest)   = evalPostfix xs
  in Bf.first (left+) $ evalPostfix rest
evalPostfix ('*':xs) = 
  let (left, rest)  = evalPostfix xs
  in Bf.first (left*) $ evalPostfix rest
evalPostfix (x:xs) = (digitToInt x, xs)

main :: IO ()
main = do 
  input <- lines <$> readFile "input.txt"
  print $ sum $ map (\s -> fst $ evalPostfix $ shunting (filter (/= ' ') s) ([],[])) input
Enter fullscreen mode Exit fullscreen mode
Collapse
 
meseta profile image
Yuan Gao •

It's a syntax parsing problem, right? So we just use PEG to parse it like we would any programming language. This takes away the heavy lifting of implementing parsing of individual characters, and let the library deal with all the recursion and traversal, leaving us to just provide methods which get called to evaluate the nodes of the AST as it traverses. The result is some clean and compact high-level code:

from parsimonious.grammar import Grammar, NodeVisitor
import math

grammar = Grammar(r"""
    OPERATION = EXPR (OP EXPR)+
    EXPR = (NUMBER / BRACKETS)
    BRACKETS = "(" OPERATION ")"
    OP = " " ("+" / "*") " "
    NUMBER    = ~r"\d"
""")

class ExprVisitor(NodeVisitor):
    def visit_OPERATION(self, node, visited_children):
        parts = [visited_children[0]]
        for op, value in visited_children[1]:
            if op == "+":
                parts[-1] += value
            if op == "*":
                parts.append(value)
        return math.prod(parts)

    def visit_EXPR(self, node, visited_children):
        return visited_children[0]

    def visit_BRACKETS(self, node, visited_children):
        return visited_children[1]

    def visit_OP(self, node, visited_children):
        return visited_children[1][0].text

    def visit_NUMBER(self, node, visited_children):
        return int(node.text)

    def generic_visit(self, node, visited_children):
        return visited_children or node

ev = ExprVisitor()
ev.grammar = grammar
print("sum", sum(ev.parse(line.strip()) for line in open("input.txt").readlines()))
Enter fullscreen mode Exit fullscreen mode
Collapse
 
ntreu14 profile image
Nicholas Treu •

Took me a while to dig through some docs to find what I wanted, but I wrote a parser in F# using FParsec.

open System.IO
open FParsec

// parsers
let parseDecimal : Parser<decimal, unit> = puint64 |>> decimal
let strWs s = pstring s >>. spaces
let parseTerm expression = (parseDecimal .>> spaces) <|> between (strWs "(") (strWs ")") expression

let runParser expr str =
  match run expr str with
    | Success (result, _ , _) -> result
    | Failure (errorMsg, _, _) -> failwithf "Error from parser: %s" errorMsg

let runPart addOperator input =
  let opp = OperatorPrecedenceParser<decimal, unit, unit>()
  let expression = opp.ExpressionParser

  let multOperator = InfixOperator ("*", spaces, 1, Associativity.Left, (*))

  opp.TermParser <- parseTerm expression
  opp.AddOperator(addOperator)
  opp.AddOperator(multOperator)

  input
    |> Array.sumBy (runParser expression) 
    |> printfn "%A"

let input = File.ReadAllLines "input.txt"

runPart (InfixOperator ("+", spaces, 1, Associativity.Left, (+))) input
runPart (InfixOperator ("+", spaces, 2, Associativity.Left, (+))) input
Enter fullscreen mode Exit fullscreen mode
Collapse
 
kudostoy0u profile image
Kudos Beluga • • Edited

Javascript solution part 1, I'll see what I can do about part 2.
I used iteration to solve this instead of parsing algorithm thingamajigs, and now I feel I should have gone that way :/

const fs = require("fs");
let data = fs.readFileSync("input.txt", "utf8").split("\n");
const balancedp = (idx, eq) => {
    let totall = 0;
    let endingindex;
    for (let i = idx, n = eq.length; i < n; i++) {
        let currentchar = eq[i];
        if (currentchar == "(") totall++
        else if (currentchar == ")") totall--
        if (totall == 0) {
            endingindex = i;
            break;
        }
    }
    return [eq.slice(idx + 1, endingindex), endingindex]
}
const tonumber = n => n.map(e => Number(e))
const processequation = eq => {
    if (eq[0] == "(") {
        return processequation("0 + " + eq)
    } else {
        let fidx = eq.match(/\d+/)
        let fnum = fidx[0]
        let op = eq.match(/(?<=\d+ )(\*|\+)/)[0];
        let lidx = eq.match(/(?<=\d+ (\*|\+) )(\(|\d+)/).index
        let lnum = eq.slice(lidx).split(" ")[0]
        if (lnum[0] == "(") lnum = "(";
        if (lnum == "(") {
            let sol = balancedp(lidx, eq);
            lidx = sol[1];
            lnum = processequation(sol[0]);
        }
        [lnum, fnum] = tonumber([lnum, fnum])
        if (op == "+") {
            eq = lnum + fnum + eq.slice(lidx + 1)
        } else {
            eq = fnum * lnum + eq.slice(lidx + 1)
        }
        let e = Number(eq)
        if (e) return Number(e)
        else return processequation(eq)
    }
}
let total = 0;
for (let i = 0, n = data.length; i < n; i++) {
    total += processequation(data[i]);
}
Enter fullscreen mode Exit fullscreen mode

Minified,

let e=require("fs").readFileSync("input.txt","utf8").split("\n");const t=e=>{if("("==e[0])return t("0 + "+e);{let l=e.match(/\d+/)[0],r=e.match(/(?<=\d+ )(\*|\+)/)[0],i=e.match(/(?<=\d+ (\*|\+) )(\(|\d+)/).index,n=e.slice(i).split(" ")[0];if("("==n[0]&&(n="("),"("==n){let l=((e,t)=>{let l,r=0;for(let i=e,n=t.length;i<n;i++){let e=t[i];if("("==e?r++:")"==e&&r--,0==r){l=i;break}}return[t.slice(e+1,l),l]})(i,e);i=l[1],n=t(l[0])}[n,l]=[n,l].map(e=>Number(e)),e="+"==r?n+l+e.slice(i+1):l*n+e.slice(i+1);let c=Number(e);return c?Number(c):t(e)}};let l=0;for(let r=0,i=e.length;r<i;r++)l+=t(e[r])
Enter fullscreen mode Exit fullscreen mode
Collapse
 
choroba profile image
E. Choroba • • Edited

My Perl solution. I used the Marpa::R2 library to write a parser. It supports rule precedence, so solving the part 2 took me just a minute.

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

use List::Util qw{ sum };
use Marpa::R2;

my $DSL = << '__DSL__';

:default ::= action => [name,values]
lexeme default = latm => 1

Expression ::= ('(') Expression (')')  assoc => group  action => ::first
             | digits                                  action => ::first
            || Expression op Expression                action => main::operate

whitespace ~ [\s]+
digits     ~ [\d]+
op         ~ [+*]
:discard   ~ whitespace

__DSL__

sub operate {
    {'+' => sub { $_[0] + $_[1] },
     '*' => sub { $_[0] * $_[1] }
    }->{$_[2]}->($_[1], $_[3])
}

my $grammar = 'Marpa::R2::Scanless::G'->new({source => \$DSL});
sub evaluate {
    my ($expression) = @_;
    return ${ $grammar->parse(\$expression) }
}

say sum(map evaluate($_), <>);
Enter fullscreen mode Exit fullscreen mode

For part 2, the DSL is

Expression ::= ('(') Expression (')') assoc => group action => ::first
             | digits                                action => ::first
            || Expression '+' Expression             action => main::operate
            || Expression '*' Expression             action => main::operate

whitespace ~ [\s]+
digits     ~ [\d]+
:discard   ~ whitespace
Enter fullscreen mode Exit fullscreen mode
Collapse
 
neilgall profile image
Neil Gall • • Edited

At first I wasted some time trying to get my parsers to produce an expression AST but they're not that advanced. Tokenising the text and using Dijkstra's shunting yard algorithm was a much better approach. I was also pleased to avoid copying token objects in the shunting yard algorithm - it just returns a new vector with the same objects the parser output, just reordered. Efficient!

use parser::*;

#[derive(Debug, Copy, Clone, PartialEq)]
enum Token {
    Num(i64),
    Add,
    Mul,
    Open,
    Close
}

fn tokenize(input: &str) -> ParseResult<Vec<Token>> {
    let token = whitespace_wrap(
        integer.map(Token::Num)
        .or(match_literal("+").means(Token::Add))
        .or(match_literal("*").means(Token::Mul))
        .or(match_literal("(").means(Token::Open))
        .or(match_literal(")").means(Token::Close))
    );

    one_or_more(token).parse(input)
}

fn shunting_yard<F>(tokens: &[Token], precedence: F) -> Vec<&Token>
where
    F: Fn(&Token, &Token) -> bool
{
    let mut stack: Vec<&Token> = vec![];
    let mut result: Vec<&Token> = vec![];

    for token in tokens {
        match token {
            Token::Num(_) => {
                result.push(token)
            }

            Token::Add | Token::Mul => {
                while let Some(t) = stack.last() {
                    if *t == &Token::Add || *t == &Token::Mul && precedence(token, *t) {
                        result.push(*t);
                        stack.pop();
                    } else {
                        break;
                    }
                }
                stack.push(token)
            }

            Token::Open => {
                stack.push(token)
            }

            Token::Close => {
                while let Some(t) = stack.pop() {
                    if t == &Token::Open {
                        break
                    } else {
                        result.push(t);
                    }
                }
            }
        }   
    }

    while let Some(t) = stack.pop() {
        result.push(t);
    }

    result
}

fn shunting_yard_v1(tokens: &[Token]) -> Vec<&Token> {
    shunting_yard(tokens, |_, _| true)
}

fn shunting_yard_v2(tokens: &[Token]) -> Vec<&Token> {
    shunting_yard(tokens, |t1, t2| !(t1 == &Token::Add && t2 == &Token::Mul))
}

fn eval_rp(tokens: &[&Token]) -> i64 {
    let mut stack: Vec<i64> = vec![];

    for token in tokens {
        match token {
            Token::Num(n) => {
                stack.push(*n)
            }

            Token::Add => {
                let a = stack.pop().unwrap();
                let b = stack.pop().unwrap();
                stack.push(a + b);
            }

            Token::Mul => {
                let a = stack.pop().unwrap();
                let b = stack.pop().unwrap();
                stack.push(a * b);
            }

            _ => panic!("shunting yard should remove all parens!")
        }
    }

    stack.pop().unwrap()
}

fn eval_v1(input: &str) -> i64 {
    let tokens = tokenize(input).unwrap().1;
    let rp = shunting_yard_v1(&tokens);
    eval_rp(&rp)
}

fn eval_v2(input: &str) -> i64 {
    let tokens = tokenize(input).unwrap().1;
    let rp = shunting_yard_v2(&tokens);
    eval_rp(&rp)
}

fn part1(input: &str) -> i64 {
    input.lines().map(eval_v1).sum()
}

fn part2(input: &str) -> i64 {
    input.lines().map(eval_v2).sum()
}

fn main() {
    let input = std::fs::read_to_string("./input.txt").unwrap();
    println!("part 1 {}", part1(&input));
    println!("part 2 {}", part2(&input));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_tokenize() {
        use Token::*;
        assert_eq!(tokenize("1 + 2 * (3+9)"), Ok(("", vec![
            Num(1), Add, Num(2), Mul, Open, Num(3), Add, Num(9), Close
        ])) );
    }

    #[test]
    fn test_shunting_yard_v1_simple_add() {
        use Token::*;
        let input = [Num(1), Add, Num(2)];
        assert_eq!(shunting_yard_v1(&input), vec![&Num(1), &Num(2), &Add])
    }

    #[test]
    fn test_shunting_yard_v1_with_parens() {
        use Token::*;
        let input = [Num(1), Add, Open, Num(2), Mul, Num(3), Close, Add, Num(7)];
        assert_eq!(shunting_yard_v1(&input), vec![&Num(1), &Num(2), &Num(3), &Mul, &Add, &Num(7), &Add])
    }

    #[test]
    fn test_eval_rp() {
        use Token::*;
        assert_eq!(eval_rp(&[&Num(1), &Num(2), &Num(3), &Mul, &Num(7), &Add, &Add]), 14);
    }

    #[test]
    fn test_eval_v1() {
        assert_eq!(eval_v1("2 * 3 + (4 * 5)"), 26);
        assert_eq!(eval_v1("5 + (8 * 3 + 9 + 3 * 4 * 3)"), 437);
        assert_eq!(eval_v1("5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4))"), 12240);
        assert_eq!(eval_v1("((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2"), 13632);
    }

    #[test]
    fn test_eval_v2() {
        assert_eq!(eval_v2("1 + (2 * 3) + (4 * (5 + 6))"), 51);
        assert_eq!(eval_v2("2 * 3 + (4 * 5)"), 46);
        assert_eq!(eval_v2("5 + (8 * 3 + 9 + 3 * 4 * 3)"), 1445);
        assert_eq!(eval_v2("5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4))"), 669060);
        assert_eq!(eval_v2("((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2"), 23340);
    }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
ervin_szilagyi profile image
Ervin Szilagyi • • Edited

Today's problem is the perfect candidate for using a recursive divide-and-conquer approach

Basically what I did is to solve the innermost expressions in the parenthesis and use this partial result to solve the outer expressions recursively. In case of part two, it is a bit trickier, since there is operator precedence. In this case when I encountered a multiplication, I've split the expression in 2 parts, basically solving the additions first and applying the multiplications afterwards for the partial results.

Here is my code in Java. It's a bit hefty, because Java, but it does the job:

public interface Day18 {
    Pattern pattern = Pattern.compile("[0-9]+");

    static long part1(List<String> lines) {
        return lines.stream()
                .map(Day18::splitLine)
                .mapToLong(Day18::solveExpressionSameOperationPrecedence)
                .sum();
    }

    static long part2(List<String> lines) {
        return lines.stream()
                .map(Day18::splitLine)
                .mapToLong(Day18::solveExpressionAdditionPrecedence)
                .sum();
    }

    private static List<String> splitLine(String line) {
        List<String> parts = new ArrayList<>();
        for (String part : line.split(" ")) {
            if (part.charAt(0) == '(' || part.charAt(part.length() - 1) == ')') {
                Matcher matcher = pattern.matcher(part);
                String number = "";
                if (matcher.find()) {
                    number = matcher.group(0);
                }
                String brackets = part.replaceFirst(number, "");
                if (part.charAt(0) == '(') {
                    for (char c : brackets.toCharArray()) {
                        parts.add(String.valueOf(c));
                    }
                    parts.add(number);
                } else {
                    parts.add(number);
                    for (char c : brackets.toCharArray()) {
                        parts.add(String.valueOf(c));
                    }
                }
                continue;
            }
            parts.add(part);
        }
        return parts;
    }

    private static long solveExpressionSameOperationPrecedence(List<String> expression) {
        long result = 0;
        Operation operation = Operation.ADD;
        int i = 0;
        while (i < expression.size()) {
            String part = expression.get(i);

            if (pattern.matcher(part).matches()) {
                long value = Long.parseLong(part);
                result = operation.apply(result, value);
                i++;
                continue;
            }

            if (part.equals("(")) {
                List<String> subEquation = extractSubExpression(expression, i);
                result = operation.apply(result, solveExpressionSameOperationPrecedence(subEquation));
                i += subEquation.size() + 2;
                continue;
            }

            operation = Operation.fromString(part);
            i++;
        }
        return result;
    }

    private static long solveExpressionAdditionPrecedence(List<String> expression) {
        long result = 0;
        int i = 0;
        while (i < expression.size()) {
            String part = expression.get(i);

            if (pattern.matcher(part).matches()) {
                result = Operation.ADD.apply(result, Long.parseLong(part));
                i++;
                continue;
            }

            if (part.equals("(")) {
                List<String> subExpression = extractSubExpression(expression, i);
                result = Operation.ADD.apply(result, solveExpressionAdditionPrecedence(subExpression));
                i += subExpression.size() + 2;
                continue;
            }

            if (Operation.fromString(part) == Operation.MULTIPLY) {
                result = Operation.MULTIPLY.apply(result, solveExpressionAdditionPrecedence(expression.subList(i + 1, expression.size())));
                break;
            }
            i++;
        }
        return result;
    }

    private static List<String> extractSubExpression(List<String> expression, int index) {
        int openBrackets = 1;
        int i = index + 1;
        for (; i < expression.size() && openBrackets > 0; i++) {
            String nextPart = expression.get(i);
            if (nextPart.equals("(")) {
                openBrackets++;
                continue;
            }
            if (nextPart.equals(")")) {
                openBrackets--;
            }
        }
        return expression.subList(index + 1, i - 1);
    }
}

enum Operation {
    ADD {
        public long apply(long a, long b) {
            return a + b;
        }
    },
    MULTIPLY {
        public long apply(long a, long b) {
            return a * b;
        }
    };

    public static Operation fromString(String operation) {
        if (operation.equals("+")) {
            return Operation.ADD;
        } else if (operation.equals("*")) {
            return Operation.MULTIPLY;
        }
        throw new IllegalArgumentException();
    }

    public abstract long apply(long a, long b);
}
Enter fullscreen mode Exit fullscreen mode

All my solutions can be found at: github.com/Ernyoke/advent-of-code-...

Collapse
 
bgaster profile image
Benedict Gaster •

Well today was done in less that 10 minutes, which I have to say was nice as I had a lot on today :-) Parsed expressions into AST, as I have multiple Haskell parsers for DSP programming languages that I've developed over the last few years and so it was a simple cut paste, rename, and factorize for part one and two to work with the same parser.

data Expr = Num Integer | Op Op Expr Expr
  deriving Show

data Op = Add | Mul
  deriving Show

eval :: ([Parser (Expr -> Expr -> Expr)], [Parser (Expr -> Expr -> Expr)]) -> String -> Integer
eval ops = eval' . parseExpr ops

eval' :: Expr -> Integer
eval' (Num x)           = x
eval' (Op Add x y)      = eval' x + eval' y
eval' (Op Mul x y)      = eval' x * eval' y

-- Parser

parseExpr :: ([Parser (Expr -> Expr -> Expr)], [Parser (Expr -> Expr -> Expr)]) -> String -> Expr
parseExpr ops s =
  case parse (spaces *> expression ops <* eof) "" s of
    Left e  -> error $ show e
    Right x -> x

expression :: ([Parser (Expr -> Expr -> Expr)], [Parser (Expr -> Expr -> Expr)]) -> Parser Expr
expression ops = lowerExpr ops
         <|> higherExpr ops
         <|> number
         <|> parens (expression ops)

lowerExpr :: ([Parser (Expr -> Expr -> Expr)], [Parser (Expr -> Expr -> Expr)]) -> Parser Expr
lowerExpr (ops,ops') = try $ expression' `chainl1` operator
  where expression' = higherExpr (ops,ops')
                  <|> number
                  <|> parens (expression (ops,ops'))

        operator = choice ops <* spaces

higherExpr :: ([Parser (Expr -> Expr -> Expr)], 
               [Parser (Expr -> Expr -> Expr)]) -> Parser Expr
higherExpr (ops,ops') = try $ expression' `chainl1` operator
    where expression' = number
                    <|> parens (expression (ops,ops'))

          operator = choice ops' <* spaces

number :: Parser Expr
number = do
  digits <- many1 digit
  spaces
  return $ Num $ read digits

parens :: Parser a -> Parser a
parens = between open close 
  where open  = char '(' <* spaces
        close = char ')' <* spaces

-- lower and higer precedence ops for task1
task1 :: ([Parser (Expr -> Expr -> Expr)], [Parser (Expr -> Expr -> Expr)])
task1 = ([ Op Add <$ char '+', Op Mul <$ char '*' ], [])

-- lower and higer precedence ops for task2
task2 :: ([Parser (Expr -> Expr -> Expr)], [Parser (Expr -> Expr -> Expr)])
task2 = ([Op Mul <$ char '*'], [Op Add <$ char '+'])

main  = do
  is <- readFile "day18_input" <&> lines

  print (sum $ map (eval task1) is)
  print (sum $ map (eval task2) is)
Enter fullscreen mode Exit fullscreen mode
Collapse
 
rpalo profile image
Ryan Palo • • Edited

Here's my solution. Doesn't quite support arbitrary levels of precedence, but we only needed two max, and that's what it works for. I'm comfortable with the knowledge that I could probably have put together an arbitrary precedence interpreter together if I had needed to. 😁

#include "Day18.h"

#include <stdio.h>

#include "parsing.h"

/// Day 18: Operation Order
///
/// Parse math expressions with different precedence rules than normal.

#define MAX_TOKENS 100  ///< Maximum number of tokens in a line

/// The different tokens our parser might encounter
typedef enum {
  TOK_NULL,         ///< A placeholder token to represent {0}
  TOK_NUM,          ///< A digit 0-9 (no double-digits in input)
  TOK_OPEN_PAREN,   ///< (
  TOK_CLOSE_PAREN,  ///< )
  TOK_PLUS,         ///< +
  TOK_STAR,         ///< *
  TOK_END,          ///< End of line sentinel
} TokenType;

const char* token_type[] = {"Null", "Num", "Open Paren", "Close Paren", "Plus", "Star", "End"};

/// A Token is essentially just a TokenType, but NUM tokens can store their value
typedef struct {
  TokenType type;
  long val;
} Token;

/// An iteratable of Tokens, that can be consumed and used up
/// but is also really just a list of Tokens with a memory
typedef struct {
  Token* tokens;
  Token* current;
} TokenIter;

/// Parse a line of input into a TokenIter
TokenIter parse_line(FILE* fp) {
  Token* tokens = (Token*)malloc(sizeof(Token) * MAX_TOKENS);
  int i = 0;
  char c;
  while ((c = getc(fp)) != EOF) {
    switch (c) {
      case '0' ... '9':
        tokens[i].type = TOK_NUM;
        tokens[i].val = c - '0';
        break;
      case '(': tokens[i].type = TOK_OPEN_PAREN; break;
      case ')': tokens[i].type = TOK_CLOSE_PAREN; break;
      case '+': tokens[i].type = TOK_PLUS; break;
      case '*': tokens[i].type = TOK_STAR; break;
      case '\n': 
        tokens[i].type = TOK_END; 
        return (TokenIter){
          .tokens = tokens,
          .current = NULL,
        };
      case ' ': continue;
      default: printf("Bad char %c.\n", c); exit(EXIT_FAILURE);
    }
    i++;
  }

  // May encounter end of file without newline
  tokens[i].type = TOK_END;
  return (TokenIter){
    .tokens = tokens,
    .current = NULL,
  };
}

/// Parse input file so that each line is an iter of Tokens
TokenIter* parse(const char* filename, int* count) {
  FILE* fp;
  fp = fopen(filename, "r");
  if (fp == NULL) {
    printf("Couldn't open input file.\n");
    exit(EXIT_FAILURE);
  }

  *count = count_lines(fp);
  TokenIter* lines = (TokenIter*)malloc(sizeof(TokenIter) * *count);

  for (int i = 0; i < *count; i++) {
    lines[i] = parse_line(fp);
  }

  fclose(fp);
  return lines;
}

/// Iterate to next token (or prime the pump on a fresh iterable)
Token* token_next(TokenIter* iter) {
  if (iter->current == NULL) {
    iter->current = iter->tokens;
    return iter->current;
  }
  if (iter->current->type == TOK_END) return iter->current;
  return ++iter->current;
}

/// Short helper function to actually interpret operators
long do_op(TokenType op, long a, long b) {
  switch (op) {
    case TOK_PLUS: return a + b;
    case TOK_STAR: return a * b;
    default: printf("Unsupported op type: %d\n", op); exit(EXIT_FAILURE);
  }
}

/// Evaluate a line of input with only L-to-R and () precedence
long evaluate(TokenIter* tokens) {
  Token* t;
  long val_stack[MAX_TOKENS] = {0};
  int sp = 0;
  TokenType op_stack[MAX_TOKENS] = {0};
  int op_sp = 0;
  for (int i = 0; (t = token_next(tokens))->type != TOK_END; i++) {
    switch (t->type) {
      case TOK_NUM: 
        if (op_sp > 0) {
          val_stack[sp - 1] = do_op(op_stack[--op_sp], t->val, val_stack[sp - 1]);
        } else {
          val_stack[sp++] = t->val; 
        }
        break;
      case TOK_PLUS: op_stack[op_sp++] = TOK_PLUS; break;
      case TOK_STAR: op_stack[op_sp++] = TOK_STAR; break;
      case TOK_OPEN_PAREN: {
          long val = evaluate(tokens);
          if (op_sp > 0) {
            val_stack[sp - 1] = do_op(op_stack[--op_sp], val_stack[sp - 1], val);
          } else {
            val_stack[sp++] = val;
          }
        };
        break;
      case TOK_CLOSE_PAREN:
        if (op_sp > 0) {
          printf("End paren with unresolved operators.\n");
          exit(EXIT_FAILURE);
        }
        if (sp > 1) {
          printf("Unresolved integers on the stack.\n");
          exit(EXIT_FAILURE);
        }
        return val_stack[0];
      default: break;
    }
  }
  if (op_sp > 0) {
    printf("End paren with unresolved operators.\n");
    exit(EXIT_FAILURE);
  }
  if (sp > 1) {
    printf("Unresolved integers on the stack.\n");
    exit(EXIT_FAILURE);
  }
  return val_stack[0];
}

/// Given only paren and L-to-R precedence, add up the result of
/// evaluating each line of input
long part1(const char* filename) {
  int count;
  TokenIter* lines = parse(filename, &count);

  long total = 0;
  for (int i = 0; i < count; i++) {
    total += evaluate(&lines[i]);
    free(lines[i].tokens);
  }

  free(lines);
  return total;
}

/// Helper macro for unraveling the stack of operators.
/// Each operator pops two values off the value stack, operates on them
/// and disappears, pushing the result back on the value stack.
#define UNRAVEL_OPS \
  while (op_sp != 0) { \
    long a = val_stack[--sp]; \
    long b = val_stack[--sp]; \
    val_stack[sp++] = do_op(op_stack[--op_sp], a, b); \
  }

/// Evaluate a line of input with addition taking precedence over 
/// multiplication, and () being highest precedence
long evaluate_plus_prec(TokenIter* tokens) {
  Token* t;
  long val_stack[MAX_TOKENS] = {0};
  int sp = 0;
  TokenType op_stack[MAX_TOKENS] = {0};
  int op_sp = 0;
  for (int i = 0; (t = token_next(tokens))->type != TOK_END; i++) {
    switch (t->type) {
      case TOK_NUM: val_stack[sp++] = t->val; break;
      case TOK_STAR: 
        UNRAVEL_OPS;
        op_stack[op_sp++] = TOK_STAR; 
        break;
      case TOK_PLUS: op_stack[op_sp++] = TOK_PLUS; break;
      case TOK_OPEN_PAREN: val_stack[sp++] = evaluate_plus_prec(tokens); break;
      case TOK_CLOSE_PAREN:
        UNRAVEL_OPS;
        if (sp > 1) {
          printf("Unresolved integers on the stack.\n");
          exit(EXIT_FAILURE);
        }
        return val_stack[0];
      default: break;
    }
  }
  UNRAVEL_OPS;
  if (sp > 1) {
    printf("Unresolved integers on the stack.\n");
    exit(EXIT_FAILURE);
  }
  return val_stack[0];
}

#undef UNRAVEL_OPS

/// Add up the result of each line of input assuming precedence goes
/// () before + before *.
long part2(const char* filename) {
  int count;
  TokenIter* lines = parse(filename, &count);

  long total = 0;
  for (int i = 0; i < count; i++) {
    total += evaluate_plus_prec(&lines[i]);
    free(lines[i].tokens);
  }

  free(lines);
  return total;
}

/// Run both parts
int day18() {
  printf("====== Day 18 ======\n");
  printf("Part 1: %ld\n", part1("data/day18.txt"));
  printf("Part 2: %ld\n", part2("data/day18.txt"));
  return EXIT_SUCCESS;
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
thibpat profile image
Thibaut Patel •

My JavaScript walkthrough:

I've used a bunch of regular expressions and it helped keep my code small :)

Read next

abhay_yt_52a8e72b213be229 profile image

Docker Logging Drivers: A Comprehensive Guide for Effective Log Management

Abhay Singh Kathayat -

abhay_yt_52a8e72b213be229 profile image

Unlocking Advanced Docker Networking: Macvlan vs. Ipvlan

Abhay Singh Kathayat -

abhay_yt_52a8e72b213be229 profile image

Unlocking Docker BuildKit for Faster and More Secure Builds

Abhay Singh Kathayat -

abhay_yt_52a8e72b213be229 profile image

Docker Distributed Storage: GlusterFS vs. Ceph for Persistent Container Data

Abhay Singh Kathayat -