Perl – Page 3 – Ryan J Thompson

April 27, 2022

PWC 162 › Wheatstone–Playfair Cipher

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Challenge #2 this week asks us to implement a version of the Playfair Cipher, which is a simple symmetric key cipher, invented in 1854 by Charles Wheatstone, that was used with pencil and paper. It ended up being called the Playfair Cipher because⁠—as I understand it⁠—the ironically named Lord Playfair promoted its use and basked in the glory.

This cipher was used by the Brits up to and including the First World War, to encrypt messages sent via telegraph. Without the key, messages can be decrypted eventually (and it’s easier, the longer the ciphertext, as it is vulnerable to frequency analysis), but the British knew that by the time the enemy decoded the message, the information would no longer be relevant.

April 27, 2022April 27, 2022

PWC 162 › ISBN-13

This week‘s first task is simple: validate ISBN-13 codes.

ISBNs have been around for a long time and come in many different flavours. ISBN-13 is a thirteen-digit code consisting of twelve digits plus a check digit. The checksum calculation is simple. Given the digits x₁, x₂, …, x₁₂, and the check digit, x₁₃:

(10 – (x₁ + 3x₂ + x₃ + 3x₄ + … + x₁₁ + 3x₁₂ + x₁₃)) ≡ 0 (mod 10)

To make calculation a little easier, we can move the check digit (x₁₃) out of the sum and compare it at the end. For example, given the code 978-0-306-40615-7, we can calculate:

10 – (9 + 3×7 + 8 + 3×0 + 3 + 3×0 + 6 + 3×4 + 0 + 3×6 + 1 + 3×5) % 10) = 7

Using List::Util‘s pairmap function, we can simplify the calculation significantly:

April 23, 2022April 23, 2022

PWC 161 › Pangrams

For this week’s second challenge, the task is to generate a pangram.

A pangram is simply a collection of words that contain every letter in the alphabet (English, in this case). A classic pangram example is:

the quick brown fox jumped over the lazy dog
Wikipedia

April 23, 2022April 23, 2022

PWC 161 › Abecedarian Words

I know, it’s been a long time!

This week, I’m back. I submitted the challenges for this week, so I thought it’s only fair that I give them a go myself. Unfortunately, I realized too late that this Abecedarian Words is essentially the same as Week 111’s “Ordered Letters” submitted by the venerable E. Choroba. I thought we hadn’t done it. Nuts. I’m sorry.

Challenge Description

An abecedarian word is a word whose letters are arranged in alphabetical order. For example, “knotty” is an abecedarian word, but “knots” is not. Output or return a list of all abecedarian words in the dictionary, sorted in decreasing order of length.
From: PWC Challenge #161

April 27, 2021April 27, 2021

PWC 110 › Phone Number Validation

Personal note: I’ve had to take a break from participating in the PWC, but I’m back for this week, at least. Hopefully I’ll be able to contribute more again.

The first task this week is a sort of simple phone number validation, based on provided templates. Numbers must match the following, where n is any decimal digit:

+nn  nnnnnnnnnn
(nn) nnnnnnnnnn
nnnn nnnnnnnnnn

Based on the provided sample output, it seems clear that leading and trailing whitespace are ignored. Internal whitespace is also compressed, as the first provided template has two spaces after +nn, yet the phone number +44 1148820341 is supposed to match.

Let’s try two different methods of matching, with Perl and Raku.

April 27, 2021April 27, 2021

PWC 110 › Transpose CSV File

The second task this week is simple: given a (simplified) comma-separated-value (CSV) file, transpose its rows and columns. For example:

$
\begin{bmatrix}
A & B & C & D \\
1 & 2 & 3 & 4 \\
w & x & y & z
\end{bmatrix}^T
\Rightarrow
\begin{bmatrix}
A & 1 & w \\
B & 2 & x \\
C & 3 & y \\
D & 4 & z
\end{bmatrix}
$

The challenge task does not actually refer to the input as CSV, so I’m using that term loosely, with simplified parsing to match the input specification. If more compliant parsing is needed, one could use the usual Text::CSV module in Perl, or ports in Raku.

There are a couple of ways to transpose files, which I’ll explore in Raku and Perl.

April 19, 2020April 23, 2022

PWC 056 › Path Sum

Task #2 this week is a simple tree traversal:

You are given a binary tree and a sum, write a script to find if the tree has a path such that adding up all the values along the path equals the given sum. Only complete paths (from root to leaf node) may be considered for a sum.

For both my Perl and Raku versions, I’m going super-lean with the implementation, using only array references. The “node,” which recursively defines an entire (sub)tree, looks like this:

Element 0: Node’s value
Elements 1..N: References to child nodes

Thus, the (Raku) syntax my @tree = [10, [18, [5], [2]], [8, [16, [18]], [9]]] describes a tree that looks like this:

              10
            /    \
           18     8
          / \    / \
         5   2  16  9
               /
              18

If we look for a path sum of 30, there is precisely one path with that sum: 10 → 18 → 2.

It’s worth noting that, although the task is limited to binary trees, my implementation will handle m-ary trees. Forcing it to handle only binary trees would actually be slightly more difficult, and a lot less useful.

April 19, 2020

PWC 056 › Diff-K

Task #1 this week is to implement the Diff-K algorithm, as explained by Mohammad:

You are given an array @N of positive integers (sorted) and another non negative integer k. Write a script to find if there exists 2 indices i and j such that A[i] – A[j] = k and i != j.

This one is pretty easy. We can boil down the solution into two operations for each element ($_) of @N:

First, filter @N for elements where $k+$_ exists in @N.
For the remaining elements, return an array containing the indexes of $k+$_ and $_.

To make this easier and more efficient, we’ll create an %idx_of hash to store the index of each element in @N. This can be created in linear time, and gives us O(1) lookups for both operations, above.

I really like how easy it is to create a reverse hash like this in Raku:

my %idx_of = @N.antipairs;

April 5, 2020April 5, 2020

PWC 054 › Collatz Conjecture

Task #2 this week was one of my devising:

It is thought that the following sequence will always reach 1:

$
Collatz(n) = \begin{cases}
n \div 2 & n \text{ is even} \\
3n + 1 & n \text{ is odd}
\end{cases}
$

For example, if we start at 23, we get the following sequence:

23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Write a function that finds the Collatz sequence for any positive integer. Notice how the sequence itself may go far above the original starting number.

Extra Credit

Have your script calculate the sequence length for all starting numbers up to 1000000 (1e6), and output the starting number and sequence length for the longest 20 sequences.

I’ve always liked the Collatz conjecture. It is simple enough for schoolchildren to play with, yet the math to prove the conjecture is still beyond our greatest mathematicians.

Here is how I solved this task.

April 5, 2020

PWC 054 › kth Permutation

Task #1 this week is as follows:

Write a script to accept two integers n (>=1) and k (>=1). It should print the kth permutation of n integers. For more information, please follow the wiki page.

For example, for n=3 and k=4, the possible permutation sequences are 123, 132, 213, 231, 312, 321. The script should print the 4th permutation sequence, 231.

This is fairly straightforward. There are a number of easy ways to generate permutations that we’ve all seen time and time again, but as I need to optimize for programmer time this week, I’m going to use Algorithm::Combinatorics for my Perl solution. However, since it’s an efficient module, it’ll also optimize for processor time!