The Weekly Challenge 286

Self Spammer & Order Game: Source Quines and Array Reduction in Perl & Python

Lubos Kolouch September 9, 2024 Challenge Details GitHub Solutions

Task 1: Self Spammer

Write a program that outputs one word of its own script / source code at random.

A "word" in this context is defined as any continuous sequence of non-whitespace characters separated by whitespace.

Method Explanation

The task belongs to the family of self-referential programs or quines. Instead of recreating its entire source code, the script needs to access its own file content, parse it into whitespace-delimited tokens ("words"), and select one uniformly at random.

In both languages, this can be achieved cleanly:

  • Perl: The special variable $0 holds the current program filename. We open the file safely, read line-by-line or slurp the contents, split on \s+, filter out empty strings, and pick an element using $words[ rand @words ].
  • Python: We use __file__ or os.path.abspath(__file__) to locate the running script. The content is read with UTF-8 encoding, tokenized using Python's built-in str.split() (which automatically collapses whitespace), and a word is selected via random.choice().

Perl Solution

use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(Str);
use Test::More;

signature_for get_random_word => (
    method     => 0,
    positional => [ Str, { default => $0 } ],
);

sub get_random_word ( $filename = $0 ) {
    open my $fh, '<', $filename or die "Cannot open $filename: $!";
    my @words;
    while ( my $line = <$fh> ) {
        push @words, split( /\s+/, $line );
    }
    close $fh;

    # Filter out empty tokens
    @words = grep { length $_ } @words;

    my $random_word = $words[ rand @words ];
    return $random_word;
}

Python Solution

import os
import random

def get_random_word(filename: str | None = None) -> str:
    """Read source code, tokenize into whitespace-delimited words, and return a random word."""
    target_path = filename if filename is not None else os.path.abspath(__file__)
    with open(target_path, encoding="utf-8") as file:
        content = file.read()
    words = content.split()
    return random.choice(words)  # nosec B311

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 and return the last remaining element.

The rules of the game are:

  1. At each round, pair consecutive elements: (ints[2*i], ints[2*i + 1]).
  2. If the pair index i is even (0, 2, 4, ...), replace the pair with min(a, b).
  3. If the pair index i is odd (1, 3, 5, ...), replace the pair with max(a, b).
  4. Repeat the reduction until only one element remains.

Method Explanation

The game is simulated iteratively. Because the array length $N$ is always a power of 2, pairing adjacent elements halves the size of the array at each round ($N \to N/2 \to \dots \to 1$), guaranteeing termination after $\log_2 N$ rounds.

In each step:

  • We loop over indices $i \in [0, \dots, N/2 - 1]$.
  • The two numbers forming the $i$-th pair are located at indices $2i$ and $2i+1$.
  • If $i \pmod 2 == 0$, we append $\min(\text{first}, \text{second})$.
  • If $i \pmod 2 == 1$, we append $\max(\text{first}, \text{second})$.
  • The newly constructed list replaces the current list.

Perl Solution

use v5.38;
use warnings;
use List::Util qw(min max);
use Type::Params -sigs;
use Types::Standard qw(ArrayRef Int);

signature_for order_game => (
    method     => 0,
    positional => [ ArrayRef [Int] ],
);

sub order_game ($ints) {
    my @current_list = @$ints;
    while ( @current_list > 1 ) {
        my @next_list;
        my $pairs = int( @current_list / 2 );
        for my $i ( 0 .. $pairs - 1 ) {
            my $first  = $current_list[ 2 * $i ];
            my $second = $current_list[ 2 * $i + 1 ];
            if ( $i % 2 == 0 ) {
                push @next_list, min( $first, $second );
            }
            else {
                push @next_list, max( $first, $second );
            }
        }
        @current_list = @next_list;
    }
    return $current_list[0];
}

Python Solution

def order_game(ints: list[int]) -> int:
    """Simulate the Order Game on the given list of integers."""
    current_list = list(ints)
    while len(current_list) > 1:
        next_list: list[int] = []
        n = len(current_list)
        for i in range(n // 2):
            first = current_list[2 * i]
            second = current_list[2 * i + 1]
            if i % 2 == 0:
                next_list.append(min(first, second))
            else:
                next_list.append(max(first, second))
        current_list = next_list
    return current_list[0]