Perl Weekly Challenge 177.
My solutions (task 1 and task 2 ) to the The Weekly Challenge - 177.
Task 1: Damm Algorithm
Submitted by: Mohammad S Anwar
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 Damm algorithm is useful for detecting changes in a single symbol within a sequence, as well as a single transposition between adjacent symbols. It is based on a weak totally anti-symmetric group consisting of an operation ∗ on the possible elements of the sequence, meaning, it obeys (c∗x)∗y=(c∗y)∗x⇒x=y for all elements c, x, y. The group is characterized by a table. Constructing the table is a more challenging task than using it. The Wikipedia article contains a sample table for the digits 0..9, namely
∗ 0 1 2 3 4 5 6 7 8 9
0 0 3 1 7 5 9 8 6 4 2
1 7 0 9 2 1 5 4 8 6 3
2 4 2 0 6 8 7 1 3 5 9
3 1 7 5 0 9 8 3 4 2 6
4 6 1 2 3 0 4 5 9 7 8
5 3 6 7 4 2 0 9 5 8 1
6 5 8 6 9 7 2 0 1 3 4
7 8 9 4 5 3 6 2 0 1 7
8 9 4 3 8 6 1 7 2 0 5
9 2 5 8 1 4 3 6 7 9 0
Using the table is quite simple. To test the sequence N0N1N2…Nm, where the last digit is the check digit I evaluate (…((0∗N0)∗N1)…)∗Nm If the result is 0, then there are no simple errors as described above. This yields a simple 3-liner.
perl -MList::Util=reduce -E 'my @d= split "", "03175986427092154863420687135917509834266123045978"
."36742095815869720134894536201794386172052581436790"; my $t=[map {[@d[10*$_..10*$_+9]]}(0..9)];
say "$_->", (reduce {$t->[$a][$b]} (0,split "", $_))?0:1 for @ARGV;
' 5724 5727
Results:
5724->1
5727->0
The reason this works is that after a mistaken digit, say, replacing Nk by a different digit Mk, the subsequent partial sequences (…((0∗N0)∗N1)…)∗Mk)∗Nk+1)…)∗Nk+j do not coincide, for any j, with the original value (…((0∗N0)∗N1)…)∗Nk∗Nk+1)…)∗Nk+j, i.e., a change of one digit produces a change in a partial product that is not corrected by subsequent partial products. Similarly, a transposition produces a change in the partial product (…((0∗N0)∗N1)…)∗Nk+1)∗Nk) that is not corrected by subsequent partial products (…((0∗N0)∗N1)…)∗Nk+1)∗Nk)*Nk+2…)∗Nk+j. Choosing the multiplication table with zeroes in the diagonal, i.e., x∗x=0, allows us to choose the check digit as the product of all previous digits.
The full code is
1 # Perl weekly challenge 177
2 # Task 1: Damm algorithm
3 #
4 # See https://wlmb.github.io/2022/08/08/PWC177/#task-1-damm-algorithm
5 use v5.36;
6 use List::Util qw(reduce);
7 die "Usage: $0 N1 [N2... ]\nTo check N_{i} with Damm's algorithm\n" unless @ARGV;
8 my @digits= map {split "", $_} # consecutive digits of a Damm table
9 qw(0317598642 7092154863 4206871359 1750983426 6123045978
10 3674209581 5869720134 8945362017 9438617205 2581436790);
11 # Organice the digits as a 2D array
12 my $table=[map {[@digits[10*$_..10*$_+9]]}(0..9)];
13 # The group operation $n ∗ $m is given by $table->[$n][$m]
14 say "$_ ", (reduce {$table->[$a][$b]} (0,split "", $_))?"isn't":"is", " correct" for @ARGV;
Example:
./ch-1.pl 5724 5727
Results:
5724 is correct
5727 isn't correct
Task 2: Palindromic Prime Cyclops
Submitted by: Mohammad S Anwar
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
A solution may be obtained by generating numbers in sequence, skipping those that contain zeroes, reversing them to construct a cyclops number and testing it for primality. This fits into a oneliner.
perl -MMath::Prime::Util=is_prime -d -E '
$i=1; while($n<20){$c=$i."0".reverse $i; ++$n, print "$c " if $i!~/0/ && is_prime($c); ++$i}
'|fmt
Results:
101 16061 31013 35053 38083 73037 74047 91019 94049 1120211 1150511
1160611 1180811 1190911 1250521 1280821 1360631 1390931 1490941 1520251
The full code is
# Perl weekly challenge 177
# Task 2: Palyndromic prime cyclops
#
# See https://wlmb.github.io/2022/08/08/PWC177/#task-2-palindromic-prime-cyclops
use v5.36;
use Math::Prime::Util qw(is_prime);
my $left=1;
my $count=0;
my $how_many=shift//20;
while($count<$how_many){
my $candidate=$left."0".reverse $left;
++$count, print "$candidate " if $left!~/0/ && is_prime($candidate);
++$left
}
./ch-2.pl 20|fmt
Results:
101 16061 31013 35053 38083 73037 74047 91019 94049 1120211 1150511
1160611 1180811 1190911 1250521 1280821 1360631 1390931 1490941 1520251
Other languages
I translate my solutions to other languages with which I’m not yet too familiar, to start learning about them. Surely, my solutions will not be the most elegant or efficient.
Raku
Task-1
1 # Perl weekly challenge 177
2 # Task 1: Damm algorithm
3 #
4 # See https://wlmb.github.io/2022/08/08/PWC177/#task-1-damm-algorithm
5 die "Usage: $*PROGRAM-NAME N1 [N2... ]\nTo check Ni with Damm's algorithm\n" unless @*ARGS.Bool;
6 my @table= <0317598642 7092154863 4206871359 1750983426 6123045978 3674209581
7 5869720134 8945362017 9438617205 2581436790>.map({.comb.map({.Int})});
8 @*ARGS.map({say "$^x ", (unshift($^x.comb.Array,0).reduce({@table[$^a][$^b]}))==0??
9 "is"!!"isn't", " correct"});
Example:
./ch-1.raku 5724 5727
Results:
5724 is correct
5727 isn't correct
Task-2
# Perl weekly challenge 177
# Task 2: Palyndromic prime cyclops
#
# See https://wlmb.github.io/2022/08/08/PWC177/#task-2-palindromic-prime-cyclops
my $left=1;
my $count=0;
my $how_many=@*ARGS[0]//20;
while $count < $how_many {
my $candidate=$left~0~$left.flip;
if !($left ~~ /0/) && is-prime($candidate) {
++$count;
"$candidate ".print;
}
++$left;
}
"".say;
Example:
./ch-2.raku |fmt
Results:
101 16061 31013 35053 38083 73037 74047 91019 94049 1120211 1150511
1160611 1180811 1190911 1250521 1280821 1360631 1390931 1490941 1520251
Julia
Task 1
1 # Perl weekly challenge 177
2 # Task 1: Damm algorithm
3 #
4 # See https://wlmb.github.io/2022/08/08/PWC177/#task-1-damm-algorithm
5 using PartialFunctions
6 table=[[0,3,1,7,5,9,8,6,4,2], [7,0,9,2,1,5,4,8,6,3],
7 [4,2,0,6,8,7,1,3,5,9], [1,7,5,0,9,8,3,4,2,6],
8 [6,1,2,3,0,4,5,9,7,8], [3,6,7,4,2,0,9,5,8,1],
9 [5,8,6,9,7,2,0,1,3,4], [8,9,4,5,3,6,2,0,1,7],
10 [9,4,3,8,6,1,7,2,0,5], [2,5,8,1,4,3,6,7,9,0]];
11 function checkdamm(n)
12 reduce((i,j)->table[i+1][j+1], vcat([0], map(parse $ Int64, split(n, ""))))==0
13 end
14 if isempty(ARGS)
15 println("Usage: $PROGRAM_FILE N1 [N2...]\nTo check N1 N2 for Damm correctness")
16 exit()
17 end
18 for n in ARGS
19 println(n , checkdamm(n) ? " is " : " isn't ", "correct")
20 end
Example:
./ch-1.jl 5724 5727
Results:
5724 is correct
5727 isn't correct
Task 2
Here is a version in Julia:
# Perl weekly challenge 177
# Task 2: Palyndromic prime cyclops
#
# See https://wlmb.github.io/2022/08/08/PWC177/#task-2-palindromic-prime-cyclops
using Primes
let left=1
count=0
howmany=if isempty(ARGS) 20 else parse(Int64,ARGS[1]) end
while(count<howmany)
leftstring=string(left)
if !occursin("0", leftstring)
candidate=parse(Int64, leftstring*"0"*reverse(leftstring))
if isprime(candidate)
count +=1
print("$candidate ")
end
end
left += 1
end
end
Example:
./ch-2.jl|fmt
Results:
101 16061 31013 35053 38083 73037 74047 91019 94049 1120211 1150511
1160611 1180811 1190911 1250521 1280821 1360631 1390931 1490941 1520251
Emacs-Lisp
Task 1
;; Perl weekly challenge 177
;; Task 1: Damm algorithm
;; See https://wlmb.github.io/2022/08/08/PWC177/#task-1-damm-algorithm
(defun show-damm (n)
"Print if string of digits n is correct by applying Damm's algorithm"
(princ (format "%s %s correct " n (if (test-damm n) "is" "isn't"))))
(defun test-damm (n)
"Test string of digits n for Damm-correctness"
(equal 0(test-damm1 (cons 0 (mapcar 'string-to-number(split-string n "" t))))))
(defun test-damm1 (s)
"Test the sequence of digits s for Damm-correctness"
(cl-reduce (lambda (i j)(aref2 table i j)) s))
(defun aref2 (table i j)
"Access 2D table with two indices"
(aref (aref table i) j))
(let
(
(table ; Damm table
(vconcat
(mapcar
(lambda(x)
(vconcat
(mapcar 'string-to-number (split-string x "" t))))
'("0317598642" "7092154863" "4206871359" "1750983426" "6123045978"
"3674209581" "5869720134" "8945362017" "9438617205" "2581436790"))))
(candidates '("5724" "5727"))) ; examples to test
(mapc 'show-damm candidates))
Results:
"5724 is correct 5727 isn't correct "
Task 2
;; Perl weekly challenge 177
;; Task 2: Palyndromic prime cyclops
;; See https://wlmb.github.io/2022/08/08/PWC177/#task-2-palindromic-prime-cyclops
(defun cyclops (how-many)
(cl-loop
for left from 1 ; danger: no guard
for left-string = (number-to-string left)
for has0 = (string-match "0" left-string)
for candidate = (string-to-number(concat left-string "0" (reverse left-string)))
for prime = (car (math-prime-test candidate 1))
for success = (and (not has0) prime)
for count = 0 then (if success (+ count 1) count)
while (< count how-many)
if success
collect candidate ))
(princ (cyclops 20))
Results:
(101 16061 31013 35053 38083 73037 74047 91019 94049 1120211
1150511 1160611 1180811 1190911 1250521 1280821 1360631
1390931 1490941 1520251)
I made also a version without the sophisticated common-lisp loop:
;; Perl weekly challenge 177
;; Task 2: Palyndromic prime cyclops
;; See https://wlmb.github.io/2022/08/08/PWC177/#task-2-palindromic-prime-cyclops
(defun cyclops (how-many)
(let ((left 1)(count 0)(result nil))
(while (< count how-many)
(let ((left-string (number-to-string left)))
(unless (string-match "0" left-string)
(let ((cyclops (string-to-number(concat left-string "0" (reverse left-string)))))
(when (car (math-prime-test cyclops 1))
(setq result (cons cyclops result))
(setq count (+ count 1))))))
(setq left (+ left 1)))
(reverse result)))
(print (cyclops 20))
Results:
(101 16061 31013 35053 38083 73037 74047 91019 94049 1120211
1150511 1160611 1180811 1190911 1250521 1280821 1360631
1390931 1490941 1520251)
I’m not sure which version reads better.