Advertisement
JoelSjogren

Untitled

Mar 24th, 2020
270
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.96 KB | None | 0 0
  1. def z(x0, y0):
  2.     outx = []
  3.     outy = []
  4.     x = (x0 << 1)
  5.     y = (y0 << 1)
  6.     n = 1
  7.     other = lambda t: t ^ (n << 1)
  8.     parent = lambda t: (t | n) & ~(n << 1)
  9.     b = False  # whether some descendant of x is greater than x0
  10.     c = (x == y)
  11.     while n <= x0:
  12.         nx, x, ny, y = other(x), parent(x), other(y), parent(y)
  13.         if c:
  14.             # after x and y meet on their path to the root
  15.             if nx < x:
  16.                 outx.append(nx)
  17.         elif x == y:
  18.             # they meet for the first time
  19.             if not b:
  20.                 outx.clear()
  21.                 outx.append(other(nx))
  22.             c = True      
  23.         else:
  24.             # x and y have not met yet
  25.             if not b and x < nx:
  26.                 b = True
  27.                 outx.clear()
  28.                 outx.append(other(nx))
  29.             elif nx < x:
  30.                 outx.append(nx)
  31.             outy.append(ny)
  32.         n <<= 1
  33.     return sorted(outx + outy)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement