RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved a core function and some recreational mathematics. (Note that this ends today.)

Task 1: Reverse String

You are given a string.

Write a script to reverse the given string without using standard reverse function.

This differs mostly in terms of whether one preallocates a string (like a fixed-length array of characters) or can readily add to it (in some cases by copying it and appending the new character). Most languages offer the latter, of course. Thus Perl:

sub reversestring($a) {

Just in case there's something iffy about the empty string, which I don't think there is here but there is in some of the other languages.

  if ($a eq '') {
    return $a;
  }

Start with an empty output string.

  my $b = '';

Cache the input length to avoid having to recalculate it.

  my $l = length($a) - 1;

Split the input string into characters, similarly that getting a specific character is a bit faster.

  my @aa = split '', $a;

Drop in the characters in reverse order.

  foreach my $i (0 .. $l) {
    $b .= $aa[$l - $i];
  }
  $b;
}

I wrote a cleaner version of this in Lua, where I simply prepend each character in order to the existing output string.

function reversestring(t)
   local u = ""
   string.gsub(t,
               "(.)",
               function(c)
                  u = c .. u
               end
   )
   return u
end

In PostScript a string has an allocated length, so I fill in the characters one by one. (I have written a library function to reverse an array, not a string; in many respects they're similar, but I also have converters to turn a string into an array of characters and back again. If I were using those, the answer would be s2a reverse a2s, But that would be dull.)

/reversestring {
    0 dict begin
    /a exch def
    /b a length string def
    /l a length 1 sub def
    0 1 l {
        /i exch def
        b i a l i sub get put
    } for
    b
    end
} bind def

Task 2: Armstrong Number

You are given two integers, $base and $limit.

Write a script to find all Armstrong numbers in base $base that are less than $limit.

If raising each of the digits of a nonnegative integer to the power of the total number of digits, then taking the sum, equals the original number, it is an Armstrong number.

These are also known as narcissistic numbers.

In Rust I include my standard integer-only exponentiation-by-squaring function. (I think this is in the num crate, but bringing in any crate means I can't run this directly from the command line, and it's only the one 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
}

Now the bit specific to the problem.

fn armstrongnumber(base: u32, limit: u32) -> Vec<u32> {

Initialise the output list.

    let mut out = Vec::new();

Test each candidate. (We could cheat and populate the list with (0 to base-1) and then start doing this bit from base, because trivially those small numbers are all narcissistic; that would be fractionally faster, but I didn't bother.)

    for candidate in 0 .. limit {

Initialise the digit list.

        let mut digits = Vec::new();

Special case zero.

        if candidate == 0 {
            digits.push(0);
        } else {

Otherwise take the digits in base base. (In reverse order, because it's slightly simpler to do and we don't care about the order.)

            let mut c = candidate;
            while c > 0 {
                digits.push(c % base);
                c /= base;
            }
        }

Cache the number of digits.

        let dl = digits.len() as u32;

Map each digit to (digit ^ length), then sum them.

        let test = digits.iter().map(|x| pow(*x, dl)).sum::<u32>();

If it matches, add it to the output list.

        if test == candidate {
            out.push(candidate);
        }
    }
    out
}

Full code on codeberg.