Kotlin solution for https://adventofcode.com/2021/day/16

submarine.kt

private fun readChar(): Char = readString()[0]
private fun readChars(): CharArray = readString().toCharArray()
private fun readInt(): Int = readLine()!!.toInt()
private fun readInts(): List<Int> = readLine()!!.trim().split(" ").map(String::toInt)
private fun readLong(): Long = readLine()!!.toLong()
private fun readLongs(): List<Long> = readLine()!!.trim().split(" ").map(String::toLong)
private fun readString(): String = readLine()!!.trim()
private fun readStrings(): List<String> = readLine()!!.trim().split(" ")

data class Header(val version: Long, val typeId: Long)

data class Group(val done: Boolean, val nybble: Long)

sealed class Packet

data class LiteralValue(val header: Header, val literalValue: Long) : Packet()

sealed class Operator : Packet()

data class Sum(val header: Header, val subPackets: List<Packet>) : Operator()

data class Product(val header: Header, val subPackets: List<Packet>) : Operator()

data class Minimum(val header: Header, val subPackets: List<Packet>) : Operator()

data class Maximum(val header: Header, val subPackets: List<Packet>) : Operator()

data class GreaterThan(val header: Header, val subPackets: List<Packet>) : Operator()

data class LessThan(val header: Header, val subPackets: List<Packet>) : Operator()

data class EqualTo(val header: Header, val subPackets: List<Packet>) : Operator()


data class UnknownPacket(val header: Header) : Packet()

fun parseThreeBits(binaryString: String, start: Int) = run {
	val end = start + 3
	val num = binaryString.substring(start until end).toLong(2)
	Pair(num, end)
}

fun parseVersion(binaryString: String, start: Int) = parseThreeBits(binaryString, start)

fun parseTypeId(binaryString: String, start: Int) = parseThreeBits(binaryString, start)

fun parseHeader(binaryString: String, start: Int) = run {
	val versionResult = parseVersion(binaryString, start)
	val typeIdResult = parseTypeId(binaryString, versionResult.second)
	Pair(Header(versionResult.first, typeIdResult.first), typeIdResult.second)
}

fun parseNybble(binaryString: String, start: Int) = run {
	val end = start + 5
	val done = binaryString[start] == '0'
	val nybble = binaryString.substring(start + 1 until end).toLong(2)
	Pair(Group(done, nybble), end)
}

fun parseLiteralValue(binaryString: String, start: Int) = run {
	var nybbleResult = Pair(Group(false, 0L), start)
	var literalValue = 0L
	do {
		nybbleResult = parseNybble(binaryString, nybbleResult.second)
		literalValue = (literalValue shl 4) or nybbleResult.first.nybble
	} while (!nybbleResult.first.done)
	Pair(literalValue, nybbleResult.second)
}

fun parseBits(binaryString: String, start: Int, length: Int) =
	Pair(binaryString.substring(start until start + length).toLong(2), start + length)

fun parseLengthTypeId(binaryString: String, start: Int) = Pair(binaryString[start] == '1', start + 1)

fun parseOperator0SubPackets(binaryString: String, start: Int) = run {
	val lengthResult = parseBits(binaryString, start, 15)
	val subPacketsStart = lengthResult.second

	val subPackets = mutableListOf<Packet>()
	var subPacketResult: Pair<Packet?, Int> = Pair(null, subPacketsStart)
	do {
		subPacketResult = parsePacket(binaryString, subPacketResult.second)
		subPackets.add(subPacketResult.first)
	} while (subPacketResult.second - subPacketsStart < lengthResult.first)

	Pair(subPackets, subPacketResult.second)
}

fun parseOperator1SubPackets(binaryString: String, start: Int) = run {
	val lengthResult = parseBits(binaryString, start, 11)
	val subPackets = mutableListOf<Packet>()
	var subPacketResult: Pair<Packet?, Int> = Pair(null, lengthResult.second)
	for (i in 0 until lengthResult.first) {
		subPacketResult = parsePacket(binaryString, subPacketResult.second)
		subPackets.add(subPacketResult.first)
	}

	Pair(subPackets, subPacketResult.second)
}

fun parsePacket(binaryString: String, start: Int = 0): Pair<Packet, Int> = run {
	val headerResult = parseHeader(binaryString, start)
	var header = headerResult.first
	if (header.typeId == 4L) {
		val literalResult = parseLiteralValue(binaryString, headerResult.second)
		Pair(LiteralValue(header, literalResult.first), literalResult.second)
	} else {
		val lengthTypeIdResult = parseLengthTypeId(binaryString, headerResult.second)
		val subPacketsResult =
			if (lengthTypeIdResult.first) {
				parseOperator1SubPackets(binaryString, lengthTypeIdResult.second)
			} else {
				parseOperator0SubPackets(binaryString, lengthTypeIdResult.second)
			}

		Pair(
			when (header.typeId) {
				0L -> Sum(header, subPacketsResult.first)
				1L -> Product(header, subPacketsResult.first)
				2L -> Minimum(header, subPacketsResult.first)
				3L -> Maximum(header, subPacketsResult.first)
				5L -> GreaterThan(header, subPacketsResult.first)
				6L -> LessThan(header, subPacketsResult.first)
				7L -> EqualTo(header, subPacketsResult.first)
				else -> UnknownPacket(header)
			}, subPacketsResult.second
		)
	}
}

fun evaluate(packet: Packet): Long =
	when (packet) {
		is LiteralValue -> packet.literalValue
		is Sum -> packet.subPackets.fold(0) { acc, subPacket -> acc + evaluate(subPacket) }
		is Product -> packet.subPackets.fold(1) { acc, subPacket -> acc * evaluate(subPacket) }
		is Minimum -> packet.subPackets.fold(evaluate(packet.subPackets[0])) { acc, subPacket ->
			acc.coerceAtMost(
				evaluate(
					subPacket
				)
			)
		}
		is Maximum -> packet.subPackets.fold(evaluate(packet.subPackets[0])) { acc, subPacket ->
			acc.coerceAtLeast(
				evaluate(
					subPacket
				)
			)
		}
		is GreaterThan -> if (evaluate(packet.subPackets[0]) > evaluate(packet.subPackets[1])) 1 else 0
		is LessThan -> if (evaluate(packet.subPackets[0]) < evaluate(packet.subPackets[1])) 1 else 0
		is EqualTo -> if (evaluate(packet.subPackets[0]) == evaluate(packet.subPackets[1])) 1 else 0
		else -> throw Exception("Unknown Packet")
	}

@OptIn(ExperimentalStdlibApi::class)
fun main() {
	var nextLine = readString()

	nextLine@ while (nextLine.isNotEmpty()) {
		val d = nextLine.map { it.digitToInt(16).toString(2).padStart(4, '0') }.joinToString("")

		val packetResult = parsePacket(d)

//		println("packetResult: $packetResult")
//		println("versionSum: ${versionSum(packetResult.first)}")
		println(evaluate(packetResult.first))
		nextLine = readString()
	}
}