Task — 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.

Examples

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

Analysis

There seems to be little point in not doing this exactly as defined. The number of min and max halves with every operation, so even with a million (2 ** 20) input numbers only 20 operations would be needed. So hyper-efficiency is hardly necessary.

My solution copies the values within @ints. One could perhaps not copy the numbers but just keep track of the indices still in play, but that's not going to save much.

As always, in 'real life' it would be prudent to check the assertion that the the number of @ints is a power of 2.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2024-09-09
use utf8;     # Week 286 - task 2 - Order game
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

my ($minmax, @mm);
@mm = qw(min max);

order_game(2, 1, 4, 5, 6, 3, 0, 2);
order_game(9, 2, 1, 4, 5, 6, 0, 7, 3, 1, 3, 5, 7, 9, 0, 8);

# larger example
my ($j, @ints);
@ints[$_] = int(rand(50)) for 0 .. 31;
order_game(@ints);

sub order_game {
    
    my (@ints, $m, $n, $op, $e);
    
    # initialise
    @ints = @_;
    $minmax = 0;
    say qq[\nInput:  \@ints = (] . join(', ', @ints) . ')';
    
    # loop over operations
    $n = @ints;
    while ($n >= 2) {
        $e .= qq[\n\nOperation ] . ++ $op . ':';
        
        # loop over pairs
        for ($m = 0; $m < $n; $m += 2) {
            $e .= qq[\n   $mm[$minmax]($ints[$m], $ints[$m + 1]) = ];
            $ints[$m / 2] = minmax($ints[$m], $ints[$m + 1]);
            $e .= $ints[$m / 2];
        }       
        $n /= 2;
    }       
    
    # and the answer is ...
    say qq[Output: $ints[0]$e];
}

sub minmax {
    
    $minmax = 1 - $minmax;
    if ($minmax) {
        return $_[0] < $_[1] ? $_[0] : $_[1];
    } else {
        return $_[0] > $_[1] ? $_[0] : $_[1];
    }
}

Output

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

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

Input:  @ints = (6, 35, 14, 4, 21, 0, 0, 21, 17, 7, 3, 5, 45, 6, 16, 25, 10, 47, 48, 42, 22, 44, 13, 0, 43, 7, 41, 41, 14, 8, 30, 34)
Output: 6

Operation 1:
   min(6, 35) = 6
   max(14, 4) = 14
   min(21, 0) = 0
   max(0, 21) = 21
   min(17, 7) = 7
   max(3, 5) = 5
   min(45, 6) = 6
   max(16, 25) = 25
   min(10, 47) = 10
   max(48, 42) = 48
   min(22, 44) = 22
   max(13, 0) = 13
   min(43, 7) = 7
   max(41, 41) = 41
   min(14, 8) = 8
   max(30, 34) = 34

Operation 2:
   min(6, 14) = 6
   max(0, 21) = 21
   min(7, 5) = 5
   max(6, 25) = 25
   min(10, 48) = 10
   max(22, 13) = 22
   min(7, 41) = 7
   max(8, 34) = 34

Operation 3:
   min(6, 21) = 6
   max(5, 25) = 25
   min(10, 22) = 10
   max(7, 34) = 34

Operation 4:
   min(6, 25) = 6
   max(10, 34) = 34

Operation 5:
   min(6, 34) = 6