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;
}
Notes:
- The %VALUE hash is created once (use of
statevariable). - The
dostatement lets me localize the index variable,$v. - We loop by taking the last character from
$streach time. There are a couple of trivial variations:- We could split the string into individual characters and
popcharacters - We could reverse the string and loop forwards instead.
- We could split the string into individual characters and
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...
-
Input: $rat1 =
-
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...
-
Input: $rat1 =
-
Example 3"
-
Input: $rat1 =
"0.1(234)"$rat2 ="0.12(342)" - Output: true
-
Input: $rat1 =
-
Example 4:
-
Input: $rat1 =
"12.99(99)"$rat2 = "13." -
Output:
true
-
Input: $rat1 =
-
Example 5:
-
Input: $rat1 =
"0.(123)"$rat2 ="0.1(231)" -
Output:
true
-
Input: $rat1 =
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
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;
}
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;
}
Notes:
- Both the
fixedandrepeatparts 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 thebigratmodule. It no longer does division; it constructs aMath::BigRatobject representing a rational number with a numerator and a denominator.
Top comments (0)