07 December 2022

Completing the time and levelling the letters

Completing the time

We are given a time, such as 12:34, with one of the digits replaced by '?'. We are asked what digit when substituted for the '?' results in the maximum valid time.

There are six cases to consider:

  1. The first digit is ? and the second is [0123] - the answer is 2
  2. The first digit is ? and the second is [456789] - the answer is 1
  3. The second digit is ? and the first is 1 - the answer is 9
  4. The second digit is ? and the first is 2 - the answer is 3
  5. The third digit is ? - the answer is 5
  6. The fourth digit is ? - the answer is 9

This is a rather messy set of conditions. The easiest - and perhaps clearest - way of performing the task is just a set of if/elsif clauses using the above logic, and that's what I submitted. I used split to put the characters into in array to make my conditions easy to read - for example $chars[0] eq '?' - but it could equally be done using regular expressions - for example $string =~ m|^...\?| is true if the 4th character, ie third digit, is '?'.

Levelling the letters

We are given a string of characters (lower case letters in the examples) and asked whether the deletion of a single character would mean that the frequencies of occurrence of all the other characters are the same.

The condition will be met if all but one of the characters appear exactly n times, and the other one appears n + 1 times. Removing a single instance of the latter means that all characters appear n times.

The logic I used has three steps:

  1. Create $freq{'x'} as the frequency of 'x' occurring in the string
  2. Find the maximum frequency $max_freq, and the letter $max_char that occurs that frequently
  3. Check if each of the letters is either $max_char or has a frequency of $max_freq - 1.
  4. If they do, then the string meets the requirement; if they don't then it doesn't.

In step 2, there may be several characters having the maximum frequency in which case the string could immediately be disqualified, but there is little to be gained by that as such a string will quickly be ruled out in step 3.

There are however cases where the above will not work.  Consider a string like abbbccc. If we remove a then the frequency of the remaining characters will be the same. None of the examples given illustrates this, but neither does the wording of the task rule it out. Moreover, there are strings like abcde, where the removal of any of the characters will leave the string matching the criterion.

If the cases in the previous paragraph are to be included, step 3 above needs to check for those, and in my submission I have done that. Specifically, if one character appears only once and all the others appear the same number of times (eg abbbccc) , then deletion of the once-appearing character satisfies the criterion, or if all the characters appear only once (eg abcde) then deletion of any one of them meets the criterion.

No comments:

Post a Comment