6
\$\begingroup\$

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

2 Answers 2

3
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ I can't get this code running and producing the correct results... do you have a TIO link? \$\endgroup\$
    – Quintec
    Apr 30, 2021 at 13:27
  • \$\begingroup\$ Added a tio.run link now, sorry for forgetting to do that \$\endgroup\$
    – umnikos
    May 1, 2021 at 16:51
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\$
16
  • \$\begingroup\$ Fail on [[-8],[5]] I guess, though I don't knows what it is \$\endgroup\$
    – l4m2
    Jan 7, 2019 at 5:05
  • \$\begingroup\$ Yeah, invalid. Probably should be 0? \$\endgroup\$
    – ASCII-only
    Jan 7, 2019 at 6:39
  • \$\begingroup\$ half fixed \$\endgroup\$
    – ASCII-only
    Jan 7, 2019 at 8:11
  • \$\begingroup\$ there we go, now to golf it \$\endgroup\$
    – ASCII-only
    Jan 7, 2019 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, 2019 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.