Simplify a fraction

Question

Winner: Ian D. Scott's answer, by one byte (48 bytes)! Superb!

Your program must accept input from a fraction that can be simplified, then simplify it.

Rules:

• If the fraction is already in its most simplified form, you must inform the user
• No built-in functions to do this
• The user must type the number at some point, however the method the program reads it does not matter. It can be with stdin, console.readline, etc. As long as the user types 9/18 (for example) at some point, it is valid
• Output must be done with stdout, console.writeline, etc...
• The fraction will be put in as x/y, and must output as a/b
• The fraction must output the most simplified form. For example, 8/12 -> 6/9 is not valid, the only valid solution is 2/3.

---

• This contest ends on August 9th, 2014 (7 days from posting)
• This is a code-golf question, so the shortest code wins

Answer 1

Python - 69 48

The first thing to do is to represent it in python's native format for storing fractions, namely the Fraction class.

print(__import__("fractions").Fraction(input()))

Now we simplify... but look! It's already simplified.

Does this count as using a built-in function? It is not intended specifically for simplifying, and Fraction is a class anyway, not a function.

I didn't call any simplifying function, so it's not my fault if python decides to do it itself.

Answer 2

><> (92)

0v
+>>>>>>a*ic4*-:0(?v
v@:{:~^?=2l0  ,a~ <
>:?!v:@%
=1:~<;no-1*4c,n,@:/?
|oooo;!'simplest' /

I know I can get this lower, I'll golf it a bit more in the morning.

Basic explanation: First two lines, and the latter half of the third, are all for reading numbers. Sadly, ><> has no way to do that, so the parsing takes up half the program.

4th line is a simple iterative gcd calculation. I'm surprised at how well ><> did on byte count for the actual algorithm. If it wasn't for the terrible i/o, it could actually be a reasonable golf language.

Last two lines are just for printing the result and dividing the original numbers by the gcd.

Answer 3

GolfScript, 49 characters

'/'/{~}%.~{.@\%.}do;:G({{G/}%'/'*}{;'simplest'}if

Run the two testcases here:

> 8/12
2/3

> 7/12
simplest

Answer 4

JavaScript 101

For once, a solution not using EcmaScript 6

v=prompt().split('/');for(a=v[0]|0,b=v[1]|0;a-b;)a>b?a-=b:b-=a;
alert(a>1?v[0]/a+'/'+v[1]/a:'Reduced')

But with E6 could be 93

[n,d]=prompt().split('/');for(a=n|0,b=d|0;a-b;)a>b?a-=b:b-=a;
alert(a>1?n/a+'/'+d/a:'Reduced')

Answer 5

PHP>=7.1, 76 Bytes (Non-Competing)

for([$x,$y]=explode("/",$argn),$t=1+$x;$y%--$t||$x%$t;);echo$x/$t."/".$y/$t;

Online Version

Answer 6

Python 2.7, 124

from fractions import gcd;x,y=map(int,raw_input().split('/'));g=gcd(x,y);print'%d/%d'%(x/g,y/g)if g!=1 else'Already reduced'

Very simple solution, though I know it would be shorter in many other languages.

I used an imported gcd but if it counts as a built-in fraction reducer it could be implemented directly.

Answer 7

Python 2 (82)

A,B=a,b=map(int,raw_input().split("/"))
while b:a,b=b,a%b
print`A/a`+"/"+`B/a`,a<2

Prints a Boolean afterward to say whether the original was in simplest form. Just does the usual GCD algorithm. Most of the characters are spent on input/output.

Answer 8

C, 94

Just brute force guess and check, for GCD starting at a|b down to 1;

main(a,b,c){scanf("%d/%d",&a,&b);for(c=a|b;--c;)if(a%c+b%c<1)a/=c,b/=c;printf("%d/%d\n",a,b);}

Answer 9

Rebmu (104 characters)

P"/"rSst[a b]paSp AtiA BtiB Ca DbFOiMNcD 1 -1[izADmdCiMDdI[CdvCi DdvDi]]QapAPtsCpTSdIa^e?aCe?bD[Q"Err"]Q

Unmushed:

P"/"
rS
; extract numerator to a, denominator to b
st [a b] pa s p
; convert a,b to integers
AtiA
BtiB
; set c=a, d=b
Ca Db
; loop from min(c,d) to 1
fo i mn c d 1 -1[
    ; check if (c mod i) + (d mod i) is 0
    iz ad md c i md d i [
        ; divide c, d by i
        Cdv c i
        Ddv d i
    ]
]
; set Q to c/d
Qap ap ts c p ts d
; check if a==c and b==d
i a^ e? a c e? b d[
    ; set q to "err"
    Q"err"
]
; print q
Q

Answer 10

PHP 156

meh.

$f=$argv[1];$p=explode('/',$f);$m=max(array_map('abs',$p));for(;$m;$m--)if(!($p[0]%$m||$p[1]%$m)){$r=$p[0]/$m.'/'.$p[1]/$m;break;}echo $r===$f?'reduced':$r;

Run:

php -r "$f=$argv[1];$p...[code here]...:$r;" 9/18;
1/2

• prints "reduced" if the fraction is already in its simplest form
• works with negative fractions
• works with improper fractions (e.g. 150/100 gives 3/2)
• kinda works with decimals (e.g. 1.2/3.6 gives 0.75/2.25)
• 99/0 incorrectly gives 1/0 ?
• won't reduce to a whole number (e.g. 100/100 gives 1/1)

Here's an ungolfed version with some testing (modified into function form):

<?php
$a = array(
    '9/18','8/12','50/100','82/100','100/100','150/100','99/100',
    '-5/10','-5/18','0.5/2.5','1.2/3.6','1/0','0/1','99/0'
);
print_r(array_map('r',array_combine(array_values($a),$a)));

function r($f) {
    $p = explode('/',$f);
    $m = max(array_map('abs',$p));
    for ( ; $m; $m-- )
        if ( !($p[0] % $m || $p[1] % $m) ) {
            $r = $p[0]/$m.'/'.$p[1]/$m;
            break;
        }
    return $r === $f ? 'reduced' : $r;
}
/*
Array(
    [9/18] => 1/2
    [8/12] => 2/3
    [50/100] => 1/2
    [82/100] => 41/50
    [100/100] => 1/1
    [150/100] => 3/2
    [99/100] => reduced
    [-5/10] => -1/2
    [-5/18] => reduced
    [0.5/2.5] => 0.2/1
    [1.2/3.6] => 0.75/2.25
    [1/0] => reduced
    [0/1] => reduced
    [99/0] => 1/0
)
*/
?>

Answer 11

Java, 361 349 329 (thanks @Sieg for the int tip)

class P{public static void main(String[]a){String[]e=a[0].split("/");String f="";int g=new Integer(e[0]),h=new Integer(e[1]);if(g>h){for(int i=h;i>=1;i--){if(g%i==0&&h%i==0){f=g/i+"/"+h/i;break;}}}else if(g<h){for(int i=g;i>=1;i--){if(g%i==0&&h%i==0){f=g/i+"/"+h/i;break;}}}else if(g.equals(h)){f="1/1";}System.out.println(f);}}

I know it's not short, but I'm just mesmerized of what I did.

To use it, compile the code and run it passing the arguments through the command-line.

• Integers only (I'm not into doubles and the task doesn't require it).
• If the fraction is already simplified, returns itself.
• Doesn't work with negative fractions.
• Dividing by zero? No cookie for you (Returns an empty string).

Ungolfed (if anyone wants to see this mess):

class P{
    public static void main(String[]a){
        String[]e=a[0].split("/");
        String f="";
        int g=new Integer(e[0]),h=new Integer(e[1]);
        if(g>h){
            for(int i=h;i>=1;i--){
                if(g%i==0&&h%i==0){
                    f=g/i+"/"+h/i;
                    break;
                }
            }
        }else if(g<h){
            for(int i=g;i>=1;i--){
                if(g%i==0&&h%i==0){
                    f=g/i+"/"+h/i;
                    break;
                }
            }
        }else if(g.equals(h)){
            f="1/1"; //no processing if the number is THAT obvious.
        }
        System.out.println(f);
    }
}

Answer 12

Ruby — 112 characters

g is a helper lambda that calculates the GCD of two integers. f takes a fraction as a string, e.g. '42/14', and outputs the reduced fraction or simplest if the numerator and denominator are relatively prime.

g=->a,b{(t=b;b=a%b;a=t)until b==0;a}
f=->z{a,b=z.split(?/).map &:to_i;y=g[a,b];puts y==1?:simplest:[a/y,b/y]*?/}

Some test cases:

test_cases = ['9/18', '8/12', '50/100', '82/100', '100/100',
              '150/100', '99/100', '-5/10', '-5/18', '0/1']

test_cases.map { |frac| f[frac] }

Output:

1/2
2/3
1/2
41/50
1/1
3/2
simplest
-1/2
simplest
simplest

Note, although against the rules, Ruby has Rational support baked in, so we could do

a=gets.chomp;b=a.to_r;puts b.to_s==a ?:simplest:b

Answer 13

Lua - 130 115 characters

10/10 i really tried

a,b=io.read():match"(.+)/(.+)"u,v=a,b while v+0>0 do t=u u=v v=t%v end print(a+0==a/u and"reduced"or a/u.."/"..b/u)

• prints "reduced" if fraction is in simplest form
• works with negatives
• works with improper fractions
• presumably works with decimals (1.2/3.6 gives 5.4043195528446e+15/1.6212958658534e+16)
• any number/0 gives 1/0
• does not reduce to whole numbers

I fully took advantage of Lua's ability to auto convert a string to a number when doing arithmetic operations on a string. I had to add "+0" in place of tonumber for some comparison code.

Sorry, I don't have an ungolfed version, the above is actually how I wrote it

Answer 14

JavaScript (91) (73)

Returns '/' when the fraction is already in it's simplest form. The function g calculates the gcd. BTW: Is there any shorter way for '1==something' where something is a non negative integer?

function s(f){[n,m]=f.split(b='/');g=(u,v)=>v?g(v,u%v):u;return 1==(c=g(n,m))?b:n/c+b+m/c;}

Thanks to @bebe for an even shorter version:

s=f=>([n,m]=f.split(b='/'),c=(g=(u,v)=>v?g(v,u%v):u)(n,m))-1?n/c+b+m/c:f;

Answer 15

Batch - 198

for /f "tokens=1,2delims=/" %%a in ("%1")do set a=%%a&set b=%%b&set/ac=%%b
:1
set/ax=%a%%%%c%&set/ay=%b%%%%c%
if %x%%y%==00 set/aa/=%c%&set/ab/=%c%
if %c% GTR 0 set/ac=%c%-1&goto 1
echo %a%/%b%

Input is split as a/b, then for every c in b,b-1,...1 we check if a and b are divisible by c, and divide them by c if they are. Then we return a/b

Answer 16

Befunge 93 (192)

&04p~$&14p2       > :24p  v       >34g#v_0"tselpmiS">:#,_@
>134p 24g>        ^+1g42$<>04g`   |    >04g."/",14g.@
^p41/g42p40/g42<         |%g42:g41<
         #     |!%g42:g40<
   0     ^+1g42<

Answer 17

C 135

Accepts input for 2 space-separated integers. Keeps dividing by minimum of a & b down to 1 to find GCD.

int a,b,m;
void main()
{
scanf("%d %d", &a, &b);
m=a<b?a:b;
for (;m>0;m--){if (a%m==0&&b%m==0)break;}
printf("%d/%d",a/m,b/m);
}

Answer 18

Java (200)

The previous best solution in Java still had >300 bytes, this one has 200:

class M {public static void main(String[]args){String[]s=args[0].split("/");int a=Integer.parseInt(s[0]),b=Integer.parseInt(s[1]),c=a,d=b;while(d>0){int g=c;c=d;d=g%d;}System.out.print(a/c+"/"+b/c);}}

This uses the (faster) modulo to determine the gcd instead of iterating all numbers.