Lonely ones and equalities

Weekly challenge 270 — 20 May 2024

Week 270 - 20 May 2024

Task 2

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.

Example 1Input: @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 => 9Example 2Input: @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

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`

:

- Sort
`@list`

, and if`$list[0] == $largest`

then stop. - If
`$list[1]`

is less than`$largest`

then buy a`$y`

and increment`$list[0]`

and`$list[1]`

. - or else buy an
`$x`

and add 1 to`$list[0]`

. - 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.

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

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)

Peter Campbell Smith is hereby placed in the public domain