RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved base conversions and repeating decimals. (Note that this ends today.)

Task 1: Reverse Base

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

This was my suggestion, as the reverse of challenge 384 part 1. And the code looks quite similar. In Crystal:

def reversebase(a, base)

Build the list of valid "digit" characters.

  digits = Array(Char).new
  c = '0'
  while c <= '9'
    digits.push(c)
    c += 1
  end
  c = 'A'
  while c <= 'Z'
    digits.push(c)
    c += 1
  end
  c = 'a'
  while c <= 'z'
    digits.push(c)
    c += 1
  end
  digits.push('+')
  digits.push('/')

Build a hashmap to convert those digit characters quickly to numerical values.

  dd = Hash(Char, Int32).new
  digits.each_with_index do |y, x|
    dd[y] = x
  end

Start with a zero output value.

  ov = 0

For each character,

  a.chars.each do |c|

Multiply the existing output value by the base, and add the value of this digit.

    ov *= base
    ov += dd[c]
  end

Return the total.

  ov
end

Task 2: Rational Numbers

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.

Clearly the hard bit is getting a version of the number that is testable for equality, since the string representation as given is not unique (see for example ex2, both sides of which expand to the same repeating decimal). But I remembered a trick: 0.(xyz) recurring is the same thing as xyz/999. So I can express the decimal part and the recurring part as fractions, then add them into a single fraction.

Rust has a Rational type, which made my initial solution easier because I could focus on the parsing, but for Perl I adopted the pattern I used in my Fraction class from way back in challenge 146 task 2. This doesn't need many methods: an initialiser, an adder, an equality tester, and most importantly a reducer (e.g. "2/4" is reduced to "1/2") which is invoked automatically. (In PostScript I can still write the methods but I don't have the OO infrastructure to make sure they're only applied to the right sort of variable. This has now made it into my library code.)

In Perl:

Solving the actual problem: is the rational representation of $a equal to that of $b?

sub rationalnumbers($a, $b) {
  str2rat($a)->equals(str2rat($b)) ? 1:0;
}

Most of the work happens here, converting the string to a rational. Because it's Perl I use regexps.

sub str2rat($a) {
  my $fixedpart;
  my $repeatpart;

Split "a.b" from "(c)".

  if ($a =~ /^(.*)\((.*)\)$/) {
    $fixedpart = $1;
    $repeatpart = $2;
  } else {
    $fixedpart = $a;
    $repeatpart = '0';
  }

Work out where the decimal point is in the fixed part, and so how to convert it to a rational. (E.g. "12.3" will become 123/10.) That goes into the rational $v.

  my $point = index($fixedpart, '.');
  my $tens = length($fixedpart) - $point - 1;
  my $n = substr($fixedpart, 0, $point) . substr($fixedpart, $point + 1);
  my $v = Local::Fraction->new($n, 10 ** $tens);

Based on the length of the repeating part, build a series of 9s to be the denominator, and build another fraction for that part, scaled based on the decimal places in the fixed part. (So "12.3(45)" would get as a repeating part 45/990.)

  my $repeatd = 10 ** length($repeatpart) - 1;
  my $w = Local::Fraction->new($repeatpart, (10 ** $tens) * $repeatd);

Add the two fractions together, and return the result.

  $v->add($w);
  $v;
}

Now for the local fraction class, into which I import my existing lcm and gcd functions.

package Local::Fraction;

sub lcm {
  my ($m, $n)=@_;
  return $m / gcd($m, $n) * $n;
}

sub gcd($m, $n) {
  while ($n!=0) {
    ($m, $n)=($n, $m % $n);
  }
  return $m;
}

We initialise the class as a hash with "n" and "d" entries for numerator and denominator, and set them if we have reasonable values.

sub new {
  my $class=shift;
  my $self={
    n => 1,
    d => 1,
      };
  bless $self,$class;
  if (scalar @_ == 1) {
    $self->set_from_string($_[0]);
  } elsif (scalar @_ == 2) {
    $self->{n} = $_[0];
    $self->{d} = $_[1];
  }
  $self->reduce;
  return $self;
}

The reduction method, dividing each side of the fraction by their gcd. This gets called whenever a new fraction is created.

sub reduce {
  my $self = shift;
  my $gcd = gcd($self->{n}, $self->{d});
  $self->{n} /= $gcd;
  $self->{d} /= $gcd;
}

Add another fraction to this one. Classic school algebra. Reduce at the end.

sub add {
  my $self = shift;
  my $other = shift;
  my $lcm = lcm($self->{d}, $other->{d});
  my $n = $self->{n} * $lcm / $self->{d} + $other->{n} * $lcm / $other->{d};
  $self->{n} = $n;
  $self->{d} = $lcm;
  $self->reduce;
}

Because we only ever have reduced forms, an equality test just needs to test that both fields match.

sub equals {
  my $self = shift;
  my $other = shift;
  return $self->{n} == $other->{n} && $self->{d} == $other->{d};
}

(There's also a stringify and a set_from_string which aren't relevant here.)

In Rust I use the Rational class, and avoid regexps.

use num::rational::Rational32;

An integer exponentiation function.

fn pow(x0: u32, pow0: u32) -> u32 {
    let mut x = x0;
    let mut pow = pow0;
    let mut ret = 1;
    while pow > 0 {
        if (pow & 1) == 1 {
            ret *= x;
        }
        x *= x;
        pow >>= 1;
    }
    ret
}

fn str2rat(a: &str) -> Rational32 {
    let fixedpart;
    let repeatpart;

Find the "(" to divide the parts.

    if let Some(op) = a.find('(') {
        fixedpart = a.get(0..op).unwrap();
        repeatpart = a.get(op + 1..a.len() - 1).unwrap();
    } else {
        fixedpart = a;
        repeatpart = "0";
    }

Find the "." in the fixed part, and proceed as before."

    let point = fixedpart.find('.').unwrap();
    let tens = fixedpart.len() - point - 1;
    let n = fixedpart.get(0..point).unwrap().to_owned()
        + fixedpart.get(point + 1..).unwrap();
    let v =
        Rational32::new(n.parse::<i32>().unwrap(), pow(10, tens as u32) as i32);
    let repeatd = (pow(10, repeatpart.len() as u32) - 1) as i32;
    let w = Rational32::new(
        repeatpart.parse::<i32>().unwrap(),
        pow(10, tens as u32) as i32 * repeatd,
    );
    v + w
}

Again, the final function is trivial.

fn rationalnumbers(a: &str, b: &str) -> bool {
    str2rat(a) == str2rat(b)
}

Full code in all tagged languages is on codeberg.