This is my response to The Weekly Challenge #302.
@str, and two integers,
$x and $y.
@str such
that there are at most $x 0’s and $y 1’s in the subset.
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")
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")
#! /usr/bin/env raku
subset PosInt of Int where * > 0;
unit sub MAIN (*@str where @str.elems > 1 && all(@str) ~~ /^<[01]>+$/, # [1]
:a(:$all) = 0, # [2]
PosInt :o(:$ones) = 0, # [3]
PosInt :z(:$zeroes) = 0, # [4]
:v(:$verbose) = $all); # [2a]
my $output = 0; # [5]
for @str.combinations(1 .. *).reverse -> @combo # [6]
{
my %freq = @combo.join.comb.Bag; # [7]
%freq<0> //= 0; # [7a]
%freq<1> //= 0; # [7b]
if %freq<0> <= $zeroes && %freq<1> <= $ones # [8]
{
say ": + { @combo.join(",") } -> 0:%freq<0> 1:%freq<1> [{ @combo.elems }]"
if $verbose;
$output = @combo.elems unless $output; # [5a]
last unless $all; # [2b]
}
elsif $verbose
{
say ": - { @combo.join(",") } -> 0:%freq<0> 1:%freq<1>";
}
}
say $output; # [5b]
[1] Two or more strings consisting of one or more binary digits only.
[2] The program will stop after the first match (the longest), but use the «all» option if you want to see all of them (handled by [2b]). This option enables verbose as well [2a], as it would not make sense otherwise.
[3] I find o (ones) better than x, so have chosen to use that instead.
The program will die if the named argument is not supplied, as the
default value (zero) is ilegal. An explicit die as default value
will also work.
[4] z (zeroes) instead of y.
[5] The result, collected here so that «all» mode can do its job. Update the value, if not already set [5a]. Print the value if set [5b]. Note that initialising it to zero works, as the lowest possible answer is 1.
[6] All possible combinations, excluding the one
with no elements. Note that the argument to combinations is a
Range, which cannot count dowm so we have to reverse the
result so that we get the largest subset first.
See docs.raku.org/routine/combinations for more information about combinations.
[7] Get the count of ones and zeroes, courtesy of a Bag
that we then assign to a plain hash. Ensure that the two hash values
exist [7a,b], so that looking them up later on does not give warnings.
See docs.raku.org/routine/Bag for more information about Bag.
[8] Is the rule in the challenge satisfied? If so, save the length [5a] if not already done, and exit [2b] unless «all» mode is used.
Running it:
$ ./ones-and-zeroes -z=5 -o=3 10 0001 111001 1 0
4
$ ./ones-and-zeroes -z=1 -o=1 10 1 0
2
Looking good.
With verbose mode:
$ ./ones-and-zeroes -v -z=5 -o=3 10 0001 111001 1 0
: - 10,0001,111001,1,0 -> 0:7 1:7
: - 0001,111001,1,0 -> 0:6 1:6
: - 10,111001,1,0 -> 0:4 1:6
: + 10,0001,1,0 -> 0:5 1:3 [4]
4
$ ./ones-and-zeroes -v -z=1 -o=1 10 1 0
: - 10,1,0 -> 0:2 1:2
: + 1,0 -> 0:1 1:1 [2]
2
With «all» mode:
$ ./ones-and-zeroes -a -z=5 -o=3 10 0001 111001 1 0
: - 10,0001,111001,1,0 -> 0:7 1:7
: - 0001,111001,1,0 -> 0:6 1:6
: - 10,111001,1,0 -> 0:4 1:6
: + 10,0001,1,0 -> 0:5 1:3 [4]
: - 10,0001,111001,0 -> 0:7 1:6
: - 10,0001,111001,1 -> 0:6 1:7
: - 111001,1,0 -> 0:3 1:5
: + 0001,1,0 -> 0:4 1:2 [3]
: - 0001,111001,0 -> 0:6 1:5
: - 0001,111001,1 -> 0:5 1:6
: + 10,1,0 -> 0:2 1:2 [3]
: - 10,111001,0 -> 0:4 1:5
: - 10,111001,1 -> 0:3 1:6
: + 10,0001,0 -> 0:5 1:2 [3]
: + 10,0001,1 -> 0:4 1:3 [3]
: - 10,0001,111001 -> 0:6 1:6
: + 1,0 -> 0:1 1:1 [2]
: - 111001,0 -> 0:3 1:4
: - 111001,1 -> 0:2 1:5
: + 0001,0 -> 0:4 1:1 [2]
: + 0001,1 -> 0:3 1:2 [2]
: - 0001,111001 -> 0:5 1:5
: + 10,0 -> 0:2 1:1 [2]
: + 10,1 -> 0:1 1:2 [2]
: - 10,111001 -> 0:3 1:5
: + 10,0001 -> 0:4 1:2 [2]
: + 0 -> 0:1 1:0 [1]
: + 1 -> 0:0 1:1 [1]
: - 111001 -> 0:2 1:4
: + 0001 -> 0:3 1:1 [1]
: + 10 -> 0:1 1:1 [1]
4
$ ./ones-and-zeroes -a -z=1 -o=1 10 1 0
: - 10,1,0 -> 0:2 1:2
: + 1,0 -> 0:1 1:1 [2]
: - 10,0 -> 0:2 1:1
: - 10,1 -> 0:1 1:2
: + 0 -> 0:1 1:0 [1]
: + 1 -> 0:0 1:1 [1]
: + 10 -> 0:1 1:1 [1]
2
No subset is also a result:
$ ./ones-and-zeroes -v -a -z=1 -o=1 11 110 001 0001
: - 11,110,001,0001 -> 0:6 1:6
: - 110,001,0001 -> 0:6 1:4
: - 11,001,0001 -> 0:5 1:4
: - 11,110,0001 -> 0:4 1:5
: - 11,110,001 -> 0:3 1:5
: - 001,0001 -> 0:5 1:2
: - 110,0001 -> 0:4 1:3
: - 110,001 -> 0:3 1:3
: - 11,0001 -> 0:3 1:3
: - 11,001 -> 0:2 1:3
: - 11,110 -> 0:1 1:4
: - 0001 -> 0:3 1:1
: - 001 -> 0:2 1:1
: - 110 -> 0:1 1:2
: - 11 -> 0:0 1:2
0
@ints.
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
Input: @ints = (1, 2)
Output: 1
Input: @ints = (1, -2, -3)
Output: 5
#! /usr/bin/env raku
unit sub MAIN (*@ints where @ints.elems > 1 && all(@ints) ~~ Int, # [1]
:v(:$verbose));
NXT: for 1 .. * -> $start # [2]
{
say ": Start value $start" if $verbose;
my $sum = $start; # [3]
for @ints -> $int # [4]
{
say ": $sum + ({ $int < 0 ?? $int !! "+$int" }) = { $sum + $int }"
if $verbose;
$sum += $int; # [5]
next NXT if $sum < 1; # [6]
}
say $start; # [7]
last; # [8]
}
[1] Ensure at least 2 integers.
[2] Iterate over the non-negative integers, starting at the lowest. This is the candidate for the «minimum positive start value» we are looking for.
[3] The current sum, starting with (at) the start value.
[4] Iterate over the input values.
[5] • Add the current value.
[6] • Skip this iteration of the outer loop [2] if the condition is not met.
[7] Failure to fail (in [6]) means success. Say so.
[8] We are done; exit the loop (and the program).
Running it:
$ ./step-by-step -- -3 2 -3 4 2
5
$ ./step-by-step 1 2
1
$ ./step-by-step 1 -2 -3
5
Looking good.
The -- (double dash) argument is there to tell the
system to stop parsing the arguments as command line options. We do
not want it to treat -3 as a command line option.
With verbose mode:
$ ./step-by-step -v -- -3 2 -3 4 2
: Start value 1
: 1 + (-3) = -2
: Start value 2
: 2 + (-3) = -1
: Start value 3
: 3 + (-3) = 0
: Start value 4
: 4 + (-3) = 1
: 1 + (+2) = 3
: 3 + (-3) = 0
: Start value 5
: 5 + (-3) = 2
: 2 + (+2) = 4
: 4 + (-3) = 1
: 1 + (+4) = 5
: 5 + (+2) = 7
5
$ ./step-by-step -v 1 2
: Start value 1
: 1 + (+1) = 2
: 2 + (+2) = 4
1
$ ./step-by-step -v 1 -2 -3
: Start value 1
: 1 + (+1) = 2
: 2 + (-2) = 0
: Start value 2
: 2 + (+1) = 3
: 3 + (-2) = 1
: 1 + (-3) = -2
: Start value 3
: 3 + (+1) = 4
: 4 + (-2) = 2
: 2 + (-3) = -1
: Start value 4
: 4 + (+1) = 5
: 5 + (-2) = 3
: 3 + (-3) = 0
: Start value 5
: 5 + (+1) = 6
: 6 + (-2) = 4
: 4 + (-3) = 1
5
And that's it.