Task — Equalize array

You are give an array of integers, @ints and two integers, $x and $y. Write a script to execute one of the two options:

• Level 1: Pick an index i of the given array and do $ints[i] += 1
• Level 2: Pick two different indices i,j and do $ints[i] +=1 and $ints[j] += 1.

You are allowed to perform as many levels as you want to make every element in the given array equal. There is a cost attached for each level: for Level 1, the cost is $x and $y for Level 2.

In the end return the minimum cost to get the work done.

Examples

Example 1
Input: @ints = (4, 1), $x = 3 and $y = 2
Output: 9
Level 1: i=1, so $ints[1] += 1.
@ints = (4, 2)
Level 1: i=1, so $ints[1] += 1.
@ints = (4, 3)
Level 1: i=1, so $ints[1] += 1.
@ints = (4, 4)
We performed operation Level 1, 3 times.
So the total cost would be 3 x $x => 3 x 3 => 9

Example 2
Input: @ints = (2, 3, 3, 3, 5), $x = 2 and $y = 1
Output: 6
Level 2: i=0, j=1, so $ints[0] += 1 and $ints[1] += 1
@ints = (3, 4, 3, 3, 5)
Level 2: i=0, j=2, so $ints[0] += 1 and $ints[2] += 1
@ints = (4, 4, 4, 3, 5)
Level 2: i=0, j=3, so $ints[0] += 1 and $ints[3] += 1
@ints = (5, 4, 4, 4, 5)
Level 2: i=1, j=2, so $ints[1] += 1 and $ints[2] += 1
@ints = (5, 5, 5, 4, 5)
Level 1: i=3, so $ints[3] += 1
@ints = (5, 5, 5, 5, 5)
We performed operation Level 1, 1 time and Level 2, 4 times.
So the total cost would be (1 x $x) + (3 x $y) => (1 x 2) + (4 x 1) => 6

Analysis

I believe that what is required is to bring each item in the list up to equal the largest value in the original list. I can't think of any case where that would not be true.

Let's start with an easy case: if $y isn't cheaper than 2 * $x then it isn't a bargain and the answer is simply sum(largest value - each value) * $x.

Otherwise, buying a $y is cheaper than buying 2 $x, so we need to maximise the number of $y we buy. Ideally we would only buy $y if the total of the increments needed is an even number, and buy lots of $y and just one $x if it's odd. But that won't always work: consider for example (5, 5, 5, 5, 1), where the only solution is to buy 4 $x.

So here is my solution, where $largest is the largest value in the original @list:

1. Sort @list, and if $list[0] == $largest then stop.
2. If $list[1] is less than $largest then buy a $y and increment $list[0] and $list[1].
3. or else buy an $x and add 1 to $list[0].
4. Go back to step 1.

This does involve a lot of sorting when only the smallest and second smallest current values are needed, but unless @list is massive or there is a huge gap between the largest and smallest elements of @list then I doubt that the overhead is significant.

Try it 

Script

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2024-05-20
use utf8;     # Week 270 - task 2 - Distribute elements
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

distribute_elements([4, 1], 3, 2);
distribute_elements([2, 3, 3, 3, 5], 2, 1);
distribute_elements([2, 3, 3, 3, 5], 2, 5);
distribute_elements([7, 7, 7, 7, 7], 2, 1);
distribute_elements([2, 3, 3, 3, 5], 2, 5);

sub distribute_elements {
    
    my ($list_ref, @list, $x, $y, $largest, $bought_x, $bought_y);

    # initialise
    ($list_ref, $x, $y) = @_;
    @list = sort {$a <=> $b} @$list_ref;
    $largest = $bought_x = $bought_y = 0;
    $largest = ($_ > $largest ? $_ : $largest) for @list;
    
    # if $y is not a bargain just buy lots of $x
    if ($y > 2 * $x) {
        $bought_x += $largest - $_ for @list;
    
    # buy until all values match the largest
    } else {
        while ($list[0] != $largest) {
            
            # can buy $y and add 1 to two smallest values
            if ($list[1] < $largest) {
                $bought_y ++;
                $list[0] ++;
                $list[1] ++;
                
            # only one value needs incrementing so buy an $x    
            } else {
                $bought_x ++;
                $list[0] ++;
            }
            @list = sort {$a <=> $b} @list;
        }
    }

    printf(qq[\nInput:  \@list = (%s), \$x = %d, \$y = %d\n], join(', ', @$list_ref), $x, $y);
    printf(qq[Output: %d (%d * \$x + %d * \$y)\n], $bought_x * $x + $bought_y * $y, $bought_x, $bought_y);
}

Output

Input:  @list = (4, 1), $x = 3, $y = 2
Output: 9 (3 * $x + 0 * $y)

Input:  @list = (2, 3, 3, 3, 5), $x = 2, $y = 1
Output: 6 (1 * $x + 4 * $y)

Input:  @list = (2, 3, 3, 3, 5), $x = 2, $y = 5
Output: 18 (9 * $x + 0 * $y)

Input:  @list = (7, 7, 7, 7, 7), $x = 2, $y = 1
Output: 0 (0 * $x + 0 * $y)

Input:  @list = (2, 3, 3, 3, 5), $x = 2, $y = 5
Output: 18 (9 * $x + 0 * $y)