DEV Community

Bob Lied
Bob Lied

Posted on

PWC 386 All Your Base Are Belong to Rational Numbers

We have a couple of math problems for this week's challenge tasks. Let's set the mood with Paul Simon's song, "When Numbers Get Serious", from the under-rated 1983 album, Hearts and Bones.

Task 1: Reverse Base

Task Description

You are given a string representing a number, and an integer specifying the base of that representation.

Write a function to convert this string to an integer. (For bases greater than 10, use characters A-Z, a-z, + and / in that order.)

  • Example 1 Input: $num = "101010", $base = 2 Output: 42
  • Example 2 Input: $num = "EEADEE", $base = 16 Output: 15642094
  • Example 3 Input: $num = "755", $base = 8 Output: 493
  • Example 4 Input: $num = "1BRJB", $base = 36 Output: 2228519
  • Example 5 Input: $num = "7MyqL", $base = 64 Output: 123456789

Observations

This is the inverse of last week's problem. We need a table that looks up the values of the symbols, and a loop that multiplies each digit to its exponent place in the number.

Implementation

sub task($num, $base)
{
    state %VALUE = do { my $v = 0; map { $_ => $v++ } ( '0'..'9', 'A'..'Z', 'a'..'z', '+', '/'); };

    my $n = 0;
    my $place = 1;
    while ( (my $d = substr($num, -1, 1, '') ) ne '' )
    {
        $n += $place * $VALUE{$d};
        $place *= $base;
    }
    return $n;
}
Enter fullscreen mode Exit fullscreen mode

Notes:

  • The %VALUE hash is created once (use of state variable).
  • The do statement lets me localize the index variable, $v.
  • We loop by taking the last character from $str each time. There are a couple of trivial variations:
    • We could split the string into individual characters and pop characters
    • We could reverse the string and loop forwards instead.

Task 2: Rational Numbers

Task Description

You are given two strings representing non-negative rational numbers. Write a script to return true if the two given rational numbers are same otherwise false.

  • Example 1:
    • Input: $rat1 = "0.(12)" $rat2 = "0.(121)"
    • Output: false
    • Expansion of "0.(12)" = 0.12121212...
    • Expansion of "0.(121)" = 0.121121121...
  • Example 2:
    • Input: $rat1 = "0.1(23)" $rat2 = "0.12(32)"
    • Output: true
    • Expansion of "0.1(23)" = 0.1232323...
    • Expansion of "0.12(32)" = 0.12323232...
  • Example 3"
    • Input: $rat1 = "0.1(234)" $rat2 = "0.12(342)"
    • Output: true
  • Example 4:
    • Input: $rat1 = "12.99(99)" $rat2 = "13."
    • Output: true
  • Example 5:
    • Input: $rat1 = "0.(123)" $rat2 = "0.1(231)"
    • Output: true

Observations

There's a temptation to do something with string manipulation to see if $rat1 can be converted to $rat2, but Example 4 trips that up. What this requires is to think back to middle-school math and recall how to convert a repeating decimal to the form of a rational number with a numerator and denominator.

If we convert both rat1 and rat2 into the form of rational numbers we can compare them.

So how do we convert decimal representation to a rational number? The trick is to multiply the number by enough powers of 10 so that all the fixed parts are left of the decimal, and the repeating part starts at the decimal. Then subtract away the repeating decimals to leave a simple division.

For example, let's take example 4, 12.(99). Let s=12.(99). Then, 100s = 1299.(99).

   100s = 1299.9999...
   -  s =   12.9999...
   -------------------
    99s = 1287.0

    s = 1287/99 = 13/1
Enter fullscreen mode Exit fullscreen mode

In general, we'll have to identify the fixed and repeating parts, then use their lengths to set up multipliers to shift the decimal point.

Perl has modules for doing arithmetic with rational numbers. The most convenient is bigrat. It has some nice properties. First, it's a core module, so it's always present without an external dependency. Second, it reduces fractions to their lowest-common-denominator form (e.g., 1/2 compares equal to 2/4), so we don't have to worry about that. And, third, it overloads the common arithmetic operators, including == comparison.

Implementation

If we assume we can create a rational number from the odd representation given as input (let's defer that assumption into a function called asRational()), then the main task is simple:

use bigrat;
sub task($rat1, $rat2)
{
    my $r1 = asRational($rat1);
    my $r2 = asRational($rat2);
    return $r1 == $r2;
}
Enter fullscreen mode Exit fullscreen mode

So the remaining problem is to write asRational(). It needs to extract the fixed and repeating parts, which can be done with a regular expression. Then it needs to figure out the multipliers needed, based on the lengths of the strings.

sub asRational($rat)
{
    my ($whole, $fixed, $repeat) = $rat =~ m/
            (\d*)       # Capture whole number part before decimal
            \.          # Decimal point always present
            (\d*)?      # Capture optional fixed digits
            (?:\(       # Group the part in parentheses
            (\d+)       # Capture repeating digits
            \))?        # Close parentheses group, repeat is optional
            /x;
    $fixed ||= 0;
    $repeat ||= 0;

    # Multiplier to move fixed to right of decimal point.
    my $multFixed  = ( $fixed  ? 10 ** length($fixed)      : 1 );

    # Multiplier to move repeat to right of decimal point, minus 1
    my $multRepeat = ( $repeat ? 10 ** length($repeat) - 1 : 1 );

    # Move all digits right of decimal point. Example: 1.2(34) --> 1234.
    my $numerator   = ($whole * $multFixed + $fixed) * $multRepeat + $repeat;

    my $denominator = $multFixed * $multRepeat;

    # Returns a BigRat object, not math. Handles reducing fractions.
    return $numerator / $denominator;
}
Enter fullscreen mode Exit fullscreen mode

Notes:

  • Both the fixed and repeat parts are optional. If they're not picked up by the regular expression match, set them to zero so that they disappear in the later arithmetic (as opposed to causing exception for using an undefined value).
  • Similarly, for the multipliers, use 1 if not present, otherwise the '0' would be a string of length 1 and cause the multiplier to be 10.
  • The rest is math, except that the / opertor is overridden by the bigrat module. It no longer does division; it constructs a Math::BigRat object representing a rational number with a numerator and a denominator.

Top comments (0)