| 27 March 2026 | Challenge 366 |
Pre-Timed Counters
Task 1: Count Prefixes
Submitted by: Mohammad Sajid Anwar
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.
Example 1
Input: @array = ("a", "ap", "app", "apple", "banana"), $str = "apple"
Output: 4
Example 2
Input: @array = ("cat", "dog", "fish"), $str = "bird"
Output: 0
Example 3
Input: @array = ("hello", "he", "hell", "heaven", "he"), $str = "hello"
Output: 4
Example 4
Input: @array = ("", "code", "coding", "cod"), $str = "coding"
Output: 3
Example 5
Input: @array = ("p", "pr", "pro", "prog", "progr", "progra", "program"), $str = "program"
Output: 7
Solution
Perl
The function index($haystack, $needle) returns zero if and only if $needle is a substring in
$haystack and starts at position zero - in other words: if it is a prefix.
grep may be used to filter the list. It provides the requested prefix count in scalar context and the prefixes themselves in list context .
use strict;
use warnings;
use experimental 'signatures';
sub count_prefixes ($str, @arr) {
grep !index($str, $_), @arr;
}
See the full solution to task 1.
J
The logic in J is a bit different.
x E. y provides a binary array signaling that x is a substring of y starting at the positions of ones in the result.
Taking x as the list of words and y as the string, all prefixes can be identified by a one in the first position.
The sum over these elements is the requested count.
count_prefixes =: +/@:({.@:E.~&>)
echo (<'apple') count_prefixes 'a';'ap';'app';'apple';'banana'
See the full solution.
Task 2: Valid Times
Submitted by: Mohammad Sajid Anwar
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.
Example 1
Input: $time = "?2:34"
Output: 3
0 -> "02:34" valid
1 -> "12:34" valid
2 -> "22:34" valid
Example 2
Input: $time = "?4:?0"
Output: 12
Hours: tens digit ?, ones digit 4 -> can be 04, and 14 (2 possibilities)
Minutes: tens digit ?, ones digit 0 -> tens can be 0-5 (6 possibilities)
Total: 2 × 6 = 12
Example 3
Input: $time = "??:??"
Output: 1440
Hours: from 00 to 23 -> 24 possibilities
Minutes: from 00 to 59 -> 60 possibilities
Total: 24 × 60 = 1440
Example 4
Input: $time = "?3:45"
Output: 3
If tens digit is 0 or 1 -> any ones digit works, so 03 and 13 are valid
If tens digit is 2 -> ones digit must be 0-3, but here ones digit is 3, so 23 is valid
Therefore: 0,1,2 are all valid -> 3 possibilities
Example 5
Input: $time = "2?:15"
Output: 4
Tens digit is 2, so hours can be 20-23
Ones digit can be 0,1,2,3 (4 possibilities)
Therefore: 4 valid times
Solution
One obvious way to solve this task is to enumerate all valid ‘hh:mm’ strings, match these against a pattern corresponding to the given time string and count the matches. Though this is probably easy to implement I’m not going to follow this approach.
Independent from the content at any other position in the time string, the first minute place provides a factor of one or six and the second place a factor of one or ten.
The hour places must be considered in common.
To unify and simplify the terms that are used in the following, question marks are represented as -1.
The table below provides the factor that is derived from the hour positions \(h_1\,h_2\).
It shall be read as an if-elseif-...-else chain, i.e. the first matching row provides the actual factor.
The column edge HH shows the input edge case for the corresponding condition.
\(\hat{h}_{max}\) will be described in the section describing the J solution.
| condition | edge HH |
\(\hat{h}_{max}\) | factor |
|---|---|---|---|
| \(h_1 \lt 0 \wedge h_2 \lt 0\) | ?? |
-41 | 24 |
| \(h_1 \lt 2 \wedge h_2 \lt 0\) | 1? |
-21 | 10 |
| \(h_2 \lt 0\) | 2? |
-11 | 4 |
| \(h_1 \lt 0 \wedge h_2 \lt 4\) | ?3 |
-7 | 3 |
| \(h_1 \lt 0\) | ?9 |
-1 | 2 |
| \(10 h_1 + h_2 \lt 24\) | 23 |
23 | 1 |
29 |
\(\infty\) | 0 |
The product of the factors for the hour places and both minute places provides the requested number of valid times.
Perl
The if-elseif-...-else-chain can easily be implemented as a chain of conditional operators ?:.
The input string is parsed and split into its components with the help of a regular expression.
The factors are calculated by anonymous subroutines that are applied in sequence to the split input string and the results are multiplied.
use strict;
use warnings;
use List::Util 'reduce';
BEGIN {
my @count_pos = (
sub (@time) {$time[0] < 0 && $time[1] < 0 ? 24 :
$time[0] < 2 && $time[1] < 0 ? 10 :
$time[1] < 0 ? 4 :
$time[0] < 0 && $time[1] < 4 ? 3 :
$time[0] < 0 ? 2 :
10 * $time[0] + $time[1] < 24 ? 1 : 0},
sub (@time) {$time[2] < 0 ? 6 : 1},
sub (@time) {$time[3] < 0 ? 10 : 1},
);
sub valid_times ($time) {
my @time = map $_ eq '?' ? -1 : $_,
$time =~ /^([0-2?])([0-9?]):([0-5?])([0-9?])$/ or return 0;
reduce {$a * $b->(@time)} 1, @count_pos;
}
}
See the full solution to task 2.
J
The usage of if-elseif-else is less common in J.
Following a more functional path.
The pairs \(h_1 \, h_2\) can be combined into a single integer value \(\hat{h}\) that equals the hour \(h_1 h_2\) as a decimal number for regular hours and is negative if any of \(h_1\) or \(h_2\) is negative (i.e. there is a placeholder in the hour places). For the computed \(\hat{h}\) the cases from above fall into disjoint intervals. See the table for each case’s maximum \(\hat{h}\) value.
Setting
\[h_2^{\prime} = \begin{cases} h_2& \text{ if } h_2 \ge 0\\ -31& \text{ otherwise} \end{cases}\]we may define
\[\hat{h} = 10 h_1 + h_2^{\prime}\]For any \(\hat{h}\) we find the smallest \(\hat{h}_{max} \ge \hat{h}\) from the table and take the corresponding factor.
x I. y finds the index of the respective interval defined by x, which y falls into.
This is used as an index into the list of factors.
Again, the product over all three factors gives the requested count.
require 'regex'
count_valid =: {{
splittime =. ((2 4 0 0)"_ ^:(-.@*@#)@('^([0-2?])([0-9?]):([0-5?])([0-9?])$'&([: _1&".@>@}.@, rxmatches rxfrom ])))
join_h =. (10&*@[ + _31"_^:(0&>@]))/@:(2&{.) , 2&}.
cnt_h =. {&(24 10 4 3 2 1 0)@((_41 _21 _11 _7 _1 23)&I.)
cnt_m1 =. {&(6 1)@(0&<:)
cnt_m2 =. {&(10 1)@(0&<:)
*/@:(cnt_h`cnt_m1`cnt_m2 "0)@join_h@splittime y
}}
echo count_valid '?2:34'
See the full solution .