Surreal Numbers

Surreal Numbers are one way of describing numbers using sets. In this challenge you will determine the value of a surreal number.

Intro

A surreal number consists of two sets: a left and right. The value of the surreal number must be greater than all numbers in the left set and less than all numbers in the right set. We define 0 as having nothing in each set, which we write as {|}. Each surreal number also has a birth date. 0 is born on day 0. On each successive day, new surreal numbers are formed by taking the numbers formed on previous days and placing them in the left/right sets of a new number. For example, {0|} = 1 is born on day 1, and {|0} = -1 is also born on day 1.

To determine the value of a surreal number, we find the number "between" the left and right sets that was born earliest. As a general rule of thumb, numbers with lower powers of 2 in their denominator are born earlier. For example, the number {0|1} (which is born on day 2 by our rules) is equal to 1/2, since 1/2 has the lowest power of 2 in its denominator between 0 and 1. In addition, if the left set is empty, we take the largest possible value, and vice versa if the right set is empty. For example, {3|} = 4 and {|6} = 5.

Note that 4 and 5 are just symbols that represent the surreal number, which just happen to align with our rational numbers if we define operations in a certain way.

Some more examples:

{0, 1|} = {1|} = {-1, 1|} = 2
{0|3/4} = 1/2
{0|1/2} = 1/4
{0, 1/32, 1/16, 1/2 |} = 1


Input

A list/array of two lists/arrays, which represent the left and right set of a surreal number. The two lists/arrays will be sorted in ascending order and contain either dyadic rationals (rationals with denominator of 2^n) or other surreal numbers.

Output

A dyadic rational in either decimal or fraction form representing the value of the surreal number.

Examples

Input -> Output
[[], []] -> 0
[[1], []] -> 2
[[], [-2]] -> -3
[[0], [4]] -> 1
[[0.25, 0.5], [1, 3, 4]] -> 0.75
[[1, 1.5], [2]] -> 1.75
[[1, [[1], [2]]], [2]] -> 1.75


This is , so shortest code wins.

• Isn't 0 always born the earliset, since it's born on day 0? Jan 3, 2019 at 23:42
• @EmbodimentofIgnorance Yes, but 0 isn't always within the bounds of the left and right set. Jan 3, 2019 at 23:44
• What does "between" the two sets mean? Jan 3, 2019 at 23:50
• And for the last example, is the [[1],[2]] a surreal number? If so, do we evaluate the value of surreal numbers inside the set first, then use the values as regular rational integers to find the value of the outside surreal number? Jan 3, 2019 at 23:56
• @EmbodimentofIgnorance For your second comment: yes, that's correct on both counts. Jan 4, 2019 at 0:07

Python 3.7, 228197 184 bytes

Thanks to @LyricLy and friends for helping me golf this down a lot

1e999 stolen from @Quintec's solution

m=1e999
g=lambda p:[f(*x)if[]==x*0else x for x in p]
def f(l,h):
h=min(g(h+[m]));l=max(g(l+[-m]));s=1
while h-l<=1:l*=2;h*=2;s*=2
return-(-h//1+1)/s if h<=0else l*h>=0and(l//1+1)/s


Try it online!

• I can't get this code running and producing the correct results... do you have a TIO link? Apr 30, 2021 at 13:27
• Added a tio.run link now, sorry for forgetting to do that May 1, 2021 at 16:51

Python, 371362261251248241236234 231 bytes

-122 bytes thanks to @ASCII-only

def f(s):
if s<[]:return s
a=map(f,s[1]+[1e999,-1e999]+s[0]);m,n,u=a[-1],a[0],1
while n-m<=1:m*=2;n*=2;u/=2.
x,y=abs(m)-1,abs(n)-1;s=m>0>n or m<0<n;r=[[m-x*s,m+x*s][m<0]+1,[n-y*s,n+y*s][n<0]-1][x>y];return u*int([0,r][r<"m"])


Try it online!

• Fail on [[-8],[5]] I guess, though I don't knows what it is
– l4m2
Jan 7, 2019 at 5:05
• Yeah, invalid. Probably should be 0? Jan 7, 2019 at 6:39
• half fixed Jan 7, 2019 at 8:11
• there we go, now to golf it Jan 7, 2019 at 8:25
• Still invalid though, only works up to 9e9 in either direction, unless you change the spec to, say, require only up to the limits of a float32 or float64 Jan 7, 2019 at 8:48