The Bear's Den

Enter at your own risk

03 January 2025 Challenge 302

Optimal Steps

Task 1: Ones and Zeroes

Submitted by: Mohammad Sajid Anwar

You are given an array of binary strings, @str, and two integers, $x and $y.

Write a script to return the size of the largest subset of @str such that there are at most $x 0’s and $y 1’s in the subset.

A set m is a subset of n if all elements of m are also elements of n.

Example 1

Input: @str = ("10", "0001", "111001", "1", "0")
       $x = 5
       $y = 3
Output: 4

The largest subset with at most five 0's and three 1's:
("10", "0001", "1", "0")

Example 2

Input: @str = ("10", "1", "0")
       $x = 1
       $y = 1
Output: 2

The largest subset with at most one 0's and one 1's:
("1", "0")

Solution

This task can be regarded as Binary Linear Programming and solved using the GNU Linear Programming Kit (GLPK). There is a PDL module that can be used for this task.

We take \(a_{1i}\) as the number of zeroes and \(a_{2i}\) as the number of ones in \(\operatorname{str}_i\) and consider the following Binary Linear Program:

\[\begin{xalignat*}{2} &\text{maximize:} & x_1 + \ldots + x_n \\ &\text{subject to:} & a_{11} x_1 + \ldots + a_{1n} x_n & \le x \\ & & a_{21} x_1 + \ldots + a_{2n} x_n & \le y \\ & & x_i & \in \{0, 1\} \end{xalignat*}\]

After having counted the number of zeroes and ones in all strings from @str, we can solve the task with a single call to glpk:

use strict;
use warnings;
use PDL;
use PDL::NiceSlice;
use PDL::Opt::GLPK;
use experimental 'signatures';

sub ones_and_zeroes ($x, $y, @str) {
    my $a = long(
        [map {my $c = tr/0/0/} @str],
        [map {my $c = tr/1/1/} @str]
    );
    my $one = ones($a(,(0)));

    glpk($one, $a, long($x, $y), $one, $one,
        long(GLP_UP, GLP_UP), GLP_BV * $one, GLP_MAX,
        null, my $fopt = null, my $status = null);
    die "glpk returned $status\n" unless $status == GLP_OPT;

    $fopt;
}

A Larger Example

When the number of elements in @str is slightly increased, an approach based on an enumeration of subsets becomes more and more impracticable. We construct \(n\) binary strings of length \(n\) (with \(n\) as a multiple of 4) as:

\[\begin{alignat*}{2} &100&\cdots&000\\ &110&\cdots&000\\ &\vdots\\ &111&\cdots&110\\ &111&\cdots&111 \end{alignat*}\]

Now we look at any symmetric pair from the list, i.e. \(\operatorname{str}_k\) and \(\operatorname{str}_{n - k + 1}\). Together this pair contributes

to a subset. By picking \(n / 4\) different pairs, i.e. \(n / 2\) elements, we find

There is no larger subset of @str having not more than \(x\) zeros and \(y\) ones.

For \(n = 64\) this specific task can be solved using GLPK in sub-second time:

$ time ./ch-1.pl -tests 
# Seeded srand with seed '20250102' from local date.
ok 1 - skipped test # skip examples
ok 2 - one half of 64
1..2

real    0m0.151s
user    0m0.144s
sys     0m0.008s

See the full solution to task 1.

Task 2: Step by Step

Submitted by: Mohammad Sajid Anwar

You are given an array of integers, @ints.

Write a script to find the minimum positive start value such that step by step sum is never less than one.

Example 1

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

For start value 5.
5 + (-3) = 2
2 + (+2) = 4
4 + (-3) = 1
1 + (+4) = 5
5 + (+2) = 7

Example 2

Input: @ints = (1, 2)
Output: 1

Example 3

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

Solution

Here we calculate the cumulative sum over the list and restrict to non-positive values. The minimum thereof needs to be subtracted from one to get the requested minimum start value.

use strict;
use warnings;
use PDL;

sub start_val {
    1 - long(@_)->cumusumover->hclip(0)->min;
}

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.