RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved counting digits and matching bit-counts. (Note that this ends today.)

Task 1: Count Even Digits Number

You are given a array of positive integers, @ints.

Write a script to find out how many integers have even number of digits.

Obviously I could just take the string representation, which is pretty trivial even in a strongly-typed language, but I thought it would be more fun to keep the operations purely numeric. (That way I can change base if it's needed.) Python:

def countevendigitsnumber(a):
  t = 0
  for p in a:
    even = False

Make a copy of the value.

    pt = p

Divide it repeatedly by 10, toggling the evenness flag.

    while pt >= 10:
      pt //= 10
      even = not even
    if even:
      t += 1
  return t

Task 2: Sum of Values

You are given an array of integers, @int, and an integer $k.

Write a script to find the sum of values whose index binary representation has exactly $k number of 1-bit set.

Two parts to this, therefore: a Hamming weight calculation and then a fairly straightforward filter.

For Rust of course the former is built in:

fn sumofvalues(a: Vec<u32>, k: u32) -> u32 {
    a.iter()
        .enumerate()
        .filter(|(i, _n)| i.count_ones() == k)
        .map(|(_i, n)| n)
        .sum()
}

and ditto in recent Python, but for most languages I implemented the popcount64c function from Wikipedia. Thus in Raku with its unique bitwise operators:

sub popcount64($x0) {
  constant $M1  = 0x5555555555555555;
  constant $M2  = 0x3333333333333333;
  constant $M4  = 0x0f0f0f0f0f0f0f0f;
  constant $H01 = 0x0101010101010101;
  my $x = $x0;
  $x -= ($x +> 1) +& $M1;
  $x = ($x +& $M2) + (($x +> 2) +& $M2);
  $x = ($x + ($x +> 4)) +& $M4;
  return ($x * $H01) +> 56;
}

sub sumofvalues(@a, $k) {
  return (0 .. @a.end).grep({popcount64($_) == $k}).map({@a[$_]}).sum;
}

JavaScript got the same algorithm using BigInt. Exceptions came when I couldn't trust the reliability of 64-bit integers (Lua and Ruby), where I implemented Kernighan's method, popcount64d from the same Wikipedia page. (Which, on small numbers like these indices, is probably faster.)

Full code on github.