How Do I Ensure a Candidate Latin Square Is a Valid Damm Operation Table

Question

I am attempting to write a function in Scala that takes a valid Latin Square as input and then returns a Boolean value indicating whether the input Latin Square is a valid instance of an operation-table for the Damm Algorithm, or not. The Damm Algorithm appears to be of the "Check digit" class of error detection mechanisms.

The desired function is an implementation of the implication described in the Design section of the Wikipedia article for the Damm Algorithm. The implication is captured by the assertion of:

a weak totally anti-symmetric quasigroup with the property x ∗ x = 0

I'm insufficient in both the math skills to properly read and interpret Damm's paper, and then having enough German (the language within which the paper was written) reading skills to be able to confidently interpret how I would encode a correct validation function.

Given the following function definition:

def validate(latinSquare: List[List[Int]]): Boolean =
  ???

With what would I replace the ????

Within the paper, a single instance of a valid 10x10 Latin Square is provided. It is reproduced within the Wikipedia article and looks like this:

 |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

I can see there are others who have sought an answer to this. However, no one has yet provided a requested code-based valid Latin Square solution.

I have coded up a generic Latin Square generator, but need the above validation function which will serve as the filter to eliminate each candidate Latin Square that does not meet the necessary condition(s) of the above implication.

Answer 1

In functional programming terms, the checksum algorithm is foldLeft with a carefully chosen binary operation. The requirements for this binary operation, in English:

• In every two-digit input, if we change one of the digits, then the checksum changes (Latin square…);
• In every three-digit input, if the latter two digits are distinct and we swap them, then the checksum changes (…with weak total antisymmetry);
• The Latin square has zeros on the diagonal.

In Python 3:

def validate(latinSquare):
    Q = range(len(latinSquare))
    return all(
        x == y
        for c in Q
        for x in Q
        for y in Q
        if latinSquare[latinSquare[c][x]][y] == latinSquare[latinSquare[c][y]][x]
    ) and all(latinSquare[x][x] == 0 for x in Q)


print(
    validate(
        [
            [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],
        ]
    )
)

Answer 2

This is a conversion into Scala of the Python 3 Answer that was provided by David Eisenstat's answer.

View in Scastie:

def isValidDammOperationTable(validLatinSquare: List[List[Int]]): Boolean = {
  val indices = validLatinSquare.indices.toList
  (
        indices.forall(index => validLatinSquare(index)(index) == 0)
    &&  indices.forall(
          c =>
            indices.forall(
              x =>
                indices.forall(
                  y =>
                        (validLatinSquare(validLatinSquare(c)(x))(y) != validLatinSquare(validLatinSquare(c)(y))(x))
                    ||  (x == y)
                )
            )
        )
  )
}

val exampleLatinSquareX10: List[List[Int]] =
  List(
      List(0, 3, 1, 7, 5, 9, 8, 6, 4, 2)
    , List(7, 0, 9, 2, 1, 5, 4, 8, 6, 3)
    , List(4, 2, 0, 6, 8, 7, 1, 3, 5, 9)
    , List(1, 7, 5, 0, 9, 8, 3, 4, 2, 6)
    , List(6, 1, 2, 3, 0, 4, 5, 9, 7, 8)
    , List(3, 6, 7, 4, 2, 0, 9, 5, 8, 1)
    , List(5, 8, 6, 9, 7, 2, 0, 1, 3, 4)
    , List(8, 9, 4, 5, 3, 6, 2, 0, 1, 7)
    , List(9, 4, 3, 8, 6, 1, 7, 2, 0, 5)
    , List(2, 5, 8, 1, 4, 3, 6, 7, 9, 0)
  )

println(isValidDammOperationTable(exampleLatinSquareX10)) //prints "true"