The weekly challenge 302 - Task 1: Ones and Zeroes

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-302/#TASK1
 3 #
 4 # Task 1: Ones and Zeroes
 5 # =======================
 6 #
 7 # You are given an array of binary strings, @str, and two integers, $x and $y.
 8 #
 9 # Write a script to return the size of the largest subset of @str such that
10 # there are at most $x 0’s and $y 1’s in the subset.
11 #
12 # A set m is a subset of n if all elements of m are also elements of n.
13 #
14 ## Example 1
15 ##
16 ## Input: @str = ("10", "0001", "111001", "1", "0")
17 ##        $x = 5
18 ##        $y = 3
19 ## Output: 4
20 ##
21 ## The largest subset with at most five 0's and three 1's:
22 ## ("10", "0001", "1", "0")
23 #
24 ## Example 2
25 ##
26 ## Input: @str = ("10", "1", "0")
27 ##        $x = 1
28 ##        $y = 1
29 ## Output: 2
30 ##
31 ## The largest subset with at most one 0's and one 1's:
32 ## ("1", "0")
33 #
34 ############################################################
35 ##
36 ## discussion
37 ##
38 ############################################################
39 #
40 # We create all possible subsets. Then we check which ones fulfill the
41 # requirements regarding the number of ones and zeroes - of those we
42 # select the one that has the most elements.
43 
44 use strict;
45 use warnings;
46 use Data::PowerSet qw(powerset);
47 
48 one_and_zeroes(5, 3, "10", "0001", "111001", "1", "0");
49 one_and_zeroes(1, 1, "10", "1", "0");
50 
51 sub one_and_zeroes {
52    my ($x, $y, @str) = @_;
53    print "Input: x = $x, y = $y, str = (\"" . join("\", \"", @str) . "\")\n";
54    my $subsets = powerset(@str);
55    my $max = 0;
56    foreach my $subset (@$subsets) {
57       my $count = scalar @$subset;
58       my $ones = 0;
59       my $zeroes = 0;
60       foreach my $elem (@$subset) {
61          my @digits = split //, $elem;
62          foreach my $digit (@digits) {
63             if($digit eq "1" ) {
64                $ones++;
65             } else {
66                $zeroes++;
67             }
68          }
69       }
70       if($zeroes <= $x && $ones <= $y && $max < $count) {
71          $max = $count;
72       }
73    }
74    print "Output: $max\n";
75 }