Solving A Graph Problem: Part One

Introduction: Problem Solving

Problem solving, particularly algorithmic problem-solving is a key part of software development, so from time to time, I like to attempt solving a number of these problems in a bid to ensure that I stay sharp and become better at it. Most recently, I solved a graph problem, and it was particularly interesting because of the approach I took. First addressing it as a computational problem, to understanding the components of the problem, which in turn forced me to think about the solutions to each of these subproblems, before finally figuring out how the solutions to these subproblems can be put together in order to have the final solution.

I decided to write this because while I have read a number of articles that contain guidelines on how to solve computational problems, very often, the examples used are quite simple and leave significant parts of the process abstract. That makes it difficult for other people who are trying to improve their problem solving skills to learn. Other times, while the solutions to complex problems are available, not enough effort is put into explaining the systematic thought process that went into solving the problem, instead you just get an explanation of how the solution works but not how it came about.

Throughout this article, I would attempt to ensure that I do not just tell you how the solution works but I intend to walk you through the process I used to come up with the solution.

It is important to note that while this article can be read and understood by anyone who is interested in computational problem solving, the primary target audience are those people with a programming background, that being said, Python is the programming language of choice for solving this problem.

This is a long read, and because of that, I have decided that it is best if it is explained in two parts. At the bottom of this post is the link to the next post.

In this post, I will focus on explaining the problem and walking you through my thought process while solving part of the problem, before I go on to solve the rest of the problem in my next post.

The Problem

We have a pipe system represented by a 2D rectangular grid of cells. There are three different types of objects located in cells in the grid, with each cell having either 0 objects or 1 object:

Source: There is 1 source in the system. It is represented by the asterisk character '*'.

Sinks: There are an arbitrary number of sinks in the system. They are each represented by a different uppercase letter ('A', 'B', 'C', etc.).

Pipes: There are 10 different shapes of pipes, represented by the following characters: '═', '║', '╔', '╗', '╚', '╝', '╠', '╣', '╦', '╩'.

Note that each pipe has openings on 2 or 3 sides of its cell. Two adjacent cells are connected if both have a pipe opening at their shared edge. For example, the two cells '╩ ╦' are connected to each other through their shared edge. The two cells '╩ ╔' are not connected to each other through their shared edge, but they could possibly still be connected via a path through other cells around them.

Treat the source and sinks as having pipe openings at all of their edges. For example, the two cells 'A ╦' are connected through their shared edge, but the two cells 'B ╔' are not directly connected through their shared edge.

A sink may be connected to the source through another sink. For example, in the simple pipe system '* ╦ X Y ═ Z', all three sinks are connected to the source.

Your objective is to write a function that determines which sinks are connected to the source in a given pipe system. As an example, consider the following illustration of a pipe system:

* ╣ ╔ ═ A
╠ ═ ╝
C ╚ ═ B

In this system, the source is connected to sinks A and C, but it is not connected to sink B.

A system is specified by an input text file that contains rows of data indicating the location of the objects in the grid. Each row has three pieces of information, separated by a space character:

1. The character representing the object (asterisk, uppercase letter, or pipe).

2. The x-coordinate of the object in the grid. This has a minimum value of 0.

3. The y-coordinate of the object in the grid. This has a minimum value of 0.

Below are the contents of an input file that specifies the example pipe system illustrated above. The order of the rows within the file is arbitrary, so the rows could be given in any order. The coordinates (0, 0) will always correspond to the same corner of the grid as in this example, so make sure to understand in which directions the x- and y-coordinates increase.

* 0 2
C 1 0
╠ 1 1
╣ 1 2
═ 2 1
╚ 3 0
╝ 3 1
╔ 3 2
═ 4 0
═ 4 2
B 5 0
A 5 2

Understanding the problem

We are presented with a system that consists of cells and objects. Objects are contained in cells, although not all cells contain an object. The objects can be one of three types:

1. A sink
2. A source
3. A pipe

In each system, there is only one source, and an arbitrary number of sinks and pipes.

Given the rules of connection of cells, what we are asked to do is to determine what sinks are connected to the source, directly or indirectly.

The problem here is that while we can draw out this system and visualise it in order to determine what sinks are connected to the source, the computer cannot do that in the same way. In fact there is an underlying issue, it is that we, as humans, aren't aware of the process we employ in order to determine this, so that sounds like a good place to start, doesn't it?

How do we know what sinks are connected to the source?

Following my analysis of how I was able to determine this, I figured out that I was able to do this in one of two ways:

1. Identify each sink and trace their connection to the source one after the other until I have been able to determine all the sinks that are connected to the source.

2. Trace all the routes going out from the source one after the other and determine which ones are connected to a sink.

For both options, I need to be able to determine when one cell is connected to another. Let that be subproblem 1.

Once I have this, I can use it to check all the cells around a cell and determine if they are connected to the cell in question or not. This is also a subproblem that is dependent on the solution to our first subproblem, let's call it subproblem 2.

At this point, we will have to decide if we are going with option 1 or 2 in order to solve this problem.

Looking at it, I believe it would be best to go with the first option, since going with the second option would require us to traverse routes that don't have a sink along them, ultimately wasting time and computational resources.

In order to successfully implement option 1, we have to first be able to identify all the sinks in the system. Let us call this subproblem 3.

The Solution

So now we have our subproblems. In order to arrive at our final solution, we need to solve each of these subproblems separately, before assembling them.

Subproblem 1

Following the rules outlined in the problem description, we know that one cell being connected to another is dependent on two factors:

1. The shape or type of the object in the cell.
2. The position of the cell (up, down, left or right).

Using these two factors and the rules given, we can create a dictionary that would represent the rules given. The reason for choosing a dictionary is that it allows us to retrieve the rules for a particular object by using the object as a key.

The dictionary can be found below.

rules = {
    "╩": {
        "up": ["╦", "║", "╠", "╔", "╗", "╣"],
        "down": [],
        "left": ["╦", "╠", "╔", "╩", "╚", "═"],
        "right": ["╩", "╣", "╗", "╦", "╝", "═"],
    },
    "═": {
        "up": [],
        "down": [],
        "left": ["╦", "╠", "╔", "╩", "╚", "═"],
        "right": ["╩", "╣", "╗", "╦", "╝", "═"],
    },
    "║": {
        "up": ["╦", "║", "╠", "╔", "╗", "╣"],
        "down": ["╚", "╝", "╣", "╠", "║", "╩"],
        "left": [],
        "right": [],
    },
    "╔": {
        "right": ["╩", "╣", "╗", "╦", "╝", "═"],
        "down": ["╚", "╝", "╣", "╠", "║", "╩"],
        "up": [],
        "left": [],
    },
    "╗": {
        "left": ["╦", "╠", "╔", "╩", "╚", "═"],
        "down": ["╚", "╝", "╣", "╠", "║", "╩"],
        "up": [],
        "right": [],
    },
    "╚": {
        "up": ["╦", "║", "╠", "╔", "╗", "╣"],
        "right": ["╩", "╣", "╗", "╦", "╝", "═"],
        "down": [],
        "left": [],
    },
    "╝": {
        "left": ["╦", "╠", "╔", "╩", "╚", "═"],
        "up": ["╦", "║", "╠", "╔", "╗", "╣"],
        "down": [],
        "right": [],
    },
    "╠": {
        "right": ["╩", "╣", "╗", "╦", "╝", "═"],
        "up": ["╦", "║", "╠", "╔", "╗", "╣"],
        "down": ["╚", "╝", "╣", "╠", "║", "╩"],
        "left": [],
    },
    "╣": {
        "left": ["╦", "╠", "╔", "╩", "╚", "═"],
        "up": ["╦", "║", "╠", "╔", "╗", "╣"],
        "down": ["╚", "╝", "╣", "╠", "║", "╩"],
        "right": [],
    },
    "╦": {
        "right": ["╩", "╣", "╗", "╦", "╝", "═"],
        "left": ["╦", "╠", "╔", "╩", "╚", "═"],
        "down": ["╚", "╝", "╣", "╠", "║", "╩"],
        "up": [],
    },
    "╩": {
        "left": ["╦", "╠", "╔", "╩", "╚", "═"],
        "right": ["╩", "╣", "╗", "╦", "╝", "═"],
        "up": ["╦", "║", "╠", "╔", "╗", "╣"],
        "down": [],
    },
}

Next we need to define the function that will use these rules to determine if two cells are connected.

def is_connected_fn(a, b, b_position):
    if a.isupper() and b.isupper():
        return True

    if a.isupper() and b == "*":
        return True

    if a == "*" and b.isupper():
        return True

    if a.isupper():
        rules[a] = {
            "left": ["╦", "╠", "╔", "╩", "╚", "═"],
            "right": ["╩", "╣", "╗", "╦", "╝", "═"],
            "up": ["╦", "║", "╠", "╔", "╗", "╣"],
            "down": ["╚", "╝", "╣", "╠", "║", "╩"],
        }

    rules[a][b_position].extend(alphabet)

    return b in rules[a][b_position]

alphabet is an array that holds all the upper case letters of the alphabet and "*".

alphabet = [
    "A",
    "B",
    "C",
    "D",
    "E",
    "F",
    "G",
    "H",
    "I",
    "J",
    "K",
    "L",
    "M",
    "N",
    "O",
    "P",
    "Q",
    "R",
    "S",
    "T",
    "U",
    "V",
    "W",
    "X",
    "Y",
    "Z",
    "*",
]

With these, we have sufficiently solved our first subproblem.

Before we move on to our next subproblem, I would like to provide you with the function used to load the data from the file. The data in the file is in the format specified in the problem description.

I would not be providing much of an explanation as this is not as relevant to the thought process:

def load_data(file_path):
    with open(file_path, "r") as file:
        data = []
        for line in file:
            line_arr = line.strip().split(" ")
            data.append([line_arr[0], int(line_arr[1]), int(line_arr[2])])

        return data

The function above returns the data as an array of arrays, where each array contains an object and its coordinates like so:

[object, x_index, y_index]

Let's call them elements.

Conclusion

So far, I have explained the problem, broken it down into subproblems and solved the first subproblem. I'll stop here for now and continue in my next post.

I hope that this has been an enjoyable read for you so far. If you have any questions, thoughts or ideas, please feel free to share them in the comment section, I look forward to reading them.

Solving A Graph Problem: Part Two.