Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Task:

Your program is given a proper, positive simple fraction in the format <numerator>/<denominator>.

For this input, it must find two fractions.

  1. A fraction that is less than the input.
  2. A fraction that is greater than the input.

Both fractions must have a lower denominator than the input. Of all possible fractions, they should have the lowest difference to the input.

Output:

Your program's output must be:

  • A fraction that is smaller than the input, in the format <numerator>/<denominator>.
  • Followed by a space character (ASCII-code 32).
  • Followed by a fraction that is greater than the input, in the format <numerator>/<denominator>.

As follows:

«fraction that is < input» «fraction that is > input»

Rules:

  • All fractions outputted must be in lowest terms.
  • All fractions outputted must be proper fractions.
  • If there are no proper fractions possible that are allowed by the rules, you must output 0 instead of a fraction < input, and 1 instead of a fraction > input.
  • You can choose whether you want to receive the fraction as a command-line argument (e.g. yourprogram.exe 2/5) or prompt for user input.
  • You may assume your program won't receive invalid input.
  • The shortest code (in bytes, in any language) wins.
  • Any non-standard command-line arguments (arguments that aren't normally required to run a script) count towards the total character count.

  • What your program must not do:

    • Depend on any external resources.
    • Depend on having a specific file name.
    • Output anything other than the required output.
    • Take exceptionally long to run. If your program runs over a minute for fractions with a 6-digit numerator and denominator (e.g. 179565/987657) on an average home user's computer, it's invalid.
    • Output fractions with 0 as the denominator. You can't divide by zero.
    • Output fractions with 0 as the numerator. Your program must output 0 instead of a fraction.
    • Reduce an inputted fraction. If the fraction given as input is reducible, you must use the fraction as it is inputted.
  • Your program must not be written in a programming language for which there did not exist a publicly available compiler / interpreter before this challenge was posted.

Examples:

Input: 2/5
Output: 1/3 1/2

Input: 1/2
Output: 0 1

Input: 5/9
Output: 1/2 4/7

Input: 1/3
Output: 0 1/2

Input: 2/4
Output: 1/3 2/3

share|improve this question
1  
Your first example does not match the specification: Both fractions must have a lower denominator than the input. –  Howard Apr 25 at 9:59
    
@Howard Thanks, fixed. –  user2428118 Apr 25 at 10:01
1  
First example, output should be 1/3 1/2. –  Heiko Oberdiek Apr 25 at 10:02
    
@HeikoOberdiek You're right. Fixed. –  user2428118 Apr 25 at 10:19
1  
Define "average home user's computer". Is 90 seconds on a 1.6GHz Intel Atom machine acceptable? –  Jan Dvorak Apr 26 at 6:02

5 Answers 5

up vote 2 down vote accepted

Julia - 127 bytes

I've approached this from a mathematical perspective to avoid need for loops, so this code runs quite fast for large inputs (note: if a/b is the input, then a*b must fit within Int64 (Int32 on 32 bit systems), otherwise nonsense answers are generated - if a and b are both expressible in Int32 (Int16 on 32 bit systems), no problems occur).

\ =div;a,b=int(split(readline(),"/"));k=gcd(a,b);f=b-invmod(a\k,b\k);d=2b-f-b\k;print(a*d\b,d<2?" ":"/$d ",a*f\b+1,"/$f"^(f>1))

Ungolfed:

\ =div               # Overloads backslash as integer division to save characters
a,b=int(split(readline(),"/")) # Read in STDIN in form a/b, convert to int
k=gcd(a,b)           # Get the greatest common denominator
f=b-invmod(a\k,b\k)  # Calculate the denominator of the next biggest fraction
d=2b-f-b\k           # Calculate the denominator of the next smallest fraction
print(a*d\b,d<2?" ":"/$d ",a*f\b+1,"/$f"^(f>1)) # Calculate numerators and print

Basic idea: find the largest d and f less than b that satisfies ad-bc=gcd(a,b) (next smallest) and be-af=gcd(a,b) (next largest), then calculate c and e from there. Resulting output is c/d e/f, unless either d or f is 1, in which case the /d or /f is omitted.

Interestingly, this means that the code also works for positive improper fractions, so long as the input is not an integer (that is, gcd(a,b)=a).

Note that it overloads an infix operator - I chose backslash because it doesn't interfere with anything important and has appropriate precedence, but if this is used in the REPL or a larger piece of code, and then regular code is to be used afterwards, one should use

\ =Base. \

to reset it, or insert the code into a code block. Also note that the first use of the code will cause Julia to also print a warning about this overloading.

On my system, inputting 194857602/34512958303 takes no perceivable time to output 171085289/30302433084 23772313/4210525219

share|improve this answer
    
Testing with 55552/999999 gives me -396/920632 486/936509. –  user2428118 May 22 at 8:20
    
@user2428118 - Are you on a 32 bit system (or using a 32 bit Julia)? I've used "int", which means that on a 32 bit system, it'll use Int32 rather than Int64. int32(55552*999999) gives -282630400. For me, with that test, I get 51143/920632 52025/936509 - note that the denominators are the same, and that 52025-51143 = 486-(-396). I'll add a note to mention this issue. –  Glen O May 22 at 9:54
    
If you want to ensure that the code will work for all Int64 size inputs, you can replace "int" with "int128". With that change, inputting 1234567891234567/2145768375829475878 results in 869253326028691/1510825213275018197 365314565205876/634943162554457681. This change adds just 3 extra characters. –  Glen O May 22 at 10:19
    
Yes, I'm using a 32-bit computer. I'll try it on a 64-bit machine sometime when I've got the time for it. –  user2428118 Jun 2 at 20:00
    
Testing on a 64-bit computer gives the correct result, so I'm accepting this answer. –  user2428118 Jun 7 at 10:03

Python 2.7 - 144

x,y=n,d=map(int,raw_input().split('/'))
while y:x,y=y,x%y
def f(p,a=d):
 while(a*n+p)%d:a-=1
 print(+(p>0),`(a*n+p)/d`+'/'+`a`)[a>1],
f(-x);f(x)

I started with the obvious brute-force solution, but I realized that since the OP wanted to be able to solve instances with six digit numerators and denominators in under a minute, I need a better solution than trying a trillion possibilities. I found a handy formula on the Wikipedia page for the Farey sequence: If a/b, c/d are neighbors in one of the Farey sequences, with a/b<c/d, then b*c-a*b=1. The while loop inside f in my program extends this fact to non-reduced numbers, using the gcd, which the other while loop calculates.

I've golfed this pretty hard already, but I'd love to hear any suggestions.

Edits:

166->162: Removed a and b from the outer program. They were unnecessary.
162->155: str() -> ``
155->154: Added k.
154->152: Removed x from inside the function, passed it as an argument instead.
152->150: Gave a a default value instead of passing it as an argument.
150->146: Changed the initialization of x and y.
146->145: Removed k.
145->144: Changed ... and ... or ... to (...,...)[...], thereby saving a space.

Test cases:

2/5
1/3 1/2

1/2
0 1

2/4
1/3 2/3

179565/987657
170496/937775 128779/708320

12345678/87654321
12174209/86436891 11145405/79132382

The second to last test took under a second on my computer, while the last one took about 5-10 seconds.

share|improve this answer
    
This k=1 is pure wickedness. –  Evpok Apr 25 at 13:32
1  
@Evpok: I was trying to get k=y=n to work, but apparently if you modify a variable inside a function, python wants it to be local. This was the only way to get a local variable in 4 characters. Also, since the fraction is positive and proper, the denominator can't be 1. –  isaacg Apr 25 at 13:36
    
Command-line arguments are easy with Python, so they should have been used for input as instructed here. –  Alex Thornton Apr 25 at 20:45
1  
"You can choose whether you want to receive the fraction as a command-line argument (e.g. yourprogram.exe 2/5) or prompt for user input." –  isaacg Apr 26 at 5:58

Mathematica, 163 bytes

{a,b}=FromDigits/@InputString[]~StringSplit~"/";r=Range[b-1];""<>Riffle[#~ToString~InputForm&/@(#@DeleteCases[#2[a/b*r]/r,a/b]&@@@{{Max,Floor},{Min,Ceiling}})," "]

This is severely limited by the input/output requirement as user input and strings. Dealing with strings is really cumbersome in Mathematica (at least when you want to golf). Doing this the natural way in Mathematica, (using just integers and rationals) I'd probably get this down to 50% of the size.

It can do 6-digit numbers in a few seconds on my machine.

Slightly more readable (not really ungolfed though):

{a, b} = FromDigits /@ InputString[]~StringSplit~"/";
r = Range[b - 1];
"" <> Riffle[#~ToString~
     InputForm & /@ (#[DeleteCases[#2[a/b*r]/r, a/b]] & @@@ {{Max, 
       Floor}, {Min, Ceiling}}), " "]

For the fun of it, doing this "the natural way", i.e. as a function taking numerator and denominator and returning two rationals, this is only 84 characters (so my 50% estimate was actually pretty close):

f[a_,b_]:=#@DeleteCases[#2[a/b*(r=Range[b-1])]/r,a/b]&@@@{{Max,Floor},{Min,Ceiling}}
share|improve this answer

JavaScript, 131

With fat arrow notation and eval calls :

m=>{for(e=eval,n=e(m),i=p=0,q=1;++i</\d+$/.exec(m);)if(n*i>(f=n*i|0))g=f+1,p=f/i>e(p)?f+'/'+i:p,q=g/i<e(q)?g+'/'+i:q;return p+' '+q}

The 179565/987657 stress test is executed in approximately 35 seconds on Firefox, a lot more on Chrome (~ 6 minutes)

Faster method and without eval and fat arrow notation

for(n=eval(m=prompt(a=i=p=0,b=c=d=q=1));++i<m.match(/\d+$/);)if(n*i>(f=n*i|0))g=f+1,p=f*c>i*a?(a=f)+'/'+(c=i):p,q=g*d<i*b?(b=g)+'/'+(d=i):q;alert(p+' '+q)

The 179565/987657 stress test is executed in approximately 5 seconds.

Not golfed :

m=prompt(); //get input
a=0; c=1; //first fraction
b=1; d=1; //second fraction
n=eval(m); //evaluate input
for (i=1; i<m.match(/\d+$/); i++) { //loop from 1 to input denominator
  f=Math.floor(n*i);
  if (n*i > f) { //if fraction not equal to simplification of input
    g=f+1; // f/i and g/i are fractions closer to input
    if (f/i>a/c) a=f, c=i;
    if (g/i<b/d) b=g; d=i; 
  }
}
alert(a+'/'+c+' '+b+'/'+d); //output values handling 0 and 1 correctly
share|improve this answer
    
too... much... eval. EEK –  Jan Dvorak Apr 25 at 11:35
3  
Testing with 2/6 gives 1/3 2/5, however 1/3 is not less than but equal to 2/6. –  user2428118 Apr 25 at 12:12
    
@user2428118 fixed –  Mig Apr 25 at 12:21
    
Why has this answer been accepted so early? –  Evpok Apr 25 at 13:33
1  
@user2428118: You know, you can allow a couple days to pass before accepting solutions. Also, this solution is no longer the shortest. –  isaacg Apr 25 at 13:37

perl, 142 bytes (155 without CPAN)

use bare A..Z;$/="/";N=<>;D=<>;F=N/D;K=G=1;for$H(1..D){J<F&&J>E?(E,I):J>F&&J<G?(G,K):()=(J=$_/H,"$_/$H")for(Z=int F*H)..Z+1}print I||0," $K\n"

Or if CPAN modules are disallowed / 3-4 times faster code is needed:

$/="/";$N=<>;$D=<>;$F=$N/$D;$g=$G=1;for$d(1..$D){$f<$F&&$f>$E?($E,$e):$f>$F&&$f<$G?($G,$g):()=($f=$_/$d,"$_/$d")for($z=int$F*$d)..$z+1}print$e||0," $g\n"

The former version takes 9.55 seconds on my machine, the latter version 2.44 seconds.

Less unreadable:

($N, $D) = split(m[/], <>);
$F = $N / $D;
$G = 1;
foreach $d (1 .. $D) {
    $z = int $F * $d;
    foreach $_ ($z .. $z + 1) {
        $f = $_ / $d;
        ($f < $F && $f > $E ? ($E, $e) :
        ($f > $F && $f < $G ? ($G, $g) : ())) = ($f, "$_/$d");
    }
}
print $e || 0, ' ', $g || 1, "\n";
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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