Add day 16 solutions

4 files changed, 100 insertions, 0 deletions

diff --git a/2021/16/.gitignore b/2021/16/.gitignore
new file mode 100644
index 0000000..ffc46fe
--- /dev/null
+++ b/2021/16/.gitignore
@@ -0,0 +1 @@
+puzzle-[12].py
diff --git a/2021/16/Makefile b/2021/16/Makefile
new file mode 100644
index 0000000..247194a
--- /dev/null
+++ b/2021/16/Makefile
@@ -0,0 +1,8 @@
+all:
+	sed '/START PART 2/,/END PART 2/d' puzzles.py >puzzle-1.py
+	sed '/START PART 1/,/END PART 1/d' puzzles.py >puzzle-2.py
+	chmod +x puzzle-[12].py
+
+.PHONY: clean
+clean:
+	rm -f puzzle-[12].py
diff --git a/2021/16/input b/2021/16/input
new file mode 100644
index 0000000..a746a7f
--- /dev/null
+++ b/2021/16/input
@@ -0,0 +1 @@
+005410C99A9802DA00B43887138F72F4F652CC0159FE05E802B3A572DBBE5AA5F56F6B6A4600FCCAACEA9CE0E1002013A55389B064C0269813952F983595234002DA394615002A47E06C0125CF7B74FE00E6FC470D4C0129260B005E73FCDFC3A5B77BF2FB4E0009C27ECEF293824CC76902B3004F8017A999EC22770412BE2A1004E3DCDFA146D00020670B9C0129A8D79BB7E88926BA401BAD004892BBDEF20D253BE70C53CA5399AB648EBBAAF0BD402B95349201938264C7699C5A0592AF8001E3C09972A949AD4AE2CB3230AC37FC919801F2A7A402978002150E60BC6700043A23C618E20008644782F10C80262F005679A679BE733C3F3005BC01496F60865B39AF8A2478A04017DCBEAB32FA0055E6286D31430300AE7C7E79AE55324CA679F9002239992BC689A8D6FE084012AE73BDFE39EBF186738B33BD9FA91B14CB7785EC01CE4DCE1AE2DCFD7D23098A98411973E30052C012978F7DD089689ACD4A7A80CCEFEB9EC56880485951DB00400010D8A30CA1500021B0D625450700227A30A774B2600ACD56F981E580272AA3319ACC04C015C00AFA4616C63D4DFF289319A9DC401008650927B2232F70784AE0124D65A25FD3A34CC61A6449246986E300425AF873A00CD4401C8A90D60E8803D08A0DC673005E692B000DA85B268E4021D4E41C6802E49AB57D1ED1166AD5F47B4433005F401496867C2B3E7112C0050C20043A17C208B240087425871180C01985D07A22980273247801988803B08A2DC191006A2141289640133E80212C3D2C3F377B09900A53E00900021109623425100723DC6884D3B7CFE1D2C6036D180D053002880BC530025C00F700308096110021C00C001E44C00F001955805A62013D0400B400ED500307400949C00F92972B6BC3F47A96D21C5730047003770004323E44F8B80008441C8F51366F38F240
diff --git a/2021/16/puzzles.py b/2021/16/puzzles.py
new file mode 100644
index 0000000..75e29d1
--- /dev/null
+++ b/2021/16/puzzles.py
@@ -0,0 +1,90 @@
+#!/usr/bin/env python3
+
+from math import prod
+from typing import NamedTuple
+
+data: str
+
+
+class Packet(NamedTuple):
+	pass
+
+
+class Packet(NamedTuple):
+	version: int
+	type: int
+	value: int
+	subpackets: list[Packet]
+
+	def calculate(self) -> int:
+		f = lambda p: p.calculate()
+
+		# START PART 1
+		return self.version + sum(map(f, self.subpackets))
+		# END PART 1 START PART 2
+		match self.type:
+			case 0:
+				return sum(map(f, self.subpackets))
+			case 1:
+				return prod(map(f, self.subpackets))
+			case 2:
+				return min(map(f, self.subpackets))
+			case 3:
+				return max(map(f, self.subpackets))
+			case 4:
+				return self.value
+			case 5:
+				return self.subpackets[0].calculate() > self.subpackets[1].calculate()
+			case 6:
+				return self.subpackets[0].calculate() < self.subpackets[1].calculate()
+			case 7:
+				return self.subpackets[0].calculate() == self.subpackets[1].calculate()
+		# END PART 2
+
+
+def solve() -> Packet:
+	global data
+
+	v = int(data[:3], 2)
+	t = int(data[3:6], 2)
+	data = data[6:]
+
+	if t == 4:
+		val = ""
+		while data[0] == "1":
+			val += data[1:5]
+			data = data[5:]
+		val += data[1:5]
+		data = data[5:]
+		return Packet(v, t, int(val, 2), [])
+
+	l = data[0]
+	data = data[1:]
+
+	if l == "0":
+		length = int(data[:15], 2)
+		data = data[15:]
+		oldlen = len(data)
+
+		subpackets = []
+		while oldlen - len(data) < length:
+			subpackets.append(solve())
+
+		return Packet(v, t, 0, subpackets)
+
+	n = int(data[:11], 2)
+	data = data[11:]
+	return Packet(v, t, 0, [solve() for _ in range(n)])
+
+
+def main() -> None:
+	global data
+
+	with open("input", "r", encoding="utf-8") as f:
+		data = "".join(bin(n)[2:].zfill(8) for n in bytes.fromhex(f.read().strip()))
+
+	print(solve().calculate())
+
+
+if __name__ == "__main__":
+	main()