The weekly challenge 354 - Task 1: Min Abs Diff

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-354/#TASK1
 3 #
 4 # Task 1: Min Abs Diff
 5 # ====================
 6 #
 7 # You are given an array of distinct integers.
 8 #
 9 # Write a script to find all pairs of elements with the minimum absolute difference.
10 #
11 # Rules (a,b):
12 # 1: a, b are from the given array.
13 # 2: a < b
14 # 3: b - a = min abs diff any two elements in the given array
15 #
16 ## Example 1
17 ##
18 ## Input: @ints= (4, 2, 1, 3)
19 ## Output: [1, 2], [2, 3], [3, 4]
20 #
21 #
22 ## Example 2
23 ##
24 ## Input: @ints = (10, 100, 20, 30)
25 ## Output: [10, 20], [20, 30]
26 #
27 #
28 ## Example 3
29 ##
30 ## Input: @ints = (-5, -2, 0, 3)
31 ## Output: [-2, 0]
32 #
33 #
34 ## Example 4
35 ##
36 ## Input: @ints = (8, 1, 15, 3)
37 ## Output: [1, 3]
38 #
39 #
40 ## Example 5
41 ##
42 ## Input: @ints = (12, 5, 9, 1, 15)
43 ## Output: [9, 12], [12, 15]
44 #
45 ############################################################
46 ##
47 ## discussion
48 ##
49 ############################################################
50 #
51 # We keep track of the min abs diff and all ordered pairs with
52 # a diff that doesn't exceed the current min. That way, we can
53 # do a single pass over all pairs and end up with a hash that
54 # contains all pairs for the min abs diff. Then we can just
55 # output that.
56 
57 use v5.36;
58 
59 min_abs_diff(4, 2, 1, 3);
60 min_abs_diff(10, 100, 20, 30);
61 min_abs_diff(-5, -2, 0, 3);
62 min_abs_diff(8, 1, 15, 3);
63 min_abs_diff(12, 5, 9, 1, 15);
64 
65 sub min_abs_diff(@ints) {
66     say "Output: (" . join(", ", @ints) . ")";
67     my $min = abs($ints[0] - $ints[1]);
68     my $found = {};
69     foreach my $i (0..$#ints) {
70         foreach my $j ($i+1..$#ints) {
71             my $current = abs($ints[$j] - $ints[$i]);
72             $min = $current if $current < $min;
73             push @{ $found->{$current} },
74                 $ints[$i] < $ints[$j] ? "[$ints[$i], $ints[$j]]" : "[$ints[$j], $ints[$i]]"
75                 if $current <= $min;
76         }
77     }
78     say "Output: " . join(", ", @{$found->{$min}});
79 }