PWC 273
PWC 272
PWC 271
PWC 270
PWC 269
PWC 268
PWC 267
PWC 266
PWC 265
PWC 264
PWC 263
PWC 262
PWC 261
PWC 260
PWC 258
PWC 255
PWC 239
...under construction...

Click here for my solution TASK #1 Special Positions.**TASK #2: Equalize array [Update: 26.05.2024]**

*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 elements in the given array equal. There is cost attach 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.
*

#!/usr/bin/perl use strict; use warnings; =begin =cut sub equalize_array {

It was fun to think about a solution for TASK #2: Equalize array. The result seems unconventional. I tested it with 10 cases (see below) and used the solution from Packy Anderson to validate my results, encountering no issues. However, I don't provide a solid mathematical proof. My solution is programmatically very straightforward! It demonstrates Perl's excellent capability to interchange arrays, strings and numbers. Now, let me explain my strategy.Case 1: array with two elementsEqualizing the array (1 4) to (4 4) involves the following steps (notice that not the maximum value -as in Mohammads examples- but 0 is my target. So not adding but subtracting. It appears to have advantages: see below): Array: (1 4); Reverse sorted: (4 1) Maximum value: 4 New array (except the maximum value) containing differences between the maximum value and the original values of the array elements: (3). Operations with the number 1 as subtrahend: 3 - 1 = 2 (1 × Level 1) 2 - 1 = 1 (1 × Level 1) 1 - 1 = 0, i.e. target 0 found (1 × Level 1) So there are 3 Level 1 operations needed to equalize the array, i.e. the number of Level 1 operations equals the value of the array element. To determine the total cost, we need to multiply by the cost variables $x: (1 Level 1 operation * $x).Case 2a: array with more than two elementsLet's consider an array with more than two elements, for example, the array (1 3 2). We use 11 as subtrahend, simulating a Level 2 operation if @new_arr contains only single digits. Here are the steps I follow: Array: (1 3 2); Reverse sorted: (3 2 1) Maximum value: 3 New array (except the maximum value) containing differences between the maximum value and the original values of the array elements: (1 2). This array can be transformed into the number 12. We can simulate Level 2 operations by using the number 11 as subtrahend. My assumption here is that normal subtraction is the most efficient method to find the lowest cost solution, but I could be completely wrong. Again, I must leave you without a solid mathematical proof. Operations: 12 - 11 = 1 (1 × Level 2) 1 - 1 = 0 i.e. target 0 found (1 × Level 1) To determine the total cost, we need to multiply by the cost variables $x and $y: (1 Level 2 operation * $y) + (1 Level 1 operation * $x).Case 2b: array with more than two elementsHere's another example to show how to handle the number 0, which indicates that the difference to the maximum value has been reached. We use 11 as subtrahend, simulating a Level 2 operation if @new_arr contains only single digits. Array: (2 3 3 3 5); Reverse sorted: (5 3 3 3 2) Maximum value: 5 New array (except the maximum value) containing differences between the maximum value and the original values of the array elements: (2 2 2 3). Conversion: number to work with is 2223 Operations: 2223 - 11 = 2212 (1 x Level 2) 2212 - 11 = 2201 (1 x Level 2) Now we remove the value 0 (target 0 found) -> 221 221 - 11 = 210 (1 x Level 2) Now we remove the value 0 -> 21 21 - 11 = 10 (1 x Level 2) Now we remove the value 0 -> 1 1 < 11 so 1 refers to 1 Level 1 operation. So 4 Level 2 operations and 1 Level 1 operation. To determine the total cost, we need to multiply by the cost variables $x and $y: (4 Level 2 operation * $y) + (1 Level 1 operation * $x).Case 3: array with special distributionWe need 101 as subtrahend, simulating a Level 2 operation if @new_arr contains one or more double digits. Thanks to Bob Lied and Packy Anderson who inspired me to adapt my first version. Status now: the results of my method are the same as Packy Anderson's algorithm produces. Example: Array: (1 1 12); Reverse sorted: (12 1 1) Maximum value: 12 New array (except the maximum value) containing differences between the maximum value and the original values of the array elements: (11 11). If we'll simulate L2 operations we need another substrahend: instead of 11, we need 101 Conversion: number to work with is 1111 Operations: substract 101 1111 1010 909 808 707 606 505 404 303 202 101 0 => 11 x L2Notice: assumption the maximum value may not changeNotice: not implemented the case that $x * 2 < $y# $x and $y are cost variables my ($arr_orig_ref, $x, $y) = @_; my @arr_orig = @$arr_orig_ref;# sort array in descending order my @arr_orig_sorted = (sort {$b <=> $a} @arr_orig);# now the first element has the maximum value my $max = $arr_orig_sorted[0];# remove the first value, i.e. the maximum value shift(@arr_orig_sorted);# create a new array where each element is the result of subtracting the original value from the maximum value in @arr_orig my @new_arr = map { $max - $_ } @arr_orig_sorted;# $L1 refers to Level 1 and $L2 to Level 2 # Example: there were two Level 2 operations if $L2 equals 2 etc. my $L1 = 0; my $L2 = 0;# the simplest case where the number of Level 1 operations equals the value of array element # see Example 1 below: it takes 4 minus 1 Level 1 operations to equalize the array. if ($x > 0) { if (scalar(@new_arr) == 0) { return (0); } if (scalar(@new_arr) == 1) { $L1 = $new_arr[0]; return ($L1 * $x); }# using the number trick if ( (scalar(@new_arr) > 1) ) {# create a number from @new_arr my $no = join ("", @new_arr);# number 11 as subtrahend, simulating a Level 2 operation if @new_arr contains single digits # number 101 as subtrahend, simulating a Level 2 operation if @new_arr contains one or more double digits my $substrahend; $substrahend = 11 if( grep { length($_) == 1 } @new_arr ); $substrahend = 101 if( grep { length($_) == 2 } @new_arr ); while ($no >= $substrahend) { $no -= $substrahend; $L2++;# remove 0 from $no; 0 means 'target found' $no =~ s/0//g if( index ($no, '0') && $substrahend == 11); } $L1 = $no if ($no != 0); ($L1 != 0) ? (return ( ($L1 * $x) + ($L2 * $y) )) : (return ($L2 * $y)); } } else { return (0); } }# TESTSmy (@arr, $x, $y); @arr = qw(4 1); $x = 3; $y = 2; print("Total cost : ", equalize_array(\@arr, $x, $y), "\n");# Output: 9 @arr = qw(2 3 3 3 5); $x = 2; $y = 1; print("Total cost : ", equalize_array(\@arr, $x, $y), "\n");# Output: 6 @arr = qw(4 2 1); $x = 2; $y = 1; print("Total cost : ", equalize_array(\@arr, $x, $y), "\n");# Output: 4 @arr = qw(5 4 3 2 1); $x = 2; $y = 1; print("Total cost : ", equalize_array(\@arr, $x, $y), "\n");# Output: 5 @arr = qw(22 1); $x = 2; $y = 1; print("Total cost : ", equalize_array(\@arr, $x, $y), "\n");# Output: 42 @arr = qw(4 2 2 1); $x = 2; $y = 1; print("Total cost : ", equalize_array(\@arr, $x, $y), "\n");# Output: 5 @arr = qw(3 2 1); $x = 2; $y = 1; print("Total cost : ", equalize_array(\@arr, $x, $y), "\n");# Output: 3 @arr = qw(5 3 1); $x = 2; $y = 1; print("Total cost : ", equalize_array(\@arr, $x, $y), "\n");# Output: 6 @arr = qw(3 2 2 1); $x = 2; $y = 1; print("Total cost : ", equalize_array(\@arr, $x, $y), "\n");# Output: 2 @arr = qw(20 19 18); $x = 2; $y = 1; print("TOTAL cost : ", equalize_array(\@arr, $x, $y), "\n");# Output 3 @arr = qw(12 9 8); $x = 2; $y = 1; print("TOTAL cost : ", equalize_array(\@arr, $x, $y), "\n");# Output 5 @arr = qw(12 11 8); $x = 2; $y = 1; print("TOTAL cost : ", equalize_array(\@arr, $x, $y), "\n");# Output 7 @arr = qw(20 2 1); $x = 2; $y = 1; print("TOTAL cost : ", equalize_array(\@arr, $x, $y), "\n");# Output 20 @arr = qw(12 1 1); $x = 2; $y = 1; print("TOTAL cost : ", equalize_array(\@arr, $x, $y), "\n");# Output 11 # 4 test cases Athanasius @arr = qw(4 4 4 4); $x = 2; $y = 1; print("TOTAL cost : ", equalize_array(\@arr, $x, $y), "\n");## Output: 0 @arr = qw(2 3 3 3 5); $x = 7; $y = 0; print("TOTAL cost : ", equalize_array(\@arr, $x, $y), "\n");# Output: 7 @arr = qw(2 3 3 3 5); $x = 0; $y = 1; print("TOTAL cost : ", equalize_array(\@arr, $x, $y), "\n");# Output: 0 @arr = qw(17); $x = 3; $y = 2; print("TOTAL cost : ", equalize_array(\@arr, $x, $y), "\n");# Output: 0 # 1 test case Niels van Dijke @arr = qw(3 3 4 4); $x = 1; $y = 2; print("Total cost : ", equalize_array(\@arr, $x, $y), "\n");# Output: 2