Perl Weekly Challenge 177: Damm Algorithm and Palindromic Prime Cyclops

By laurent_r on August 8, 2022 4:21 PM

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 =  (
[ < 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 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

Damm Algorithm in Other Languages

We now present the same Damm algorithm in the following 18 guest languages (in alphabetic order):

awk
C
D
Dart
Go
Java
JavaScript
Julia
Kotlin
Lua
Nim
Pascal
Python
Ring
Ruby
Rust
Scala
Tcl

From now on, for all guest language implementations, the test will consist in listing the valid numbers between 5700 and 5800, a range that includes the two test cases (5724 and 5727) suggested in the task specification.

Damm Algorithm in awk

The awk programming language has minimal support for arrays. It doesn’t seem to support two-dimensional arrays, and iniitializing arrays in a pain in the neck (there may be some way, but the documentation is scarce). So we implement the damm lookup array as an array of strings and initialize it by initializing each item in the array (in the populate_damm function). Then we use the substr built-in function to retrieve the wanted value from the strings.

function is_valid(n) {
    t = 0
    for (j = 1; j <= length(n); j++) {
        t = substr(damm[t],substr(n, j, 1) + 1 ,1)
    }
    return t == 0
}
function populate_damm() {
    damm[0] = "0317598642"
    damm[1] = "7092154863"
    damm[2] = "4206871359"
    damm[3] = "1750983426"
    damm[4] = "6123045978"
    damm[5] = "3674209581"
    damm[6] = "5869720134"
    damm[7] = "8945362017"
    damm[8] = "9438617205"
    damm[9] = "2581436790"
}
BEGIN {
    populate_damm()
    print("Valid numbers between 5700 and 5800 are: ")
    for (i  = 5700; i<= 5800; i++) {
        if (is_valid(i)) {
            printf("%d ", i)
        }
    }
}

Output:

$ awk -f ./damm-algo.awk
Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797

Note that I was thinking about a bc implementation of the Damm algorithm, but I gave up the idea because the situation with arrays (and also documentation) is worse that in awk.

Damm Algorithm in C

Not much to say, the code is quite clear. Just note that, in the temp = damm[temp][str[i] - '0']; code line, we need to subtract the Ascii value of 0 (48) from the value in the str integer-to-string conversion in order to get proper subscripts. We will have to do the same in a number of other guest language implementations.

#include <stdio.h>

const char damm[10][10] = {
        {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},
    };

int is_valid(int num) {
    int temp = 0;
    char str[10];
    int len = sprintf(str, "%d", num);   // convert input int to string
    str[len] = '\0';
    for (int i = 0; i < len; i++) {
         temp = damm[temp][str[i] - '0'];
    }
    return temp == 0;
}

int main() {
    printf("%s\n", "Valid numbers between 5700 and 5800 are: ");
    for (int i = 5700; i < 5800; i++) {
        if (is_valid(i)) 
            printf("%d ", i);
    }
    printf("%s\n", "");
}

Output:

$ ./a.out
Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797

Damm Algorithm in D

As usual, the D syntax is very similar to the C syntax, but D is just a bit simpler to use than C.

import std.stdio;
import std.conv;

auto 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],
];

bool is_valid (int num) {
    string str = to!string(num, 10);
    int temp = 0;
    foreach (ch; str) {
        temp = damm[temp][ch - '0'];
    }
    return temp == 0;
}

void main() {
    writeln("Valid numbers between 5700 and 5800 are: ");
    for (int i = 5700; i < 5800; i++) {
        if (is_valid(i)) 
            printf("%d ", i);
    }
    writeln("");
}

Output:

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

Damm Algorithm in Dart

Like in awk, I haven’t found a good way to declare and initialize two-dimensional arrays in Dart, and the documentation is quite sparse. So I used the same solution as in awk: an array of strings.

import "dart:io";

var damm = [ "0317598642",
             "7092154863",
             "4206871359",
             "1750983426",
             "6123045978",
             "3674209581",
             "5869720134",
             "8945362017",
             "9438617205",
             "2581436790" ];

void main() {
    print("Valid numbers between 5700 and 5800 are:");
    for (int i = 5700; i <= 5800; i++ ) {
        if (is_valid(i)) {
            stdout.write("$i ");
        }
    }
    stdout.write("\n");
}
bool is_valid(n) {
    var digits = n.toString().split("");
    int temp = 0;
    var len = digits.length;
    for (int i = 0; i < len; i++) { 
        var row = damm[temp];
        var idx = int.parse(digits[i]);
        temp = int.parse(row[idx]);
    }
    return temp == 0;
}

Output:

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

Damm Algorithm in Go

import (
    "fmt"
    "strconv"
)

var damm = [10][10] int {
    {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},
}

func is_valid(num int) bool {
    var n_str = strconv.Itoa(num)
    var temp = 0
    for _, ch := range n_str {
        temp = damm[temp][ch-'0']
    }
    return temp == 0
}

func main() {
    fmt.Println("Valid numbers between 5700 and 5800 are:")
    for i := 5700; i <= 5800; i++ {
        if is_valid(i) {
            fmt.Printf("%d ", i)
        }
    }
    fmt.Println("")
}

Output:

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

Damm Algorithm in Java

public class DammCheckDigit {
    private static final int[][] 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} };

    private static boolean is_valid(Integer num) {
        char[] n = num.toString().toCharArray();
        int temp = 0;
        for (char ch : n) {
            temp = damm[temp][ch - '0'];
        }
        return temp == 0;
    }

    public static void main(String[] args) {
        System.out.printf("%s", "Valid numbers between 5700 and 5800 are:");
        for(int i = 5700; i <= 5800; i++) {
            if (is_valid(i))  System.out.printf("%d ", i);
        }
        System.out.printf("%s", "\n");
    }
}

Output:

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

Damm Algorithm in JavaScript

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] ];

function is_valid (n) {
    let digits = n.toString().split("")
    var temp = 0
    for (var i = 0; i < digits.length; i++) {
        temp = damm[temp][digits[i]]
    }
    return temp == 0
}

console.log("Valid numbers between 5700 and 5800 are:")
for (var i = 5700; i <= 5800; i++) {
    if (is_valid(i)) {
        process.stdout.write(i + " ")
    }
}
console.log("")

Output:

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

Damm Algorithm in Julia

Julia array indices start at 1, not 0, so the crucial code line (temp = damm[temp + 1][d - '0' + 1]) needs to add 1 to the array subscripts when retrieving values from the damm matrix.

function is_valid(num)
    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))
    temp = 0
    str = string(num)
    for d in str
        temp = damm[temp + 1][d - '0' + 1]
    end
    return temp == 0
end

println("Valid numbers between 5700 and 5800 are: ")
for i in 5700:5800
    if is_valid(i)
        print("$i ")
    end
end
println("")

Output:

$ julia ./damm-algo.jl
Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797

Damm Algorithm in Kotlin

Declaring and initializing a matrix in Kotlin is somewhat painful, but the code is otherwise fairly straight forward.

val damm = arrayOf(
    intArrayOf(0, 3, 1, 7, 5, 9, 8, 6, 4, 2),
    intArrayOf(7, 0, 9, 2, 1, 5, 4, 8, 6, 3),
    intArrayOf(4, 2, 0, 6, 8, 7, 1, 3, 5, 9),
    intArrayOf(1, 7, 5, 0, 9, 8, 3, 4, 2, 6),
    intArrayOf(6, 1, 2, 3, 0, 4, 5, 9, 7, 8),
    intArrayOf(3, 6, 7, 4, 2, 0, 9, 5, 8, 1),
    intArrayOf(5, 8, 6, 9, 7, 2, 0, 1, 3, 4),
    intArrayOf(8, 9, 4, 5, 3, 6, 2, 0, 1, 7),
    intArrayOf(9, 4, 3, 8, 6, 1, 7, 2, 0, 5),
    intArrayOf(2, 5, 8, 1, 4, 3, 6, 7, 9, 0)
)

fun is_valid(num: Int): Boolean {
    val n_str = num.toString()
    var temp = 0
    for (d in n_str) {
        temp = damm[temp][d - '0']
    }
    return temp == 0
}

fun main() {
    println("Valid numbers between 5700 and 5800 are: ")
    for (i in 5700..5800) {
        if (is_valid(i)) print("$i ")
    }
    println("")
}

Output:

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

Damm Algorithm in Lua

Like in Julia, Lua array indices start at 1, not 0, so the crucial code line (temp = damm[temp + 1][ch + 1]) needs to add 1 to the array subscripts when retrieving values from the damm matrix.

local 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}
}
function is_valid(num)
    local n_str = tostring(num)
    local temp = 0
    for ch in n_str:gmatch"." do
        temp = damm[temp + 1][ch + 1]
    end
    return temp == 0
end

print("Valid numbers between 5700 and 5800 are: ")
for i = 5700, 5800 do
    if is_valid(i) then
        io.write(i, " ")
    end
end
print("")

Output:

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

Damm Algorithm in Nim

Remember that Nim control flow is indentation-based, like Python.

import strutils

let 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] ]

proc is_valid(num: int): bool =
  let n_str = intToStr(num)
  var temp = 0
  for i in 0..len(n_str) - 1:
    temp = damm[temp][int(n_str[i]) - 48]
  return temp == 0

echo "Valid numbers between 5700 and 5800 are:"
for i in 5700..5800:
  if is_valid(i):
    stdout.write i, " "
echo ""

Output:

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

Damm Algorithm in Pascal

I’m not particularly fond of Pascal, which I found too verbose (at least, by today’s criteria), and I’ve never used it for real-life projects (well, except some quite small Delphi projects a number of decades ago). But, having said that, I must add that Pascal is nonetheless a soft point for me, as it is the first language that I learned in my IS studies (although I had programmed as an autodidact before starting my studies, in Basic, in C, and in the pseudo-assembler of programmable pocket calculators). Pascal is quite clean (perhaps too clean) and it is with Pascal that I first learned the tenets of structured programming. Other languages that I used at the time and found interesting were Fortran, Ada, Prolog, Caml, and especially Modula-2 (or, was it Modula-3? Quite possibly both, one after the other. I’m not quite sure). I might try implementations in some of these languages some day, although I have forgotten most about them. Another language that I also (vaguely) learned at the time of my early studies is Cobol, but I disliked it so much that it is very unlikely that I will ever try to code something in it in the future.

program DammCheckDigit;
uses
  sysutils;

const damm : array[0..9,0..9] of integer =
    ( (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) );

function is_valid(num : integer) : boolean;
var
    temp, i : integer;
    n_str : string;
begin
    n_str := inttostr(num);
    temp := 0;
    for i := 0 to length(n_str) do
    begin
        temp := damm[temp, ord(n_str[i]) - ord ('0')];
    end;
    is_valid := temp=0;
end;

var
    i : integer;
begin
    writeln('Valid numbers between 5700 and 5800 are:');
    for i := 5700 to 5800 do
    begin
        if is_valid(i) then
             write(i, ' ');
    end;
    writeln
end.

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

Damm Algorithm in Python

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

def is_valid(num: int) -> bool:
  temp = 0
  for d in str(num):
    temp = damm[temp][int(d)] 
  return temp == 0

print("Valid numbers between 5700 and 5800 are:")
for i in range(5700, 5801):
  if is_valid(i):
    print(i, end=' ')
print("")

Output:

$ python3 ./damm-algo.py
Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797

Damm Algorithm in Ring

Like in Julia and Lua, array indices start at 1, not 0, so the crucial code line (temp = damm[temp + 1][ch - '0' + 1]) needs to add 1 to the array subscripts when retrieving values from the damm matrix.

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] ]

see "Valid numbers between 5700 and 5800 are:" + nl
for i = 5700 to 5800
    if is_valid(i)
        see "" + i + " "
    ok
next
see " " + nl

func is_valid(num)
    temp = 0
    n = string(num)
    for ch in n
        temp = damm[temp + 1][ch - '0' + 1]
    next
    return temp = 0

Output:

$ ring ./damm-algo.ring
Valid numbers between 5700 and 5800 are:
5708 5719 5724 5735 5743 5756 5762 5770 5781 5797

Damm Algorithm in Ruby

The Ruby implementation is very simple and very concise, thanks to the built-in digits function. Note, however, that this function returns the digits in an inverse order, so we need to reverse it.

def is_valid (n)
    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] ]
    temp = 0
    for ch in n.digits.reverse
        temp = damm[temp][ch]
    end
    return temp == 0
end

puts("Valid numbers between 5700 and 5800 are:")
for i in 5700..5800
    if is_valid(i)
        printf("%d ", i)
    end
end
puts("")

Output:

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

Damm Algorithm in Rust

fn is_valid(num: u32) -> bool {
    static DAMM: [[u8; 10]; 10] = [
        [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],
    ];

    let mut temp = 0;
    let n_str = num.to_string();
    let digits = n_str.bytes();
    for i in digits {
        temp = DAMM[temp as usize][i as usize - 48];
    };
    return temp == 0
}

fn main() {
    println!("{}", "Valid numbers between 5700 and 5800 are:");
    for i in 5700..5800 {
        if is_valid(i) {
            print!("{} ", i);
        }
    }
    println!("{}", " ");
}

Output:

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

Damm Algorithm in Scala

object DammCheckDigit extends App {
  var damm =
    Vector(
      Vector(0, 3, 1, 7, 5, 9, 8, 6, 4, 2),
      Vector(7, 0, 9, 2, 1, 5, 4, 8, 6, 3),
      Vector(4, 2, 0, 6, 8, 7, 1, 3, 5, 9),
      Vector(1, 7, 5, 0, 9, 8, 3, 4, 2, 6),
      Vector(6, 1, 2, 3, 0, 4, 5, 9, 7, 8),
      Vector(3, 6, 7, 4, 2, 0, 9, 5, 8, 1),
      Vector(5, 8, 6, 9, 7, 2, 0, 1, 3, 4),
      Vector(8, 9, 4, 5, 3, 6, 2, 0, 1, 7),
      Vector(9, 4, 3, 8, 6, 1, 7, 2, 0, 5),
      Vector(2, 5, 8, 1, 4, 3, 6, 7, 9, 0)
    )

  def is_valid(num: Int): Boolean = {
    val num_str = num.toString.getBytes
    var temp = 0
    for (ch <- num_str) {
      temp = damm(temp)(ch - '0')
    }
    return temp == 0
  }

  println("Valid numbers between 5700 and 5800 are:")
  for (i <- 5700 to 5800) {
    if (is_valid(i)) {
      printf("%d ", i)
    }
  }
  println("")
}

Output:

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

Damm Algorithm in Tcl

As in awk and Dart, I haven’t found a good way to declare and initialize two-dimensional arrays in Tcl, and the documentation is quite sparse. So I used the same solution as in awk and Dart for the conversion matrix: an array of strings. My knowledge of Tcl dates from the 1990s and is very rusty, so I initially had an interpreter error on almost every code line. So, be aware that my implementation certainly doesn’t satisfy the best practices of this language.

proc is_valid {n} {
    set damm(0) "0317598642"
    set damm(1) "7092154863"
    set damm(2) "4206871359"
    set damm(3) "1750983426"
    set damm(4) "6123045978"
    set damm(5) "3674209581"
    set damm(6) "5869720134"
    set damm(7) "8945362017"
    set damm(8) "9438617205"
    set damm(9) "2581436790"

    set temp 0
    foreach ch [split $n {}] {
        set row $damm($temp)
        set temp [ string index $row $ch ]
    }
    return [ expr $temp == 0 ? 1 : 0]
}

puts "Valid numbers between 5700 and 5800 are: "
for {set i 5700} {$i <= 5800} {incr i} {
    if [ is_valid $i ] {
        puts -nonewline  "${i} "
    }
}
puts ""

Output:

$ tclsh ./damm-algo.tcl
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

Palindromic Prime Cyclops in Other Languages

We now present the same palindromic prime cyclop implementations in the following 8 guest languages:

Julia
JavaScript
Kotlin
Lua
Python
Ring
Ruby
Coconut

Palindromic Prime Cyclops in Julia

I like the concision of Perl and Raku postfix conditionals such as:

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;

In most other languages, you would need three code lines for each case, for example in JavaScript:

if (s[mid] != '0') {
    return false
}
if (s.slice(0, mid-1).search('0') >= 0) {
    return false
}
if (s.slice(mid+1).search('0') >= 0) {
    return false
}
return true

Julia doesn’t have postfix conditionals, but you can use short-circuit evaluation of the && and || operators as an alternative to short if statements to reach the same concision.

The short-circuit evaluation, which is common to most imperative programming languages, means that:

In the expression a && b, the subexpression b is only evaluated if a evaluates to true.
In the expression a || b, the subexpression b is only evaluated if a evaluates to false.

Instead of if <cond> <statement> end, one can write <cond> && <statement> (which could be read as: <cond> and then <statement>). Similarly, instead of if ! <cond> <statement> end, one can write || (which could be read as: <cond> or else <statement>). This idiomatic alternative to short if statement is frequently used in Julia. Although most languages have the short-circuit behavior of logical operators, not many of them support this construct with an ending statement. Raku and Perl do, but this is not commonly used because the return false if ... is admittedly clearer. In the seven guest languages used here, only Kotlin also supports this construct.

So, in Julia, we will have, for example:

len % 2 == 0 && return false
...
s[mid] == '0' || return false

This is our Julia implementation using this concise construct:

using Primes

function is_cyclops(n)
    s = string(n)
    len = length(s)
    len % 2 == 0 && return false
    mid = Int((len + 1) /2)
    s[mid] == '0' || return false
    if occursin('0', s[1:mid-1]) || occursin('0', s[mid+1:len])
        return false
    end
    return true;
end

count = 0
for i = [101:999; 10000:99999; 1000000:9999999]
    string(i) != reverse(string(i)) && continue
    is_cyclops(i) || continue
    if isprime(i)
        print("$i ")
        global count += 1
        count >= 20 && break
    end
end
println("")

Output:

$ julia ./cyclop.jl
101 16061 31013 35053 38083 73037 74047 91019 94049 1120211 1150511 1160611 1180811 1190911 1250521 1280821 1360631 1390931 1490941 1520251

Palindromic Prime Cyclops in JavaScript

JavaScript doesn’t have a built-in function for prime numbers (just as almost all other guest languages to follow). So we roll out our own is_prime function (ported from the Perl implementation above).

It also doesn’t seem possible to combine ranges as we’ve done previously in other languages, so we use a if ... else if ... else if ... construct to simulate range concatenation.

function is_cyclops (n) {
    let s = n.toString()
    let len = s.length
    if (len % 2 == 0) {
        return false
    }

    let mid = (len - 1) / 2
    if (s[mid] != '0') {
        return false
    }

    if (s.slice(0, mid-1).search('0') >= 0) {
        return false
    }
    if (s.slice(mid+1).search('0') >= 0) {
        return false
    }
    return true
}

function is_prime(n) {
    if (n == 2) {
        return true
    }
    if (n < 2 || n % 2 == 0) {
        return false
    }
    var p = 3
    let sqrt_n = Math.sqrt(n)
    while (p <= sqrt_n) {
        if (n % p == 0) {
            return false
        }
        p += 2
    }
    return true
}

var count = 0
var i = 100
while (count < 20) {
    i++
    if (i == 999) {
        i = 10000
    } else if (i == 99999) {
        i = 1000000
    } else if (i >= 9999999) {
        break
    }
    if (i.toString() != i.toString().split("").reverse().join("")) {
        continue;
    }
    if (! is_cyclops(i)) {
        continue;
    }
    if (is_prime(i)) {
        process.stdout.write(i + " ")
        count++
    }
}
console.log("")

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 Kotlin

I do not know whether the short-circuit evaluation alternative to short if statement described above in the context of the Julia language is as commonly used in Kotlin as it is in Julia, but, since it works in Kotlin, I’ll use it here. Also note that we need to implement our own is_prime function in Kotlin.

fun is_prime(n: Int): Boolean {
    n == 2 && return true
    if (n < 2 || n % 2 == 0) {
        return false
    }
    var p = 3
    val sqrt_n : Int = Math.sqrt(n.toDouble()).toInt()
    while (p <= sqrt_n) {
        n % p == 0 && return false
        p += 2
    }
    return true
}

fun is_cyclops(num: Int): Boolean {
    val s = num.toString()
    val len = s.length
    len % 2 == 0 && return false
    val mid = ((len - 1) /2).toInt()
    s[mid] == '0' || return false
    if ('0' in s.slice(0 until mid) or '0' in s.slice(mid+1 until len) {
        return false
    }
    return true
}

fun main() {
    var count = 0
    var i = 100
    while (count < 20) {
        i++
        if (i == 999) {
             i = 10000
        } else if (i == 99999) {
            i = 1000000
        } else if (i >= 9999999) {
            break
        }
        if (i.toString() != i.toString().reversed()) {
            continue;
        }
        if (! is_cyclops(i)) {
            continue;
        }
        if (is_prime(i)) {
            print("$i ")
            count++
        }
    }
    println(" ")
}

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 Lua

Lua doesn’t have a next or continue statement to go directly to the next iteration of a loop, because “the language is designed to be small.” I’m not sure it is a very good reason, as, in my humble opinion, this kind of statement is very useful. This is the reason for which we have two goto skip statements in the main part of the program. I know very well what Edsger Dijkstra said in his famous letter to ACM “Go To Statement Considered Harmful,” but Donald Knuth commented that a “goto forward” within the same routine wasn’t that bad. This is the case here. Having said that, I would definitely prefer if Lua had a continue or next statement rather than a goto statement.

We also have to implement a is_prime function here.

local function is_cyclops(num)
    local n_str = tostring(num)
    size = string.len(n_str)
    if size % 2 == 0 then
        return false
    end
    mid = (size + 1) / 2
    if string.sub(n_str, mid, mid ) ~= '0' then
        return false
    end
    if string.sub(n_str, 1, mid-1):find "0" ~= nil then
        return false
    end
    if string.sub(n_str, mid+1, len):find "0" ~= nil then
        return false
    end
    return true
end

local function is_prime(n)
    if n == 2 then
        return true
    end
    if n < 2 or n % 2 == 0 then
        return false
    end
    local p = 3
    sqrt_n = math.sqrt(n)
    while p <= sqrt_n do
        if n % p == 0 then
            return false
        end
        p = p + 2
    end
    return true
end

count = 0
i = 100
while count < 20 do
    i = i + 1
    if i == 999 then
        i = 10000
    elseif i == 99999 then
        i = 1000000
    elseif i >= 9999999 then
        break
    end

    if i ~= tonumber(string.reverse(tostring(i))) then
        goto skip
    end
    if not is_cyclops(i) then
        goto skip
    end
    if is_prime(i) then
        io.write(i, " ")
        count = count + 1
    end
    ::skip::
end
print("")

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 Python

import math
from re import search
from itertools import chain

def is_prime(n):
  if n == 2:
    return True
  if n == 0 or n == 1 or n % 2 == 0:
    return False
  p = 3
  sqrt_n = math.sqrt(n)
  while (p <= sqrt_n):
    if ((n % p) == 0):
      return False
    p += 2
  return True

def is_cyclops (num):
  s = str(num)
  size = len(s)
  if size % 2 == 0:
    return False
  mid = int((size - 1) / 2)
  if s[mid] != '0':
    return False
  if search(r"0", s[0:mid-1]) or search(r"0", s[mid+1:size-1]):
    return False
  return True

count = 0
myrange = chain(range(100, 999), range(10000, 99999), range(1000000, 9999999))
for i in myrange:
  if str(i) != str(i)[::-1]:
    continue
  if not is_cyclops(i):
    continue
  if is_prime(i):
    print(i, end=' ')
    count += 1
    if count >= 20: 
      break

print("")

Output:

$ python3 ./cyclop.py
101 16061 31013 35053 38083 73037 74047 91019 94049 1120211 1150511 1160611 1180811 1190911 1250521 1280821 1360631 1390931 1490941 1520251

Palindromic Prime Cyclops in Ring

As far as I can tell, Ring also doesn’t have continue or next statements (and also no last and no break). Or, at least, I couldn’t find them (or an equivalent) in the documentation. So I had to use nested if statements, something that I don’t like too much. It also appears that there is no built-in function for reversing a string, so I wrote a is_palindrome function. And also a is_prime function. Also note that the equality operator (== in many languages) is spelled with a single equal sign in Ring, so we have for example if n % p = 0. I wonder how the compiler can distinguish it from the assignment operator, there must be some cases that are ambiguous.

i = 100
count = 0
while count < 20
    i++
    if i = 999
        i = 10000
    ok
    if i = 99999
        i = 1000000
    ok
    if is_palindrome(i)
        if is_cyclops(i)
            if is_prime(i)
                count++
                see "" + i + " "
            ok
       ok
   ok
end
see "" + nl

func is_prime (n)
    if n = 2 
        return true
    ok
    if n < 2 or n % 2 = 0
        return false
    ok
    p = 3
    sqrt_n = sqrt(n)
    while p < sqrt_n
        if n % p = 0
            return false
        ok
        p++
    end
    return true

func is_cyclops(n)
    s = "" + n
    size = len(s)
    if size % 2 = 0
        return false
    ok
    mid = ( size + 1) / 2
    if s[mid] != 0
        return false
    ok

    if substr(left(s, mid-1), "0") > 0
        return false
    ok
    if substr(right(s, mid-1), "0") > 0
        return false
    ok
    return true

func is_palindrome(n)
    s = "" + n
    size = len(s)
    for i = 1 to size/2
        if s[i] != s[size - i + 1]
            return false
        ok
    next
    return true

Output:

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

Palindromic Prime Cyclops in Ruby

Ruby has a built-in prime function, so we don’t need to implement it. I found a way to combine ranges, but I must admit that this is copied from a post on Stack Overflow, I would not have found it by myself.

require 'prime'

def is_cyclops (num) 
    s = num.to_s
    len = s.length;
    if len % 2 == 0 then
        return false
    end
    mid = (len - 1) / 2
    if s[mid] != '0' then
        return false
    end
    if s[0..mid-1][/0/] || s[mid+1..len-1][/0/]
        return false
    end 
    return true
end

count = 0;
range = [ 100..999, 10000..99999, 1000000..9999999 ].map { |r| Array(r) }.inject( :+ )
for i in range
    if i.to_s != i.to_s.reverse || ! is_cyclops(i)
        next
    end
    if i.prime?
        printf("%d ", i)
        count += 1;
        if count == 20
            break
        end
    end
end
puts ""

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 Coconut (a Functional Extension of Python)

This section on Coconut was added on August 18, 2022.

Coconut is a variant of Python built for functional programming. It is actually a kind of extension of Python, and Coconut code is in fact compiled to Python code. The documentation is still somewhat limited, but there is a good Coconut Tutorial and a reference Coconut Documentation.

I was interested in trying to use Coconut for this task essentially because of its support to pipeline style programming. Since we’re looking for the first twenty integers having a certain set of properties (prime, palindromic, with an odd number of digits, with a 0 in the middle and no other 0, etc.), it is appealing to use a pipeline of filters, one for each of these properties, as done in the last (main) section of the code below.

import math
from re import search

def is_prime(n):
    case n:
        match 0:
            return False
        match 1:
            return False
        match 2:
            return True
        match _ is int if n > 2:
            if n % 2 == 0:
                return False
            p = 3
            sqrt_n = math.sqrt(n)
            while (p <= sqrt_n):
                if (n % p) == 0:
                    return False
                p += 2
            return True

def is_cyclops (num):
  s = str(num)
  size = len(s)
  mid = int((size - 1) / 2)
  if s[mid] != '0':
    return False
  if search(r"0", s[0:mid-1]) or search(r"0", s[mid+1:size-1]):
    return False
  return True

range(100, 999) :: range(10000, 99999) :: range(1000000, 9000000) \
|> filter$( -> str(_) == str(_)[::-1]) \    # palindrome
|> filter$( -> len(str(_)) %2 != 0) \       # odd number of digits
|> filter$(is_cyclops) |> filter$(is_prime) \
|>  list |> .$[:20] |> print

Output:

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.

0 comments

Name

Email Address

URL

Remember personal info?

Comments (You may use HTML tags for style)

About laurent_r

I am the author of the "Think Perl 6" book (O'Reilly, 2017) and I blog about the Perl 5 and Raku programming languages.

More info »

laurent_r