Perl Weekly Challenge: The Times They Are A-Countin’

Posted on by

Perl Weekly Challenge 366‘s tasks are “Count Prefixes” and “Valid Times”. When I looked at the second task, and I saw how the times were changin’, I needed to listen to some Robert Allen Zimmerman.

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.

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

Approach

Thing to note: example 4 shows that the empty string can be a prefix.

In most languages, there’s a function that takes a needle string and returns the starting position of that string in a haystack string. In Raku/Perl, it’s called index.

Raku

In Raku, the Str index method returns a Nil if the substring isn’t found, but because Nil == 0 yields the warning “Use of Nil in numeric context”, we want to defined-or that with a non-zero numeric value, and because it’s fun I picked Inf.

sub countPrefixes($str, @array is copy) {
  @array.grep({ ($str.index($_) // Inf) == 0 }).elems
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
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

Perl

In Perl, however, the index function returns -1 when the substring isn’t found, so we don’t need to worry about non-numeric comparisons.

sub countPrefixes($str, @array) {
  scalar(grep { index($str, $_) == 0 } @array)
}

View the entire Perl script for this task on GitHub.

Python

In Python, the index method on strings raises a ValueError when the substring isn’t found, so we want to use the find method instead, which returns -1 when the substring isn’t found just like Perl’s index.

def count_prefixes(string, array):
  return len([ s for s in array if string.find(s) == 0 ])

View the entire Python script for this task on GitHub.

Elixir

Elixir, however, totally wins this round because of the String.starts_with?/2 function. The only reason this isn’t a one-liner is because Elixir pipes look better lined up vertically.

  def count_prefixes(string, array) do
    array
    |> Enum.filter(fn s -> String.starts_with?(string, s) end)
    |> length
  end

View the entire Elixir script for this task on GitHub.

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.

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

Approach

I was wondering what the best approach to this would be. I think what I’m going to do is split the time field on the colon, and pass it to a function with a maximum value: the hours portion gets passed with a max of 23, and the minutes portion gets passed with a max of 59. The function will then figure out the number of possibilities and return it, and I’ll multiply the two values together for the total number of valid times.

So next I need to figure out what the function does. It accepts two parameters: the string of hours or minutes, and the maximum value. First, it should cover the two edge cases: if there are no ? in the string, there’s only 1 possible valid value (if the string itself is less than the maximum, otherwise there are 0 valid values). If there’s two ?s in the string, the possible valid values is the maximum value plus one (because we need to count 00). That leaves us with a single ?, and we can substitute digits from 0 to 9 until it exceeds the maximum value, and keep count while we do so.

Raku

This approach was easy in Raku. I used the Str method .contains to determine if the sting contained a single ?, and I used the Str method .subst to replace that ? with numeric digits. I took advantage of Raku’s lazy typing to operate on the strings and then compare them numerically (I won’t be able to do that in Python ad Elixir—I’ll have to cast them as integers before comparing them).

sub possible($field, $max) {
  return $max+1 if $field eq "??";
  return $field <= $max ?? 1 !! 0 unless $field.contains("?");
  my $count = 0;
  for 0..9 -> $i {
    return $count if $field.subst("?", $i) > $max;
    $count++;
  }
  return $count;
}

sub validTimes($time) {
  my ($hours, $minutes) = $time.split(":");
  return possible($hours, 23) * possible($minutes, 59);
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: $time = "?2:34"
Output: 3

Example 2:
Input: $time = "?4:?0"
Output: 12

Example 3:
Input: $time = "??:??"
Output: 1440

Example 4:
Input: $time = "?3:45"
Output: 3

Example 5:
Input: $time = "2?:15"
Output: 4

Example Trivial 1:
Input: $time = "23:59"
Output: 1

Example Trivial 2:
Input: $time = "25:1?"
Output: 0

Perl

In Perl, though, we get to use the index function again, to serve the function Raku’s .contains had. Then I’m using the substr function to replace the ? character. I’m keeping track of the position of the ? so substr can just repeatedly change out the character at that position, rather than searching for the character each time through the loop.

sub possible($field, $max) {
  return $max+1 if $field eq "??";
  my $pos = index($field, "?");
  return $field <= $max ? 1 : 0 unless $pos >= 0;
  my $count = 0;
  foreach my $i (0..9) {
    substr($field, $pos, 1, $i);
    return $count if $field > $max;
    $count++;
  }
  return $count;
}

sub validTimes($time) {
  my ($hours, $minutes) = split /:/, $time;
  return possible($hours, 23) * possible($minutes, 59);
}

View the entire Perl script for this task on GitHub.

Python

In Python, there’s a str.split method like Raku’s, and we’re using the find method again. We’re using str.replace to change out the ? for the digits, and note that we need to use int when we’re comparing strings to integers, and str when we’re putting integers into strings.

def possible(field, maxval):
  if field == "??": return maxval+1
  if field.find("?") == -1:
    return 1 if int(field) <= maxval else 0
  count = 0
  for i in range(0, 10):
    if int(field.replace("?", str(i))) > maxval: return count
    count += 1
  return count

def valid_times(time):
  hours, minutes = time.split(":")
  return possible(hours, 23) * possible(minutes, 59)

View the entire Python script for this task on GitHub.

Elixir

Like Raku, in Elixir we’re using String.contains?/2 to check whether the string field has a ? in it or not, and using a String.replace/4 to change out the ? for the numeric digit.

def possible(field, max) when field == "??", do: max + 1
def possible(field, max) do
  if not String.contains?(field, "?") do
    if String.to_integer(field) <= max, do: 1, else: 0
  else
    0..9 |> Enum.count(fn i ->
      String.replace(field, "?", Integer.to_string(i))
      |> String.to_integer <= max
    end)
  end
end

def valid_times(time) do
  [hours, minutes] = String.split(time, ":")
  possible(hours, 23) * possible(minutes, 59)
end

View the entire Elixir script for this task on GitHub.

Here’s all my solutions in GitHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-366/packy-anderson

Leave a Reply