1  from lib import *
 2  
 3  input = read_input(2021, 16)
 4  
 5  lines = input.splitlines()
 6  
 7  
 8  bits = io.StringIO("".join(bin(int(x, 16))[2:].zfill(4) for x in lines[0]))
 9  
10  
11  def read(n):
12      return int(bits.read(n), 2)
13  
14  
15  def parse1():
16      version = read(3)
17      t = read(3)
18      if t == 4:
19          lit = 0
20          while True:
21              c = read(1)
22              lit *= 16
23              lit += read(4)
24              if not c:
25                  break
26          return version
27      else:
28          vals = []
29          if not read(1):
30              c = read(15) + bits.tell()
31              while bits.tell() < c:
32                  vals.append(parse1())
33          else:
34              for _ in range(read(11)):
35                  vals.append(parse1())
36          return version + sum(vals)
37  
38  
39  print(parse1())
40  
41  
42  bits = io.StringIO("".join(bin(int(x, 16))[2:].zfill(4) for x in lines[0]))
43  
44  
45  def parse2():
46      read(3)
47      t = read(3)
48      if t == 4:
49          lit = 0
50          while True:
51              c = read(1)
52              lit *= 16
53              lit += read(4)
54              if not c:
55                  break
56          return lit
57      else:
58          vals = []
59          if not read(1):
60              c = read(15) + bits.tell()
61              while bits.tell() < c:
62                  vals.append(parse2())
63          else:
64              for _ in range(read(11)):
65                  vals.append(parse2())
66          match t:
67              case 0:
68                  return sum(vals)
69              case 1:
70                  return product(vals)
71              case 2:
72                  return min(vals)
73              case 3:
74                  return max(vals)
75              case 5:
76                  return int(vals[0] > vals[1])
77              case 6:
78                  return int(vals[0] < vals[1])
79              case 7:
80                  return int(vals[0] == vals[1])
81  
82  
83  print(parse2())