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)
CodePudding user response：
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()