The weekly challenge 249 - Task 1: Shortest Distance

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-249/#TASK1
 3 #
 4 # Task 1: Shortest Distance
 5 # =========================
 6 #
 7 # You are given an array of integers with even number of elements.
 8 #
 9 # Write a script to divide the given array into equal pairs such that:
10 #
11 # a) Each element belongs to exactly one pair.
12 # b) The elements present in a pair are equal.
13 #
14 #
15 ## Example 1
16 ##
17 ## Input: @ints = (3, 2, 3, 2, 2, 2)
18 ## Output: (2, 2), (3, 3), (2, 2)
19 ##
20 ## There are 6 elements in @ints.
21 ## They should be divided into 6 / 2 = 3 pairs.
22 ## @ints is divided into the pairs (2, 2), (3, 3), and (2, 2) satisfying all the
23 ## conditions.
24 #
25 ## Example 2
26 ##
27 ## Input: @ints = (1, 2, 3, 4)
28 ## Output: ()
29 ##
30 ## There is no way to divide @ints 2 pairs such that the pairs satisfy every
31 ## condition.
32 #
33 ############################################################
34 ##
35 ## discussion
36 ##
37 ############################################################
38 #
39 # We use the elements of the array as keys for a hash in which we
40 # count the amount of elements of this value in the array.
41 # If in the end, all values in the hash are even, we can spit out the
42 # correct number of arrays, otherwise we can only return an empty array.
43 
44 use strict;
45 use warnings;
46 
47 shortest_distance(3, 2, 3, 2, 2, 2);
48 shortest_distance(1, 2, 3, 4);
49 
50 sub shortest_distance {
51    my @ints = @_;
52    print "Input: (" . join(", ", @ints) . ")\n";
53    my $map;
54    map { $map->{$_}++ } @ints;
55    my @result = ();
56    foreach my $key (keys %$map) {
57       if($map->{$key} % 2) {
58          print "Output: ()\n";
59          return;
60       }
61       my $i = int( $map->{$key} / 2 );
62       foreach my $elem (1..$i) {
63          push @result, [ $key, $key ];
64       }
65    }
66    my $first = 1;
67    print "Output: ";
68    foreach my $elem (@result) {
69       if($first) {
70          $first = 0;
71       } else {
72          print ", ";
73       }
74       print "(" . join(", ", @$elem) . ")";
75    }
76    print "\n";
77 }
78 
79