PWC 178

PWC 178

I didn't have time to do the full challenge in both Perls + Julia this week, so I have just submitted Challenge 1 in Raku, and Challenge 2 in Perl 5. The choice of language for each challenge is because of the availability of modules that make the respective task easy. I also did a partial solution to Challenge 1 in Julia.

Challenge 1 (Quater-imaginary base)

This is an offbeat number base proposed by Donald Knuth: base 2i. Read all about it in Wkipedia. We are asked to convert a given base-10 number to base-2i.

It is trivial to do this in Raku because of the Base::Any module which converts a number from (almost) any number base to (almost) any number base. (The almost is because it does not handle complex bases with both a real and imaginary part. The wholly imaginary 2i is no problem).

This allows easy conversion of any real or complex base-10 number, as I illustrate with a couple of examples from the wikipedia page (accessed 2022-8-17).

Here is my Raku solution.

Julia has a built-in digits(n,base=x) function that constructs an array of base-x digits given a base-10 (or other specified base) integer n. Here x must be a real integer but it can be negative.

We can use this to find the base-(-4) representation for a real base-10 integer. Then we can construct the base-2i representation from this as follows.

If you number the digit positions in a base-2i integer starting from 0 at the units position, and incrementing leftwards, then the digits at odd-numbered positions 1,3,5,.. etc. are all 0, and the digits at even-numbered positions 0,2,4,... etc. correspond to the digits at positions 0,1,2,... in the base-(-4) representation of the same number, again starting from the units position (position 0) and moving leftwards. For example, if the base-(-4) representation is xyz, the base-2i representation is x0y0z.

Using this we can construct the base-2i integer from the base-(-4) integer by just joining the base-(-4) digits array using '0' as the delimiter. The digits array in Julia is in reverse order (units first), so we reverse it before joining.

Here is my Julia solution. 

The logic of this follows directly from the definition of a base. A number y in an arbitrary base b can be written as (using an integer as example):

... n[4] x b^4 + n[3] x b^3 + n[2] x b^2 + n[1] x b^1 + n[0] x b^0

Here n[k] refers to the k'th digit counting from the units leftward starting from 0. This blog platform does not have an easy way to input math, so I am just using Excel formula-like notation (not Perl!). Thus "^" is "raised to the power", not a bitwise xor.

Then setting b=2i and observing that (2i)^2 = -4 we have:

... n[4] x (-4)^2 + n[3] x (2i)^3 + n[2] x (-4)^1 + n[1] x (2i)^1 + n[0] x (-4)^0.

I think you can grok the logic from that expression. The digit n[k] for odd-numbered k would evaluate to an imaginary number, which should be 0 if y is real. The digit n[k] for even-numbered k matches the corresponding (k/2)-th digit in the base (-4) representation of y. This base (-4) representation of y could be written as:

... n[3] x (-4)^3 + n[2] x (-4)^2 + n[1] x (-4)^1 + n[0] x (-4)^0.

It is not difficult to extend this logic to handle arbitrary complex input.  For a complex base-10 number y=x+iz, use the digits from the base-(-4) representation of x in the even-numbered positions (real) and the digits from the base-(-4) representation of z/2 in the odd-numbered positions (imaginary) of the base-2i representation of y (Source: wikipedia). 

But I'll settle for the solution for real integers only. 

The more interesting challenge is Perl 5, which does not provide libraries that make this task easy (as far as I know). Unfortunately, I am busy this week and have to stay away from this rabbithole. Will watch with interest to see what others do. 

Probably, the Perl 5 line of attack is to find the base-(-4) representation first, and then convert that into base-2i. To find the base-(-4) representation, we can build up a somewhat similar logic to that sketched above based on a correspondence with the base-4  representation, since the base-(-4) number can be written as:

... n[4] x (4)^4 + n[3] x (-4)^3 + n[2] x (4)^2 + n[1] x (-4)^1 + n[0] x (4)^0.

= ...n[5]x(4)^4 + n[2] x (4)^2 + n[0] x (4)^0 + (-1) x (... n[3] x (4)^3 + n[1] x (4)^1 ).

For example, 4 can be expressed as 16 - 12, or 100 + (-1) x 30 in Base-4, from which we can derive 130 as the base-(-4) representation.

Converting this logic to an algorithm is more tricky, but there are fast ready-made algorithms on wikipedia  that derive from this logic.

There is also a correspondence with hex digits, since the base-(-4) number can be written as:

... n[4] x (16)^2 + n[3] x (-4)^3 + n[2] x (16)^1 + n[1] x (-4)^1 + n[0] x (16)^0.

And of course, 4 is 2^2, so there is a direct correspondence with binary too.

Perl 5 has the Math::Base bundle, which can handle Base-4 numbers, but not negative or complex bases.

Challenge 2 (Business Date)

The next challenge is: given a timestamp and a duration in hours, find the date and time which is duration number of business hours following the timestamp.

This is easy to do in Perl 5 via the sprawling Date::Manip collection of modules. One can just specify the date in any standard format and the duration in such natural form as "in 3.5 business hours" (Several other natural languages work too: French, Spanish, etc.).

This is the approach I followed.

One minor thing I have neglected to do is to change the business hours in Date::Manip from the default of 8am to 5pm to the specification in the task which is 9am to 6pm. This is a chore involving a pair of config variables. I didn't bother. My script gives the correct answer for the test examples, but is not quite compliant with the task specification because of this.

Here is my Perl 5 solution.

I tried to use something simpler, like $date->parse("$timestamp in $hrs business hours") , but I could not get this to work. 

For this task, we use two types of Date::Manip objects, a Date object which refers to a timestamp or a fixed point in time on the calendar, and a Delta object which refers to a stretch of time, without any fixed date at the beginning or end. In our calculation, we first create a new date $date say and assign a calendar date to it using $date -> parse($timestamp). We can then attach a new delta object to the date using the $date -> new_delta method, and assign the duration to it using $delta -> parse("in $hrs business hours").  Finally we call the calc method on the date to add the delta and return the resulting date. This can be converted to a printable date string via the printf method.

One can of course call Date::Manip from Raku too using Inline::Perl5. I haven't tried.

For Julia, there is a BusinessDays package that can be used to calculate the next business day using a specified holiday calendar. This could be combined with the usual Dates support to solve this problem. I haven't tried. (It is also possible to call Perl 5 from Julia, so it might be possible to leverage Date::Manip).

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