Tag: smoothing

Wherein we review what we learned in kindergarten and remember to share…

THE WEEKLY CHALLENGE – PERL & RAKU #192 Task 2

---

“The advancement and diffusion of knowledge is the only guardian of true liberty.”

— James Madison

---

Equal Distribution

Submitted by: Mohammad S Anwar

You are given a list of integers greater than or equal to zero, @list.

Write a script to distribute the number so that each members are same. If you succeed then print the total moves otherwise print -1.

Please follow the rules (as suggested by Neils van Dijke [2022-11-21 13:00]

1) You can only move a value of '1' per move
2) You are only allowed to move a value of '1' to a direct neighbor/adjacent cell

Example 1:

Input: @list = (1, 0, 5)
Output: 4

Move #1: 1, 1, 4
(2nd cell gets 1 from the 3rd cell)

Move #2: 1, 2, 3
(2nd cell gets 1 from the 3rd cell)

Move #3: 2, 1, 3
(1st cell get 1 from the 2nd cell)

Move #4: 2, 2, 2
(2nd cell gets 1 from the 3rd cell)

Example 2:

Input: @list = (0, 2, 0)
Output: -1

It is not possible to make each same.

Example 3:

Input: @list = (0, 3, 0)
Output: 2

Move #1: 1, 2, 0
(1st cell gets 1 from the 2nd cell)

Move #2: 1, 1, 1
(3rd cell gets 1 from the 2nd cell)

ANALYSIS

First things first: what an unusual and curious puzzle!

Essentially what we have here is a simplified model of diffusion — we wish to take an irregular field of data and progressively smooth it until we obtain a continuous lowest-energy state. Only instead of operating on all points simultaneously, we instead make only one adjustment at a time in discrete steps of one unit.

In only one dimension.

So simplified, yes, but diffusion nonetheless.

In diffusion, differences in some physical value between a local state and its neighbors are distributed between the two, raising the value in one and lowering the other. The description covers any aggregate movement over time towards equilibrium in a system, be it the dissipation of energy or molecules or colored balls. When the values are the same there is no further reason to change anything, and although small movements may continue, the combined effect is unchanging and static.

Here we’re shooting for proper stability in the system. Brownian motion and self-perturbing energy states need not apply. We’re talking spherical chickens in a vacuum here.

With multidimensional fields in real space this requires an application of the differential calculus, but here in our simplified, stepwise model we don’t need all the complexity that entails. Instead we just need an algorithm that locates the next best choice of two adjacent values and adjusts one unit from one position to the other. Exactly what that means remains to be determined.

What would the best move be? It seems moving a single unit from the maximal value one position in the direction of the system minimum would be a good strategy. Move from the highest towards the lowest.

Let’s implement that. What’s the worst thing that could possibly happen?

METHOD

It seems the first thing to do is make sure a general integral leveling is even possible. If the sum of all values in the system is not evenly divisible by the number of pockets there’s no point in continuing. If it is, however, then this will be our target value.

The rules do not expressly demand we do the leveling as quickly as possible, so we’ll only worry about optimization after we’ve come up with a working method for accomplishing our goals at all. So again we are back to performing the best move at any moment over and over until we get there, consequences be damned.

Let’s start small: we’ll need two functions to determine the minimum and maximum values within the vector, and the positions where they are located. This in turn will involve iterating across the array elements and keeping a running tally. In theory this examination could be amalgamated into a single pass in a combined function, but for clarity (over optimization) we’ll keep the two actions clearly delineated. The maximum updates itself upward from negative infinity, the minimum down from infinity. I’ll note these tallies could be started with the values at the first index, but I find the special string for infinity underused and conceptually robust. So why not? It seems many people don’t even know these exist. So spread the word.

Next we will need some sort of move() action. Given a position to more from and a position to move towards, this function will subtract a unit from the first element and add it to the element adjacent in the direction up or down as indicated, changing the array in-place instead of returning and overwriting the variable container. This too seems conceptually pure. Less copying — just change the thing itself.

Finally, arriving at the meat of the matter, the solve() function takes the array and decides whether or not there is a solution using modular division. After calculating an initial minimum and maximum the process is handed over to a loop, moving one value at a time and recalculating the leftmost min and max until the two values are equal. Choosing to work from the left or the right is arbitrary but should be consistent to avoid the possibility of loop cycles.

As it works out we don’t actually need to know the target value after all for our algorithm to work. A counter keeps track of the number of cycles through the loop, returning the applications of the move function. Because I found watching the movements oddly satisfying, I left in a VERBOSE switch to detail the individual moves as they are made.

The algorithm identifies the largest difference between elements in the system taken as a whole and notes their relative placements. As it then moves to equalize the discrepancy from high to low in the direction found, no matter how far apart they are, it should always continue until an equilibrium state exists — the maximum equals the minimum. Also because it only cares about relative values, it works for any whole number input and we are not limited to non-negative integers. And as there is never any cause for backtracking, the resulting solution should use the minimum number of moves.

So that’s nice.

PERL 5 SOLUTION

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature  qw(signatures);
no warnings 'experimental::signatures';
use constant VERBOSE => 1;


sub max_pos ( @array ) {
## returns position and value of maximum element values
## leftmost value is returned in case of multiple occurences
    my ($max, $pos) = ( "-Inf", 0 );
    for (0..$#array) {
        if ($array[$_] > $max) {
            ($max, $pos) = ($array[$_], $_);
        }
    }
    return ($max, $pos);
}

sub min_pos ( @array ) {
## returns position and value of minimum element values
## leftmost value is returned in case of multiple occurences
    my ($min, $pos) = ( "Inf", 0 );
    for (0..$#array) {
        if ($array[$_] < $min) {
            ($min, $pos) = ($array[$_], $_);
        };
    }
    return ($min, $pos);
}

sub move ( $maxpos, $minpos, $arr ) {
## alters the array in-place via reference
    $arr->[$maxpos]--;
    $maxpos > $minpos 
        ? $arr->[$maxpos-1]++
        : $arr->[$maxpos+1]++ ;
}

sub solve ( @array ) {
    ## first check to see it's possible
    my $sum;
    $sum += $_ for @array;
    return -1 if $sum % @array;

    ## set the stage 
    my ($max, $maxpos) = max_pos ( @array );
    my ($min, $minpos) = min_pos ( @array );
    VERBOSE and say "@array     max $max min $min";
    
    my $moves;
    
    ## move values by 1 until lowest state
    while ( $max > $min and ++$moves ) {
        move( $maxpos, $minpos, \@array );
        ($max, $maxpos) = max_pos ( @array );
        ($min, $minpos) = min_pos ( @array );
        VERBOSE and say "@array     max $max min $min";
    }
    return $moves;
}


## input and processing
my @array = @ARGV;
@array == 0 and @array = (10, -5, 15, -6, 0, 4);  ## default example


## report
my $res = solve( @array );
VERBOSE or say $res and exit;

$res > -1 
    ? say "solved in ", $res, "\n"
    : say "no solution\n";

say "input :  @array";
say "output:  $res";