Weekly Challenge 302

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Ones and Zeroes

Task

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.

My solution

Rather than calling the variables x and y, I've named them max_zeros and max_ones, as this is more meaningful. For the command line I take the last two values as max_zeros and max_ones with the rest of the values slurped into the s array.

For this task, I have the variable length that starts with the number of items in s down to one. For each length, I then use itertool's combination function to compute all unique combinations of length items, and store this in the subset variable.

For each subset, I join all the strings together, count the number of zeros and ones, and see if they are less than or equal to max_zeros and max_ones respectively. If they are, I return the length variable. If none is found, I return zero.

def ones_and_zeros(s: list, max_zeros: int, max_ones: int) -> int:
    for length in range(len(s), 0, -1):
        for subset in combinations(s, length):
            bits = ''.join(subset)
            if bits.count('0') <= max_zeros and bits.count('1') <= max_ones:
                return length

    return 0

Examples

$ ./ch-1.py 10 0001 111001 1 0 5 3
4

$ ./ch-1.py 10 0001 10 1 0 1 1
2

Task 2: Step by Step

Task

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.

My solution

Being really pedantic, the "minimum positive start value" for an list of positive integers is 0.000...01. However, the second example seems to imply that this number is actual an integer.

For this task, I start with two variables, min_value which is set as the first value of the ints list, and value which is zero. I then iterate over the ints list, and add that number to the value variable. If value is less than min_value, I update the min_value variable.

If min_value is greater than or equal to zero, I return 1. If not, I return 1 - min_value.

def step_by_step(ints: list) -> int:
    min_value = ints[0]
    value = 0

    for i in ints:
        value += i
        if min_value > value:
            min_value = value

    if min_value >= 0:
        return 1

    return 1 - min_value

Examples

$ ./ch-1.py 10 0001 111001 1 0 5 3
4

$ ./ch-1.py 10 0001 10 1 0 1 1
2

$ ./ch-2.py -3 2 -3 4 2
5

$ ./ch-2.py 1 2
1

$ ./ch-2.py 1 -2 -3
5