6
\$\begingroup\$

Goal

Your goal is to find the simplest value in an open interval. In other words, given two values a,b with a<b, output the simplest x with a<x<b. This is a code golf, so fewest bytes wins.

Simplicity

All values in this problem are dyadic rationals, which means their binary expansions are finite, or equivalently, are rationals in simplest form a/2^b for some integer a and non-negative integer b. Integers are dyadic rationals with b=0.

Being simpler means having smaller b, tiebroken by smaller absolute value |a|.

Equivalently in terms of binary expansions, to find the simpler number:

  1. Take the one with a shorter fractional part (fewer binary digits after the point).
  2. In case of tie, take the lexicographically earlier one with length the primary sort, ignoring sign.

So, the numbers in simplicity order are

0, ±1, ±2, ±3, ±4, ...
±1/2, ±3/2, ±5/2, ...
±1/4, ±3/4, ±5/4, ...
±1/8, ±3/8, ... 
±1/16, ...
...

There's no need to say which of ±x is simpler because any interval that contains both candidates also contains 0, which is simpler than both.

(A bit of background and motivation: In combinatorial game theory, positions in a two-player games have a numerical value representing magnitude of advantage, with the sign saying which player is favored. This value is determined recursively from the two values resulting from the best move of each player. You might guess that one averages them, but in fact it's the simplest value in between.)

Program requirements

Write, in as few bytes as possible, a program or named function that takes two dyadic rationals a,b and outputs the simplest dyadic rational x with a<x<b. Input can be function input or STDIN, and output can be function return or printing.

Input format

Two dyadic rationals a,b in whatever type your languages use for real or finite-precision binary values (float, double, etc). Fraction or rational types that store the value as a numerator and denominator are not acceptable. If you language has no valid type (and only then), you may use binary strings like 101.1101, or post a comment and we'll work something out.

You are guaranteed that a,b are dyadic rationals and a<b. Integer values will be given like 3.0, not 3.

You can assume you have sufficient precision to store the values, the output, and any intermediate steps exactly. So, you shouldn't worry about precision or overflows. I won't give an explicit bound on inputs, but your algorithm should take a reasonable amount of time on inputs like the test cases.

You may take your two numbers in any reasonable built-in container like pair, tuple, list, array, or set. Structures specifically representing intervals are not allowed though.

Output

The simplest dyadic rational strictly between a and b. The same rules for the input types apply, except outputting 3 rather than 3.0 is OK.

Test cases

(-1.0, 1.0)
0.0
(0.0, 2.0)
1.0
(0.0, 4.0)
1.0
(0.5, 2.0)
1.0
(-3.25, -2.5)
-3.0
(-4, 1.375)
0.0
(4.5, 4.625)
4.5625
(-1.875, -1.5)
-1.75
\$\endgroup\$
  • \$\begingroup\$ Related: codegolf.stackexchange.com/q/26278/8478 \$\endgroup\$ – Martin Ender Oct 1 '14 at 22:28
  • \$\begingroup\$ @MartinBüttner "Fraction or rational types that store the value as a numerator and denominator are not acceptable." But if your rational type is just real numbers stored internally as rational for exact precision and you don't use things like .get_denom(), it's OK. Also, the output should be not be written in fraction form. \$\endgroup\$ – xnor Oct 1 '14 at 22:32
  • 1
    \$\begingroup\$ Ugh, it's getting late and my attention span is apparently dwindling... \$\endgroup\$ – Martin Ender Oct 1 '14 at 22:33
  • \$\begingroup\$ Probably should specify that there is at least one representable value between a and b. \$\endgroup\$ – feersum Oct 2 '14 at 0:45
  • \$\begingroup\$ @feersum How would that fail to be the case? \$\endgroup\$ – xnor Oct 2 '14 at 0:48
4
\$\begingroup\$

Python 2 - 100

I think I revised my entire method for this answer a good 4 or 5 times (which is probably an indication that it's a good code-golf question). I don't know if this answer can be golfed down any more but I do feel as if I'm missing some more clever methodological ways to shorten this.

def f(a,b,i=1.):
    r=0if a<0 else(a*i+1)//1/i
    return-f(-b,-a,i)if b<=0 else r if r<b else f(a,b,i*2)
\$\endgroup\$
  • \$\begingroup\$ This code doesn't seem to work for large-magnitude numbers. Note that x + 1 may be equal to x, if x is greater than 2**53. \$\endgroup\$ – feersum Oct 2 '14 at 0:58
  • \$\begingroup\$ I didn't intend for overflows or representation limits to be a concern. I've edited to make that clear. \$\endgroup\$ – xnor Oct 2 '14 at 1:06
  • \$\begingroup\$ How is that an overflow? It's only the result of an approach that doesn't work. \$\endgroup\$ – feersum Oct 2 '14 at 1:09
  • \$\begingroup\$ @feersum "You can assume you have sufficient precision to store the values, the output, and any intermediate steps exactly." Is that not sufficient? \$\endgroup\$ – xnor Oct 2 '14 at 1:10
  • \$\begingroup\$ OK, I see you have edited it just now. I prefer the non-watered down version. Or maybe I will make one that uses the intermediate step of adding 2^-1074 until the answer is reached:) \$\endgroup\$ – feersum Oct 2 '14 at 1:16
4
\$\begingroup\$

Haskell, 61 88 75 73

p!q|p<0= -(-q)!(-p)|r<q=max r 0|0<1=(2*p)!(2*q)/2where r=toEnum$floor$p+1

this checks if there is a whole number between the two, and if yes, return the smallest one. if not, multiply the numbers by 2, apply them recursively, divide by 2 and return.
at least, this is how it works in my mind. the actual code is a bit different.

thanks to xnor for his rounding magic

\$\endgroup\$
  • \$\begingroup\$ I don't think this works for ranges that contain 0. Trying -3!4 gives -3.5, instead of 0. I think you may be assuming that the inputs have the same sign, although, I admit I don't know much about Haskell, am I doing something wrong? (and sorry, if I am) \$\endgroup\$ – FryAmTheEggman Oct 3 '14 at 14:39
  • \$\begingroup\$ @FryAmTheEggman negatives in Haskell are a bit annoying. -3!4 is parsed as -(3!4), which should be -3.5. but you are infact right, (-3)!4 is -2.0. I'll fix it when i can \$\endgroup\$ – proud haskeller Oct 3 '14 at 14:43
  • \$\begingroup\$ Ah, thanks for that tip :) You might be able to try multiplying (or just returning?) your result by 0 if p*q<0. Again, don't know much about Haskell, but that is usually a good way to check for having different signs. \$\endgroup\$ – FryAmTheEggman Oct 3 '14 at 14:56
1
\$\begingroup\$

Java - 157 187 186

Probably could be golfed more.

Thanks to Quincunx for a byte.

void f(float a,float b){for(float i=1,d;;i*=2){for(d=0;d<i*Math.max(Math.abs(b),Math.abs(a));d++){for(float x:new float[]{d/i,-d/i}){if(x<b&&x>a){System.out.print(x);System.exit(0);}}}}}

Brute forces all values of the numerator (positive and negative) while the denominator doubles each time.

\$\endgroup\$
  • \$\begingroup\$ I don't think imports are free. \$\endgroup\$ – Ypnypn Oct 2 '14 at 0:07
  • \$\begingroup\$ This doesn't work for large values either. E.g. if I call f((float)1e30, (float)1e31) it appears to go into an infinite loop. Or was I just not patient enough? \$\endgroup\$ – feersum Oct 2 '14 at 1:07
  • \$\begingroup\$ I edited the rules to not worry about precision or representation issues. Floats are fine. \$\endgroup\$ – xnor Oct 2 '14 at 1:46
  • \$\begingroup\$ @ypnypn This is an issue that comes in Java in that you can't do imports without wrapping the function in a class. Here's what I say: You can have a "floating" import statement separate from the function, but the chars in the import statement count, including a char for newline. So this is 189 chars. \$\endgroup\$ – xnor Oct 2 '14 at 1:49
  • \$\begingroup\$ @feersum you probably aren't patient enough :) \$\endgroup\$ – Stretch Maniac Oct 2 '14 at 2:37
1
\$\begingroup\$

Python 3: 80 bytes

g=lambda a,b:-g(-b,-a)if b<=0 else int(a+1)*(a>=0)if-~int(a)<b else g(2*a,2*b)/2

Ungofed:

def g(a,b):
    if b<=0:return -g(-b,-a)
    if int(a+1)<b:return int(a+1)*(a>=0)
    return g(2*a,2*b)/2

Can probably be golfed more by changing the if/else structure to and/or. The obvious transformation fails due to non-short-circuiting on the Falsey output of 0, but there's likely a rearrangement that does it.

The space in b<=0 else can't be removed as usual because the start letter e is parsed as part of number literals like 1e6.

\$\endgroup\$
  • \$\begingroup\$ can I port your code? \$\endgroup\$ – proud haskeller Oct 5 '14 at 12:38
  • \$\begingroup\$ @proudhaskeller Definitely. \$\endgroup\$ – xnor Oct 5 '14 at 19:17
1
\$\begingroup\$

ES6, 68 67 59

g=(a,b)=>(x=~~(a+1),b>0?x<b?x*(x>0):g(2*a,2*b)/2:-g(-b,-a))

this is a port of xnor's solution (basically, the new thing in it was that it checked for having 0 in the range by *(a>=0). couldn't do this in Haskell because Haskell has a type system :) )

this is the first time I used ES6 ever, so this might still be golfable.

\$\endgroup\$
  • \$\begingroup\$ For the type issue of x*(a>=0), an alternative is max(x,0). Can you do that efficiently in Haskell? \$\endgroup\$ – xnor Oct 5 '14 at 19:41
  • \$\begingroup\$ @xnor your rounding magic is ingenious \$\endgroup\$ – proud haskeller Oct 5 '14 at 19:54
  • \$\begingroup\$ Also, you can do x*(x>0). I couldn't do that in Python because I can't assign x. \$\endgroup\$ – xnor Oct 5 '14 at 19:55
  • \$\begingroup\$ I know this is an old post, but I believe ~~(a+1) is the same as -~a, saving 4 bytes. Also, with some rearrangement, you can save another 3 bytes: g=(a,b)=>b>0?-~a<b?-~a*(~a<0):g(2*a,2*b)/2:-g(-b,-a) \$\endgroup\$ – ETHproductions Sep 8 '16 at 20:10
1
\$\begingroup\$

C, 98 bytes

Using a recursive algorithm (and the fact that f(a,b) = f(2*a,2*b)/2). I also removed some bugs. The right answer is:

float n(float a, float b){return (floor(a+1)<ceil(b))?(a<0?(b>0?0:ceil(b-1)):floor(a+1)):n(2*a,2*b)/2;}

Which, to meet the prerequisites, is 19 bytes longer than the original one (of 79 bytes)

Full code:

#include <stdio.h>
#include <math.h>
float n(float a, float b){return (floor(a+1)<ceil(b))?(a<0?(b>0?0:ceil(b-1)):floor(a+1)):n(2*a,2*b)/2;}
main() 
{
    float a = -4.0;
    float b = -1.4;
    printf("%f",n(a,b));
}

Just copy-paste it into a random online c compiler and run it.

\$\endgroup\$
  • \$\begingroup\$ Does this give f(-4, 1.375)=0.0? I don't see the code handling that case. \$\endgroup\$ – xnor Oct 2 '14 at 19:46
  • \$\begingroup\$ a and b seem to be reversed, and I think you may have misread the question a bit. n(2.1,1.2) gives me 3.0 instead of 1.5, and any integer input, like n(2.0,1.0) will crash because ceil(a)>a is always false. \$\endgroup\$ – FryAmTheEggman Oct 2 '14 at 20:14
  • \$\begingroup\$ @FryAmTheEggman but the spec tells to assume that the first parameter is smaller \$\endgroup\$ – proud haskeller Oct 3 '14 at 8:05
  • \$\begingroup\$ Does this work on negatives? Your code chooses the smallest whole number in the range, so for example on -7.5, -3.5 this would choose -7 when the result should be -4 \$\endgroup\$ – proud haskeller Oct 3 '14 at 8:17
  • 1
    \$\begingroup\$ @Gerwin when are you going to fix this? \$\endgroup\$ – proud haskeller Oct 4 '14 at 10:52
0
\$\begingroup\$

Perl (89)

most probably this can still be golfed

sub S{($q,$w)=@_;$m=1,$r=0;until($q<$r&&$r<$w){$r=int$q+1;$r<$w||map$_*=2,$m,$q,$w}$r/$m}
\$\endgroup\$

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.