algorithmscalacheck-digit# How Do I Ensure a Candidate Latin Square Is a Valid Damm Operation Table

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.

Solution

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],
]
)
)
```

- Difference between back tracking and dynamic programming
- How can we optimize this algorithm from O(N ** 2) to better complexity in order to pass performance test?
- How do I predict the required size of a Base32 Decode output?
- Reversing AND Bitwise
- Why does my binary search need an extra comparison? log2(N)+1
- How to build a trie for finding exact phonetic matches, sorted globally by weight, and paginated? (Building off this example)
- What is the Time Complexity and Space Complexity of extending a string according to a rule?
- Skyscraper puzzle algorithm
- Check if all elements in a list are equal
- Bitwise Interval Arithmetic
- fast algorithm for drawing filled circles?
- How to find distance from the latitude and longitude of two locations?
- Determine if two rectangles overlap each other?
- Randomly Splitting a Graph according to Conditions
- Maximize distance while pushing crates
- Free a binary tree without recursion
- How can I estimate number of nodes in given tree structure?
- Explanation of class Definition for Binary Trees in leetcode
- Procedural Generation of 2D Rooms
- Is there an algorithm to find the closest element to X in an unsorted array in Ω(logN)?
- Advanced Java idiom for 2+ classes implementing a generic interface
- Is there any algorithm in c# to singularize - pluralize a word?
- Number of Common sub sequences of two strings
- Trying to solve problem 19 on Euler Project
- is a "non-decreasing" sequence "increasing"?
- Is it possible to get the original value of a number, after several multiplications **with overflow**?
- Algorithm to determine the highest and lowest possible finishing position of a team in a league
- Algorithm to calculate the number of divisors of a given number
- Rolling or sliding window iterator?
- best way to pick a random subset from a collection?