The Bear's Den

Enter at your own risk

17 January 2025 Challenge 304

Average Replacements

Task 1: Arrange Binary

Submitted by: Mohammad Sajid Anwar

You are given a list of binary digits (0 and 1) and a positive integer, $n.

Write a script to return true if you can re-arrange the list by replacing at least $n digits with 1 in the given list so that no two consecutive digits are 1 otherwise return false.

Example 1

Input: @digits = (1, 0, 0, 0, 1), $n = 1
Output: true

Re-arranged list: (1, 0, 1, 0, 1)

Example 2

Input: @digits = (1, 0, 0, 0, 1), $n = 2
Output: false

Solution

This task is not quite clear to me. While “re-arranging” would mean permuting the list, “replacing … digits” is something different. Furthermore, “replacing … with 1” would require a 0 at this place beforehand - just a the examples suggest. I suppose false is required as result if the list initially contains two consecutive 1s.

Therefore I’d like to formulate the task as:

Return true if $n zeros in the list can be flipped to ones such that there are no two consecutive ones in the resulting list and false otherwise.

The easiest way to solve this task I can think of is a regular expression applied to a binary string.

Two consecutive ones produce false. Otherwise, for every pair of zeros that is not followed by a one, we may flip the second zero to one. Additionally we may flip a leading zero in the string that is not followed by a one. The number of matches in a global search for such “flip-able” zeroes must not be less then the given $n for a true result.

The number of global matches can be found with a “half Saturn” operation.

use strict;
use warnings;
use experimental 'signatures';

sub arrange_binary ($n, @bin) {
    for (join '', @bin) {
        return 0 if /11/;
        return $n <= (() = /(?:^|0)0(?!1)/g);
    }
}

See the full solution to task 1.

Task 2: Maximum Average

Submitted by: Mohammad Sajid Anwar

You are given an array of integers, @ints and an integer, $n which is less than or equal to total elements in the given array.

Write a script to find the contiguous subarray whose length is the given integer, $n, and has the maximum average. It should return the average.

Example 1

Input: @ints = (1, 12, -5, -6, 50, 3), $n = 4
Output: 12.75

Subarray: (12, -5, -6, 50)
Average: (12 - 5 - 6 + 50) / 4 = 12.75

Example 2

Input: @ints = (5), $n = 1
Output: 5

Solution

Another case for an almost literal PDL solution: Take the maximum of the average over all contiguous sublists of length $n.

use strict;
use warnings;
use PDL;
use experimental 'signatures';

sub max_avg ($n, @ints) {
    pdl(\@ints)->lags(0, 1, $n)->xchg(0, 1)->average->max->sclr;
}

See the full solution to task 2.

If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.