Ones and zeroes

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.

Examples

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")

Analysis

This is one of my solutions which is straightforward to understand but probably isn't the fastest.

I use my old friend Algorithm::Combinatorics to generate all the subsets of @str, and then check each for being:

• longer than the best compliant subset found so far,
• and compliant with the ones and zeroes conditions

Using the CPAN power, the job becomes cake walk for anyone. See it yourself to believe.

Try it 

#!/usr/bin/perl

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

use v5.26;    # The Weekly Challenge - 2024-12-30
use utf8;     # Week 302 - task 1 - Ones and zeroes
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Algorithm::Combinatorics 'subsets';

ones_and_zeroes(['10', '0001', '111001', '1', '0'], 5, 3);
ones_and_zeroes(['10', '1', '0'], 1, 1);
ones_and_zeroes(['000000', '1111'], 5, 3);
ones_and_zeroes(['10101010101', '0000001111', '1', '0'], 5, 3);
ones_and_zeroes(['0'], 5, 3);
ones_and_zeroes(['00', '01', '10', '11', '00', '01', '10', '11', '00', '01', '10', '11'], 1, 1);

sub ones_and_zeroes {
    
    my ($s, $max0, $max1, $iter, $subset, $joined, $size, $num0, $num1, $best_size, $best_subset);
    
    # initialise
    ($s, $max0, $max1) = @_;
    $iter = subsets($s);
    $best_size = 0;
    
    # loop over all subsets
    while ($subset = $iter->next) {
        
        # concatenate the strings and abandon if smaller than the best so far
        $size = @$subset;
        next if $size <= $best_size;
        
        # check the number of 1s and 0s and abandon if too many 1s or 0s
        $joined = join('', @$subset);
        $num0 = $joined =~ s|0|0|g;
        $num1 = length($joined) - $num0;
        next if ($num0 > $max0 or $num1 > $max1);
        
        # found a better one
        $best_size = $size;
        $best_subset = join(qq[', '], @$subset);        
    }
    
    # report
    say qq[\nInput:  \@str = ('] . join(q[', '], @$s) . qq['), \$x = $max0, \$y = $max1];
    say qq[Output: ] . ($best_size > 0 ? qq[('$best_subset'), size = $best_size] : 'none');
}

16 lines of code

Output from script

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

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

Input:  @str = ('000000', '1111'), $x = 5, $y = 3
Output: none

Input:  @str = ('10101010101', '0000001111', '1', '0'), 
     $x = 5, $y = 3
Output: ('1', '0'), size = 2

Input:  @str = ('0'), $x = 5, $y = 3
Output: ('0'), size = 1

Input:  @str = ('00', '01', '10', '11', '00', '01', '10',
     '11', '00', '01', '10', '11'), $x = 1, $y = 1
Output: ('10'), size = 1