The weekly challenge 366 - Task 2: Valid Times

  1 #!/usr/bin/env perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-366/#TASK2
  3 #
  4 # Task 2: Valid Times
  5 # ===================
  6 #
  7 # You are given a time in the form ‘HH:MM’. The earliest possible time is
  8 # ‘00:00’ and the latest possible time is ‘23:59’. In the string time, the
  9 # digits represented by the ‘?’ symbol are unknown, and must be replaced with a
 10 # digit from 0 to 9.
 11 #
 12 # Write a script to return the count different ways we can make it a valid
 13 # time.
 14 #
 15 ## Example 1
 16 ##
 17 ## Input: $time = "?2:34"
 18 ## Output: 3
 19 ##
 20 ## 0 -> "02:34" valid
 21 ## 1 -> "12:34" valid
 22 ## 2 -> "22:34" valid
 23 #
 24 ## Example 2
 25 ##
 26 ## Input: $time = "?4:?0"
 27 ## Output: 12
 28 ##
 29 ## Hours: tens digit ?, ones digit 4 -> can be 04, and 14 (2 possibilities)
 30 ## Minutes: tens digit ?, ones digit 0 -> tens can be 0-5 (6 possibilities)
 31 ##
 32 ## Total: 2 × 6 = 12
 33 #
 34 ## Example 3
 35 ##
 36 ## Input: $time = "??:??"
 37 ## Output: 1440
 38 ##
 39 ## Hours: from 00 to 23 -> 24 possibilities
 40 ## Minutes: from 00 to 59 -> 60 possibilities
 41 ##
 42 ## Total: 24 × 60 = 1440
 43 #
 44 ## Example 4
 45 ##
 46 ## Input: $time = "?3:45"
 47 ## Output: 3
 48 ##
 49 ## If tens digit is 0 or 1 -> any ones digit works, so 03 and 13 are valid
 50 ## If tens digit is 2 -> ones digit must be 0-3, but here ones digit is 3, so 23 is valid
 51 ##
 52 ## Therefore: 0,1,2 are all valid -> 3 possibilities
 53 #
 54 ## Example 5
 55 ##
 56 ## Input: $time = "2?:15"
 57 ## Output: 4
 58 ##
 59 ## Tens digit is 2, so hours can be 20-23
 60 ## Ones digit can be 0,1,2,3 (4 possibilities)
 61 ##
 62 ## Therefore: 4 valid times
 63 #
 64 ############################################################
 65 ##
 66 ## discussion
 67 ##
 68 ############################################################
 69 #
 70 # If there are no "?" in $time, we check, if it is valid.
 71 # If there are "?" in $time, we count all possible times that we
 72 # get if we replace "?" for each possible digit 0..9 (recursively,
 73 # so we catch all "?" in $time).
 74 # There is no short circuit in case we use invalid digits in some places.
 75 # The whole thing is not time critical enough to complicate the algorithm
 76 # by optimizing.
 77 
 78 use v5.36;
 79 
 80 valid_times("?2:34");
 81 valid_times("?4:?0");
 82 valid_times("??:??");
 83 valid_times("?3:45");
 84 valid_times("2?:15");
 85 
 86 sub valid_times($time) {
 87     say "Input: $time";
 88     my $count = 0;
 89     if($time =~ m/\?/) {
 90         foreach my $d (0..9) {
 91             $count += find_valid($time, $d);
 92         }
 93         say "Output: $count";
 94     } else {
 95         say is_valid($time) ? "Output: 1" : "Output: 0";
 96     }
 97 }
 98 
 99 sub find_valid($time, $d) {
100     $time =~ s/\?/$d/;
101     my $count = 0;
102     if($time =~ m/\?/) {
103         foreach my $d2 (0..9) {
104             $count += find_valid($time, $d2);
105         }
106         return $count;
107     } else {
108         return is_valid($time);
109     }
110 }
111 
112 sub is_valid($time) {
113     my ($h, $m) = split /:/, $time;
114     return 1 if ($h >= 0 && $h <= 23 && $m >= 0 && $m <= 59);
115     return 0;
116 }