Hamming Largest with Raku

This is my response to The Weekly Challenge #301.

Challenge #301.1: Largest Number

Input: @ints = (20, 3)
Output: 320

Input: @ints = (3, 30, 34, 5, 9)
Output: 9534330

This can be done as a oneliner, shown here with some non-essential guardrails in place (in [1,1a]):

#! /usr/bin/env raku

subset PosInt of Int where * > 0;                                      # [1a]

unit sub MAIN (*@ints where @ints.elems > 0 && all(@ints) ~~ PosInt);  # [1]

say @ints.permutations.map( *.join ).max;                              # [2]

[1] Ensure that all the input values (of which there must be at least one) are positive integers, courtesy of the custom type set up with subset [1a].

See docs.raku.org/routine/subset for more information about subset.

[2] Get all the permutations (different ordering) of the input values, then join each permutation by gluing the values together. Then get the highest value (with max) of said sums.

Running it:

$ ./largest-number 20 3 
320

$ ./largest-number 3 30 34 5 9
9534330

Looking good.

Generating all the permutations works quite well for smaller examples, but adding more values to the input will slow it down considerably.

The problem is that the number of permutations increases exponentially:

The table shows that reducing the number of elemens to permutate by even as little as 1 will have a huge impact.

This rather silly example takes about 12 seconds on a slow laptop:

$ time ./largest-number 7 7 7 7 7 7 7 7 7 7
7777777777

Choosing the next value is quite complicated:

$ ./largest-number 20 3 1 2 29
3292201     # -> 3, 29, 2, 20, 1

$ ./largest-number 7 72 79 6 63 123
79772663123 # -> 79, 7, 72, 6, 63, 123

So we will do it another way. We can simply do all the permutations of the values staring with 7 (in the second example), and use the maximum, then do the same for 6, and finally 1. As all the values starting with 7 comes before values starting with 6, and so on.

#! /usr/bin/env raku

subset PosInt of Int where * > 0;

unit sub MAIN (*@ints where @ints.elems > 0 && all(@ints) ~~ PosInt,
               :v(:$verbose));

my @as-str = @ints>>.Str;                                    # [1]

my $result = "";                                             # [2]
my %ints;                                                    # [3]

for @as-str -> $int                                          # [4]
{
  %ints{$int.substr(0,1)}.push: $int;                        # [4a]
}

say ": Hash: { %ints.raku }" if $verbose;                    # [1a]

for %ints.keys.sort(-*) -> $key                              # [5]
{
  $result ~= @(%ints{$key}).permutations.map( *.join ).max;  # [6]
}

say $result;

[1] This gets rid of the not-printing-friendly IntStr type, by coercing each value to a string, so that the verbose output (in [1a]) looks nicer.

[2] The result will be built up here, as a string.

[3] The first digit in each value is the key; the value is a list of the values (starting with that digit).

[4] Iterate over the values, and add them to the correct hash slot.

[5] Iterate over the keys (i.e. starting digit), sorted by largest first (the (-*) argument).

[6] Add the permutation with the largest numerical value to the result, by appending it to the result string.

The result is striking:

$ time ./largest-number 7 72 79 6 63 123 2 3 4 5
797726635432123
15s

$ time ./largest-number-smart 7 72 79 6 63 123 2 3 4 5
797726635432123
0,5s

Values starting with the same digit will of course not benefit from this smartness:

$ time ./largest-number 7 72 79 76 763 7123 72 73 74
79776763747372727123
1,6s

$ time ./largest-number-smart 7 72 79 76 763 7123 72 73 74
79776763747372727123
1,6s

Challenge #301.2: Hamming Distance

Input: @ints = (4, 14, 2)
Output: 6

Binary representation:
4  => 0100
14 => 1110
2  => 0010

HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2)
  = 2 + 2 + 2 = 6.

Input: @ints = (4, 14, 4)
Output: 4

#! /usr/bin/env raku

unit sub MAIN (*@ints where @ints.elems > 1 && all(@ints) ~~ Int);  # [1]

say @ints.combinations(2).map({ ( @_[0] +^ @_[1] ).fmt('%b').comb.sum }).sum;
# 8 # 2 ################# # 3 #################### # 4 ####  # 5 # 6 ### # 7 

[1] Ensure that all the input values (of which there must be at least two) are integers.

[2] Use combinations(2) on the input to get all the possible pairs.

See docs.raku.org/routine/combinations for more information about combinations.

[3] Use map on the pairs to reduce the pair to the binary XOR value with +^.

See docs.raku.org/routine/+$CIRCUMFLEX_ACCENT for more information about the infix bitwise XOR (exclusive or) operator +^.

[4] The binary value from [3] is on decimal format (if we were to print it), so we convert it to binary with fmt, the method sibling of sprintf.

[5] Then we split the binary value into individual digits with comb,

[6] and finally add those digits together to get the number of 1 bits.

[7] Then we add together the values for all the combinations to get the result.

[8] Print the result.

Running it:

$ ./hamming-distance 4 14 2
6

$ ./hamming-distance 4 14 4
4

Looking good.

Missing verbose mode?

#! /usr/bin/env raku

unit sub MAIN (*@ints where @ints.elems > 1 && all(@ints) ~~ Int,
               :v(:$verbose));

my $sum = 0;                                           # [3]

for @ints.combinations(2) -> @combo                    # [1]
{
  my $distance = ( [+^] @combo ).fmt('%b').comb.sum;   # [2]

  $sum += $distance;                                   # [3a]

  say ": HammingDistance({ @combo.join(",") }) = $distance" if $verbose;
}

say $sum;                                              # [3b]

[1] We use a for loop instead of map to get an explicit loop.

[2] Note the use of the meta Reduction Metaoperator [] in combination with ?^ on the entire array this time. Shorter, neater, and harder to understand for the unwary.

See docs.raku.org/language/operators#Reduction_metaoperators for more information about the Reduction Metaoperator [].

[3] A variable for the sum, which we add to [3a] in the loop, and finally print [3b].

Running it, obviously with verbose mode:

$ ./hamming-distance-verbose -v 4 14 2
: HammingDistance(4,14) = 2
: HammingDistance(4,2) = 2
: HammingDistance(14,2) = 2
6

$ ./hamming-distance-verbose -v 4 14 4
: HammingDistance(4,14) = 2
: HammingDistance(4,4) = 0
: HammingDistance(14,4) = 2
4

Some more:

$ ./hamming-distance-verbose -v 1 32 255 256
: HammingDistance(1,32) = 2
: HammingDistance(1,255) = 7
: HammingDistance(1,256) = 2
: HammingDistance(32,255) = 7
: HammingDistance(32,256) = 2
: HammingDistance(255,256) = 9
29

$ ./hamming-distance-verbose -v 1 2047 2048
: HammingDistance(1,2047) = 10
: HammingDistance(1,2048) = 2
: HammingDistance(2047,2048) = 12
24

And that's it.