Aoc2021-day16.scala

package lascala.aoc2021.day11_20.day16

sealed trait BITS
object BITS:
  final case class Literal(version: Int, value: BigInt) extends BITS
  final case class Operator(version: Int, typeId: Int, subpackets: Seq[BITS])
      extends BITS

  def decode(s: String): Either[String, DecodeResult] =
    val binary = s.map { ch =>
      ("000" + BigInt(ch.toString, 16).toString(2)).takeRight(4)
    }.mkString
    decodeBinary(binary)

  def decodeBinary(binary: String): Either[String, DecodeResult] =
    val (v, xs) = binary.splitAt(3)
    val (t, tail) = xs.splitAt(3)
    BigInt(t, 2).toInt match
      case 4 =>
        val groups                = tail.sliding(5, 5).toSeq
        val (value0, remainders0) = groups.span(_.head == '1')
        val value                 = value0 :+ remainders0.head
        val remainders            = remainders0.tail
        Right(
          DecodeResult(
            Literal(BigInt(v, 2).toInt, BigInt(value.map(_.tail).mkString, 2)),
            remainders.mkString,
          ),
        )
      case typeId =>
        tail.head match
          case '0' =>
            val (l, others)       = tail.tail.splitAt(15)
            val (subs, remainder) = others.splitAt(BigInt(l, 2).toInt)
            @annotation.tailrec
            def loop(xs: String, acc: List[BITS]): Either[String, List[BITS]] =
              if xs.isEmpty then Right(acc.reverse)
              else
                decodeBinary(xs) match
                  case Right(DecodeResult(x, r)) => loop(r, x :: acc)
                  case Left(err)                 => Left(err)
            val Right(packets) = loop(subs, Nil)
            val value = BITS.Operator(BigInt(v, 2).toInt, typeId, packets)
            Right(DecodeResult(value, remainder))
          case '1' =>
            val (l, others) = tail.tail.splitAt(11)
            (0 until BigInt(l, 2).toInt)
              .foldLeft[Either[String, (List[BITS], String)]](
                (Right((Nil, others))),
              ) {
                case (Right((acc, bits)), _) =>
                  decodeBinary(bits) match
                    case Right(DecodeResult(x, r)) => Right((x :: acc, r))
                    case Left(err)                 => Left(err)
                case (Left(err), _) => Left(err)
              } match
              case Right((value, remainder)) =>
                Right(
                  DecodeResult(
                    Operator(BigInt(v, 2).toInt, typeId, value.reverse),
                    remainder,
                  ),
                )
              case Left(err) => Left(err)
end BITS

extension (b: BITS)
  def sumOfVersionNumbers: BigInt = b match
    case BITS.Literal(v, _) => BigInt(v)
    case BITS.Operator(v, _, subs) =>
      BigInt(v) + subs.map(_.sumOfVersionNumbers).sum

  def evaluate: BigInt = b match
    case BITS.Literal(_, value) => value
    case BITS.Operator(_, typeId, subs) =>
      typeId match
        case 0 => subs.map(_.evaluate).sum
        case 1 => subs.map(_.evaluate).product
        case 2 => subs.map(_.evaluate).min
        case 3 => subs.map(_.evaluate).max
        case 5 =>
          val Seq(first, second) = subs
          if first.evaluate > second.evaluate then 1 else 0
        case 6 =>
          val Seq(first, second) = subs
          if first.evaluate < second.evaluate then 1 else 0
        case 7 =>
          val Seq(first, second) = subs
          if first.evaluate == second.evaluate then 1 else 0
end extension

case class DecodeResult(bits: BITS, remainder: String)

def solve1(s: String): BigInt =
  BITS.decode(s).map(_.bits.sumOfVersionNumbers).toOption.get
end solve1

def solve2(s: String): BigInt =
  BITS.decode(s).map(_.bits.evaluate).toOption.get
end solve2

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

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

//val input =

Aoc2021-day16Test.scala

package lascala.aoc2021.day11_20.day16

import minitest.SimpleTestSuite
import hedgehog.minitest.HedgehogSupport
import hedgehog.*

object Day16Test extends SimpleTestSuite with HedgehogSupport:

  example("day15 - decode literal") {
    val input = "D2FE28"
    val expected = BITS.Literal(6, BigInt(2021))
    val remainder = "000"
    BITS.decode(input) ==== Right(DecodeResult(expected, remainder))
  }

  example("day15 - decodeBinary #1") {
    val input = "11010001010"
    val expected = BITS.Literal(6, BigInt(10))
    val remainder = ""
    BITS.decodeBinary(input) ==== Right(DecodeResult(expected, remainder))
  }

  example("day15 - decodeBinary #2") {
    val input = "0101001000100100"
    val expected = BITS.Literal(2, BigInt(20))
    val remainder = ""
    BITS.decodeBinary(input) ==== Right(DecodeResult(expected, remainder))
  }

  example("day15 - decode operator #1") {
    val input = "38006F45291200"
    val expected = BITS.Operator(1, 6, Seq(
      BITS.Literal(6, BigInt(10)),
      BITS.Literal(2, BigInt(20)),
    ))
    val remainder = "0000000"
    BITS.decode(input) ==== Right(DecodeResult(expected, remainder))
  }

  example("day15 - decode operator #2") {
    val input = "EE00D40C823060"
    val expected = BITS.Operator(7, 3, Seq(
      BITS.Literal(2, BigInt(1)),
      BITS.Literal(4, BigInt(2)),
      BITS.Literal(1, BigInt(3)),
    ))
    val remainder = "00000"
    BITS.decode(input) ==== Right(DecodeResult(expected, remainder))
  }

  example("day15 solve 1 case #1") {
    val input = "8A004A801A8002F478"
    solve1(input) ==== 16
  }

  example("day15 solve 1 case #2") {
    val input = "620080001611562C8802118E34"
    solve1(input) ==== 12
  }

  example("day15 solve 1 case #3") {
    val input = "C0015000016115A2E0802F182340"
    solve1(input) ==== 23
  }

  example("day15 solve 1 case #4") {
    val input = "A0016C880162017C3686B18A3D4780"
    solve1(input) ==== 31
  }

  example("day15 solve 2 case #1") {
    val input = "C200B40A82"
    solve2(input) ==== 3
  }

  example("day15 solve 2 case #2") {
    val input = "04005AC33890"
    solve2(input) ==== 54
  }

  example("day15 solve 2 case #3") {
    val input = "880086C3E88112"
    solve2(input) ==== 7
  }

  example("day15 solve 2 case #4") {
    val input = "CE00C43D881120"
    solve2(input) ==== 9
  }

  example("day15 solve 2 case #5") {
    val input = "D8005AC2A8F0"
    solve2(input) ==== 1
  }

  example("day15 solve 2 case #6") {
    val input = "F600BC2D8F"
    solve2(input) ==== 0
  }

  example("day15 solve 2 case #7") {
    val input = "9C005AC2F8F0"
    solve2(input) ==== 0
  }

  example("day15 solve 2 case #8") {
    val input = "9C0141080250320F1802104A08"
    solve2(input) ==== 1
  }