Most Frequent Prime solution and explanation

from collections import defaultdict

DIRECTIONS = [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)]

def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return n > 1
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return n > 10

def dfs(mat, m, n, x, y, number, visited, primes):
    visited.add((x, y))
    
    if number and number > 10 and is_prime(int(number)):
        primes[int(number)] += 1

    for dx, dy in DIRECTIONS:
        nx, ny = x + dx, y + dy
        if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in visited:
            dfs(mat, m, n, nx, ny, number + str(mat[nx][ny]), visited.copy(), primes)



def most_frequent_prime(mat):
    m, n = len(mat), len(mat[0])
    primes = defaultdict(int)
    
    for i in range(m):
        for j in range(n):
            dfs(mat, m, n, i, j, str(mat[i][j]), set(), primes)
    
    max_freq = 0
    result = -1
    for prime, freq in primes.items():
        if freq > max_freq or (freq == max_freq and prime > result):
            max_freq = freq
            result = prime
    
    return result

mat = [[1, 1], [9, 9], [1, 1]]
print(most_frequent_prime(mat))  # Output: 19

import java.util.HashMap;
import java.util.Map;

public class MostFrequentPrime {
    private static final int[][] DIRECTIONS = {
        {0, 1}, {1, 1}, {1, 0}, {1, -1},
        {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}
    };

    public static boolean isPrime(int n) {
        if (n <= 1) return false;
        if (n <= 3) return n > 10;
        if (n % 2 == 0 || n % 3 == 0) return false;
        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) return false;
        }
        return n > 10;
    }

    public static void dfs(int[][] mat, int m, int n, int x, int y, String number, boolean[][] visited, Map<Integer, Integer> primes) {
        visited[x][y] = true;
        int num = Integer.parseInt(number);
        if (num > 10 && isPrime(num)) {
            primes.put(num, primes.getOrDefault(num, 0) + 1);
        }

        for (int[] dir : DIRECTIONS) {
            int nx = x + dir[0];
            int ny = y + dir[1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                dfs(mat, m, n, nx, ny, number + mat[nx][ny], visited, primes);
            }
        }
        visited[x][y] = false;
    }

    public static int mostFrequentPrime(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        boolean[][] visited = new boolean[m][n];
        Map<Integer, Integer> primes = new HashMap<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(mat, m, n, i, j, String.valueOf(mat[i][j]), visited, primes);
            }
        }

        int maxFreq = 0;
        int result = -1;
        for (Map.Entry<Integer, Integer> entry : primes.entrySet()) {
            if (entry.getValue() > maxFreq || (entry.getValue() == maxFreq && entry.getKey() > result)) {
                maxFreq = entry.getValue();
                result = entry.getKey();
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[][] mat = {{1, 1}, {9, 9}, {1, 1}};
        System.out.println(mostFrequentPrime(mat));  // Output: 19
    }
}

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>

using namespace std;

const vector<pair<int, int>> DIRECTIONS = {{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return n > 10;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return n > 10;
}

void explorePaths(vector<vector<int>>& mat, int m, int n, int x, int y, string currentNumber, vector<vector<bool>>& visited, unordered_map<int, int>& primeCount) {
    visited[x][y] = true;
    int num = stoi(currentNumber);
    if (num > 10 && isPrime(num)) {
        primeCount[num]++;
    }

    for (const auto& d : DIRECTIONS) {
        int nx = x + d.first;
        int ny = y + d.second;
        if (nx >= 0 && ny >= 0 && nx < m && ny < n && !visited[nx][ny]) {
            explorePaths(mat, m, n, nx, ny, currentNumber + to_string(mat[nx][ny]), visited, primeCount);
        }
    }
    
    visited[x][y] = false;
}

int mostFrequentPrime(vector<vector<int>>& mat) {
    int m = mat.size();
    int n = mat[0].size();
    unordered_map<int, int> primeCount;
    
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            explorePaths(mat, m, n, i, j, to_string(mat[i][j]), visited, primeCount);
        }
    }

    int result = -1;
    int maxCount = 0;
    for (const auto& pair : primeCount) {
        if (pair.second > maxCount || (pair.second == maxCount && pair.first > result)) {
            maxCount = pair.second;
            result = pair.first;
        }
    }
    return result;
}

int main() {
    vector<vector<int>> mat = {{9, 7, 8}, {4, 6, 5}, {2, 8, 6}};
    cout << mostFrequentPrime(mat) << endl;  // Output: 97
    return 0;
}

const DIRECTIONS = [
    [0, 1], [1, 1], [1, 0], [1, -1],
    [0, -1], [-1, -1], [-1, 0], [-1, 1]
];

function isPrime(n) {
    if (n <= 1) return false;
    if (n <= 3) return n > 10;
    if (n % 2 === 0 || n % 3 === 0) return false;
    for (let i = 5; i * i <= n; i += 6) {
        if (n % i === 0 || n % (i + 2) === 0) return false;
    }
    return n > 10;
}

function dfs(mat, m, n, x, y, number, visited, primes) {
    visited[x][y] = true;
    let num = parseInt(number);
    if (num > 10 && isPrime(num)) {
        primes[num] = (primes[num] || 0) + 1;
    }

    for (const [dx, dy] of DIRECTIONS) {
        const nx = x + dx;
        const ny = y + dy;
        if (nx >= 0 && ny >= 0 && nx < m && ny < n && !visited[nx][ny]) {
            dfs(mat, m, n, nx, ny, number + String(mat[nx][ny]), JSON.parse(JSON.stringify(visited)), primes);
        }
    }
    visited[x][y] = false;
}

function mostFrequentPrime(mat) {
    const m = mat.length;
    const n = mat[0].length;
    const primes = {};
    const visited = Array.from({ length: m }, () => Array(n).fill(false));

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            dfs(mat, m, n, i, j, String(mat[i][j]), visited, primes);
        }
    }

    let maxFreq = 0;
    let result = -1;
    for (const [prime, freq] of Object.entries(primes)) {
        if (freq > maxFreq || (freq === maxFreq && Number(prime) > result)) {
            maxFreq = freq;
            result = Number(prime);
        }
    }

    return result;
}

const mat = [[9, 7, 8], [4, 6, 5], [2, 8, 6]];
console.log(mostFrequentPrime(mat));  // Output: 97

function mostFrequentPrime(mat: number[][]): number {
    const m: number = mat.length;
    const n: number = mat[0].length;
    const cnt: Map<number, number> = new Map();
    const isPrime = (x: number): boolean => {
        for (let i = 2; i <= x / i; ++i) {
            if (x % i === 0) {
                return false;
            }
        }
        return true;
    };

    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            for (let a = -1; a <= 1; ++a) {
                for (let b = -1; b <= 1; ++b) {
                    if (a === 0 && b === 0) {
                        continue;
                    }
                    let [x, y, v] = [i + a, j + b, mat[i][j]];
                    while (x >= 0 && x < m && y >= 0 && y < n) {
                        v = v * 10 + mat[x][y];
                        if (isPrime(v)) {
                            cnt.set(v, (cnt.get(v) || 0) + 1);
                        }
                        x += a;
                        y += b;
                    }
                }
            }
        }
    }

    let [ans, mx] = [-1, 0];
    cnt.forEach((x, v) => {
        if (mx < x || (mx === x && ans < v)) {
            mx = x;
            ans = v;
        }
    });
    return ans;
}

func mostFrequentPrime(mat [][]int) int {
	m, n := len(mat), len(mat[0])
	cnt := make(map[int]int)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			for a := -1; a <= 1; a++ {
				for b := -1; b <= 1; b++ {
					if a == 0 && b == 0 {
						continue
					}
					x, y, v := i+a, j+b, mat[i][j]
					for x >= 0 && x < m && y >= 0 && y < n {
						v = v*10 + mat[x][y]
						if isPrime(v) {
							cnt[v]++
						}
						x += a
						y += b
					}
				}
			}
		}
	}
	ans, mx := -1, 0
	for v, x := range cnt {
		if mx < x || (mx == x && ans < v) {
			mx = x
			ans = v
		}
	}
	return ans
}

func isPrime(n int) bool {
	for i := 2; i <= n/i; i++ {
		if n%i == 0 {
			return false
		}
	}
	return true
}