check if adjacent element in list of lists have common divisor

Question

I have a an int list of lists:

92 78 39 38 95 19 57 72
90 61 26 51 78 41 82 27
99  9  X 17 87 40 42 12
20 62 31 33 54  5 74 75
34 35 77 11 25 10 37 81
85 91 45 18 43  Y 15 36
93 13 65 63 21 49 60 58
84 69 66 70 55 30 24 29

Which is represented by the list of lists

[[92, 78, 39, 38, 95, 19, 57, 72], [90, 61, 26, 51, 78, 41, 82, 27]...]

We start either from X or Y (which can be represented by 0 or 1) and the goal is to find a path between them, this path can only switch from one number to another if both numbers have at least one common divisor other than 1.

here is my implementation so far but it seems that it does not compare only neighbors but other elements as well, thanks in advance

    def commonDivisor(num1, num2) -> bool:
        have_common = False
        if num1 == 1:
            have_common = True
        for i in range(2, min(num1, num2) + 1):
            if num1 % i == num2 % i == 0:
                have_common = True
        return have_common

    def checkList(lst, elem) -> bool:
        check = False
        for x in range(len(lst)):
            if elem in lst:
                check = True
        return check

    lst = listOfLists()
    path_list = []

    tmp = lst[2][2]
    for i in range(2, len(lst) - 1):
        for j in range(2, len(lst) - 1):
            if commonDivisor(tmp, lst[i + 1][j]) and checkList(path_list, lst[i + 1][j]) == False:  # check bottom
                tmp = lst[i + 1][j]
                path_list.append(tmp)
            if commonDivisor(tmp, lst[i - 1][j]) and checkList(path_list, lst[i - 1][j]) == False:  # check above
                tmp = lst[i - 1][j]
                path_list.append(tmp)
            if commonDivisor(tmp, lst[i][j - 1]) and checkList(path_list, lst[i][j - 1]) == False:  # check left
                tmp = lst[i][j - 1]
                path_list.append(tmp)
            if commonDivisor(tmp, lst[i][j + 1]) and checkList(path_list, lst[i][j + 1]) == False:  # check right
                tmp = lst[i][j + 1]
                path_list.append(tmp)

    print(path_list)

Answer 1

So here is how I would go about this question by leveraging components from other answers on SO. Hopefully this will give you some insight in how to tackle questions like this.

Start by defining a main function that will set up the work to be done.

def main():
    data = [
        [92, 78, 39, 38, 95, 19, 57, 72],
        [90, 61, 26, 51, 78, 41, 82, 27],
        [99, 9, 'X', 17, 87, 40, 42, 12],
        [20, 62, 31, 33, 54, 5, 74, 75],
        [34, 35, 77, 11, 25, 10, 37, 81],
        [85, 91, 45, 18, 43, 'Y', 15, 36],
        [93, 13, 65, 63, 21, 49, 60, 58],
        [84, 69, 66, 70, 55, 30, 24, 29],
    ]
    print(find_path(data))

We know that we will want to search around a cell when doing our search, so lets create some helpers for that!

def add(x, y):
    return x[0] + y[0], x[1] + y[1]


def in_bounds(loc, bounds):
    return 0 <= loc[0] < bounds[0] and 0 <= loc[1] < bounds[1]


def around(loc, bounds):
    possible_locations = [
        add(loc, (-1, 0)),
        add(loc, (1, 0)),
        add(loc, (0, -1)),
        add(loc, (0, 1)),
    ]
    return [loc for loc in possible_locations if in_bounds(loc, bounds)]

We also know that we want to find all of the common denominators between cells. Instead of calculating them on the fly, we can instead pre-calculate all of the prime factors in each item and save that as a matrix. For calculating this we will need a helper method, so I adapted another post with the added caveat to not check the X and Y non int cells.

def prime_factors(n):
    if not isinstance(n, int):
        return set()
    i = 2
    factors = set()
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.add(i)
    if n > 1:
        factors.add(n)
    return factors

For the setup of our find_path method we know that we will want to start around X and end around Y. To do that we will need to locate X and Y first. We also will need to prepare the prime factors lookup.

def find_path(data):
    bounds = len(data), len(data[0])

    x_loc = ()
    y_loc = ()
    for i, row in enumerate(data):
        if 'X' in row:
            x_loc = i, row.index('X')
        if 'Y' in row:
            y_loc = i, row.index('Y')

    start_locations = around(x_loc, bounds)
    end_locations = around(y_loc, bounds)

    data_factors = [
        [prime_factors(col) for col in row]
        for row in data
    ]

Now the fun part! We can use a BFS search to find a valid path in the matrix starting at one of the start_locations and ending at the end_locations. Adapting another answer we can modify it to use our constraints of neighbors needing to be have common factors.

def find_path(data):
    ...
    seen = set(start_locations)
    queue = deque([loc] for loc in start_locations)

    while queue:
        path = queue.popleft()
        curr_loc = path[-1]
        if curr_loc in end_locations:
            return [x_loc, *path, y_loc]
        for next_loc in around(curr_loc, bounds):
            if next_loc not in seen:
                curr_factors = data_factors[curr_loc[0]][curr_loc[1]]
                next_factors = data_factors[next_loc[0]][next_loc[1]]
                if curr_factors.intersection(next_factors):
                    queue.append(path + [next_loc])
                    seen.add(next_loc)

    return None

And thats it! Full answer is:

[(2, 2), (2, 3), (1, 3), (1, 4), 
(2, 4), (3, 4), (3, 3), (4, 3), 
(4, 2), (4, 1), (5, 1), (6, 1), 
(6, 2), (5, 2), (5, 3), (6, 3), 
(6, 4), (6, 5), (5, 5)]

Full code for reference!

from collections import deque


def prime_factors(n):
    if not isinstance(n, int):
        return set()
    i = 2
    factors = set()
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.add(i)
    if n > 1:
        factors.add(n)
    return factors


def add(x, y):
    return x[0] + y[0], x[1] + y[1]


def in_bounds(loc, bounds):
    return 0 <= loc[0] < bounds[0] and 0 <= loc[1] < bounds[1]


def around(loc, bounds):
    possible_locations = [
        add(loc, (-1, 0)),
        add(loc, (1, 0)),
        add(loc, (0, -1)),
        add(loc, (0, 1)),
    ]
    return [loc for loc in possible_locations if in_bounds(loc, bounds)]


def find_path(data):
    bounds = len(data), len(data[0])

    x_loc = ()
    y_loc = ()
    for i, row in enumerate(data):
        if 'X' in row:
            x_loc = i, row.index('X')
        if 'Y' in row:
            y_loc = i, row.index('Y')

    start_locations = around(x_loc, bounds)
    end_locations = around(y_loc, bounds)

    data_factors = [
        [prime_factors(col) for col in row]
        for row in data
    ]

    seen = set(start_locations)
    queue = deque([loc] for loc in start_locations)

    while queue:
        path = queue.popleft()
        curr_loc = path[-1]
        if curr_loc in end_locations:
            return [x_loc, *path, y_loc]
        for next_loc in around(curr_loc, bounds):
            if next_loc not in seen:
                curr_factors = data_factors[curr_loc[0]][curr_loc[1]]
                next_factors = data_factors[next_loc[0]][next_loc[1]]
                if curr_factors.intersection(next_factors):
                    queue.append(path + [next_loc])
                    seen.add(next_loc)

    return None


def main():
    data = [
        [92, 78, 39, 38, 95, 19, 57, 72],
        [90, 61, 26, 51, 78, 41, 82, 27],
        [99, 9, 'X', 17, 87, 40, 42, 12],
        [20, 62, 31, 33, 54, 5, 74, 75],
        [34, 35, 77, 11, 25, 10, 37, 81],
        [85, 91, 45, 18, 43, 'Y', 15, 36],
        [93, 13, 65, 63, 21, 49, 60, 58],
        [84, 69, 66, 70, 55, 30, 24, 29],
    ]
    print(find_path(data))


if __name__ == '__main__':
    main()