5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Isn't 0 always born the earliset, since it's born on day 0? \$\endgroup\$ – Embodiment of Ignorance Jan 3 at 23:42
  • \$\begingroup\$ @EmbodimentofIgnorance Yes, but 0 isn't always within the bounds of the left and right set. \$\endgroup\$ – Quintec Jan 3 at 23:44
  • \$\begingroup\$ What does "between" the two sets mean? \$\endgroup\$ – Embodiment of Ignorance Jan 3 at 23:50
  • \$\begingroup\$ 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? \$\endgroup\$ – Embodiment of Ignorance Jan 3 at 23:56
  • \$\begingroup\$ @EmbodimentofIgnorance For your second comment: yes, that's correct on both counts. \$\endgroup\$ – Quintec Jan 4 at 0:07
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Fail on [[-8],[5]] I guess, though I don't knows what it is \$\endgroup\$ – l4m2 Jan 7 at 5:05
  • \$\begingroup\$ Yeah, invalid. Probably should be 0? \$\endgroup\$ – ASCII-only Jan 7 at 6:39
  • \$\begingroup\$ half fixed \$\endgroup\$ – ASCII-only Jan 7 at 8:11
  • \$\begingroup\$ there we go, now to golf it \$\endgroup\$ – ASCII-only Jan 7 at 8:25
  • \$\begingroup\$ 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 \$\endgroup\$ – ASCII-only Jan 7 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.