Ugandan Firing Squad

THE WEEKLY CHALLENGE – PERL & RAKU #48

TASK #1

Survivor

There are 50 people standing in a circle in position 1 to 50. The person standing at position 1 has a sword. He kills the next person i.e. standing at position 2 and pass on the sword to the immediate next i.e. person standing at position 3. Now the person at position 3 does the same and it goes on until only one survives.

Write a script to find out the survivor.

Comments

This is much like PWC 46-2, “Is the Room Open?” albeit with a shockingly un-healthy dose of inhumanity and horror. In keeping with that spirit, I’ve changed the title and the supplied weapon from sword to shovel. I’m sure there are other options of historical precedence to choose from, but for some reason I went with Idi Amin. We will not speak to that sordid reference again.

In the Hotel challenge, the second employee merely closes every second door, which is tidy and well mannered. In this version we have two changes to that alternating pattern, the first that “closing” the element removes it from play, the second that the process is circular, so that once the last person is reached the slaughter continues unabated as the last person is still adjacent to the first. As such the processing, the elimination of the person to one’s immediate side¹, continues until there’s no one remaining for the sole survivor to murder.

---

¹left or rightward implementation of the death-dealing is neither specified, nor does it matter. Feel free to infer a political metaphor here if you wish.

Method

We will create a list of people and number them 0-49. The actual naming convention does not matter, we only need a unique label to keep track of the individuals as the winnowing progresses. Indexing on 0, though, instead of 1 will help us later, to reveal patterns in the process. So the result, position 36, according to the original spec is postion 37. As stated, we’re going to go head and keep this change, as it makes the pattern easier to see.

When we step through the process defined, the person at a given index kills the next person, at index + 1. That person is eliminated, and the person beyond moves into the empty slot. The shovel is then handed to that person, now at slot index + 1, who eyes the person at index + 2. The circular aspect is modeled by applying a modulus equal to the number of remaining people in the circle at a given moment. That number is always one more than the array index, so when we are at the end of the array, index + 1 is equal to the size of the array, the index is reset to position 0, who becomes the next unlucky target, and the horror continues unabated. No rest for the wicked.

In a post-analysis, a loop construct over a range of inputs reveals a simple underlying progression based around powers of 2, resulting in a practical survival plan:

Conclusion

If one ever has the misfortune to be in this terrible situation, quickly count the size of the group. Subtract the largest smaller power of two from that number and double the remainder. Counting from zero, make sure you are in that position in line and you will live. (Assuming you wish to survive, of course. That ethical morass is beyond the scope of the current discussion.) For example, if you have 57 people in the group, subtract 32, yielding 25, doubled to 50. Counting from 0, insert yourself at position 50. Easy peasy. Now all you have to do is kill 5 people. Sorry.

Or at the bare minimum, (remember you are counting from 0!) make sure you are in an even-numbered position (that’s position, not count). Then at least you have a chance, as all the odds are always killed.

In a more sobering note, if you are unable to control your position in the circle and conclude you are lost, the best play may be to strip naked and try and beguile the guards. If successfully distracted, or perhaps confused, grab a pistol and start shooting. The outcome will likely be the same, however you may at least have the satifaction of taking a few of the bastards with you. May the odds be in your favor.

Perl Solution

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

## ## ## ## ## MAIN
my $victims = 50;  ## I think the last person standing still qualifies as a victim in this 
                   ## psychopath's fever-dream battle royal
my @circle = (0..$victims-1);
say join ", ", @circle;
my $next = 0;

while ( scalar @circle > 1 ) {
    $next = ++$next % scalar @circle;    ## find the next target position
    splice @circle, $next, 1;            ## do the dirty deed and the next person slide into that spot
    say join "  ", @circle;              ## not necessary but makes the progression visible
}

say "survivor: ", $circle[0], "\n";



## ## ## ## ##

## now let's take a moment to look at an overview of the positional standing of
## the last survivor as we vary the starting number of victims in the circle:

for (2..100) {
    printf "%2d --> %d\n", $_, survivor($_);
}

sub survivor {
    my @circle = (0..shift(@_)-1);
    my $next = 0;

    while ( scalar @circle > 1 ) {
        $next = ++$next % scalar @circle;
        splice @circle, $next, 1;
    }

    return $circle[0];
}

Raku Solution

sub MAIN (Int:D $victims where {$victims > 0} = 50) {

    my @circle = 0 .. $victims - 1;
    @circle.join("  ").say;                 ## just a look at the starting state
    my $next = 0;
    
    while (  @circle.elems > 1 ) {
        $next = ++$next % @circle.elems;    ## advance the targeting
        @circle.splice($next, 1);           ## remove the unlucky victim nd move in the next
        @circle.join( "  " ).say;           ## not strictly necessary but allows us to observe the winnowing
    }

    ## the sole survivor is the only remaining element in the array
    say "survivor: " ~ @circle[0] ~ "\n";   
    
    say "meta-analysis by size of stating circle:\n";
    say    "size | survivor";
    say    "-----+----------";
    printf "%3d --> %d\n", $_, survivor($_) for (2..100);

}

## ## ## ## ##

## now let's take a moment to look at an overview of the positional standing of
## the last survivor as we vary the starting number of victims in the circle:

sub survivor (Int:D $size where {$size > 0}){
    my @circle = (0..$size-1);
    my $next = 0;

    while (  @circle.elems > 1 ) {
        $next = ++$next % @circle.elems;
        @circle.splice($next, 1);
    }

    return @circle[0];
}