In this exercise, you will write code to solve a problem. Your code must be in either Python (preferred) or JavaScript—solutions in other languages will not be accepted! You can write your code using any IDE you want.
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:
- The character representing the object (asterisk, uppercase letter, or pipe).
- The x-coordinate of the object in the grid. This has a minimum value of 0. 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
- Your function must be written in Python (preferred) or JavaScript.
- The function should take in a single argument, which is a string containing the file path for the input text file.
- The function should return (not print) your answer as a string of uppercase letters, in alphabetical order with no other characters. For example, if the code determines that sinks 'P', 'B', 'J', and 'T' are the only sinks connected to the source, your code should return the string 'BJPT'.
The relevant grid spaces are stored in a dictionary, keyed by its coordinate with a value of what is in the cell (either the power source, the sink, or the pipe shape). After the data object is built and the source is added to the queue and also considered "visited", we begin a breadth-first search, which essentially traverses the graph one cell "outward" at a time in each possible direction. The directions are stored in a constant, containing the delta x and y, and also the possible pipe shapes for both going INTO another pipe in the respective direction, and the pipes that would accept flow FROM another direction. For example, when going UP (dx = 0, dy = 1), all fromPipes must have an opening in the top, and all of the toPipes must have an opening below in order to be considered connected. As the queue is traversed starting with the power source and moving "outward", helpful variables are set including the fromCell, the cell to which we are testing connection, and the direction in which we are testing for an iteration. If the "new" cell has already been visited (tested by coming from another direction), we continue with the next iteration of cells to be traversed. If not yet visited, we test if the cell we have "created" in some direction exists in the grid at the assumed coordinates. If not yet visited, and exists in the grid, we proceed with the iteration and see if the "from" cell connects to the "to" cell, which we decide is possible if there is an opening on the "to" cell's pipe in the direction we are going, or it is a sink. If it does connect, we check if it is a sink, and capture a connection, if it is another pipe, the new cell is added to the queue, and also noted as visited so it is not traversed outward from its coordinate a second time. Once the queue has been exhausted of all connections stemming from the power source, the loop ends, and any "captured" sinks calculated to be connected through pipes to the power source is sorted alphanumerically, and returned.