Dinner for a Tiny Number of Dictators

Wherein we discover the biggest monsters can require the tiniest of petty trivialities to satisfy the status quo

THE WEEKLY CHALLENGE – PERL & RAKU #80

episode one:
“Tiny Numbers of Things”

---

TASK #1 › Smallest Positive Number

Submitted by: Mohammad S Anwar

You are given unsorted list of integers @N.
Write a script to find out the smallest positive number missing.

Example 1:

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

Example 2:

Input: @N = (1, 8, -1)
Output: 2

Example 3:

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

Method

As we are given an unsorted list, perhaps the first idea might be to sort it, and then maybe look for holes somehow. This may well work for shorter lists, but as they get longer it will become more and more a waste of effort to finish a giant sort when all we need to do is find a hole in the middle (the lack of any constraints on the list values is somewhat conspicuous, and we should assume negative values and zeros will abound in the data).

I think a better way to proceed in the long run will be to start with ℕ, the Natural number set, and go about this from the other direction, looking for elements not found in our list.

Perl Solution

What we are looking for is a value, not a list element. This is important because it speaks to what we don’t need to know: we don’t need a position, we don’t need a list. All we need is a value, and to know whether it exists or not.

In Perl, we have hashes, with keys, that either exist or not. Sounds perfect.

Processing through the list elements once to map them to hash keys is a simple task; after that it’s a series of hash lookups as we count upwards from 1 until we find a miss. In the very worst case scenario when we are given a list (1, 2, 3, 4, … n) the length, though indeterminate, is not infinite, and so eventually the next highest value not contained within our list will always be found when we run out of elements.

[colincrain@boris:~/Code/PWC]$  perl 80_1_tiny_numbers.pl 5 2 6 7 -1 -10 -2 0 1 4 10 2 39 -5 -2 3
input : (5, 2, 6, 7, -1, -10, -2, 0, 1, 4, 10, 2, 39, -5, -2, 3)
output:  8

use warnings;
use strict;
use feature ":5.26";

## ## ## ## ## MAIN:

my @input = @ARGV ? @ARGV : (1, 8, -1, 2, -7, 4, 0, 3);
say "input : (", (join ', ', @input), ")";

my %lookup = map { $_ => 1 } @input;
my $num;

while ( ++$num ) {  ## @input is finite so this will end eventually
    say "output:  $num" and exit if ! exists $lookup{$num};
}

Raku Solution

In Raku we can use a Bag to hold our list data; either a given element is in the Bag or not. For the main logic we iterate over an infinite list, checking to make sure a given element exists in the bag. If it doesn’t, then we speak its name and bid a hasty retreat out of our infinite loop. Given that the input list is finite, we are guaranteed to eventually run out of matches to the bag elements, so the loop will always exit.

unit sub MAIN (*@input) ;
@input.elems == 0 and @input = 5, 2, -2, 0, 16, 1, 6, 3, -18, 1, 0, 4;
my %lookup = @input.Bag;

say "input : ", @input;
%lookup{$_}:exists or say "output:  $_" and exit for (1..*);

episode two:
“Dinner for Dictators”

---

TASK #2 › Count Candies

Submitted by: Mohammad S Anwar

You are given rankings of @N candidates.
Write a script to find out the total candies needed for all candidates. You are asked to follow the rules below:

• You must given at least one candy to each candidate.
• Candidate with higher ranking get more candies than their immediate neighbors on either side.

Example 1:

Input: @N = (1, 4, 3, 2)

Explanation:

Applying rule #a, each candidate will get one candy. So total candies needed so far 4. Now applying rule #b, the first candidate do not get any more candy as its rank is lower than it’s neighbours. The second candidate gets two more candies as it’s ranking is higher than it’s both neighbour. The third candidate gets one more candy as it’s ranking is higher than it’s neighbour. Finally the fourth candidate do not get any extra candy as it’s ranking is not higher than neighbour. Therefore total candies required is 7.

Output: 7

PREFACE

Before we begin, I do think this delightful challenge deserves a reimagining for dramatic effect:

“You are tasked with providing candied treats for a dinner, at the place settings along a long table, on a dais facing a large hall. The diners are to be a gathering of dictators and very powerful men, seated in a line facing the room. Because they are by nature petulant and insecure, each man requires an offering of candy as a token of respect, in an amount that he deems worthy of his position amongst his peers. Every man of higher stature than his neighbors to either side must always have more candies than them, lest he be perceived as weak. There are no exceptions, and failure to properly dispense the correct amounts will result in imprisonment at best. For obscure reasons of protocol and diplomacy, there is no apparent ordering to the table seating, so you must rely on ratings asigned to the individual seat positions to know how to fill the candy bowls. As the government hosting the feast has only been able to procure a limited amount of candies for you to distribute, you will have no choice but to dispense the minumum number possible to fulfill your obligations, hoping you will have enough to supply the whole table. May the odds be ever in your favor.”

An astute reader will realize that I have added something in my rephrasing (besides the Hunger Games reference) —  that is, to only supply the minimum number of candies to satisfy the criteria. Otherwise without this condition a trivial answer is available: to either immediately assign a number of candies equal to the subject’s rating, or, should it be necessary, to declare the minimum rating value of the the diners to be shifted to 1, and apply an equivalent adjustment to every other other value, without any further calculation. After all, the ratings system is undefined, and could contain negative values or zeros, and every diner must be given one candy. It’s obvious this solution satisfies the text, if not the soul, of the challenge. So we will choose our own, more challenging, game.

Method

It took me a while to figure out what was realy being asked here. I spent some time constructing an additive method, making multiple passes across the data and augmenting values for each setting as required until no more adjustment was necessary, but found the end result lacking; it worked well but seemed to be somehow missing the point. It did, however, get me looking at the relationship between the solutions and the source arrays.

Then it occured to me that what we were doing was minimizing the data, while maintaining the relative relationships between adjacent elements. Those values larger than their neighbor will remain greater, those less, less, but the whole list will have those differences minimized and pushed as far as possible towards 1, the base value. A 14 rating followed by a 4 does not need to be 10 more to be greater, only 1. Thus the 14 can become a 5 without altering the big picture.

It’s somewhat akin to compressing a digital signal and normalizing it around a value such as 0, but not quite. Here both the compression and rezeroing are extremely localized events, affected only by their immediate adjacent neighbors, making the adjusting discontinuous. Specifically, any element less than both its neighbors will be immediately reduced all the way to the floor of 1, reestablishing the lower boundary again.

Taking this to mind, the process is very simple: starting with the original array, the value of each element is reduced according to the rule that if it is larger than one or both of of its neighbors, the value assigned to output is one more than the larger of these smaller neighbor’s output, and if smaller than both, then 1.

The part that makes this work, though, is the order of action. By selectively moving the smallest elements first, the baseline positions are established, then the elements that need to be one more than this are placed, then one more than that. To get the order right we will need a list of the indexes of the original array, resorted according to the array values, lowest to highest. Working through this list, at the end every element will have been valued with respect to its neighbors exactly once in assigning the output array.

Perl Solution

[colincrain:~/PWC]$  perl 80_2_dinner_for_dictators.pl 1 9 5 2 1 8 9 1 2 
input:  1 9 5 2 1 8 9 1 2
output: 1 4 3 2 1 2 3 1 2

use warnings;
use strict;
use feature ":5.26";

## ## ## ## ## MAIN:


my @input  = scalar @ARGV   ? @ARGV 
                            : (1, 9, 5, 2, 6, 8, 9, 10, 2, 5, 1);

my @output;

normalize(\@input, \@output);

say "input:  @input";
say "output: @output";

## ## ## ## ## SUBS:

sub normalize {
## starting from the smallest value, if the given index value is
## larger than either of its neighbors, then it is
## revalued in the output to be the larger of its neighbors' output plus one. If it is
## smaller than both it is 1.
    my ($in, $out) = @_;

    my @order = sort { $in->[$a] <=> $in->[$b] } keys $in->@*;  
    for my $i (@order) {
        my $min = 1;
        for (1,-1) {
            next if ( $i + $_ < 0 or not defined $in->[$i+$_]) ;
            if ($in->[$i] > $in->[$i+$_]) {
                $min = max($out->[$i+$_] + 1, $min);
            }
        }
        $out->[$i] = $min;    
    }
}

sub max {
    my $max = "-inf";
    for (@_) {
        $max = $_ if $max < $_;
    }
    return $max;
}

Raku Solution

Raku has the nice feature that if you hand a single argument to sort, it will assume you wish to sort by applying that to the list as an &sortby function, making our list of reordered indices a little more clearly constructed.

After assigning a couple of delta values (here indicated in unicode), we construct the indices for neighboring elements to each item in the ordered list and assign them to the topic, checking whether they actually exist. If they do we find the maximum of any smaller neighbors and add one to get the output for that index. If none are found the default value of 1 falls through and that is assigned instead.

unit sub MAIN (*@input) ;
@input.elems == 0 and @input = 1, 100, 5, 2, 6, 8, 9, 10, 2, 5, 1;
my @output;

normalize(@input, @output);

say "input:  ", @input;
say "output: ", @output;

sub normalize (@input, @output) {
## starting from the smallest value, if the given index value is larger than
## either of its neighbors, then it is valued in the output to be the larger of
## its (smaller) neighbors' output plus one. If it is smaller than both it is 1.

    my @order = @input.keys.sort:{ @input[$_] } ; 
    for @order -> $i {
        my $min = 1;
        for 1, -1 -> $Δ {
            given $i + $Δ {
                next unless $_ ~~ any @input.keys;          
                if @input[$i] > @input[$_] {
                    $min = (@output[$_] + 1, $min).max;     
                }
            }
        }
        @output[$i] = $min;    
    }
}