Given two scalars that contain non-negative integer values, as ($numerator, $denominator). $denominator is non-zero as well.

Find the perl golf solution subroutine that returns the reduced fraction; that is, a fraction that is still equivalent to the initial fraction but using the smaller possible (non-negative!) integer values to make it up. The fraction is returned as an array in the order of (numerator, denominator).

Examples can include: 
@a = reduce( 512, 1024 );  # @a = ( 1, 2 )
@a = reduce( 12, 18 );     # @a = ( 2, 3 )
@a = reduce( 1, 7 );       # @a = ( 1, 7 )

[download]
Thanks to tilly for the update.

-----------------------------------------------------
Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain

Replies are listed 'Best First'.
Re: (Golf) Fraction Reduction
by no_slogan (Deacon) on Jul 25, 2001 at 05:36 UTC
    43 characters: 
    $x=$_[1];$x--while grep$_%$x,@_;map$_/$x,@_

    [download]
    Too bad grep and map don't default to @_.
[reply]
[d/l]
(MeowChow) Re: (Golf) Fraction Reduction
by MeowChow (Vicar) on Jul 25, 2001 at 07:19 UTC
    I think no_slogan's will probably be the shortest, but here's some more fun with regexes at 49 chars:
      
    sub reduce {
  "@{[map 1x$_,@_]}"=~/(1+)\1* \1+$/;map$_/$+[1],@_
}

    [download]
    Update: Here's a 48-char version that uses a relatively fast algorithim for calculating the GCM of the two numbers (I think it's attributed to Euclid?):
      
    sub reduce {
  ($x,$y)=@_;($x,$y)=($y%$x,$x)while$x;map$_/$y,@_
}

    [download]
       MeowChow                                   
               s aamecha.s a..a\u$&owag.print
[reply]
[d/l]
[select]
Re: (Golf) Fraction Reduction (Russ=45) :-(
by Russ (Deacon) on Jul 26, 2001 at 02:58 UTC
    The best I could get was 45: 
    map$_/(grep!($_[0]%$_|$_[1]%$_),1..$_)[-1],@_

    [download]
    no_slogan++

    Russ
    Brainbench 'Most Valuable Professional' for Perl

[reply]
[d/l]

Back to Meditations