The weekly challenge 327 - Task 2: MAD
1 #!/usr/bin/env perl 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-327/#TASK2 3 # 4 # Task 2: MAD 5 # =========== 6 # 7 # You are given an array of distinct integers. 8 # 9 # Write a script to find all pairs of elements with minimum absolute difference 10 # (MAD) of any two elements. 11 # 12 ## Example 1 13 ## 14 ## Input: @ints = (4, 1, 2, 3) 15 ## Output: [1,2], [2,3], [3,4] 16 ## 17 ## The minimum absolute difference is 1. 18 ## Pairs with MAD: [1,2], [2,3], [3,4] 19 # 20 # 21 ## Example 2 22 ## 23 ## Input: @ints = (1, 3, 7, 11, 15) 24 ## Output: [1,3] 25 # 26 # 27 ## Example 3 28 ## 29 ## Input: @ints = (1, 5, 3, 8) 30 ## Output: [1,3], [3,5] 31 # 32 ############################################################ 33 ## 34 ## discussion 35 ## 36 ############################################################ 37 # 38 # We take two walks of the array. First, we find the MAD by calculating 39 # all absolute distances, keeping track of the minimum. Then, we keep all 40 # pairs of numbers where the absolute distance matches the minimum. For 41 # a nicer output, we sort the pairs that we keep by size, and in the end 42 # we sort the output by size as well. 43 44 use v5.36; 45 46 mad(4, 1, 2, 3); 47 mad(1, 3, 7, 11, 15); 48 mad(1, 5, 3, 8); 49 50 sub mad(@ints) { 51 say "Input: (" . join(", ", @ints) . ")"; 52 my $mad = abs($ints[0] - $ints[1]); 53 my @output = (); 54 foreach my $i (0..$#ints) { 55 foreach my $j ($i+1..$#ints) { 56 my $ad = abs($ints[$i] - $ints[$j]); 57 $mad = $ad if $mad > $ad; 58 } 59 } 60 foreach my $i (0..$#ints) { 61 foreach my $j ($i+1..$#ints) { 62 my $ad = abs($ints[$i] - $ints[$j]); 63 if($ad == $mad) { 64 push @output, $ints[$i] > $ints[$j] ? [$ints[$j], $ints[$i]] : [$ints[$i], $ints[$j]]; 65 } 66 } 67 } 68 say "Output: " . join(", ", map { "[$_->[0], $_->[1]]" } sort { $a->[0] <=> $b->[0] } @output); 69 }