The weekly challenge 270 - Task 2: Distribute Elements

  1 #!/usr/bin/perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-270/#TASK2
  3 #
  4 # Task 2: Distribute Elements
  5 # ===========================
  6 #
  7 # You are give an array of integers, @ints and two integers, $x and $y.
  8 #
  9 # Write a script to execute one of the two options:
 10 #
 11 ## Level 1:
 12 ## Pick an index i of the given array and do $ints[i] += 1
 13 ##
 14 ## Level 2:
 15 ## Pick two different indices i,j and do $ints[i] +=1 and $ints[j] += 1.
 16 #
 17 # You are allowed to perform as many levels as you want to make every elements
 18 # in the given array equal. There is cost attach for each level, for Level 1,
 19 # the cost is $x and $y for Level 2.
 20 #
 21 # In the end return the minimum cost to get the work done.
 22 #
 23 ## Example 1
 24 ##
 25 ## Input: @ints = (4, 1), $x = 3 and $y = 2
 26 ## Output: 9
 27 ##
 28 ## Level 1: i=1, so $ints[1] += 1.
 29 ## @ints = (4, 2)
 30 ##
 31 ## Level 1: i=1, so $ints[1] += 1.
 32 ## @ints = (4, 3)
 33 ##
 34 ## Level 1: i=1, so $ints[1] += 1.
 35 ## @ints = (4, 4)
 36 ##
 37 ## We perforned operation Level 1, 3 times.
 38 ## So the total cost would be 3 x $x => 3 x 3 => 9
 39 #
 40 ## Example 2
 41 ##
 42 ## Input: @ints = (2, 3, 3, 3, 5), $x = 2 and $y = 1
 43 ## Output: 6
 44 ##
 45 ## Level 2: i=0, j=1, so $ints[0] += 1 and $ints[1] += 1
 46 ## @ints = (3, 4, 3, 3, 5)
 47 ##
 48 ## Level 2: i=0, j=2, so $ints[0] += 1 and $ints[2] += 1
 49 ## @ints = (4, 4, 4, 3, 5)
 50 ##
 51 ## Level 2: i=0, j=3, so $ints[0] += 1 and $ints[3] += 1
 52 ## @ints = (5, 4, 4, 4, 5)
 53 ##
 54 ## Level 2: i=1, j=2, so $ints[1] += 1 and $ints[2] += 1
 55 ## @ints = (5, 5, 5, 4, 5)
 56 ##
 57 ## Level 1: i=3, so $ints[3] += 1
 58 ## @ints = (5, 5, 5, 5, 5)
 59 ##
 60 ## We perforned operation Level 1, 1 time and Level 2, 4 times.
 61 ## So the total cost would be (1 x $x) + (3 x $y) => (1 x 2) + (4 x 1) => 6
 62 #
 63 ############################################################
 64 ##
 65 ## discussion
 66 ##
 67 ############################################################
 68 #
 69 # We find the index of the biggest number in the array, and the
 70 # indices of the two smallest ones. As long as the smallest number
 71 # is still smaller than the biggest one, we check:
 72 # - if the second smallest number is still smaller than the biggest
 73 #   AND the cost of incrementing two numbers is less than twice the
 74 #   cost of incrementing one number, increment the two smallest
 75 #   numbers
 76 # - else increment the smallest number
 77 #
 78 # Two helper functions are used: max_at() returns the index of the
 79 # biggest number in the array, min_at() returns the indices of the
 80 # two smallest numbers in the array (first one wins if two numbers have
 81 # the same value)
 82 
 83 use strict;
 84 use warnings;
 85 
 86 distribute_elements( [4, 1], 3, 2);
 87 distribute_elements( [2, 3, 3, 3, 5], 2, 1);
 88 
 89 sub distribute_elements {
 90    my ($array, $x, $y) = @_;
 91    my @ints = @$array;
 92    print "Input: (", join(", ", @ints), "), \$x = $x, \$y = $y\n";
 93    my $result = 0;
 94    my $max_pos = max_at(@ints);
 95    my ($min1_pos, $min2_pos) = min_at(@ints);
 96    while($ints[$min1_pos] < $ints[$max_pos]) {
 97       if($ints[$min2_pos] < $ints[$max_pos] && 2*$x > $y) {
 98          $ints[$min2_pos]++;
 99          $ints[$min1_pos]++;
100          $result += $y;
101       } else {
102          $ints[$min1_pos]++;
103          $result += $x;
104       }
105       ($min1_pos, $min2_pos) = min_at(@ints);
106    }
107    print "Output: $result\n";
108 }
109 
110 sub max_at {
111    my @ints = @_;
112    my $max_pos = 0;
113    my $max = $ints[0];
114    foreach my $i (1..$#ints) {
115       if($ints[$i] > $max) {
116          $max = $ints[$i];
117          $max_pos = $i;
118       }
119    }
120    return $max_pos;
121 }
122 
123 sub min_at {
124    my @ints = @_;
125    my ($min1_pos, $min2_pos, $min1, $min2);
126    if($ints[0] > $ints[1]) {
127       $min1_pos = 1;
128       $min2_pos = 0;
129       $min1 = $ints[1];
130       $min2 = $ints[0];
131    } else {
132       $min1_pos = 0;
133       $min2_pos = 1;
134       $min1 = $ints[0];
135       $min2 = $ints[1];
136    }
137    foreach my $i (2..$#ints) {
138       next unless $ints[$i] < $min2;
139       if($ints[$i] < $min1) {
140          ($min1, $min2) = ($ints[$i], $min1);
141          ($min1_pos, $min2_pos) = ($i, $min1_pos);
142       } else {
143          $min2 = $ints[$i];
144          $min2_pos = $i;
145       }
146    }
147    return ($min1_pos, $min2_pos);
148 }
149