Hammering lists

Weekly Challenge 301

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Largest Number

Task

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.

My solution

Maybe I'm overthinking it, but this isn't as easy at it sounds.

One option would be to compute all permutations, and see which number is largest. However this gets resource intensive as we add more integers. If I had thirteen integers, there are over 6 billion permutations. So I rule this out as a possible solution.

So the obvious thing to do is to sort the integers, combine them and output the result. As Python treats strings and integers differently, I need to convert the sorted list to strings, join them and convert that back to an integer.

def largest_number(ints: list) -> int:
    sorted_ints = sorted(ints, key=cmp_to_key(number_sort), reverse=True)
    return int(''.join(map(str, sorted_ints)))

When it comes to sorting, this is a little complicated. In the second supplied example, we can see that 3, 30, and 34 are all given integers. For this, I know the largest number is obtained by ordering the items (highest to lowest) 34, 3 and 30.

For my number_sort function, I convert the integers to strings, s1 and s2. I then have the integer c1 which is the concatenation of s1 and s2, while c2 is the concatenation of s2 and s1.

If c1 is less than than c2, I return -1. If it is larger, I return 1. If they are the same, I return 0. The sorted function uses this information to sort the list as required.

def number_sort(i1: int, i2: int) -> int:
    s1 = str(i1)
    s2 = str(i2)

    c1 = int(s1 + s2)
    c2 = int(s2 + s1)

    if c1 < c2:
        return -1
    if c1 > c2:
        return 1

    return 0

The Perl code is much simpler :)

sub number_sort() {
    return "$a$b" <=> "$b$a";
}

Examples

$ ./ch-1.py 20 3
320

$ ./ch-1.py 3 30 34 5 9
9534330

Task 2: Hamming Distance

Task

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.

My solution

In the previous task I mentioned how Python treats integers and strings as different types. One of the advantages of Perl is that we are told that for all intents and purposes, we don't need to worry about typing of variables. Even though internally they are stored differently, Perl knows what to do.

In Perl 5.10 and Perl 5.16 (which is where I did most of my Perl development), there are two notable exceptions. One is the JSON module, which will output "10" for a string and 10 for an integer.

The other is bitwise operations. From the perlop page, 105 | 150 (two integers) is 255, while "105" | "150" (two strings) is 155.

So I was pleasantly surprised when I read the perlop page again to see that this has been sorted out in later version of Perl. It now has the bitwise feature which is experimental in Perl 5.22, and available in Perl 5.28. This ensures that bitwise operators always treat the values as an integer, and string-based bitwise has new operators.

Anyway, back to the task at hand. For this I compute all combinations of two integers. For each combination, I perform an XOR (exclusive or) of the two values, convert it to binary and count the number of 1s in the binary representation.

def hamming_distance(ints: list) -> int:
    solution = 0

    for i in range(len(ints)-1):
        for j in range(i+1, len(ints)):
            x = ints[i] ^ ints[j]
            solution += bin(x).count('1')

    return solution

Examples

$ ./ch-2.py 4 14 2
6

$ ./ch-2.py 4 14 4
4