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)

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);
}

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);
    }
}

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

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

#!/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($_), <>);

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

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

#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;
}