PWC 187

PWC 187

Challenge 1 (Days Together)

Two friends Foo and Bar vacation in the same city, with the start-dates and end-dates for each one's vacation given in the form 'dd-mm'. The year is assumed to be the same non-leap year for all dates. The task is to work out the number of days when Foo and Bar are both in the city at the same time. 

This resolves to finding the number of days between the later start-date and the earlier end-date, including both days in the count (e.g., if they are both the same day, then the count is 1, not zero). This is easy to do with the numerous Date modules in Perl 5, or the built-in Date support in Raku and Julia. 

In Perl 5, I used the lightweight fast Date::Calc module exporting the Delta_Days subroutine. Delta_Days counts days between two (year, month, day) triplets, input as a flat list. Since it excludes the second (ending) date from the count, I add 1 to include it for the present task.

My Perl 5 script uses simple helper subroutines to parse the 'dd-mm' string, and to find the earlier or the later of two dates.

I use 2022 as the common year for the dates. Any non-leap year will do.

My Raku script is derived from the Perl 5 one. In Raku, the helper subroutines are not needed, except for 'parse-date'. Date::Calc is not needed either, and one just uses the regular arithmetic operators + and - for Date arithmetic.

My Julia script is a direct translation of the Raku one.


Challenge 2 (Magical Triplets)

We are given a list of positive numbers @n say that contains at least three numbers.

We are asked to find the three-number sub-list(s) of the list, say (a,b,c) that satisfy the following criteria:

  1. a + b  >  c
  2. b + c  > a
  3. a + c  > b
  4. (a + b + c) is maximum.

We are asked to return the sub-list(s) sorted in descending order.

I assume that "maximum" in 4. means "maximum among all possible triplets that are sub-lists of  @n". An alternative interpretation could be "maximum among all triplet sub-lists of @n that satisfy 1 through 3". The test examples given do not distinguish between these two interpretations.

Sticking to my assumptions, the task reduces to:

  1. Find the three largest elements of @n. Their sum is automatically the maximum of any triplet sub-list. Let this sub-list be @candidate. An easy way to find @candidate is to sort @n in descending order and take the first three elements.
  2. Test if any element of @candidate is greater than or equal to the sum of the other two. If yes (some element is greater), then return an empty array. If not, then @candidate is the answer.

This is a straightforward exercise in all three languages.

The logic actually simplifies further, as fellow contributor Athanasius explains in their somewhat similar Perl 5 solution (see the detailed explanation at the start). In step 2 above, we only need to test if b + c > a. Since the triple (a, b, c) is already sorted in descending order, a >= b >= c, it follows directly that a + b > c and a + c > b. No need to check these. 

Athanasius has the alternative interpretation of 'maximum'. They implement this by sliding down the sorted @n if the first triple fails to work. They stop when they get a triple that satisfies the first three test conditions, or they have reached the end of the array.

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  and a list in
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 %_) && (return ());          #-- loop thru %_ keys, returning pairs of such keys     map {         my $k=$_;         my $num_pairs=( ($_{$k}
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