Day19.scala

package sungkmi.aoc2020.day19

enum Rule:
  case SingleChar(char: Char) extends Rule
  case Index(n: Int) extends Rule
  case And(rules: Seq[Rule]) extends Rule
  case Or(rules: Seq[Rule]) extends Rule

import Rule._

def parse(s: String): (Map[Int, Rule], Seq[String]) =
  val Array(ruleString, messages) = s `split` "\n\n"
  (parseRules(ruleString), messages.split("\n").toSeq)

def parseRules(s: String): Map[Int, Rule] = s.split("\n").map:
  line =>
    val Array(i, body) = line.split(":")
    i.toInt -> parseBody(body)
.toMap

def parseBody(body: String): Rule = body.trim match
  case s if s `contains` '|' =>
    val subBodies = s `split` '|'
    Or(subBodies.toSeq `map` parseBody)
  case s if s.startsWith('"'.toString) && s.endsWith('"'.toString) && (s.size == 3) =>
    SingleChar(s.tail.head)
  case s =>
    val indexes = s `split` ' '
    And(indexes.toSeq.map(_.toInt).map(Index(_)))

extension (rules: Map[Int, Rule])
  def `match`(s: String): Boolean =
    def matchRemainder(rule: Rule)(s: String): Option[String] =
      println(s"===> $rule: $s(${s.size})")
      rule match
        case SingleChar(ch) => if s.headOption == Some(ch) then Some(s.tail) else None
        case Index(n) => matchRemainder(rules(n))(s)
        case And(rules) => andLoop(rules.toList, Option(s))
        case Or(rules) => orLoop(rules.toList, s)
  
    @annotation.tailrec
    def andLoop(rules: List[Rule], s: Option[String]): Option[String] = (rules, s) match
      case (_, None) => None
      case (Nil, s) => s
      case (x :: xs, Some(s1)) => andLoop(xs, matchRemainder(x)(s1))

    @annotation.tailrec
    def orLoop(rules: List[Rule], s: String): Option[String] = rules match
      case Nil => None
      case x :: xs => matchRemainder(x)(s) match
        case Some(s1) => Some(s1)
        case None => orLoop(xs, s)

    val ans = matchRemainder(rules(0))(s) == Some("")
    if ans then println(s)
    ans

def modifyRule(rules: Map[Int, Rule]): Map[Int, Rule] =
  rules
    .updated(8, Or(Seq(
      Index(42),
      And(Seq(Index(42), Index(8)),
    ))))
    .updated(11, Or(Seq(
      And(Seq(Index(42), Index(31))),
      And(Seq(Index(42), Index(11), Index(31))),
    )))

def solve1(input: String): Int =
  val (rules, messages) = parse(input)
  messages.count(rules.`match`)

def solve2(input: String): Int = 
  val (rules, messages) = parse(input)
  messages.count(modifyRule(rules).`match`)

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

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

//lazy val input: String = """101: 118 64

Day19Test.scala

package sungkmi.aoc2020.day19

import Rule._

class Day19Test extends munit.FunSuite {

  val testInput1 = """0: 1 2
1: "a"
2: 1 3 | 3 1
3: "b""""
  
  val rules1: Map[Int, Rule] = Map(
    0 -> And(Seq(Index(1), Index(2))),
    1 -> SingleChar('a'),
    2 -> Or(Seq(And(Seq(Index(1), Index(3))), And(Seq(Index(3), Index(1))))),
    3 -> SingleChar('b'),
  )

  val testInput2 = """0: 4 1 5
1: 2 3 | 3 2
2: 4 4 | 5 5
3: 4 5 | 5 4
4: "a"
5: "b""""

  val rules2: Map[Int, Rule] = Map(
    0 -> And(Seq(Index(4), Index(1), Index(5))),
    1 -> Or(Seq(And(Seq(Index(2), Index(3))), And(Seq(Index(3), Index(2))))),
    2 -> Or(Seq(And(Seq(Index(4), Index(4))), And(Seq(Index(5), Index(5))))),
    3 -> Or(Seq(And(Seq(Index(4), Index(5))), And(Seq(Index(5), Index(4))))),
    4 -> SingleChar('a'),
    5 -> SingleChar('b'),
  )

  val testInput3 = """42: 9 14 | 10 1
9: 14 27 | 1 26
10: 23 14 | 28 1
1: "a"
11: 42 31
5: 1 14 | 15 1
19: 14 1 | 14 14
12: 24 14 | 19 1
16: 15 1 | 14 14
31: 14 17 | 1 13
6: 14 14 | 1 14
2: 1 24 | 14 4
0: 8 11
13: 14 3 | 1 12
15: 1 | 14
17: 14 2 | 1 7
23: 25 1 | 22 14
28: 16 1
4: 1 1
20: 14 14 | 1 15
3: 5 14 | 16 1
27: 1 6 | 14 18
14: "b"
21: 14 1 | 1 14
25: 1 1 | 1 14
22: 14 14
8: 42
26: 14 22 | 1 20
18: 15 15
7: 14 5 | 1 21
24: 14 1

abbbbbabbbaaaababbaabbbbabababbbabbbbbbabaaaa
bbabbbbaabaabba
babbbbaabbbbbabbbbbbaabaaabaaa
aaabbbbbbaaaabaababaabababbabaaabbababababaaa
bbbbbbbaaaabbbbaaabbabaaa
bbbababbbbaaaaaaaabbababaaababaabab
ababaaaaaabaaab
ababaaaaabbbaba
baabbaaaabbaaaababbaababb
abbbbabbbbaaaababbbbbbaaaababb
aaaaabbaabaaaaababaa
aaaabbaaaabbaaa
aaaabbaabbaaaaaaabbbabbbaaabbaabaaa
babaaabbbaaabaababbaabababaaab
aabbbbbaabbbaaaaaabbbbbababaaaaabbaaabba"""

  test("day19 parseRules") {
    assertEquals(parseRules(testInput1), rules1)
    assertEquals(parseRules(testInput2), rules2)
  }

  test("day19 match") {
    assertEquals(rules2 `match` "ababbb", true)
    assertEquals(rules2 `match` "abbbab", true)
    assertEquals(rules2 `match` "bababa", false)
    assertEquals(rules2 `match` "aaabbb", false)
    assertEquals(rules2 `match` "aaaabbb", false)
  }

  test("day19 solve1") {
    assertEquals(solve1(testInput3), 3)
  }

  test("day19 solve2") {
    val (rules, messages) = parse(testInput3)
    assertEquals(modifyRule(rules) `match` "babbbbaabbbbbabbbbbbaabaaabaaa", true)
//    assertEquals(solve2(testInput3), 12)
  }
}