In my previous post, I introduced the problem we are solving and my reason for writing about it. If you have not read the first part, I advise you take some time to go through that before you continue reading this. Here is the link so you can be all caught up: Solving A Graph Problem: Part One.
Since we solved the first subproblem in the first post, we can move on to the next one.
Subproblem 2
Traversals
In order for us to successfully check each surrounding cell at positions: up, down, left and right, we need to be able to traverse a cell in each direction. For any cell, the coordinates of the surrounding cell relative to its coordinates(x, y) are as follows:
up: x, y + 1
down: x, y - 1
left: x - 1, y
right: x + 1, y
To keep things simple, I defined a function that helps us to get an element from our array of elements by passing in the x and y coordinates as parameters.
def get_element(x, y):
for element in data:
if element[1] == x and element[2] == y:
return element
NB: data is the variable name for our array of elements and this has been defined in our code at a global scope using the load data function.
Moving on, we can now define our function to check connections around a cell.
def check_all_connections(element):
print("Checking all connections around", element)
up_cell = [element[1], element[2] + 1]
down_cell = [element[1], element[2] - 1]
left_cell = [element[1] - 1, element[2]]
right_cell = [element[1] + 1, element[2]]
for direction in ["up", "down", "left", "right"]:
# Check if it is connected to the cell on top
if direction == "up":
up = get_element(up_cell[0], up_cell[1])
if up and up_cell[0] >= 0 and up_cell[1] >= 0:
pass
# Check if it is connected to the cell on the right
if direction == "right":
right = get_element(right_cell[0], right_cell[1])
if right and right_cell[0] >= 0 and right_cell[1] >= 0:
pass
# Check if it is connected to the cell on the left
if direction == "left":
left = get_element(left_cell[0], left_cell[1])
if left and left_cell[0] >= 0 and left_cell[1] >= 0:
pass
# Check if it is connected to the cell down
if direction == "down":
down = get_element(down_cell[0], down_cell[1])
if down and down_cell[0] >= 0 and down_cell[1] >= 0:
pass
As you can see, this function is incomplete, but it allows us to check the cells surrounding a particular cell. We will modify this function as we go on, however, this is the initial version.
Additionally, you would notice the the conditional operation. This is used to ensure that the element exists and is not undefined before we go on to carry out other operations, and secondly, it ensures that the cell we are trying to access isn't out of bounds.
Connections
Remember we said that solving the subproblem 2 is dependent on the solution to subproblem 1. Since we have solved subproblem 1 we can carry on with our solution for subproblem 2.
We need to check for connections after each traversal, then act based on the result. Let us define these actions:
When there is a connection but the element in the cell is not the source, we'll want to begin to check the surrounding cells of the cell we just confirmed there is a connection with. For example, if we establish that the cell A is connected to the cell B, we move on to check for connections around cell B. That way, we can prioritise and follow the path we are sure has a connection.
When there is a connection and the element in the cell is the source, we know that the sink in question is connected to the source.
When there is no connection, we want to check the next position for a connection.
In order to properly implement the first action, we will need to use recursion.
def check_all_connections(element, previous_direction):
print("Checking all connections around", element)
up_cell = [element[1], element[2] + 1]
down_cell = [element[1], element[2] - 1]
left_cell = [element[1] - 1, element[2]]
right_cell = [element[1] + 1, element[2]]
for direction in ["up", "down", "left", "right"]:
# Check if it is connected to the cell on top
if direction == "up":
up = get_element(up_cell[0], up_cell[1])
if up and up_cell[0] >= 0 and up_cell[1] >= 0:
if previous_direction != "down":
is_connected = is_connected_fn(element[0], up[0], "up")
print("Is connected to UP cell ", f"[{up}]", ":", is_connected)
if is_connected and up[0] == "*":
return True
elif is_connected and up[0] != "*":
all_connections = check_all_connections(up, "up")
if all_connections == True:
return True
else:
continue
else:
continue
# Check if it is connected to the cell on the right
if direction == "right":
right = get_element(right_cell[0], right_cell[1])
if right and right_cell[0] >= 0 and right_cell[1] >= 0:
if previous_direction != "left":
is_connected = is_connected_fn(element[0], right[0], "right")
print(
"Is connected to RIGHT cell ", f"[{right}]", ":", is_connected
)
if is_connected and right[0] == "*":
return True
elif is_connected and right[0] != "*":
all_connections = check_all_connections(right, "right")
if all_connections == True:
return True
else:
continue
else:
continue
# Check if it is connected to the cell on the left
if direction == "left":
left = get_element(left_cell[0], left_cell[1])
if left and left_cell[0] >= 0 and left_cell[1] >= 0:
if previous_direction != "right":
is_connected = is_connected_fn(element[0], left[0], "left")
print("Is connected to LEFT cell ", f"[{left}]", ":", is_connected)
if is_connected and left[0] == "*":
return True
if is_connected and left[0] != "*":
all_connections = check_all_connections(left, "left")
if all_connections == True:
return True
else:
continue
else:
continue
# Check if it is connected to the cell down
if direction == "down":
down = get_element(down_cell[0], down_cell[1])
if down and down_cell[0] >= 0 and down_cell[1] >= 0:
if previous_direction != "up":
is_connected = is_connected_fn(element[0], down[0], "down")
print("Is connected to DOWN cell ", f"[{down}]", ":", is_connected)
if is_connected and down[0] == "*":
return True
if is_connected and down[0] != "*":
all_connections = check_all_connections(down, "down")
if all_connections == True:
return True
else:
continue
else:
continue
Notice that I have added an extra parameter to our function called previous_direction. This parameter allows us to ensure we don't perform redundant checks. For example, assuming cell B is on top of cell A. Starting from cell A, for us to get to checking for cell B's connections means that cell B is connected to cell A. While checking for cell B's connections, we do not need to check for a connection to the cell under cell B, because that is cell A and we already know that cell B is connected to cell A.
At this point, our function does what it is supposed to, by passing in each sink into this function, we can successfully determine if it is connected the source or not. However, after running this, I realised that there were far too many recursions than python could handle.
In order to solve this problem, I had to use memoization. By storing the results of checking the connections for each cell in a memoization dictionary, we can optimise our function and avoid redundant checks and instead, retrieve the results of that particular check.
def check_all_connections(element, previous_direction, memo={}):
if id(element) in memo:
return memo[id(element)]
memo[id(element)] = True
print("Checking all connections around", element)
up_cell = [element[1], element[2] + 1]
down_cell = [element[1], element[2] - 1]
left_cell = [element[1] - 1, element[2]]
right_cell = [element[1] + 1, element[2]]
for direction in ["up", "down", "left", "right"]:
# Check if it is connected to the cell on top
if direction == "up":
up = get_element(up_cell[0], up_cell[1])
if up and up_cell[0] >= 0 and up_cell[1] >= 0:
if previous_direction != "down":
is_connected = is_connected_fn(element[0], up[0], "up")
print("Is connected to UP cell ", f"[{up}]", ":", is_connected)
if is_connected and up[0] == "*":
return True
elif is_connected and up[0] != "*":
all_connections = check_all_connections(up, "up", memo)
if all_connections == True:
return True
else:
continue
else:
continue
# Check if it is connected to the cell on the right
if direction == "right":
right = get_element(right_cell[0], right_cell[1])
if right and right_cell[0] >= 0 and right_cell[1] >= 0:
if previous_direction != "left":
is_connected = is_connected_fn(element[0], right[0], "right")
print(
"Is connected to RIGHT cell ", f"[{right}]", ":", is_connected
)
if is_connected and right[0] == "*":
return True
elif is_connected and right[0] != "*":
all_connections = check_all_connections(right, "right", memo)
if all_connections == True:
return True
else:
continue
else:
continue
# Check if it is connected to the cell on the left
if direction == "left":
left = get_element(left_cell[0], left_cell[1])
if left and left_cell[0] >= 0 and left_cell[1] >= 0:
if previous_direction != "right":
is_connected = is_connected_fn(element[0], left[0], "left")
print("Is connected to LEFT cell ", f"[{left}]", ":", is_connected)
if is_connected and left[0] == "*":
return True
if is_connected and left[0] != "*":
all_connections = check_all_connections(left, "left", memo)
if all_connections == True:
return True
else:
continue
else:
continue
# Check if it is connected to the cell down
if direction == "down":
down = get_element(down_cell[0], down_cell[1])
if down and down_cell[0] >= 0 and down_cell[1] >= 0:
if previous_direction != "up":
is_connected = is_connected_fn(element[0], down[0], "down")
print("Is connected to DOWN cell ", f"[{down}]", ":", is_connected)
if is_connected and down[0] == "*":
return True
if is_connected and down[0] != "*":
all_connections = check_all_connections(down, "down", memo)
if all_connections == True:
return True
else:
continue
else:
continue
The Final Solution
In order to construct the final solution, we need to define one more function, that is, the function that would retrieve all the sinks so that we can check if each of them is connected to the source. Don't worry, it's a simple function.
def get_sinks(data):
sinks = [element for element in data if element[0].isupper()]
return sinks
We can now use these different solutions together in our main function and it looks like this:
def main(file_path):
global data
data = load_data(file_path)
sinks = get_sinks(data)
connected_sinks = [sink[0] for sink in sinks if check_all_connections(sink, "")]
sorted_connected_sinks = sorted(connected_sinks)
connected_sinks_string = "".join(sorted_connected_sinks)
print(connected_sinks_string)
return connected_sinks_string
if __name__ == "__main__":
file_path = input("Enter the path to the txt file with the system: ")
main(file_path)
Conclusion
I hope that this has been an enjoyable read for you, that I have been able to sufficiently explain my thought process while solving this problem and that this helps to make solving computational problems less abstract for you.
Here is a link to the complete solution on GitHub.
If you have any questions, thoughts or ideas, please feel free to share them in the comment section, I looking forward to reading them.
Cheers 🥂.
Top comments (0)