adventofcode202318

from collections import defaultdict

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

segments = defaultdict(list)

i, j = 0, 0
for dir, s in data:
  if dir == 1:
    segments[j].append([i, i+s])
  if dir == 3:
    segments[j].append([i-s, i])
  i, j = i+s*dy[dir], j+s*dx[dir]

in_segments = []
ans = 0
prev_x = 0
for x in sorted(segments):
  # add in areas since last change
  ans += sum((b-a+1)*(x-prev_x) for a,b in in_segments)
  prev_x = x

  for new_seg in sorted(segments[x]):
    # find intersections with existing in_segments
    delete = set()
    for i, in_seg in enumerate(in_segments):
      # if intersect
      if max(new_seg[0], in_seg[0]) < min(new_seg[1], in_seg[1]):
        mina, maxa = sorted((new_seg[0], in_seg[0]))
        minb, maxb = sorted((new_seg[1], in_seg[1]))

        if mina == maxa and minb == maxb:
          delete.add(i)
          # removing [mina, maxa]
          ans += (maxb - mina+1)
          break
        elif minb == maxb:
          in_seg[:] = [mina, maxa]
          # removing [maxa+1, maxb]
          ans += (maxb - (maxa+1)+1)
          break
        elif mina == maxa:
          in_seg[:] = [minb, maxb]
          # removing [mina, minb-1]
          ans += (minb-1 - (mina)+1)
          break
        else:
          in_seg[:] = [mina, maxa]
          new_seg = [minb, maxb]
          # removing [maxa+1, minb-1]
          ans += (minb - maxa - 1)
    else:
      # hack - could do this whole section inline above without sorting
      in_segments.append(new_seg[:])
      in_segments.sort()

      i = 0
      while i < len(in_segments)-1:
        if in_segments[i][-1] == in_segments[i+1][0]:
          in_segments[i][-1] = in_segments[i+1][1]
          del in_segments[i+1]
        else:
          i += 1

    if delete:
      for i in delete:
        del in_segments[i]

print(ans)