RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved string searching and sequence analysis. (Note that this ends today.)

Task 1: 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 0s and $y 1s in the subset.

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

That the strings are binary is unimportant; all that matters is how many of each character they contain. So the first stage is to build up a list of that; the second is to search all possible combinations to see which contains most elements and complies with the limits. In Rust:

fn onesandzeroes(a: Vec<&str>, zeroes: usize, ones: usize) -> usize {

Build the list of (zeroes, ones) corresponding to the input list.

    let mut ax = Vec::new();
    for ns in a {
        let mut o = 0;
        let mut n = 0;
        for c in ns.chars() {
            match c {
                '0' => { o += 1; },
                '1' => { n += 1; },
                _ => panic!("Bad digit"),
            };
        }
        ax.push((o, n));
    }
    let mut mx = 0;

Search each possible combination. (Some languages have a combinations generator that can restrict the number of items searched, but I didn't bother for this - it's just a bitmask to select all possible combinations of one or more values from the list.)

    for mask in 1 .. (1 << ax.len()) {
        let mut o = 0;
        let mut n = 0;
        let mut ct = 0;
        for (i, x) in ax.iter().enumerate() {

If this entry matches the mask, count its ones and zeroes and bail out if there are too many overall.

             if mask & (1 << i) > 0 {
                o += x.0;
                n += x.1;
                ct += 1;
                if o > zeroes || n > ones {
                    break;
                }
            }

If this is a valid combination, re-set the maximum value.

            if o <= zeroes && n <= ones {
                mx = std::cmp::max(mx, ct);
            }
        }
    }
    mx
}

Task 2: Step by Step

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.

The answer is clearly 1 minus the lowest value the progressive sum achieves (and at least 1). Raku:

sub stepbystep(@a) {

Set initial minimum value and progressive sum.

    my $mv = 0;
    my $tot = 0;

Iterate over the sequence, calculating the progressive sum and latching the lowest value seen.

    for @a -> $s {
        $tot += $s;
        if ($mv > $tot) {
            $mv = $tot;
        }
    }

Then turn that into the answer.

    1 - $mv;
}

Full code on github.