the lattice calculation bases on a matrix writing the digits of the first value as column headers and writing the digits of the second value as row labels. Each matrix cell has a diagonal. Multiplicating the column digit with the row digit the result will be
(valueA, valueB)
| 4 | """ |
| 5 | |
| 6 | def lattice(valueA, valueB): |
| 7 | """ the lattice calculation bases on a matrix writing |
| 8 | the digits of the first value as column headers and |
| 9 | writing the digits of the second value as row labels. |
| 10 | Each matrix cell has a diagonal. Multiplicating the |
| 11 | column digit with the row digit the result will be |
| 12 | splitted like this: 9 x 8 = 72 -> 7 will written above |
| 13 | the diagonal and 2 will be written below the diagonal. |
| 14 | |
| 15 | When each cell is filled - looking at the diagonals - |
| 16 | you can see that - more or less - at the top right |
| 17 | of a cell and at the bottom left the diagonal can be |
| 18 | continued when there is a further cell. Starting at |
| 19 | the bottom right of the matrix we sum up each digit |
| 20 | of same diagonal. |
| 21 | |
| 22 | The last step is to adjust each sum that way that the |
| 23 | value > 9 is transfered as "too much" to the next sum. |
| 24 | Each time a digit remains being part of the final |
| 25 | product of the multiplication. You have to start with |
| 26 | the last diagonal (bottom right of matrix) |
| 27 | """ |
| 28 | diagonals = [0] * (len(valueA) + len(valueB)) |
| 29 | for indexA, digitA in enumerate(valueA): |
| 30 | for indexB, digitB in enumerate(valueB): |
| 31 | value = int(digitA) * int(digitB) |
| 32 | diagonals[indexA+indexB+0] += value // 10 |
| 33 | diagonals[indexA+indexB+1] += value % 10 |
| 34 | |
| 35 | digits = [] |
| 36 | rest = 0 |
| 37 | for value in reversed(diagonals): |
| 38 | value += rest |
| 39 | if value > 9: |
| 40 | rest = value // 10 |
| 41 | digits.insert(0, value % 10) |
| 42 | else: |
| 43 | rest = 0 |
| 44 | digits.insert(0, value) |
| 45 | |
| 46 | if rest > 0: |
| 47 | digits.insert(0, rest) |
| 48 | |
| 49 | if digits[0] == 0: |
| 50 | del digits[0] |
| 51 | return digits |
| 52 | |
| 53 | def test(): |
| 54 | """ verifying lattice calculation """ |