Ryan J Thompson

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.)

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.

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.)

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:

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.)

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!

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.)

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:

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.)

Personal note: It’s been an extremely challenging couple of weeks for me, due to a family emergency. As such I’m combining my solutions into a single, shorter blog post this week. If you also follow my review posts on the perlweeklychallenge.org site, you’ll note they are quite late as well. I’m sorry about that! Hopefully things will settle down so I can get back into my rhythm!

Task 1 › 3Sum Problem

The 3Sum (or kSum) problem is another classic in computer science. With this, you are given a target sum ($T) and a list of integers (@L), and are asked to find all unique sets of 3 numbers in @L that sum to $T.

Perl

The brute force way is to simply have a 3-nested loop and try all combinations of integers in @L, and build a list of the sets that sum to $T. But we can eliminate the inner loop entirely if we pre-build a hash of all numbers greater than a given number:

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.)

Task #2 this week is described as follows:

You are given a list, @L, of three or more random integers between 1 and 50. A Noble Integer is an integer N in @L, such that there are exactly N integers greater than N in @L. Output any Noble Integer found in @L, or an empty list if none were found.

An interesting question is whether or not there can be multiple Noble Integers in a list.

For example, suppose we have list of 4 integers [2, 6, 1, 3].

Here we have 2 in the above list, known as Noble Integer, since there are exactly 2 integers in the list i.e. 3 and 6, which are greater than 2.

Therefore the script would print 2.

While Mohammad gave me credit for submitting this problem, I only suggested some wording changes right before it was published, so I didn’t have any sort of advantage going in.

The algorithm I came up with for finding Noble Integers is fairly simple and seems obvious: simply sort the array, and then for each array index, $i, @L.end - $i is the number of elements that come after. @L.end in Raku is $#L in Perl: the last index in the array.

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.)

Task #1 this week asks us to merge integer ranges. Here is the task description:

Write a script to merge the given intervals where ever possible.

[2,7], [3,9], [10,12], [15,19], [18,22]

The script should merge [2, 7] and [3, 9] together to return [2, 9]. Similarly it should also merge [15, 19] and [18, 22] together to return [15, 22]. The final result should be something like below:

[2, 9], [10, 12], [15, 22]

Of course, we could brute force it by comparing every interval with every other interval for an O(n²) solution. But there is a relatively straightforward algorithm to solve this in O(n log n) time.

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.)

Task #2 this week has us build an LRU cache, which is a cache of fixed capacity, whereby when it is full but a new item needs to be added, the item that was least-recently accessed is evicted from the cache.

For example, if a cache of capacity = 3 contains [a b c] (where a was accessed most recently), elements are evicted off the right side of the list. Adding element d, the list would contain [d a b], for example.

Of course, [d a b] are just the keys of the items in the cache. We’ll take an arbitrary scalar (which could itself be a reference) as a value.

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.)

Task #1 this week is as follows:

Write a script to accept a positive number as command line argument and print the smallest multiple of the given number consists of digits 0 and 1.

Brute Force

It’s easy enough to brute force this problem, by checking every multiple in order:

$_ += $_[0] while /[^10]/;

$_ now contains the answer. Unfortunately, some numbers—particularly multiples of 9—require extremely large multiples. For example, 99 × 1122334455667789 = 111111111111111111 takes several minutes to discover via this method.

We can do better, though.

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.)

Task #1 this week is described as follows:

There are 50 people standing in a circle in position 1 to 50. The person standing at position 1 has a sword. He kills the next person i.e. standing at position 2 and pass on the sword to the immediate next i.e. person standing at position 3. Now the person at position 3 does the same and it goes on until only one survives.

Write a script to find out the survivor.

This is a well known theoretical exercise in computer science, by the name of the Josepheus problem, based on the story of Flavius Josephus, a Jewish historian in the first century.

Algorithm

To me, the most natural way to solve this problem is with a circular linked list. As a very quick review, a linked list is a list of items where each item also contains a pointer, reference, index, whatever to the next item in the list. A single element is usually drawn like this: