PWC 110 › Phone Number Validation

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

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.

Continue reading “PWC 110 › Phone Number Validation”

PWC 110 › Transpose CSV File

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

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.

Continue reading “PWC 110 › Transpose CSV File”

PWC 056 › Path Sum

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

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.

Continue reading “PWC 056 › Path Sum”

PWC 056 › Diff-K

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

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;
Continue reading “PWC 056 › Diff-K”

PWC 054 › Collatz Conjecture

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

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.

Continue reading “PWC 054 › Collatz Conjecture”

PWC 054 › kth Permutation

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

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!

Continue reading “PWC 054 › kth Permutation”

PWC 053 › Vowel Strings

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

Task #2 this week has us construct “vowel strings,” as described by Mohammad:

Write a script to accept an integer 1 N 5 that would print all possible strings of size N formed by using only vowels (a, e, i, o, u).

The string should follow the following rules:

  1. ‘a’ can only be followed by ‘e’ and ‘i’.
  2. ‘e’ can only be followed by ‘i’.
  3. ‘i’ can only be followed by ‘a’‘e’‘o’, and ‘u’.
  4. ‘o’ can only be followed by ‘a’ and ‘u’.
  5. ‘u’ can only be followed by ‘o’ and ‘e’. [Note this set is not in lexical order -RJT]

This is a task tailor made for breadth first search (BFS). If you notice, each of the “rules” is essentially an edge in a directed graph, and the nodes are the vowels, a e i o u. We can use BFS to traverse the graph from five different starting points (each vowel), and explore every path of length N, and that will give us our strings.

Continue reading “PWC 053 › Vowel Strings”

PWC 053 › Matrix Rotation

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

Task #1 this week is as follows:

Write a script to rotate the following matrix by given 90/180/270 degrees clockwise.

[ 1, 2, 3 ]
[ 4, 5, 6 ]
[ 7, 8, 9 ]

At first glance, I thought this was a simple matrix transpose, which is what you get when you swap the rows and columns of a matrix. The transposition (T) of the example matrix would give us:

\(\begin{pmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{pmatrix}^\text{T} = \begin{pmatrix}
1 & 4 & 7 \\
2 & 5 & 8 \\
3 & 6 & 9
\end{pmatrix}
\) Continue reading “PWC 053 › Matrix Rotation”

PWC 052 › Lucky Winner

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

Task #2 this week can be as simple or as difficult as you make it. Mohammad’s description:

Suppose there are following coins arranged on a table in a line in random order.

£1, 50p, 1p, 10p, 5p, 20p, £2, 2p

Suppose you are playing against the computer. Player can only pick one coin at a time from either ends. Find out the lucky winner, who has the larger amounts in total?

Analysis

The problem is quite specific, in that we are only given one possible input list, and it is set up as a human v. computer contest, with no other challenge as to how smart (or stupid) the computer is. In fact, this particular problem can be reduced to: “whomever gets the £2 piece wins,” as all the other coins add to 188p.

If you go first, picking £1 will force the opponent to pick 50p or 2p. Keep going until your opponent picks the 2p piece (or the 20p piece), then you get the £2 piece and win.

If the opponent goes first, the same thing applies. Keep stalling until they pick the 20p or 2p piece, then pick the £2 piece and win. Unless of course your opponent is using the same strategy, in which case, they’ve stalled you, and you lose.

So, this isn’t terribly interesting, but I’ll implement it in Raku anyway. Stick around for the Perl version if you yearn for a more general version, though!

Continue reading “PWC 052 › Lucky Winner”

PWC 052 › Stepping Numbers

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

Task #1 this week is straightforward. Here’s what Mohammad had to say about it:

Write a script to accept two numbers between 100 and 999. It should then print all Stepping Numbers between them.

A number is called a stepping number if the adjacent digits have a difference of 1. For example, 456 is a stepping number but 129 is not.

Update [2020-Mar-28]

There seem to have been two interpretations to this problem. In my weekly review, I noticed there were several people in both of the following groups:

Continue reading “PWC 052 › Stepping Numbers”