Prime Vigenere and Raku

This is my response to the Perl Weekly Challenge #15.

Challenge #15.1

 For example, the nth prime number is represented by p(n).

  p(1) = 2
  p(2) = 3
  p(3) = 5
  p(4) = 7
  p(5) = 11

  Strong Prime number p(n) when p(n) > [ p(n-1) + p(n+1) ] / 2
  Weak   Prime number p(n) when p(n) < [ p(n-1) + p(n+1) ] / 2

The rules (the last two lines) are almost code, so programming this is quite easy:

my \p := (1 .. Inf).grep(*.is-prime);   # [1]

my @strong;                             # [3]
my @weak;                               # [4]

for 1 .. Inf -> \n                      # [2]
{
  if p[n] > ( p[n-1] + p[n+1] ) / 2     # [3]
  {
    @strong.push: p[n];                 # [3]
  }
  elsif p[n] < ( p[n-1] + p[n+1] ) / 2  # [4]
  {
    @weak.push: p[n];                   # [4]
  }

  last if @strong.elems >= 10 && @weak.elems >= 10;  # [5]
}

say "Strong primes: { @strong[^10].join(", ") }.";  # [6]
say "Weak primes: { @weak[^10].join(", ") }.";      # [7]

[1] We start with the primes, as a sequence, using is-prime to get them. Note the sigil-less variable name «p» (declared as «\p» and simply used as «p»). I have done it to make the code look as similar to the rules (given above) as possible.

[2] A loop from 1 to infinity. This is the index, «n», in the definitions. The challenge started with index 1, but I have chosen to start with index 0 (as a Raku array does so). The first value (index 1) is the second element in the array, as the formula part «n-1» doesn't work on the first one.

[3] If the prime is strong we add it to the «@strong» array.

[4] Or if the prime is weak we add it to the «@weak» array.

[5] Exit the infinite loop if we have at least 10 strong primes, and at least 10 weak primes. This ensures that we have enough of them both, but will probably give us too many of one of them.

[6] Print the first 10 strong primes, as a comma separated list. «^10» is the same as the list «0 .. 9», and the result is an array slice; where we ask for several values at once. The indices are ordered here, but they do not have to be.

[7] and the first 10 weak primes.

See docs.raku.org/routine/is-prime for more information about is-prime.

Running it:

$ raku prime-strong-weak
Strong primes: 11, 17, 29, 37, 41, 59, 67, 71, 79, 97.
Weak primes: 3, 7, 13, 19, 23, 31, 43, 47, 61, 73.

The values are the same as the ones given by www.numbersaplenty.com/set/weak_prime/, so I am satisfied that I have gotten it right.

We can speed it up a little bit by evaluating the values only one time, and store them in variables. E.g:

  my $pn = p[n];
  my $px = ( p[n-1] + p[n+1] ) / 2;

Then use those variables in the «if» and «push» statements. (But setting up three new variables also takes some time, so in the end we may not actually gain anything. Timing the code would show us, and feel free to have a go at it.)

More Sequences

my \p := (1 .. Inf).grep(*.is-prime);

my $strong := gather
{
  for 1 .. Inf -> \n
  {
    take p[n] if p[n] > ( p[n-1] + p[n+1] ) / 2;
  } 
}

my $weak := gather
{
  for 1 .. Inf -> \n
  {
    take p[n] if p[n] < ( p[n-1] + p[n+1] ) / 2;
  }
}

say "Strong primes: { $strong[^10].join(", ") }";
say "Weak primes: { $weak[^10].join(", ") }";

This version is not as efficient as the first one, as it does the loop twice. But it sets them up as sequences which can be reused when (or rather if) we should need them. And the sequences are lazy, so the values are only computed when needed.

We can shorten the code quite a bit:

my \p := (1 .. Inf).grep(*.is-prime);

my $strong := gather take p[$_] if p[$_] > ( p[$_-1] + p[$_+1] ) / 2 for 1 .. *;
my $weak   := gather take p[$_] if p[$_] < ( p[$_-1] + p[$_+1] ) / 2 for 1 .. *;

say "Strong primes: { $strong[^10].join(", ") }";
say "Weak primes: { $weak[^10].join(", ") }";

I have changed «1 .. Inf» to «1 .. *» to fit the article width.

The remaining primes (when we remove the strong and weak; where the two expressions are equal), are called balanced. The challenge didn't ask for them, but I have included the «$balanced» sequence in the «prime-sequences» file (not shown; see the zip file) for completeness.

Challenge #15.2

«Write a script to implement Vigenère cipher. The script should be able encode and decode. Checkout wiki page for more information.»

Reading several articles cannot hurt, and I found www.geeksforgeeks.org/vigenere-cipher/ easier to understand than the wikipedia article.

The code is quite straightforward:

subset UCASE of Str where * ~~ /^<[A .. Z]>+$/;                         # [1]

unit sub MAIN (UCASE $uppercase-string, UCASE $key, :$decrypt = False); # [2]

my $base = "A".ord;                                                     # [3]
my $key-length = $key.chars;                                            # [4]

my @string = $uppercase-string.comb.map({ $_.ord - $base });            # [5]
my @key    = $key.comb.map({ $_.ord - $base });                         # [6]

for ^@string.elems -> $p                                                # [7]
{
  my $k = $p mod $key-length;                                           # [4a]

  $decrypt                                                              # [8]
    ?? print ($base + (@string[$p] - @key[$k] + 26) mod 26).chr         # [8a]
    !! print ($base + (@string[$p] + @key[$k]) mod 26).chr;             # [8b]
}

print "\n";

[1] The text to encode, the key, and the encoded text are all in uppercase letters (A to Z). This custom type ensures that we only allow strings that satisfies this rule.

[2] «unit sub» instead of «sub» to save us one level of curlies. Note the type restraints on the string and key. The optional «--decrypt» argument is used to choose decryption instead of encryption.

[3] The unicode (or ascii) value (or position) of the letter «A» (which is 65). We need it as the algorithm uses the value 0 for A, 1 for B and so on. Calculating the value ensures that it works even if we had used a different character set.

[4] The key should be repeated over and over if it is shorter than the text. I use the modula function (in [4a]) to do this with the indices, instead of repeating the key itself to the required length.

[5] This gives us a list of numbers; one element for each letter in the string. «comb» gives us a list of single letters, and the «map» code gives us the unicode value and subracts 65 from it. This gives us the values 0 for A, 1 for B, and so on.

[6] The same for the key.

[7] This loop iterates over the indices in the string array. [4a] gives us the corresponding index in the key array.

[8] Did we ask for decryption? Then decrypt (in [8a]), or else we encrypt (in [8b]). The algorithms are taken almost verbatim from the article. Note that we must add the base value (the unicode value of «A») to get back to a letter (from 0 to A, and so on), and use «.chr» to convert the number to the corresponding character.

See docs.raku.org/routine/ord for more information about ord.

See docs.raku.org/routine/chr for more information about chr.

Running it, with the examples given in the Wikipedia article:

$ raku vigenère GEEKSFORGEEKS AYUSH
GCYCZFMLYLEIM

$ raku vigenère --decrypt GCYCZFMLYLEIM AYUSH
GEEKSFORGEEKS

And that's it.