Balancing Parentheses

Part 2 of the most recent Perl Weekly Challenge was to generate a random string of open and close parentheses and validate which strings were properly balanced. That is, which contained and equal number of open and closed parentheses.


ch-2.pl
ch-2.pl
Collapse )

Perl Weekly Challenge 040

Final Perl Weekly Challenge of 2019

Part 1

ch-1.pl
ch-1.pl

Sample Run

ch-1.pl output
ch-1.pl output

What I Did

  1. Wrote a function display() which takes as input any number of arrays references.
  2. In display(): Find the maximum array index (Line 13). In this example the arrays are all the same size but we do not assume that will always be the case.
  3. In display(): Loop over the arrays and print out the elements, separated by a tab. If an array does not have an element in that index, print an empty string.

Part 2

ch-2.pl
ch-2.pl

Sample Run

ch-2.pl output
ch-2.pl output

What I Did

  1. Set up some Readonly arrays to hold the example data.
  2. Initialize @sorted to be the original array. Line 12
  3. Obtain the specified elements and sort them. Line 13
  4. Sort the indices. Line 14.
  5. Put the sorted values in the right locations in @sorted.
  6. Print the now partially sorted array, as specified.

Notes

Thank you to Mohammad S. Anwar for creating and continuously organizing the Perl Weekly Challenge! The PWC began in early 2019 and it has provided a great mental outlet throughout this past year, especially during lengthy interminable conference calls at work! Besides just Perl and Raku I have even been inspired to occasionally submit solutions in C++. Other members have also submitted guest language solutions in Haskell, Python, and, most heroically of all, Postscript.

Also, quite noteworthy, the PWC has spawned a small resurgence in Perl specific blogs as each week participants describe and elaborate on their solutions.

Happy New Year to Team PWC! 

Parse::Yapp - Introductory Example

Over the course of the past year or so I have made use of Parse::Yapp for several solutions to the Perl Weekly Challenge. This most recent time, for Challenge 039, I thought that it may be helpful to others to dive deeper into this extremely useful module. My hope is to illustrate the use of Parse::Yapp with examples while taking note of the features being used, both in this blog post and in future postings. I am aiming for a slightly simpler and practical minded example based treatment than what is provided by the current module docs which, to the extent in which they document many of the modules's features, are already quite excellent.

To start, let's look at a specific problem, to implement a Reverse Polish Notation calculator.

Recall that Reverse Polish Notation, otherwise known as postfix notation, is simply the positioning of the operator after the operands. For example, in infix notation we would write 10 + 8 and in postfix notation we would write 10 8 +.

Here we are only concerned with the basic four functions (+, -, *, /).

The code for this is a small script (ch-2.pl) to create some examples and call the parser and the parser definition (Rpn.yp).

ch-2.pl The test script.
ch-2.pl The test script.
Rpn.yp The RPN calculator grammar.
Rpn.yp The RPN calculator grammar.

Sample Run

$ perl -I. ch-2.pl
18
-48
80
26
4

What I Did

  1. Define a grammar in Rpn.yp. Unless you really prefer writing your lexing functions elsewhere include them in this file as well.
  2. Execute yapp -m Rpn Rpn.yp. This generates the parser and saves it to a file named Rpn.pm. Specifying an output filename with the -m option will allow you to give the generated parser a name which may make more sense then the default.
  3. Write a wrapper to the parser, as I have done in ch-2.pl. Mine here is very small and straightforward since we're just parsing several strings. Larger projects will need more code to, say, stream larger bodies of text.
  4. The use of -I. in the example above is so that Perl can find Rpn.pm, which happens to be in the same directory I am running the command in (the current working directory). You may have your Rpn.pm (or other generated module) located somewhere else.

The RPN Grammar in Detail

Header

Everything before the first %% is the header section. In Rpn.yp we have just a single line in the header section %token NUMBER which declares a token. In this case NUMBER can be thought of as a label for a whole group of tokens defined in the lexer. Look at line 24. There we can see that a regular expression is defined which identifies numbers and sends them to the parser. NUMBER can be used for any value returned on this line, this is much more convenient than trying to identify which combinations of digits we might want to accept! Technically this %token line is optional, since Yapp does not require this sort of explicit token declaration, however its use certainly helps readability of your grammar.

Rules

The next section, after the first %% is the rules section. This is the heart of the grammar, where we define what we understand to be the definition of the postfix rules are implemented.

Each rule is given a name or label, followed by a : and one or right hand side rule definitions separated by a | and terminated with a ;. Once defined the rule name can be used on the right hand side. In this way rules have a recursive definition.

On line 4 we define a line as being either nothing more than a newline (\n) or a rpn followed by a newline. But what is this rpn? Look to line 7. There the rpn rule is defined as either a NUMBER or an rpn followed by another rpn, followed by an operator. We have four different lines, one for each operator. 

After the right hand side of the rule we define actions which are blocks of Perl code which do something according to the rules that have just been defined. For the four operator rules we take the two tokens and perform the expected operation, adding them, subtracting the, etc. We refer to the tokens by their position in the idiomatic Perl argument array @_. We can see, then, that we can think of each action as a subroutine with its own arguments. Inside @_ we can expect to find $_[1] to $_[n] to be the parameters matching the tokens in the rule with $_[0] saved for a reference to the parser object itself. What happens to the value of this action? You can consider them saved as the value of the left hand side! In this way we can see that just with our simple recursively defined rules we can evaluate a somewhat complicated looking postfix expression such as 2 2 + 3 3 + + 1 7 - + ! The answer is 4, by the way. 

Note that our top level rule has the action of printing the answer once it sees a newline.

Footer

The final section, everything after the second %% is the footer section. This section is technically optional, however, unless your flexing function is particularly complicated it makes sense to usually place it here along with the error reporting and parse functions. sub lexer is our lexer function. The data is stored in a hash under the {INPUT} key. We loop over the input identifying tokens with regular expressions and sending them to the parser. Each token is sent as a pair where the first element is a name or label (remember NUMBER?) and the second is the value of the token. By using s// we are removing the token from the input, reducing it at each pass. When the input is finally empty, having been reduced in this way, the lexer function completes.

sub error is a simple error reporting function. We can customize the error reporting here, perhaps in an effort to provide something useful to the user so they can correct some syntax error. This is optional and if no function is provided for this then any errors will report the default Parser error.

sub parse is the entry point for the parser. See ch-2.pl where it is called by the test script. We can see that it gets passed in an input string, sets it to the value of the {INPUT} key, and calls YYParse (the actual parser generated by Yapp) with references to the lexer and error functions. Finally, the result from YYParse is returned. 

Notes

Implementing an RPN calculator for the Perl Weekly Challenge provided what I considered to be the material for an easily digestible introductory example to Parse::Yapp. As other examples arise I will make additional posts here to further add to the body of documentation.

Lights On!

For the Perl Weekly Challenge 039 we are asked to compute the total time a light is on, based on some log entries.

Part 1

ch-1.pl
ch-1.pl

Sample Run

$ perl perl/ch-1.pl
1 hours 50 minutes

What I Did

I think this implementation is straightforward enough due to the use of DateTime and DateTime::Duration. Each entry in the log is parsed and the total time on is computed. The parsing itself is only complicated by the need to remove some spaces and unnecessary characters.

The main consideration, other than cleaning and parsing the input, is to detect the overlapping of times, which I use DateTime to do.

Perl Weekly Challenge 038

Part 1

ch-1.pl
ch-1.pl

Sample Run

$ perl perl/ch-1.pl
1923-01-20

What I Did

First we have to validate the input, which seemed to be best done with a regex. I don't write regexes often enough to keep one this long in my head so I usually use a tool like Regexer to help write and debug a regex of this length. The function is_valid returns a list of values, the first one being a boolean indicating whether or not the input is valid. If this value is true we pass the other values, which are the fields of interest, to the function which formats the output as required.

Part 2

ch-2.pl
ch-2.pl

Sample Run 

$ perl perl/ch-2.pl
LETTERS: B, H, T, X, E, C, U
BUTCH has a score of 20.
These letters were used: B, H, T, C, U.

What I Did

First off I considered that we are really only asked to perform this for a single set of letters. In that spirit I did not include some optimizations. Specifically, back in previous challenges which involved anagrams I used an approach with the Fundamental Theorem of Arithmetic which allowed for quick finding of words by assigning each word a value based on assigning each letter a unique prime number value. This is skipped here, generating a comprehensive lookup table would be unnecessary effort for evaluating a single set of letters. If interested please see, for example, my description of Challenge 005.

The approach here can be summarized as follows:

  • Create Readonly hashes for character frequencies and values.
  • Use the frequency hash to generate a random set of letters.
  • For each word in the system dictionary see if it can be made up of some or all of our random letters.
  • Every word that meets this criteria is computed a score using the character value hash.
  • The highest word score, the word itself, and the letters used are returned and displayed.

References

https://regexr.com

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.