Matrix match in python

Question

How can I find the best "match" for small matrix in big matrix? For example:

 small=[[1,2,3],
        [4,5,6],
        [7,8,9]]



    big=[[2,4,2,3,5],
         [6,0,1,9,0],
         [2,8,2,1,0],
         [7,7,4,2,1]]

The match is defined as difference of numbers in matrix, so match in position (1,1) is as if number 5 from small would be on number 0 from big matrix (so the central number from small matrix in coordinates (1,1) of big matrix.

The match value in position (1,1) is: m(1,1)=|2−1|+|4−2|+|2−3|+|6−4|+|0−5|+|1−6|+|2−7|+|8−8|+|2−9|=28

The goal is to find the lowest difference posible in those matrixes.

The small matrix always has odd number of lines and columns, so it's easy to find it's centre.

Answer 1

You can iterate through the viable rows and columns and zip the slices of big with small to calculate the sum of differences, and use min to find the minimum among the differences:

from itertools import islice
min(
    (
        sum(
            sum(abs(x - y) for x, y in zip(a, b))
            for a, b in zip(
                (
                    islice(r, col, col + len(small[0]))
                    for r in islice(big, row, row + len(small))
                ),
                small
            )
        ),
        (row, col)
    )
    for row in range(len(big) - len(small) + 1)
    for col in range(len(big[0]) - len(small[0]) + 1)
)

or in one line:

min((sum(sum(abs(x - y) for x, y in zip(a, b)) for a, b in zip((islice(r, col, col + len(small[0])) for r in islice(big, row, row + len(small))), small)), (row, col)) for row in range(len(big) - len(small) + 1) for col in range(len(big[0]) - len(small[0]) + 1))

This returns: (24, (1, 0))