<p>You are given a <code>m x n</code> <strong>0-indexed </strong>2D<strong> </strong>matrix <code>mat</code>. From every cell, you can create numbers in the following way:</p>

<ul>
	<li>There could be at most <code>8</code> paths from the cells namely: east, south-east, south, south-west, west, north-west, north, and north-east.</li>
	<li>Select a path from them and append digits in this path to the number being formed by traveling in this direction.</li>
	<li>Note that numbers are generated at every step, for example, if the digits along the path are <code>1, 9, 1</code>, then there will be three numbers generated along the way: <code>1, 19, 191</code>.</li>
</ul>

<p>Return <em>the most frequent <span data-keyword="prime-number">prime number</span> <strong>greater</strong> than </em><code>10</code><em> out of all the numbers created by traversing the matrix or </em><code>-1</code><em> if no such prime number exists. If there are multiple prime numbers with the highest frequency, then return the <b>largest</b> among them.</em></p>

<p><strong>Note:</strong> It is invalid to change the direction during the move.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<strong><img alt="" src="https://assets.leetcode.com/uploads/2024/02/15/south" style="width: 641px; height: 291px;" /> </strong>

<pre>
<strong>
Input:</strong> mat = [[1,1],[9,9],[1,1]]
<strong>Output:</strong> 19
<strong>Explanation:</strong> 
From cell (0,0) there are 3 possible directions and the numbers greater than 10 which can be created in those directions are:
East: [11], South-East: [19], South: [19,191].
Numbers greater than 10 created from the cell (0,1) in all possible directions are: [19,191,19,11].
Numbers greater than 10 created from the cell (1,0) in all possible directions are: [99,91,91,91,91].
Numbers greater than 10 created from the cell (1,1) in all possible directions are: [91,91,99,91,91].
Numbers greater than 10 created from the cell (2,0) in all possible directions are: [11,19,191,19].
Numbers greater than 10 created from the cell (2,1) in all possible directions are: [11,19,19,191].
The most frequent prime number among all the created numbers is 19.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> mat = [[7]]
<strong>Output:</strong> -1
<strong>Explanation:</strong> The only number which can be formed is 7. It is a prime number however it is not greater than 10, so return -1.</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> mat = [[9,7,8],[4,6,5],[2,8,6]]
<strong>Output:</strong> 97
<strong>Explanation:</strong> 
Numbers greater than 10 created from the cell (0,0) in all possible directions are: [97,978,96,966,94,942].
Numbers greater than 10 created from the cell (0,1) in all possible directions are: [78,75,76,768,74,79].
Numbers greater than 10 created from the cell (0,2) in all possible directions are: [85,856,86,862,87,879].
Numbers greater than 10 created from the cell (1,0) in all possible directions are: [46,465,48,42,49,47].
Numbers greater than 10 created from the cell (1,1) in all possible directions are: [65,66,68,62,64,69,67,68].
Numbers greater than 10 created from the cell (1,2) in all possible directions are: [56,58,56,564,57,58].
Numbers greater than 10 created from the cell (2,0) in all possible directions are: [28,286,24,249,26,268].
Numbers greater than 10 created from the cell (2,1) in all possible directions are: [86,82,84,86,867,85].
Numbers greater than 10 created from the cell (2,2) in all possible directions are: [68,682,66,669,65,658].
The most frequent prime number among all the created numbers is 97.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == mat.length</code></li>
	<li><code>n == mat[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 6</code></li>
	<li><code>1 &lt;= mat[i][j] &lt;= 9</code></li>
</ul>

class Solution:
    def mostFrequentPrime(self, mat: List[List[int]]) -> int:

        def isprime(N: int) -> bool:
            trivial_primes = [2, 3, 5, 7]
            if N in trivial_primes:
                print(f'{N=} trivial prime')
                return True
            if N < 10:
                print(f'{N=} trivial non-prime')
                return False
            for P in trivial_primes:
                if N % P == 0:
                    print(f'{N=} non-prime {P=}')
                    return False
            k = 5
            # all primes > 3 will be of the form 6x-1 or 6x+1:
            # therefore check only those
            while k * k <= N:
                print(f'{N=} Check {k} and {k+2}')
                if N % k == 0:
                    print(f'{N=} non-prime {k=}')
                    return False
                if N % (k + 2) == 0:
                    print(f'{N=} non-prime {k+2=}')
                    return False
                k += 6
            print(f'{N=} prime ({k=} {k*k=})')
            return True
        
        # print(f'TEST: {isprime(11)=}')

        # SHORTCUT: instead of going through each cell, working
        # in each of eight directions, and composing numbers,
        # we will create four sets of numbers, one for each
        # of Horiz, Vert, Dexter, Sinister, which we will then
        # subdivide into each possible fragment and reversed-ness
        
        REV = lambda row: tuple(reversed(tuple(row)))
        REVSTR = lambda S: ''.join(REV(S))
        MIRROR = lambda grid: tuple(map(REV, grid))
        INV = lambda grid: tuple(zip(*grid))

        Horiz = lambda grid: tuple([''.join(map(str, row)) for row in grid])
        Vert = lambda grid: Horiz(INV(grid))

        def Dexter(grid: List[List[int]]) -> List[str]:
            grid = list(grid)   # mutable copy for this function
            answer = []
            row = grid.pop(0)
            extras = len(grid)

            clean = lambda row: list(map(str, row)) + [''] * extras

            working = clean(row)
            # print(f'{answer=} {working=}')
            for row in grid:
                answer.append(working.pop(0))
                next_row = clean(row)
                working = [
                    A + B
                    for A, B in zip(working, next_row)
                ]
                # print(f'{answer=} {working=}')
            answer.extend(working)
            working = ()
            # print(f'{answer=} {working=}')
            return tuple(answer)

        Sinister = lambda grid: Dexter(MIRROR(grid))
        
        Groups = [
            Horiz(mat),
            Vert(mat),
            Dexter(mat),
            Sinister(mat),
        ]
        # print(f'A: {Groups=}')
        Groups = [
            N
            for group in Groups
            for N in group
        ]
        # print(f'B: {Groups=}')
        GroupsR = list(map(REVSTR, Groups))
        # print(f'b: {GroupsR=}')
        Groups += GroupsR
        # print(f'C: {Groups=}')

        def fragments(N: str) -> List[str]:
            for i in range(len(N)):
                for j in range(i+1, len(N)):
                    yield N[i:j+1]
        
        # print(f'TEST: {tuple(fragments("12345"))=}')

        Numbers = [
            N
            for G in Groups
            for N in fragments(G)
        ]
        print(f'D: {Numbers=}')

        Numbers = [
            int(N)
            for N in Numbers
            if len(N) > 1               # number > 10
            if N[-1] not in '024568'    # not multiple of 2 or 5
        ]
        print(f'E: {Numbers=}')

        counts = Counter(Numbers)
        print(f'{counts=}')
        best_answers = sorted(
            # sorting them by largest count, then largest number
            counts.most_common(),
            key=lambda x: (x[1], x[0]),
            reverse=True,
        )
        print(f'{best_answers=}')
        for (answer, count) in best_answers:
            if isprime(answer):
                return answer

        return -1

17100