RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved prefix testing and time validation. (Note that this ends today.)

Task 1: Count Prefixes

You are given an array of words and a string (contains only lowercase English letters).

Write a script to return the number of words in the given array that are a prefix of the given string.

This is a one-liner in all the languages I'm using that have functional characteristics (and I've bodged those into the ones that don't). For example in Ruby:

def countprefixes(a, b)
  a.select {|x| b.start_with?(x)}.size
end

Filter the words that are prefixes to the target string, and count them.

Even in Lua, though I had to write a filter function to make it work.

function countprefixes(a, b)
   return #filter(a, function(x) return string.find(b, x, 1, true) end)
end

OK, rather more lines in PostScript (and again my own filter).

/countprefixes {
    0 dict begin
    /b exch def
    {
        b exch anchorsearch {
            pop pop true
        } {
            pop false
        } ifelse
    } filter length
    end
} bind def

Task 2: Valid Times

You are given a time in the form 'HH:MM'. The earliest possible time is '00:00' and the latest possible time is '23:59'. In the string time, the digits represented by the '?' symbol are unknown, and must be replaced with a digit from 0 to 9.

Write a script to return the count different ways we can make it a valid time.

The Raku was a particlarly fiddly one. Not only does it have that perverse non-standard "regular expression" syntax, you can't have a list of lists without special accessor methods. (Even though Perl, and other older and newer languages, are perfectly able to do this.)

But the core of this is combinator, a list of four lists of possible digits. If that's a single digit, that's the only one in the list; otherwise it's the full list of valid digits for that position. So for example "?2:34" gets parsed out to

[
  [ 0, 1, 2 ],
  [ 2 ].
  [ 3 ],
  [ 4 ],
]

That's the first part of this job:

sub validtimes($a) {
    my @combinator;

Go through the input string, numbering the characters.

    for $a.comb.kv -> $i, $c {

If it's a valid number,

        if ($c ~~ /<[0..9]>/) {

push that in as an array of one entry.

            @combinator.push([0 + $c, ]);
        } else {

Otherwise ("?" or ":") act based on the position. First character (tens of hours) can be 0, 1 or 2:

            if ($i == 0) {
                @combinator.push([0 .. 2]);

Second or fifth (single hours and single minutes) can be 0 to 9.

            } elsif ($i == 1 || $i == 4) {
                @combinator.push([0 .. 9]);

Fourth (tens of minutes) can be 0 to 5.

            } elsif ($i == 3) {
                @combinator.push([0 .. 5]);
            }

And third (the colon) we just ignore.

        }
    }

If we didn't get a full set of elements, bail out.

    if (@combinator.elems != 4) {
        return 0;
    }

I'd originally planned to work through all the combinations, but by the time I got to this bit it had occurred to me that while the hour numbers need to be checked in pairs for validity (9 is a valid number for single hours if tens of hours is 0 or 1, but not if it's 2) the minute numbers don't (0-9 is always the range of valid single minutes digits whatever the tends of minutes). So for the number of valid minute combinations I just need to multiply the number of entries in those fields.

    my $minutes = @combinator[2].elems * @combinator[3].elems;

Then for hours I work through each possibility.

    my $ct = 0;

Tens of hours.

    for @combinator[0].list -> $ax {

Ones of hours.

        for @combinator[1].list -> $bx {

Count up valid combinations.

            if ($ax * 10 + $bx <= 23) {
                $ct++;
            }
        }
    }

Then we return the number of possible hours multiplied by the number of possible minutes.

    $ct * $minutes;
}

Full code on codeberg.