8
\$\begingroup\$

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 question, so the shortest code wins
\$\endgroup\$
  • 1
    \$\begingroup\$ How should we inform the user? \$\endgroup\$ – bebe Aug 2 '14 at 7:13
  • \$\begingroup\$ Stdout, console.writeline, etc. \$\endgroup\$ – Jon Aug 2 '14 at 7:14
  • 7
    \$\begingroup\$ This is really quite a trivial problem. All you do is divide by the gcd (a function that is often built in but would not be hard to write). \$\endgroup\$ – Calvin's Hobbies Aug 2 '14 at 7:41
  • 1
    \$\begingroup\$ @Calvin'sHobbies Yeah, the problem itself is trivial. Doing it in the shortest amount of code isn't as easy. \$\endgroup\$ – Jon Aug 2 '14 at 17:47
  • 3
    \$\begingroup\$ What do you mean by "If the fraction is already in its most simplified form, you must inform the user"? Should there be a specific message apart from just returning the input? If so, I don't the the accepted answer satisfies this. \$\endgroup\$ – Martin Ender Apr 15 '15 at 17:52

18 Answers 18

1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ But the constructor of that class is a function? \$\endgroup\$ – flawr Aug 3 '14 at 9:12
  • \$\begingroup\$ @flawr type(fractions.Fraction.__init__) returns wrapper_descriptor rather than function, so you could say it is not a function. This actually just means it is implemented in c, but anything not in class function is not a function, right? \$\endgroup\$ – Ian D. Scott Aug 3 '14 at 16:16
  • 2
    \$\begingroup\$ -1: this is a built-in. While it doesn't say "simplify" in the name, it simplifies fractions. \$\endgroup\$ – Cyoce May 21 '17 at 21:44
5
\$\begingroup\$

><> (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.

\$\endgroup\$
  • \$\begingroup\$ you actually did better that everyone except the golfscript one. nice! \$\endgroup\$ – proud haskeller Aug 2 '14 at 10:47
  • \$\begingroup\$ not longer true :-( \$\endgroup\$ – proud haskeller Aug 4 '14 at 2:36
3
\$\begingroup\$

GolfScript, 49 characters

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

Run the two testcases here:

> 8/12
2/3

> 7/12
simplest
\$\endgroup\$
3
\$\begingroup\$

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')
\$\endgroup\$
  • 1
    \$\begingroup\$ for([a,b]=[c,d]=prompt().split('/');b;[a,b]=[b,a%b]);alert(a-1?c/a+'/'+d/a:'Reduced'); 86 i hope it's mathematically correct... \$\endgroup\$ – bebe Aug 3 '14 at 9:26
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Wouldn't it be shorter to use Python 3 for input()? \$\endgroup\$ – mbomb007 Apr 15 '15 at 19:01
  • \$\begingroup\$ @mbomb007 It's been a while, but I think the 4 chars saved on that are more than lost by Python 3 needing parens around print, the map being unpacked, and maybe integer rather than float division. \$\endgroup\$ – xnor Apr 15 '15 at 20:56
  • \$\begingroup\$ Forgot about the division. That alone would make it 'not worth.' What do you mean about map being unpacked? \$\endgroup\$ – mbomb007 Apr 15 '15 at 21:44
  • \$\begingroup\$ @mbomb007 My mistake, a,b=map(int,...) doesn't require any extra chars since a,b=... unpacks automatically. The problem you sometimes run into with Python 3 is that map doesn't produce a list but a map object that requires turning into a list before you can do something like slice it. An expression like *l,=map(...) is needed to assign l as a list instead. \$\endgroup\$ – xnor Apr 15 '15 at 21:46
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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);}
\$\endgroup\$
  • \$\begingroup\$ 83: c;d;f(a,b){b?f(b,a%b):printf("%d/%d",c/a,d/a);}main(){scanf("%d/%d",&c,&d);f(c,d);} \$\endgroup\$ – bebe Aug 3 '14 at 10:06
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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
)
*/
?>
\$\endgroup\$
0
\$\begingroup\$

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);
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ You really should use int instead of Integer, even in production code. Int is allocated from the stack, while integer is from the heap. \$\endgroup\$ – seequ Aug 2 '14 at 21:17
  • \$\begingroup\$ @Sleg Well, I didn't knew that, thank you very much. \$\endgroup\$ – g.carvalho97 Aug 2 '14 at 21:20
  • \$\begingroup\$ Then something you should not use in production. Just calling new Integer(str) will have the same result as Integer.parseInt(str). Also, why not use String f="" (always)? \$\endgroup\$ – seequ Aug 2 '14 at 21:32
  • \$\begingroup\$ @Sieg Thanks again, but why is that? I know that new Integer(str) creates a Integer out of a string, but doesn't Integer.parseInt(str) do the same thing? And the thing with String f="", I know that I should use it over String f=new String(), but I don't know why I don't, maybe it's a bad habit :P \$\endgroup\$ – g.carvalho97 Aug 2 '14 at 21:37
  • 1
    \$\begingroup\$ Integer.parseInt indeed does the same thing, but with some cached values for faster lookup. \$\endgroup\$ – seequ Aug 2 '14 at 21:43
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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;
\$\endgroup\$
  • \$\begingroup\$ use es6 consistently. call your function s=f=>... then assign g when using it (g=...)(n,m) then pass it to c and test if it equals to 1 by c-1?not_equals:equals and try to avoid using return. result: 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; 73 (returns the simplest form (f) if it cannot be reduced) \$\endgroup\$ – bebe Aug 3 '14 at 11:17
  • 1
    \$\begingroup\$ Wow thats great! I could not think of a way to pack the shole thing into one statement thats why I used function and return. And thanks for the -1=) \$\endgroup\$ – flawr Aug 3 '14 at 11:22
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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<
\$\endgroup\$
0
\$\begingroup\$

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);
}
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ You can remove the space after class M \$\endgroup\$ – mbomb007 Apr 15 '15 at 19:03

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.