The weekly challenge 301 - Task 2: Hamming Distance

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-301/#TASK2
 3 #
 4 # Task 2: Hamming Distance
 5 # ========================
 6 #
 7 # You are given an array of integers, @ints.
 8 #
 9 # Write a script to return the sum of Hamming distances between all the pairs
10 # of the integers in the given array of integers.
11 #
12 # The Hamming distance between two integers is the number of places in which
13 # their binary representations differ.
14 #
15 #
16 ## Example 1
17 ##
18 ## Input: @ints = (4, 14, 2)
19 ## Output: 6
20 ##
21 ## Binary representation:
22 ## 4  => 0100
23 ## 14 => 1110
24 ## 2  => 0010
25 ##
26 ## HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
27 #
28 ## Example 2
29 ##
30 ## Input: @ints = (4, 14, 4)
31 ## Output: 4
32 #
33 ############################################################
34 ##
35 ## discussion
36 ##
37 ############################################################
38 #
39 # First, we turn each number into its binary representation.
40 # Then, we check each binary number against each other binary
41 # number, adding leading zeroes to euqalize the length (by simply
42 # making all numbers as long as the longest one). Then we
43 # calculate the Hamming Distance for each pair of numbers and return
44 # the sum of all of those distances.
45 
46 use v5.40;
47 
48 hamming_distance(4, 14, 2);
49 hamming_distance(4, 14, 4);
50 
51 sub hamming_distance {
52    my @ints = @_;
53    print "Input: (" . join(", ", @ints) . ")\n";
54    my $max_len = 0;
55    my @bins = ();
56    my $dist = 0;
57    foreach my $num (@ints) {
58       my $bin = sprintf ("%b", $num);
59       my $len = length($bin);
60       $max_len = $len if $len > $max_len;
61       push @bins, $bin;
62    }
63    foreach my $i (0..$#bins) {
64       my $len = length($bins[$i]);
65       my $lendiff = $max_len - $len;
66       if($lendiff) {
67          $bins[$i] = '0'x$lendiff . $bins[$i];
68       }
69       foreach my $j ($i+1..$#bins) {
70          my $len = length($bins[$j]);
71          my $lendiff = $max_len - $len;
72          if($lendiff) {
73             $bins[$j] = '0'x$lendiff . $bins[$j];
74          }
75          $dist += _hamming_distance($bins[$i], $bins[$j]);
76       }
77    }
78    print "Output: $dist\n";
79 }
80 
81 sub _hamming_distance {
82    my ($i, $j) = @_;
83    my $dist = 0;
84    my @first = split //, $i;
85    my @second = split //, $j;
86    foreach my $k (0..$#first) {
87       $dist++ if $first[$k] != $second[$k];
88    }
89    return $dist;
90 }