Day18.scala

package sungkmi.aoc2020.day18

sealed trait Token

final case class Digit(n: BigInt) extends OpDigit

sealed trait OpParen extends Token

enum Op extends OpParen with OpDigit:
  case Plus, Multiply

enum Parentheses extends OpParen:
  case Open, Close

sealed trait OpDigit extends Token

def precBasic(opp: OpParen): Int = opp match
    case _: Parentheses => 0
    case _: Op => 1

def precAdvanced(opp: OpParen): Int = opp match
    case _: Parentheses => 0
    case Op.Multiply => 1
    case Op.Plus => 2

def toPostfix(s: String, prec: OpParen => Int): List[OpDigit] =
  def mergeDigitStackToOut(digitStack: List[Char], out: List[OpDigit]): List[OpDigit] =
    if digitStack.isEmpty then out else
      Digit(BigInt(digitStack.reverse.mkString)) :: out
  def filterOpAndReverse(input: List[OpParen]): List[Op] =
    input.foldLeft(List.empty[Op]):
      (acc, op) => op match
        case op: Op => op :: acc
        case p: Parentheses => acc
  val (out, digitStack, opStack) = 
    s.toList.foldLeft((List.empty[OpDigit], List.empty[Char], List.empty[OpParen])):
      case ((out, digitStack, opStack), char) if char.isDigit =>
        (out, char :: digitStack, opStack)
      case ((out, digitStack, opStack), char) =>
        //println(s"===> ($out, $digitStack, $opStack), '$char'")
        val out0 = mergeDigitStackToOut(digitStack, out)
        val (out1, opStack1) = char match
          case ' ' => (out0, opStack)
          case '(' => (out0, Parentheses.Open :: opStack)
          case ')' =>
            val (f, b) = opStack.span(_ != Parentheses.Open)
            (filterOpAndReverse(f) ::: out0, b.tail)
          case opChar if opChar =='+' || opChar == '*' =>
            val op: Op = opChar match
              case '+' => Op.Plus
              case '*' => Op.Multiply
            val (f, b) = opStack.span(prec(_) >= prec(op))
            (filterOpAndReverse(f) ::: out0, op :: b)
        (out1, Nil, opStack1)
  
  (filterOpAndReverse(opStack) ::: mergeDigitStackToOut(digitStack, out)).reverse

def evalPostFix(postFix: List[OpDigit]): BigInt =
  //println(s"===> Postfix: $postFix")
  postFix.foldLeft(List.empty[BigInt]):
    case (stack, Digit(n)) => n :: stack
    case (stack, Op.Plus) => stack match
      case x :: y :: ints => (x + y) :: ints
      case _ => throw Exception(s"Wrong stack: $stack")
    case (stack, Op.Multiply) => stack match
      case x :: y :: ints => (x * y) :: ints
      case _ => throw Exception(s"Wrong stack: $stack")
  .head

def evalBasic(line: String): BigInt =
  evalPostFix(toPostfix(line, precBasic))

def evalAdvanced(line: String): BigInt =
  evalPostFix(toPostfix(line, precAdvanced))

def solve1(input: String): BigInt =
  input.split("\n").map(evalBasic).sum

def solve2(input: String): BigInt = 
  input.split("\n").map(evalAdvanced).sum

@main def part1: Unit =
  val ans = solve1(input)
  println(ans)

@main def part2: Unit = 
  val ans = solve2(input)
  println(ans)

//lazy val input: String = """

Day18Test.scala

package sungkmi.aoc2020.day18

class Day18Test extends munit.FunSuite {

  val testInputs = IndexedSeq(
    "1 + 2 * 3 + 4 * 5 + 6",
    "1 + (2 * 3) + (4 * (5 + 6))",
    "2 * 3 + (4 * 5)",
    "5 + (8 * 3 + 9 + 3 * 4 * 3)",
    "5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4))",
    "((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2",
  )
  
  val expectedPostfix2 = List(
    Digit(2),
    Digit(3),
    Op.Multiply,
    Digit(4),
    Digit(5),
    Op.Multiply,
    Op.Plus,
  )

  val expectedAnswers = IndexedSeq(
    71, 51, 26, 437, 12240, 13632
  ).map(BigInt(_))

  val expectedAnswers2 = IndexedSeq(
    231, 51, 46, 1445, 669060, 23340
  ).map(BigInt(_))

  test("toPostfix") {
    assertEquals(toPostfix(testInputs(2), precBasic), expectedPostfix2)
  }

  test("evalPostFix") {
    assertEquals(evalPostFix(expectedPostfix2), expectedAnswers(2))
  }

  test("evalBasic") {
    for(i <- 0 until 6) assertEquals(evalBasic(testInputs(i)), expectedAnswers(i))
  }

  test("evalAdvanced") {
    for(i <- 0 until 6) assertEquals(evalAdvanced(testInputs(i)), expectedAnswers2(i))
  }
}