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.

Part 1

Sample Run

$ perl ch-1.pl "Perl {Daily,Weekly,Monthly,Yearly} Challenge"
Perl Daily Challenge
Perl Weekly Challenge
Perl Monthly Challenge
Perl Yearly Challenge

What I Did

There's probably a few ways to solve this that I didn't consider, however, I think in this case regular expressions are the way to go. everything before, inside, and after the braces are captured with the regex and then printed.

Part 2

Sample Run

$ perl -I. -Iblib/arch/auto/pwc ch-2.pl 10000
100

What I Did

Whenever I need to interface Perl and code written in another language I greatly prefer SWIG over any other option. The Inline modules require a compiler to be present on the system running the code and in my experience many environment forbid compilers being installed on production systems for security reasons so I've never considered them a real option. XS is fine if you're only looking to integrate a C or C++ code base with Perl but then you'd end up having to use SWIG for anything else anyway. I previously wrote on interfacing C++ and Perl and what I did here is mostly the same, but for a much smaller problem. The challenge asked only to demonstrate calling a C function so here I decided to call the sqrt() function from math.h. The file pwc.i described the interface between Perl and the C functionality we which to wrap. In that file we are telling SWIG to generate a Perl module named pwc.pm which wraps sqrt() from math.h. When we run the command

$ swig -perl pwc.i

SWIG will generate several files, most importantly are pwc.pm and pwc_wrap.c. The Makefile.PL shown above will further automate the actual building of the C code. That is the following commands

$ perl Makefile.PL
$ make

will build the library in a blib directory. And that's it! As shown above be sure to include the SWIG generated library if it's in a location outside of your @INC. If you are writing something that you'd like to keep around then consider further running

$ make install

as you would expect to do for installing any module.

Part 1

Part 1

What I Did

Using a well known formula [1] I computed the intersection from the four given points. Perhaps the greatest complexity in this code was the handling of the points on the command line. The input format given in this week's challenge required some escaping in the shell and a bit of parsing to get everything organized in an easily usable way.

Sample Run

$ perl perl5/ch-1.pl \(0,0\) \(9,9\) \(0,9\) \(9,0\)
(0, 0)--(9, 9) and (0, 9)--(9, 0) intersect at (4.5, 4.5)

Part 2

What I Did

This part of the challenge stumped me for a while! After a bunch of thought I decided that a source filter would do the trick! I've never used this particular feature of Perl but Filter::Simple made the implementation of the filter itself somewhat straightforward. The filter itself is in Audit.pm. What it does is use a regular expression to identify scalar variables and appends a call to audit() after the nearest semicolon. For example, let's say we have these lines:

    my $a = 0;
   $a = 2 + 2;

the filter will change them to appear as

    my $a = 0; audit($a);
   $a = 2 + 2; audit($a);

This will log the values of the variable in a hash (%Log) keyed by the variable name itself. There are a few other functions that do some convenient things like clear %Log or print the contents of %Log in a formatted way. If you want to see what objects actually contain you'll want to use pretty_print_log() vs print_log(), see the example output below for what the differences are. Note that pretty_print_log() simply wraps Data::Dump's pp() since that did not seem like an appealing wheel to re-invent!

As I was finalizing my submission I had a few final thoughts on this.

• The name Audit seems to be already taken on CPAN. Since I have no interest in distributing this I think that's OK. My Audit.pm exists solely for this purpose. Hopefully nobody will be confused by the overlap with the name I chose for this small project.
• I did not test this very much. It seems fairly robust but surely some corner cases exist where this approach will break down!
• The warnings about the use of source filters seem accurate. That is, unless very clearly documented and understood when used I can see how there is opportunity for significant errors to be introduced into your code in subtle and confusing ways.

Sample Run

$ perl -I perl5 perl5/ch-2.pl

$test0: undef, 2, 3
$test1: bless({
# tied Tie::ExtraHash
A => "B",
}, "Class::Hash"), bless({
# tied Tie::ExtraHash
B => "C",
}, "Class::Hash"), bless({
# tied Tie::ExtraHash
C => "D",
}, "Class::Hash")

Note: If we instead had simply used Audit::print_log() this is what would have been the output. We see that the object references have been changed but do not see the values within the objects.

$test0: undef, 2, 3
$test1: Class::Hash=HASH(0x7fde390b2a70), Class::Hash=HASH(0x7fde38014920), Class::Hash=HASH(0x7fde38014b18)

References

[1]http://www.ambrsoft.com/MathCalc/Line/TwoLinesIntersection/TwoLinesIntersection.htm 

Part 1

Sample Run

$ perl perl5/ch-1.pl chancellor chocolate
8

What I Did

First off, I have to say that I re-used some code from Part 2 of Challenge 004. In that challenge I did the same basic technique used here where for each letter in the alphabet we are searching from (the "stones" string) a closure is created which removes a specific letter from the target (the "jewels"). 

Looking at the code you'll see that all the closures are stored in an array and called in a loop. At each iteration of the loop the "jewels" are reviewed and the number of removed "stones" are added to $count. At the end of the loop $count will contain the total number of "stones" found in "jewels" and is returned.

Part 2

Sample Run

$ perl perl5/ch-2.pl 10 20 30
20

$ perl perl5/ch-2.pl 355 15 5
5

What I Did

When working with angles one of the main causes of frustration is the use of degrees and radians. Intuitively most people think in degrees but almost all trigonometry functions provided by standard libraries expect arguments passed as radians. Because this is a challenge I choose, as usual, to avoid using any CPAN modules. Due to this I have defined my own deg2rad and rad2deg functions. The value of PI is held in a constant defined using a classic identity with atan2.

The list of angles is provided on the command line in degrees. These are converted to radians and the converted angles are passed to compute_mean_angle() which implements the computation described in [1]. I generally dislike the overuse of map in Perl code but here it seems to fit very well and the code has an overall cleaner appearance because of it, I believe.

The mean angle is returned, in radians, and converted to degrees and printed.

References

[1] https://en.wikipedia.org/wiki/Mean_of_circular_quantities

Given a list of Pokemon names, what is the longest sequence of names which can be obtained by creating a name ladder where the first letter of a name is the same letter as the name preceding it? Turns out to be 105 characters long, according to the method I used.

The Code

How it works

The names are read in, they are held in the scripts __DATA__ section for convenience, and added to a Graph. Each vertex is a Pokemon name and the (directed) edges are created by the name ladder rule. The edge weight is the negative of the length of the vertex's successor. The Floyd-Warshall All Pairs Shortest Path algorithm is run on the resulting graph and the returned paths are reviewed to see which one is the longest in terms of overall character length. By using the negative of the weight the paths found are actually the longest, not shortest. The result is printed along with the length.

The full number of Pokemon as of this writing is 809! Here I am just using a sampling of the complete set.

Sample Run

$ perl perl5/ch-1.pl
machamp-petilil-lunatone-exeggcute-emboar-registeel-loudred-darmanitan-nosepass-simisear-rufflet-tyrogue-emolga-audino 105

The history of Chaocipher is so well covered elsewhere, I won't bother with the details here. Instead I'll concentrate on an implementation of a playing card based simulation [1] of the cipher. That is, taking the manual technique created by Aaron Toponce and executing a Perl based model.

The Code

File ch-2.pl performs the high level details of the encrypting and decrypting process. A Deck of "cards" is created and split into two piles (red and black/left and right). As we'll see, the cards are keyed to the letters of the alphabet. Encrypting any single letter of the plaintext is done by finding the position of the letter in the plaintext pile and then providing the value of the card in the same position in the cypher text pile. The two piles are both them permuted according to straightforward rules. Decryption is virtually the same, except first the cypher text pile is searched and the corresponding index used for the plaintext pile.

Deck.pm

In the snippet of Deck.pm above you can see the permuting process. In both cases we are essentially cutting the piles at the index of the plaintext/cyphertext, swapping the halves, and then re-assigning the cards at index 0 and 13 (the so called zenith and nadir.) [1] describes the process in slightly more detail.

The Deck itself is a blessed array reference of Card objects. Cards are based on Class::Enum. The reason for this has more to do with the design of some older code I had written for a game simulation than for the purposes of Choacipher, but it ends up working well here too, I think.

CypherCard.pm

CypherCard.pm is a really a wrapper around the information contained in a card: Suit, Rank, and the letter assigned to it for use in the cipher.

Rank.pm

The usefulness of having enumerated ranks is not necessary for Chaocipher but for simplicity's sake this code was left in place.

Suit.pm

Suit.pm uses the ordinal property of the enum to red/black divide the suits.

Putting it all together we can see below what happens when we encrypt the message ATTACKATDAWN and the decrypt the encrypted message. It works!

Sample Run

$ perl -Iperl5 perl5/ch-2.pl
SUUSNFSULSRK
ATTACKATDAWN

Summary

All the details of this playing card technique can be found in [1]. Aaron Toponce should be congratulated for this extremely clever playing card cipher system! Simulating the use of this card technique, rather than the cipher directly, provides greater insight into the playing card method as well as the original cipher process itself.

References

[1] https://aarontoponce.org/wiki/crypto/card-ciphers/chaocipher

Part 1 of Perl Weekly Challenge 024 was to create an Inverted Index. Here I will describe how I created the Inverted Index and also how I displayed the results using format.

The Code

Sample Run

$ perl perl5/ch-2.pl

-----------------------------------------------------------------------------------------|Word                     |                                          Documents                                         |
-----------------------------------------------------------------------------------------
.
.
.
|abbey                    |arrow.txt                                                                                       |
|abolishing            |eighty.txt                                                                                      |
|about                    |catriona.txt, eighty.txt                                                                |
|address                 |balloon.txt                                                                                    |
|adventures           |kidnapped.txt                                                                              |
.
.
.

What I Did

While there are several modules available on CPAN which provide a Read Eval Print Loop the classic technique for executing Perl statements interactively is via the perl debugger. To start a REPL session execute the following:

perl -d -e 0

And you will enter the debugger and be able to execute commands interactively, along with the ability to use debugging functions. For example,

$ perl -d -e 0

Loading DB routines from perl5db.pl version 1.53
Editor support available.

Enter h or 'h h' for help, or 'man perldebug' for more help.

main::(-e:1): 0
DB<1> $a = 2;

DB<2> $b = $a * 9;

DB<3> print "B!" if($b > $a);
B!
DB<4> x $b
0 18
DB<5> 

The debugger commands are pretty well documented if you're interested in using them.

In order to get the debugger into this interactive mode you specify the -d and -e command line options. After the -e you could specify whatever code you'd like but in most cases, if you are doing this for REPL purposes, you can specify the shortest possible syntactically correct Perl code which is simply a single numeric value. The use of 0 is arbitrary. What happens is that whatever code follows -e is used in the interactive debugging session. Since we don't really care about if we just want to try out some commands in a repl 0 is usually fine. To give a full sense of what is actually happening though look at the following:

$ perl -d -e '$a = 7;'

Loading DB routines from perl5db.pl version 1.53
Editor support available.

Part 1

Sample Run

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

$ perl perl5/ch-1.pl 2 5 9 2 8 1 6
-11, 13, -13, 12

What I Did

My use of recursion here is pretty much for fun. Writing an outer loop that iterates for $order number of times would not look too weird here at all. Other than that note I think the code (should hopefully!) speak for itself.

Part 2

Sample Run

$ perl perl5/ch-2.pl 228
2, 2, 3, 19

$ perl perl5/ch-2.pl 1228
2, 2, 307

$ perl perl5/ch-2.pl 1000
2, 2, 2, 5, 5, 5

What I Did

Because of my method for implementing the anagram logic in Challenge 005 I pretty much had already written this code before. Check out that earlier challenge for a neat use of the Fundamental Theorem of Arithmetic which states that every integer greater than 1 is either a prime number itself or can be represented as the unique product of prime numbers.