PWC 301 › Hamming Distance and Large Numbers

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Task 1 › Large Numbers

The first task this week has us taking a list of numbers and finding the permutation whose concatenation gives the largest number. For example: largest(20,3) = 320.

At first, I thought I might get away with a greedy join('', reverse sort @ints) but the greedy approach doesn’t work in this case. For example, join('', reverse sort(5, 50, 51)) would give 51505, but the correct answer is 55150. So, a more deliberate approach is needed. However, see the update below this section!

What I settled on is a relatively simple recursive algorithm that starts with the full list of @ints, sort that alphanumerically (in reverse order), and will then recurse for each integer that starts with the highest remaining digit. Clear as mud? Here’s a worked example:

largest(5 50 51):
  $sub->('' => reverse sort(5 50 51)) # 51 50 5
    $sub->(51 => 50 5)
      $sub->(5150 => 5) = 51505  # new max
      $sub->(515 => 50) = 51550  # new max
    $sub->(50 => 51 5)
      $sub->(5051 => 5) = 50515
      $sub->(505 => 51) = 50551
    $sub->(5 => 51 50)
      $sub->(551 => 50) = 55150  # new max
      $sub->(550 => 51) = 55051

The maximum value is kept in a closure and returned by the parent function.

Here is the complete subroutine:

sub largest(@ints) {
    my $sub = sub {
        my $num = shift;
        return $num.($_[0]//0) if @_ <= 1;
        my $max_val = 0; # Our candidate answer

        # Loop until current number starts with a lower digit than previous
        for my $i (0..$#_) {
            last if $i > 0 and substr($_[$i], 0, 1) ne substr($_[0], 0, 1);

            my @new_ints = @_;
            splice @new_ints, $i, 1; # Remove $i-th element

            my $val = __SUB__->($num.$_[$i], @new_ints);
            $max_val = length($val) > length($max_val) ? $val
                            : $val gt        $max_val  ? $val : $max_val;
        }

        $max_val;
    };

    return $sub->('',reverse sort @ints);
}

2025-01-04: Updated to use a stringwise numerical max calculation, which handles large numbers better.

I also got this great suggestion from long-time contributor wanderdoc in the comments below this post, which bears highlighting. His version is as follows:

sub largest(@ints) { join '', sort { $b.$a <=> $a.$b } @ints }

It seems my Holiday brain didn’t take my initial hunch of join '', sort { ... } quite far enough! This is exactly the kind of concise solution I like, and even handles large results just fine, so long as no pair of numbers in @ints concatenate into a value larger than the maximum integer.

Task 2 › Hamming Distance

Hamming distance calculations are a simple form of error detection. It measures the number of changes needed to turn one value into another. With integers x and y (represented in binary), the Hamming distance is simply the number of bits that differ between the two numbers. Note that x ^ b (XOR or exclusive or) will give us a 1 for any bit that differs, so we simply count the 1s in x ^ b. For example:

x   = 15 = 1111b
y   =  4 = 0100b
----------------
x^y = 11 = 1011b -> 3 1s, so hamming(15,4) = 3

In Perl, the Hamming distance between two numbers can therefore be implemented simply:

sub hamming($x,$y) { ()= sprintf('%b', $x ^ $y) =~ /1/g }

If you are squinting at the ()= in that expression, then let me introduce you to the =()= operator in Perl!

You can see I’m converting $x ^ $y to binary, and then running it through a simple regex, /1/g. The /g makes the regex return all of the matches, but we’re not interested in getting a bunch of 1s; we want to know how many matches there were. So the ()= puts the expression into list context, and then back into scalar context.

If you instead wanted to assign the result to a variable, you could write it as follows:

my $hamming_distance =()= sprintf('%b', $x ^ $y) =~ /1/g

That, of course, only calculates the Hamming distance between two numbers, whereas the task asks us to calculate the Hamming distance between all numbers, and sum the result. Why? I have no idea. I’m not aware of any good reason to do this, except that it’s a fun bit of recreational coding.

sub hamming_multi(@ints) {
    my $dist = 0;

    for my $i (0..$#ints-1) {
        $dist += hamming($ints[$i], $_) for @ints[$i+1..$#ints];
    }

    $dist;
}

As you can see, a simple nested loop does the trick.

Going faster: C implementation

The gcc compiler provides access to the __builtin_popcount() builtin, which can often calculate a single Hamming distance extremely quickly. Most modern CPUs have some kind of “popcount” instruction that counts the number of 1s in an integer, in a single instruction. On x86 for example, the POPCNT instruction does all of the heavy lifting, and __builtin_popcount() will use this platform-specific instruction (or one like it) if available. So our C function is simply:

int hamming(int x, int y) {
    return __builtin_popcount(x ^ y);
}

The hamming_multi() instruction is very similar to the Perl version:

int hamming_multi(int count, int ints[]) {
    int dist = 0; // Total Hamming distance

    for (int i = 0; i < count - 1; i++)
        for (int j = i + 1; j < count; j++)
            dist += hamming(ints[i], ints[j]);

    return dist;
}