Perl Weekly Challenge 177: Damm Algorithm and Palindromic Prime Cyclops

Дата публікації:
08/08/2022 23:21

Постійна адреса новини:
http://www.vsinovyny.com/9223079

Perl Weekly Challenge 177: Damm Algorithm and Palindromic Prime Cyclops

08/08/2022 23:21 // blogs.perl.org

These are some answers to the Week 177 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few of days from now (on Aug. 14, 2022 at 23:59). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

Task 1: Damm Algorithm

You are given a positive number, $n.

Write a script to validate the given number against the included check digit.

Please checkout the wikipedia page for information.

Example 1

Input: $n = 5724
Output: 1 as it is valid number

Example 2

Input: $n = 5727
Output: 0 as it is invalid number

The algorithm is a check digit algorithm named after H. Michael Damm, who presented it in 2004.

The process is quite simple. We’ll use the quasi-group table provided in the afore-mentioned Wikipedia article:

0 3 1 7 5 9 8 6 4 2
7 0 9 2 1 5 4 8 6 3
4 2 0 6 8 7 1 3 5 9
1 7 5 0 9 8 3 4 2 6
6 1 2 3 0 4 5 9 7 8
3 6 7 4 2 0 9 5 8 1
5 8 6 9 7 2 0 1 3 4
8 9 4 5 3 6 2 0 1 7
9 4 3 8 6 1 7 2 0 5
2 5 8 1 4 3 6 7 9 0

Damm Algorithm in Raku

The process is simple. We start with a temporary value of 0. For each digit in the input number, we look up the table with the temporary variable and the digit, and set the temporary variable to the integer found in the table. At the end, the number is valid is the temporary variable is 0. For our test, we will use the two examples provided in the task specification, and we will test all numbers in the 5700..5800 range.

my @damm =  < 0 3 1 7 5 9 8 6 4 2 >,
            < 7 0 9 2 1 5 4 8 6 3 >,
            < 4 2 0 6 8 7 1 3 5 9 >,
            < 1 7 5 0 9 8 3 4 2 6 >,
            < 6 1 2 3 0 4 5 9 7 8 >,
            < 3 6 7 4 2 0 9 5 8 1 >,
            < 5 8 6 9 7 2 0 1 3 4 >,
            < 8 9 4 5 3 6 2 0 1 7 >,
            < 9 4 3 8 6 1 7 2 0 5 >,
            < 2 5 8 1 4 3 6 7 9 0 >;

sub is-valid ($n) {
    my $t = 0;
    $t = @damm[$t][$_] for $n.comb;
    return $t == 0;
}

for 5724, 5727 -> $test {
    say $test, is-valid($test) ?? " is valid." !! " is not valid.";
}
say "\nValid numbers between 5700 and 5800 are: ";
for 5700..5800 -> $i {
    print "$i " if is-valid $i;
}
say "";

This program displays the following output:

$ raku ./damm-algo.raku
5724 is valid.
5727 is not valid.

Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797

Damm Algorithm in Perl

The algorithm for finding the check digit is the same as the one for testing whether a number is valid. So, rather than simply testing the validity directly as we did in Raku, we’ll write a find_check subroutine to find the check digit. Then, a number will be valid if its check digit is 0. Thus, we sort of get the two functions for the price of one. Besides that, the process is essentially the same as in Raku. Check the Raku section above is you need further explanations.

use strict;
use warnings;
use feature qw/say/;

my @damm =  (
    [ qw < 0 3 1 7 5 9 8 6 4 2 > ],
    [ qw < 7 0 9 2 1 5 4 8 6 3 > ],
    [ qw < 4 2 0 6 8 7 1 3 5 9 > ],
    [ qw < 1 7 5 0 9 8 3 4 2 6 > ],
    [ qw < 6 1 2 3 0 4 5 9 7 8 > ],
    [ qw < 3 6 7 4 2 0 9 5 8 1 > ],
    [ qw < 5 8 6 9 7 2 0 1 3 4 > ],
    [ qw < 8 9 4 5 3 6 2 0 1 7 > ],
    [ qw < 9 4 3 8 6 1 7 2 0 5 > ],
    [ qw < 2 5 8 1 4 3 6 7 9 0 > ] );

sub find_check {
    my $n = shift;
    my $t = 0;
    $t = $damm[$t][$_] for split //, $n;
    return $t;
}

sub is_valid {
    my $n = shift;
    return find_check($n) == 0;
}

for my $test (5724, 5727) {
    say $test, is_valid($test) ? " is valid." : " is not valid.";
}
say "\nValid numbers between 5700 and 5800 are: ";
for my $i (5700..5800) {
    print "$i " if is_valid $i;
}
say "";

This program displays the following output:

$ perl  ./damm-algo.pl
5724 is valid.
5727 is not valid.

Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797

Task 2: Palindromic Prime Cyclops

Write a script to generate first 20 Palindromic Prime Cyclops Numbers.

A cyclops number is a number with an odd number of digits that has a zero in the center only.

Output

101, 16061, 31013, 35053, 38083, 73037, 74047, 91019, 94049,
1120211, 1150511, 1160611, 1180811, 1190911, 1250521, 1280821,
1360631, 1390931, 1490941, 1520251

Palindromic Prime Cyclops in Raku

In order to reduce the pointless computations, we’ll only test number ranges with an odd number of digits (100..999, 10000..99999, 1000000..9999999). As it turns out, the process is quite fast (about 2.6 seconds), so that performance enhancement wasn’t really required. I find it nonetheless better to avoid useless computations.

sub is-cyclops ($n) {
    my $length = $n.chars;
    return False if $length %% 2;
    my $mid = ($length - 1) /2;
    return False if substr($n, $mid, 1) != 0;
    return False if $n.comb[0..$mid-1] ~~ /0/;
    return False if $n.comb[$mid+1..$length-1] ~~ /0/;
    return True;
}

my $count = 0;
for |(100..999), |(10000..99999), |(1000000..9999999) -> $i {
    next unless $i eq $i.flip;
    next unless $i.is-prime;
    if is-cyclops $i {
        print "$i ";
        $count++;
        last if $count == 20;
    }
}
say "";

This program displays the following output:

$ time raku ./cyclops.raku
101 16061 31013 35053 38083 73037 74047 91019 94049 1120211 1150511 1160611 1180811 1190911 1250521 1280821 1360631 1390931 1490941 1520251

real    0m2,573s
user    0m0,015s
sys     0m0,015s

Palindromic Prime Cyclops in Perl

This is a port to Perl of the Raku program above. Since Perl doesn’t have a built-in is_prime subroutine, we roll out our own.

use strict;
use warnings;
use feature qw/say/;

sub is_cyclops {
    my $n = shift;
    my $len = length $n;
    return 0 if $len % 2 == 0;
    my $mid = ($len - 1) /2;
    return 0 if substr($n, $mid, 1) != 0;
    return 0 if (split //, $n)[0..$mid-1] =~ /0/;
    return 0 if (split //, $n)[$mid+1..$len-1] =~ /0/;
    return 1;
}

sub is_prime {
   my $n = shift;
   return 1 if $n == 2;
   return 0 if $n % 2 == 0;
   return 0 if $n == 1;
   my $p = 3;
   my $sqrt = sqrt $n;
   while ($p <= $sqrt) {
       return 0 if $n % $p == 0;
       $p += 2;
   }
   return 1;
}

my $count = 0;
for my $i (100..999, 10000..99999, 1000000..9999999) {
    next unless $i eq reverse $i;
    next unless is_cyclops $i;
    if (is_prime $i) {
        print "$i ";
        $count++;
        last if $count == 20;
    }
}

This program displays the following output:

$ perl ./cyclops.pl
101 16061 31013 35053 38083 73037 74047 91019 94049 1120211 1150511 1160611 1180811 1190911 1250521 1280821 1360631 1390931 1490941 1520251

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on August 21, 2022. And, please, also spread the word about the Perl Weekly Challenge if you can.

» Читати повністю

«	Наступна новина з архіву Зуб за зуб, взлом за взлом: неизвестные слили в сеть 4ТБ данных Cellebrite	Попередня новина з архіву Кисень був на Землі ще до початку фотосинтезу: вчені знайшли приховане джерело	»