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.

Well documented and crafted solutions in Perl and on top you get to play with it. Well done and keep it up great work.

Try it 

#!/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);
}

20 lines of code

Output from script

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)