laurent_r

These are some answers to the Week 286, Task 2, of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few days from now (on September 15, 2024, at 23:59). This blog post provides some solutions to this challenge. Please don’t read on if you intend to complete the challenge on your own.

Task 2: Order Game

You are given an array of integers, @ints, whose length is a power of 2.

Write a script to play the order game (min and max) and return the last element.

Example 1

Input: @ints = (2, 1, 4, 5, 6, 3, 0, 2)
Output: 1

Operation 1:

    min(2, 1) = 1
    max(4, 5) = 5
    min(6, 3) = 3
    max(0, 2) = 2

Operation 2:

    min(1, 5) = 1
    max(3, 2) = 3

Operation 3:

    min(1, 3) = 1

Example 2

Input: @ints = (0, 5, 3, 2)
Output: 0

Operation 1:

    min(0, 5) = 0
    max(3, 2) = 3

Operation 2:

    min(0, 3) = 0

Example 3

Input: @ints = (9, 2, 1, 4, 5, 6, 0, 7, 3, 1, 3, 5, 7, 9, 0, 8)
Output: 2

Operation 1:

    min(9, 2) = 2
    max(1, 4) = 4
    min(5, 6) = 5
    max(0, 7) = 7
    min(3, 1) = 1
    max(3, 5) = 5
    min(7, 9) = 7
    max(0, 8) = 8

Operation 2:

    min(2, 4) = 2
    max(5, 7) = 7
    min(1, 5) = 1
    max(7, 8) = 8

Operation 3:

    min(2, 7) = 2
    max(1, 8) = 8

Operation 4:

    min(2, 8) = 2

Order Game in Raku

We loop over the input array (@in), picking two items ($iand $j) each time, compute and store the min or max into a new array (@next-list). At the end of this loop, we replace @in by the new array, and start all over again. The process stops when there is only one element left in the array.

To know whether we need to perform max or min, we set a Boolean variable ($min) to true before we start and negate its value at each step of the process. If $min is true, then we need to compute the min, if it is false, then we compute the max.

sub order-game (@in is copy) {
    my $min = True;
    loop {
        my @next-list;
        for @in -> $i, $j {
            my $new = $min ?? min $i, $j !! max $i, $j;
            push @next-list, $new;
            $min = not $min;
        }
        return @next-list[0] if @next-list.elems == 1;
        @in = @next-list;
    }
}

my @tests = (2, 1, 4, 5, 6, 3, 0, 2), (0, 5, 3, 2),
            (9, 2, 1, 4, 5, 6, 0, 7, 3, 1, 3, 5, 7, 9, 0, 8);
for @tests -> @test {
    printf "%-8s ... => ", "@test[0..3]";
    say order-game @test;
}

This program displays the following output:

$ raku ./order-game.raku
2 1 4 5  ... => 1
0 5 3 2  ... => 0
9 2 1 4  ... => 2

Note that we display only the four first items of the input array for reasons having to do with the formatting of this blog post (to avoid too long lines).

That works fine, but you may want to look below for a simpler solution.

Order Game in Perl

For solving the task in Perl, we first need to have some min and max subroutines. Since I believe it is not really fair to use an off-the-shelf software component for a coding challenge, I wrote two auxiliary subroutines on this model:

sub max { $_[0] > $_[1] ? $_[0] : $_[1]; }

My next task was to port the Raku order-game subroutine to Perl, as I usually do. At this point, it came to my mind that there might be a simpler solution. Instead of using two nested loops, we could use a single loop on a circular buffer, i.e. an array where, at each step of the process, we pick and remove two items from the beginning and add the min or max, as the case may be, at the end of the array. Most of the time, I copy the arguments into new variables but, here, I decided to work directly on @_ because it is simpler to shift from it. The drawback it that it modifies the subroutine arguments on the caller side, but we don't care since they are no longer used.

To know whether we need max or min, we set a Boolean variable ($min) to a true value (1) before we start and negate its value at each step of the process. If $min is true, then we need to compute the min, if it is false, then we compute the max.

use strict;
use warnings;
use feature 'say';

sub max { $_[0] > $_[1] ? $_[0] : $_[1]; }

sub min { $_[0] > $_[1] ? $_[1] : $_[0]; }

sub order_game {
    my $min = 1;
    my @in = @_;
    while (1) {
        my ($i, $j) = (shift, shift);
        push @_, $min ? min($i, $j) : max $i, $j;
        $min = not $min;
        return $_[0] if @_ == 1;
    } 
}

my @tests = ([2, 1, 4, 5, 6, 3, 0, 2], [0, 5, 3, 2],
            [9, 2, 1, 4, 5, 6, 0, 7, 3, 1, 3, 5, 7, 9, 0, 8]);
for my $test (@tests) {
    printf "%-8s ... => ", "@$test[0..3]";
    say order_game @$test;
}

This program displays the following output:

$ perl ./order-game.pl
2 1 4 5  ... => 1
0 5 3 2  ... => 0
9 2 1 4  ... => 2

Order Game in Raku, revisited

Since this Perl solution is better than the previous Raku implementation, I thought it would be nice to back port the Perl program to Raku.

sub order-game (@in is copy) {
    my $min = True;
    loop {
        my @pair = @in.splice(0, 2);
        push @in, $min ?? min @pair !! max @pair;
        $min = not $min;
        return @in[0] if @in.elems == 1;
    }
}

my @tests = (2, 1, 4, 5, 6, 3, 0, 2), (0, 5, 3, 2),
            (9, 2, 1, 4, 5, 6, 0, 7, 3, 1, 3, 5, 7, 9, 0, 8);
for @tests -> @test {
    printf "%-8s ... => ", "@test[0..3]";
    say order-game @test;
}

This program displays the same output as its previous version:

$ raku ./order-game-2.raku
2 1 4 5  ... => 1
0 5 3 2  ... => 0
9 2 1 4  ... => 2

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on September 22, 2024. And, please, also spread the word about the Perl Weekly Challenge if you can.