Surreal Numbers

Question

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 code-golf, so shortest code wins.

• Gymhgy: Isn't 0 always born the earliset, since it's born on day 0?
• Quintec: @EmbodimentofIgnorance Yes, but 0 isn't always within the bounds of the left and right set.
• Gymhgy: What does "between" the two sets mean?
• Gymhgy: 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?
• Quintec: @EmbodimentofIgnorance For your second comment: yes, that's correct on both counts.

Answer 1

Python 3.7, (削除) 228 (削除ここまで) (削除) 197 (削除ここまで) 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!

• Quintec: I can't get this code running and producing the correct results... do you have a TIO link?
• umnikos: Added a tio.run link now, sorry for forgetting to do that

Answer 2

Python, (削除) 371 (削除ここまで) (削除) 362 (削除ここまで) (削除) 261 (削除ここまで) (削除) 251 (削除ここまで) (削除) 248 (削除ここまで) (削除) 241 (削除ここまで) (削除) 236 (削除ここまで) (削除) 234 (削除ここまで) 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!

• l4m2: Fail on [[-8],[5]] I guess, though I don't knows what it is
• ASCII-only: Yeah, invalid. Probably should be 0?
• ASCII-only: half fixed
• ASCII-only: there we go, now to golf it
• ASCII-only: 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