Weekdays and Daytimes

This week's Perl Weekly Challenge dealt with calculations related to days of the week (part 1) and times (part 2). 

Part 1 was related enough to some previous challenges (in particular Challenge 019) where I was able to re-use code which implemented Sakamoto's algorithm. 

Part 2 seemed to put me in a situation where I made an exception to my rule of not using CPAN modules, at least not for the core part of the challenge. My solution did some screen scraping of a web page and then a time calculation. Neither of those things seemed worth the extraordinary effort of re-inventing!

Part 1

Here we are asked to Write a script to calculate the total number of weekdays (Mon-Fri) in each month of the year 2019. The code which implements Sakamoto's algorithm and returns the counts is below. For the sake of saving space I left out some code which is mostly just use constant declarations.

ch-1.pl
ch-1.pl

Sample Run 

$ perl perl5/ch-1.pl 

January: 23 days
February: 20 days
March: 21 days
April: 22 days
May: 23 days
June: 20 days
July: 23 days
August: 22 days
September: 21 days
October: 23 days
November: 21 days
December: 22 days

What I did

This re-uses code from Challenge 019 and Challenge 013 which asked for similar calculations which were done with Sakamoto's algorithm. I don't think I have anything new to say this time around but see those two earlier challenges for details.

Part 2

In Part 2 we are asked to Write a script to find out the DayLight gain/loss in the month of December 2019 as compared to November 2019 in the city of London. A website is given which contains some data for this calculation. My approach is to grab the data from the given sites with LWP and then perform the necessary calculation with DateTime::Duration

ch-2.pl
ch-2.pl

Sample Run

$ perl perl5/ch-2.pl 

loss of 19 hours 48 minutes 72 seconds

What I did

Using LWP I fetch the contents of the page which contains a table (shown below) with the values (Daylength) we are interested in. The table is parsed with HTML::TableExtract and the values are computed with DateTime::Duration.

Sun in London. From https://www.timeanddate.com/sun/uk/london?month=11&year=2019.
Sun in London. From https://www.timeanddate.com/sun/uk/london?month=11&year=2019.





VIN Validation

Part of Perl Weekly Challenge 036 was to implement validator for Vehicle Identification Numbers (VINs). The Wikipedia article on VINs is very comprehensive and has more than enough information to solve this challenge.

ch-1.pl
ch-1.pl

Notes

We assume North American VINs. The validation process is as follows:

  • Confirm that the VIN has the required format, using a regular expression (Line 48).
  • Compute the checksum (Lines 52-57).
  • Verify the check digit (Line 59).
  • There is a lot of static data for this, the character/value transliterations and weights. I decided to use Readonly data structures for this.

References

If you would like to generate known good VINs for testing I highly recommend https://randomvin.com.

Slicing a map in C++

In Perl Weekly Challenge 34 one of the questions asked to demonstrate the use of a hash slice. In Perl the preferred term for associative arrays or maps is hash. Short for hashmap Perl hashes are unordered maps. To slice a hash is to use a bit of convenient syntax to extract multiple values at a time from a hash when given multiple keys. I wrote up an example of doing this in Perl and it's very straightforward, just one line. 

Let's take a look at how to do the most similar thing in C++. That is, in the spirit of Perl and other dynamic scripting languages, how could we, in the most syntactically terse way, get multiple values from a std::map when given multiple keys?

Code

Sample Run

$ g++ -o cxx/ch-1 cxx/ch-1.cxx
$ cxx/ch-1
second
fourth

Details

I think this is about as close as we can get in C++. 

  • I've intentionally avoided any explicit loops.
  • I used a lambda to check for matching keys.
  • Vectors are used to store keys and return values for maximum flexibility in the number of keys to check at runtime (although here they are simply hardcoded).

The only slightly awkward thing might be that we end up with some empty strings in the return vector. Here I just ignore them when printing the output. In more general use you could just as easily do an erase-remove.

Line by Line

  1. Line 17 initializes the vector of keys we will be getting values for.
  2. Line 18 similarly initializes the map we will be checking.
  3. Line 19 is the vector the return values will be put into.
  4. Line 20 starts the real action! std::transform will apply a function (4th argument, our lambda) to each element of the given range (arguments 1 and 2) and then store the output in the range given in the 3rd argument.
  5. Line 27 prints the output by making a call to print_element for each element in the vector of values.

Perl Weekly Challenge 034

Time constraints prevented me from really rolling my sleeves up and exploring different aspects of this week's Perl Weekly Challenge. Somewhat conveniently both parts yielded short solutions, although both have intriguing aspects which will have to be left for another time!

Part 1

Sample Run

$ perl perl5/ch-1.pl
second
fourth

Notes

I think maybe the most significant issue with hash slices in Perl is that you need to switch the sigil on the hash top be @. If you do not and, for example, leave it as a %, then you will receive both the keys and the matching values.

Part 2

Sample Run

$ perl perl5/ch-2.pl
Hello!
Goodbye!

Notes

  • A dispatch table is really just an arrangement of references to functions. It isn't strictly required that they even be in a hash.
  • You don't have to have anonymous functions, I just did it this way for the sake of brevity. You could declare functions the normal way and then use references to them. 
  • Make sure that, in the case of using a hash as I did, to not just retrieve the functions from the hash but actually make sure perl knows to execute them. If I did not add have, for example, $dispatch_table{hello}() but instead just had $dispatch_table{hello} I would have gotten this error:

    Useless use of hash element in void context at perl5/ch-2.pl line 10.

Perl Weekly Challenge 033

I continued my efforts in the Perl Weekly Challenge with solutions in Perl, Raku, and the guest language C++. I've decided to split any write-ups on the C++ solutions to a separate blog entry. This week's C++ solutions are discussed here.

Part 1

Perl

Sample Run

Raku

Sample Run

Part 2

The first attempt at this in Perl was with formats. Formatting this sort of output is a natural use for this underutilized built in ability. The fact that it is underutilized is probably almost entirely because this sort of output is much less used these days. Console output and print have long since ceded to web based reports. I noticed when reading up on formats that there was a cpan module, Perl6::Form, which allows the use of Raku's form function in Perl. I was happy to think that I could write largely the same code in both languages! Only after re-writing the Perl code to use Perl6::Form and then beginning the Raku solution did I discover that the present state of the form function in Raku is essentially non-functional. I could not  get any variables to properly interpolate into the format string. The best I could do was use it for some static header text. The rest of the table formatting is done with sprintf. If anyone is interested in a cool Raku project take a stab at updating this! The main repo for this seems to be here.

Perl

Sample Run

Raku

Sample Run

Formatting output with C++

In order to explore the language, including new features, I make an effort to implement C++ solutions to the Perl Weekly Challenge

These challenges are generally designed to be short and take advantage of the high level features that a scripting language such as Perl offers. It has been nice to find that modern C++ offers features, mostly through STL and Boost, that allow for code that is not much longer than would be required in a scripting language. The main difference is usually just that in C++ we must, of course, pay attention to types.

Solutions in Perl and Raku are here.

Part 1

Sample Run

$ g++ -o cxx/ch-1 cxx/ch-1.cxx
$ echo abracadabra | cxx/ch-1
a: 5
b: 2
c: 1
d: 1
r: 2

Part 2

Sample Run

Notes

  • In Part 1 we are asked to keep a count of the number of times letters are used in some text. This code follows pretty directly from my Perl solution to this problem: iterate over each character in the string, ignore whitespaces and punctuation, and store a count for each character in a map.
  • Part 2 involved mostly formatting output into a nice table. Perl offers some nice report templating abilities but doing it slightly more manually C++ style by setting field widths and left/right justifying is not much more work. In fact, the number of lines of code required to print the same table was equal in all of Perl, Raku, and C++.

Perl Weekly Challenge 032

My approach this week was to first implement solutions in Perl as a proof of concept and to determine the best approach to each of the two parts of the challenge. I then re-implemented the approach in C++, which is naturally much more verbose and requires more coding. I finished things out by exploring a Raku version.

This use of Perl as a proof of concept tool for algorithm development is one of it's classic selling points. 

Part 1

Perl

Sample Run

$ perl perl5/ch-1.pl < data
apple 3
cherry 2
banana 1

Raku

Sample Run

$ perl6 raku/ch-1.p6 < data
apple 3
cherry 2
banana 1

C++

Sample Run

$ g++ -o cxx/ch-1 cxx/ch-1.cxx
$ cxx/ch-1 < data
apple 3
cherry 2
banana 1

What I Did

The approach is to read the data (stored in a file data) from stdin. Each unique word is used as a key to a hash and each time it is seen in the file the hash value, a count, is incremented. To print the results as required dictates sorting the hash by value. This sort is readily done in Perl and Raku. C++ data structures are not so flexible. To sort a hash (i.e. a map) in C++ is best done by copying the key/value pairs to a vector and then sorting the vector by the value in the pairs. Modern C++ is able to handle all this in a somewhat surprisingly succinct way, much of the verbosity is required in order to ensure types are managed properly.

Part 2

Perl

Sample Run

$ perl perl5/ch-2.pl '{"apple":3,"cherry":2,"banana":1}'
apple      | ###############
cherry    | ##########
banana  | #####

Raku

Sample Run

$ perl6 raku/ch-2.p6 '{"apple":3,"cherry":2,"banana":1}'
apple      | ###############
cherry    | ##########
banana  | #####

C++

Sample Run

$ g++ -I /opt/local/include -o cxx/ch-2 cxx/ch-2.cxx
$ cxx/ch-2 '{"apple":3,"cherry":2,"banana":1}'

apple      | ###############  
cherry    | ##########  
banana  | #####

Notes

  • Boost provides a very nice library for handling JSON. 
  • I was previously unaware of the std::string constructor which allows for repeating a character n times (line 40). Very convenient!

What I Did

In order to maintain a common input across all three solutions I give the input in JSON format. The input JSON is given on the command line and decoded into a hash map. The same sort by value as Part 1 is performed. The sorted hash map is then iterated over and for each value

  • The value is scaled to be between 0 and 1.
  • The scaled value is multiple by the maximum bar length to determine the number of '#' characters to print.
  • The hash key and the bar representation of the value is printed.

Again Perl and Raku demonstrate the appropriateness of this approach in relatively few lines of code. C++ has more overhead required in setting up data structures and managing types but is ultimately faster, and all that managing of types provides an additional measure of safety!

Perl Weekly Challenge 031

Perl Weekly Challenge has started to see "guest" entries in other languages. Of course, the focus of the challenges will always be Perl and Raku but I like the idea of entries in other languages being made. If nothing else, it's a good way to maintain a good perspective on how these ideas may be implemented elsewhere. In this spirit I have added some C++ entries this week. As my time allows I would like to maintain this as something I do going forward.

Part 1

Create a function to check divide by zero error without checking if the denominator is zero.

All solutions use some variant of try/catch in that they perform the division and then try to gracefully handle what happens. The C++ solution of catching a SIGFPE could have been implemented in all three but I chose to explore the variety of possibilities.

Perl

The traditional Perl way to do this to use an eval block and then test $@ to see if an error was thrown. Modules exist on can to allow for try/catch syntax if you'd prefer. 

Collapse )

Perl Weekly Challenge 030

I was traveling for work most of this past week and so the creativity behind the solutions to this week's Perl Weekly Challenge might not be at exactly the highest level! Then again, although stressed for time, I think my preferred solutions to these problems are as straightforward as what I ended up implementing anyway.

Part 1

Sample Run

$ perl perl5/ch-1.pl
2022
2033
2039
2044
2050
2061
2067
2072
2078
2089
2095

What I Did

I have used Sakamoto's algorithm previously for day of week calculations, most recently for challenge 019. Here I repeat that calculation but for every 25 December for the years stated and check if the result is Sunday, which has a numerical value of 0. If the result does happen on a Sunday the year is printed.

Part 2

Sample Run

$ perl perl5/ch-2.pl
-7 9 10
-6 8 10
-5 7 10
-5 8 9
-4 6 10
-4 7 9
-3 5 10
-3 6 9
-3 7 8
-2 4 10
-2 5 9
-2 6 8
-1 3 10
-1 4 9
-1 5 8
-1 6 7
0 2 10
0 3 9
0 4 8
0 5 7
1 2 9
1 3 8
1 4 7
1 5 6
2 3 7
2 4 6
3 4 5

What I Did

First off, the challenge statement didn't specify any particular range of numbers to consider. Obviously, if we only consider positive numbers then the total number of combinations possible is small, only 11, but if we include negative numbers an infinite number of combinations are possible. For fun I decided to consider negative numbers. Clearly when we consider triplets from a wide range of values the number of combinations because extraordinarily large and so for this challenge I selected a range of [-10, 10]. I don't compute all he combinations directly, instead I decided to rely on Math::Combinatorics to provide these. Each combination is evaluated for the two criteria (i.e. at least one even number and must sum to 12) and any passing both criteria are printed.


Notes

The number of combinations possible are computed as follows. Let's consider the case of triplets selected from 21 numbers, as in the example of all the integers in the interval [-10, 10].

C(n,r)   =    C(21,3)

=                21!
           -----------
           (3!(21−3)!)

=          1330

So in the solution to Part 2 we evaluated 1330 possibilities. How many would we have to evaluate if we expanded the range to [-100, 100]? 1,333,300!

For a tenfold increase of the input we have a thousand fold increase in the output. This rapid growth from small input changes is what is often called a combinatorial explosion.

To read more on this, the Binomial Co-efficient, I suggest starting with the Mathworld article.