PWC 194

PWC 194

Aside on Advent of Code

I also discovered Advent of Code and got started on it. Not sure if I will continue, because the daily cycle may be too much for me. I thought initially of doing it using Raku, but looking at the challenges, immediately decided to go with Perl 5. The tasks so far all involve reading an input file with some data in an arbitrary text-based format, then doing some computations with that data, and finally spitting out some output which one submits to Advent of Code for validation. This is exactly what Perl was designed to do. Raku of course is a development from the same source, but it's a bit less focused on the "practical extraction and reporting" stuff.

Here is the repo with my solutions.

And now, back to our regular scheduled weekly challenge.

Challenge 1 (Digital Clock)

We are given an input string which is a 24-hour clock time, in the format 'hh:mm'. For example, 23:59. From the examples, 24:00 is not allowed.

One number is missing, and replaced with a question mark. I assume that there must always be one number left missing, and that there is no more than one number missing. That is, there is exactly one question mark in the string.

We are asked to find the highest number that can replace the question mark.

For example, in '?3:59', this is 2. In '?9:59', this is 1.

This is essentially an input validation program, and so one cannot evade input validation chores beyond the specific task. For example, it makes no sense to find the "highest" missing digit for an invalid string like '?3:61'.

I did it first in Perl 5, and then ported my Perl 5 code directly to Raku and Julia. 

I initially use a regex to verify that the string is in the correct hh:mm format (with '?'). Here is the Perl 5 version of the regex (Julia is identical).

/^[0-2?][0-9?]:[0-5?][0-9?]$/

I next check for whether the first two digits are a number greater than 23, or the last two digits are a number greater than 59. In both cases, the subroutine returns an "Invalid Input" notification (-1 in Julia to conform to the stated integer return value type).

I then loop through the string elements after splitting it (except in Julia which lets you  loop directly through the string), and get the location of the '?' in the input string, as well as the number of times '?' occurs (if more than once, that's "Invalid Input"). I use hashes for this in Perl 5 and Raku. I could have used the 'index' function to directly give the index position of (the first) '?' in the input string. In Julia I use 'findfirst' which is the Julia equivalent of  Perl 'index'.

Finally, I have conditional statements to find the maximum replacement for '?'. I use old-fashioned C-style if..else blocks. Not very idiomatic in Perl, but they are efficient and readable, and easier to port to Julia.

If '?' is at position 0 (1 in Julia), then the answer is 1 if position 1 (2 in  Julia) has 4 or higher, and 2 if position 1 has 0 to 3.

If '?' is at position 1 (2 in Julia), then the answer is 9 if position 0 (1 in Julia) has 0 or 1, and 3 if position 0 has 2.

If '?' is at position 3 (4 in Julia), then the answer is 5 in every case, and if '?' is at position 4 (5 in Julia), then the answer is 9 in every case.

Challenge 2 (Frequency Equalizer)

We are given a string made up of alphabetic characters (the logic extends to any character, so I have not tested for alphabetic input). We are asked to test whether it is possible to transform the string to one where every element occurs the same number of times by just removing a single element. For example, in 'aabbccc', removing any 'c' will lead to 'aabbcc' in which each of the elements has the same frequency of 2.

This is trickier than it seems, because there are some edge cases that the test examples do not cover. A simple solution that satisfies the test examples would be to count the frequencies of each element in the string, and then verify that (1) there are exactly two frequencies; and (2) one of the frequencies is exactly one more than the other.

This is what I started off with, using hashes to do the counting in all three languages. This logic satisfies all the test examples. But this misses some edge cases where one element occurs only once (h/t Peter Campbell Smith). For example, consider 'abbbccc'. This would fail my test above, but obviously removing 'a' would leave the remaining elements with the same frequency. Also consider a string where every element occurs just once, say 'aeiou'. Again this will fail my test above, but removing any element will leave the string in a state where every element has the same frequency.

I therefore modify my logical test, getting  the more complicated (Perl 5 version):

( (scalar(@s) <= 2) && ( ($s[0]==1) ||
        ( exists($s[1]) && (abs($s[1] - $s[0])==1) ) ) ) &&
        (return 1);

Here @s is a sorted list of the frequencies of elements in the input string. The test checks if the number of frequencies is less than or equal to 2, and then if either the lowest frequency equals 1, or the difference between the 2 frequencies (if there are 2) is 1.

I'm afraid that even this does not cover every edge case, though I am not going to improve it. The very thorough Athanasius points out the following two cases, which my logic will not handle:

  1. The case where there is only one element in the input string, say 'aaaaaaa'. Then removing any one 'a' will leave the string in a state where the frequency of the remaining element is the same (as itself).
  2. As a special case of the above, a string consisting of just a single character say 'a'. Then removing the character leaves an empty string q(), which trivially can be said to have the same frequency of every element (no elements with a frequency of zero).
Here is my Perl 5 solution

Update: (13 Dec) And! Unfortunately, that is not the end of the story. As Bruce Gray points out there is another glaring situation where my logic won't work. And it is not an edge case! Consider the string 'aaabbbcc'. This will pass my logic, but that is an error. There is no way to remove a single character from this string leaving the remaining characters having the same frequency. Since we are past the deadline, I won't fix this. But I should state the disclaimer that the script just satisfies the test examples, that's it.

Comments

Post a Comment

Popular posts from this blog

PWC 258

PWC 258 Last week (#257) I finished challenge 2 and my blog post for challenge 257 late last week, so had only submitted challenge 1. Here is my blog post for PWC 257 , including the full code for my challenge 2 solution. This week, I have done both challenges in perl 4.019 on DOSBOX. Both scripts also work fine on the latest Perl 5.38. I also did the challenges in Raku, where they are one-liners.  Challenge 1 (Count Even Digits Number) We are given a list of integers, and asked to count the number of elements whose base-10 representation has an even number of digits. In Raku , this is a one-liner. Here it is: raku -e 'say +@*ARGS.grep({$_.chars %% 2})' $@ It could be a one-liner in Perl 4 too, but since I run it on DOSBOX, my script would not be a bash shell script. Here is the short subroutine that does the job.  sub count_even_digits {  scalar( grep( ((length($_) % 2) == 0), @_) ); } The full code is here . Challenge 2 (Sum of values) We are given an integer k  an...
Read more

PWC 253

PWC 253 I do both challenges this week using old software on DOSBOX: perl 4.019, and for comparison, also python 1.4 beta. My solutions also work on the current versions of Perl 5 (5.38) and Python 2 (2.7.18) respectively. Challenge 1 (Split Strings) Links to code: perl4.019 python1.4b We are given a list of strings, and a single character say sep . We are asked to return the list, with the strings split into component substrings using sep as a separator. We should not include any empty strings in the output. In perl 4, I first stick a backslash in front of the separator character, so that it is escaped if entered in a regex. This is because the perl split function takes a regex as its first argument indicating the separator. If we have a character like '$' or ',', we want to escape it so that it is read literally when parsing the regex. Here is the key subroutine:   sub split_strings {  local ($separator, @words)=@_;  local (@retval)=(); #array to be returned  # ...
Read more

PWC 249

PWC 249 Challenge 1 (Equal pairs) We are given a list of integers with an even number of elements. We are asked to check if the list can be completely divided into sub-lists of size 2 with each sub-list containing the same integer repeated, like say (2,2). If so, we are asked to return the list of such sub-lists. This is straightforward in Perl 5. I use modern conveniences this time, though it could be done using only primitive Perl 4 syntax. Here is my subroutine. It returns a list of array references. local *equal_pairs = sub {     #-- return () if input is of odd length     ((scalar(@_) % 2) > 0) && (return ());          #-- count number of occurrences of each element using a hash     local %_ = ();     map {$_{$_}++} @_;          #-- if any element occurs an odd number of times, return ()     (grep {($_{$_} % 2) > 0} keys %_) &&...
Read more