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

Popular posts from this blog

PWC 215

PWC 227

PWC 234