RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved strings, numbers and bit counting. (Note that this ends today.)

Task 1: Largest Number

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

Write a script to arrange all the elements in the given list such that they form the largest number and return it.

In other words it's all about string concatenation. I ended up doing this with a custom sorting function—but unlike many sorts this can't be proxied with a key function, at least not one that I could work out—so it needs an actual custom comparator. For example, the sequence [3, 30, 34] has to become [34, 3, 30] in the final ordering and a mere ASCIIbetical sort isn't up to that.

Of course in a dynamically-typed language like Perl this is very easy:

sub largestnumber($c) {
  my @b = reverse sort {
    return "$a$b" cmp "$b$a";
  } @{$c};
  0 + join('', @b);
}

It's rather more work in say Crystal:

def largestnumber(a)
  ax = a.map{|x| x.to_s}
  ax.sort! do |i, j|
    ij = i + j
    ji = j + i
    ij.to_i <=> ji.to_i
  end
  ax.reverse!
  ax.join("").to_i
end

(It doesn't actually matter whether the final internal comparison is string or integer because the two ephemeral strings will be the same length.)

Task 2: Hamming Distance

You are given an array of integers, @ints.

Write a script to return the sum of Hamming distances between all the pairs of the integers in the given array of integers.

The Hamming distance between two integers is the number of places in which their binary representations differ.

The Hamming distance between a and b is also the count of set bits in the xor of those two numbers. So like 299's part 1, it felt like a set of language features to be assembled:

• get each possible pair of integers;
• bitwise xor them together;
• count bits in result and add to total.

and I have bit-counting functions (where needed) from earlier Weekly Challenge problems.

Rust:

fn hammingdistance(a: Vec<u32>) -> u32 {
    let mut t = 0;
    for i in 0 .. a.len() - 1 {
        for j in i + 1 .. a.len() {
            t += (a[i] ^ a[j]).count_ones();
        }
    }
    t
}

Full code on github.