1  from lib import *
  2  
  3  input = read_input(2021, 18)
  4  
  5  lines = input.splitlines()
  6  
  7  parent = lambda n: n >> 1
  8  left = lambda n: n << 1
  9  right = lambda n: n << 1 | 1
 10  
 11  
 12  def parse(lst):
 13      out = [None] * 64
 14  
 15      def fill(l, n):
 16          if not isinstance(l, list):
 17              out[n] = l
 18          else:
 19              fill(l[0], left(n))
 20              fill(l[1], right(n))
 21  
 22      fill(lst, 1)
 23      return out
 24  
 25  
 26  def explode(lst):
 27      def move_up(i, x):
 28          while lst[i] is None:
 29              i = parent(i)
 30  
 31          lst[i] += x
 32  
 33      for n in range(1 << 4, 1 << 5):
 34          if lst[n] is not None:
 35              continue
 36  
 37          l = lst[a := left(n)]
 38          r = lst[b := right(n)]
 39          if l is None and r is None:
 40              continue
 41  
 42          lst[a] = None
 43          lst[b] = None
 44          lst[n] = 0
 45  
 46          if a - 1 >= 1 << 5:
 47              move_up(a - 1, l)
 48          if b + 1 < 1 << 6:
 49              move_up(b + 1, r)
 50  
 51          return True
 52  
 53      return False
 54  
 55  
 56  def split(lst, n=1):
 57      if (x := lst[n]) is None:
 58          return split(lst, left(n)) or split(lst, right(n))
 59  
 60      if x < 10:
 61          return False
 62  
 63      k = x >> 1
 64      lst[n] = None
 65      lst[left(n)] = k
 66      lst[right(n)] = x - k
 67      return True
 68  
 69  
 70  def add(a, b):
 71      out = [None, None]
 72      for i in range(6):
 73          out += a[1 << i : 1 << i + 1]
 74          out += b[1 << i : 1 << i + 1]
 75  
 76      while explode(out) or split(out):
 77          pass
 78  
 79      return out
 80  
 81  
 82  def magnitude(lst, n=1):
 83      if lst[n] is not None:
 84          return lst[n]
 85  
 86      return 3 * magnitude(lst, left(n)) + 2 * magnitude(lst, right(n))
 87  
 88  
 89  def mk_list(lst, n=1):
 90      if lst[n] is not None:
 91          return lst[n]
 92  
 93      return [mk_list(lst, left(n)), mk_list(lst, right(n))]
 94  
 95  
 96  print(magnitude(reduce(add, (parse(ast.literal_eval(line)) for line in lines))))
 97  
 98  
 99  out = 0
100  
101  for a in lines:
102      for b in lines:
103          if a == b:
104              continue
105  
106          out = max(out, magnitude(add(parse(ast.literal_eval(a)), parse(ast.literal_eval(b)))))
107  
108  print(out)