RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved various sorts of array searching. (Note that this ends today.)

Task 1: Consecutive One

You are given a binary array containing only 0 or/and 1.

Write a script to find out the maximum consecutive 1 in the given array.

A state machine seemed the simplest approach. JavaScript:

function consecutiveone(a) {

Initialise the hash for storing spans. (Doesn't matter if this entry gets overwritten later; it's there only in case we find no spans at all. I could do this just with a list, but I still tend to think in terms of hashes as a fundamental data structure.)

    let h = new Map;
    h.set(0, 0);

Initialise the state machine.

    let latch = 0;
    let latched = false;

Iterate through the list.

    a.forEach((n, i) => {

If we find a 1, and we weren't in a run, start a span.

        if (n == 1 && !latched) {
            latched = true;
            latch = i;
        }

If we find a 0, and we weren't in a run, end a span, recording its start point and length.

        if (n == 0 && latched) {
            latched = false;
            h.set(latch, i - latch);
        }
    });

If we're still in a run at the end of the list, add the final span. (This could also be done by simply re-setting the current span every time we see a 1, which would be more elegant but I didn't feel like rewriting once I'd thought of it.)

    if (latched) {
        h.set(latch, a.length - latch);
    }

Return the greatest span length.

    return Math.max(...h.values());
}

Task 2: Final Price

You are given an array of item prices.

Write a script to find out the final price of each items in the given array.

There is a special discount scheme going on. If there's an item with a lower or equal price later in the list, you get a discount equal to that later price (the first one you find in order).

Which is a bit odd, but the problem is well-defined. Raku:

sub finalprice(@a) {

Initialise the output list.

    my @out;

Iterate over the input list.

    for @a.kv -> $i, $n {
        my $discount = 0;

At each position, search from one later to the end.

        for $i + 1 .. @a.end -> $mi {

Take the first lower or equal price we find, and set discount to that value.

            if (@a[$mi] <= $n) {
                $discount = @a[$mi];
                last;
            }
        }

Apply the discount and add the value to the output list.

        @out.push($n - $discount);
    }
    @out;
}

I enjoyed writing the PostScript version:

/finalprice {
    0 dict begin
    /a exch def

I'll build the output array one element at a time.

    [
        a enumerate.array {
            aload pop
            /n exch def
            /i exch def

Here's my default discount.

            0
            i 1 add 1 a length 1 sub {
                /mi exch def
                a mi get
                dup

If I've found a lower price, I swap it with the zero default discount, pop that, and exit.

                n le {
                    exch pop
                    exit
                } if
                pop
            } for
            n exch sub
        } forall
    ]
    end
} bind def

Full code on github.