Programming Problems #2 : Water Connection Problem

Today we will discuss the “Water Connection Problem”. This is an interesting problem and has been rated as “hard” across quite a few coding contest platforms. We will use a graph search algorithm to find the number of tanks and pipes to connect a set of buildings. We will go over the problem and implement the solution using Python.

Problem Statement

Each building in our university has at most one pipe going into it and at most one pipe going out of it. Tanks and taps are to be installed in a manner such that every building with one outgoing pipe, but no incoming pipe gets a tank installed on its roof and each building with only an incoming pipe and no outgoing pipe gets a tap. Given 2 integers p and q denoting the number of buildings and the number of pipes. The connections of pipe among the houses contain three input values: a, b, d denoting the pipe of diameter d from building a to building b, develop an efficient solution for the network. The output will contain the number of pairs of tanks and taps t installed in first line and the next t lines contain three integers: building number of tanks, building number of tap and the minimum diameter of pipe between them.”

Example :
n=9
p=4
Input
7, 4, 98
5, 9, 72
4, 6, 10
2, 8, 22
Output
3
2 8 22
5 9 72
7 6 10

Solution

From the problem statement, we can make the following observations :

  1. A building with an outgoing pipe but no incoming pipe gets a tank installed.
  2. A building with an incoming pipe but no outgoing pipe gets a tap.

From the sample input, we can draw a directed graph of the connections of the different components/building to determine the number of tanks and taps to be fitted.

Graph of connected buildings

The above figure represents the connected buildings provided in the input as a graph. Let’s find out where to place tanks and taps in this configuration.

  1. In 5->9, 5 only has an outgoing pipe, hence it will have a tank installed. 9 only has an incoming pipe so it will have a tap installed. Since there are no other buildings connected, the minimum diameter will be 72.
  2. Similarly in 2->8, 2 has an outgoing pipe hence a tank and 8 has an incoming pipe, hence a tap. Here the minimum diameter is 22.
  3. In the connected components 7->4->6, 7 has an outgoing pipe hence it will have a tank installed. 4 has an incoming pipe and an outgoing pipe, so does not match any of the conditions given to us in the problem, so we neither place a tank nor tap in building 4. 6 has an incoming pipe only, so it has a tap. The minimum diameter of this configuration is 10<98, 10.

From 1,2&3 we can infer that the first and last buildings are the tank-tap pairs. Hence, when we have multiple connected components, we have to traverse the nodes in order of depth, using depth first search (DFS) to find the very last node. The code for this solution is provided below. In case you are new to depth first search you can read about here.

Water Connection Problem Solution

References

  1. https://jovian.ai/aakashns/python-graph-algorithms
  2. https://www.youtube.com/watch?v=PxYviqEuWlA
  3. https://www.geeksforgeeks.org/water-connection-problem/

--

--

--

Grad Student (MTech in AI). Engineer. Musician. Yoga Instructor. Philomath. I write about anything that makes me curious. https://vijpandaturtle.github.io/

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

ARK Mobile Wallet v1.8.0 Released — Enhanced Developer Support

Web development trends business owners should follow

Instrumenting Lambda with Traces: A Complete Example in Python — Honeycomb

Three bees on honeycomb.

Creating a triple shot for my Player

Go / Golang Basic Data Types

Compendium Framework — Part 2 — Preparing the VCS (Git & GitHub)

ARK Desktop Wallet v2.4— Introducing Plugins, One Of The First Plugin Enabled Crypto Wallets

New Updates in Zilliqa!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Vijayasri Iyer

Vijayasri Iyer

Grad Student (MTech in AI). Engineer. Musician. Yoga Instructor. Philomath. I write about anything that makes me curious. https://vijpandaturtle.github.io/

More from Medium

Programming Problems #3 : Muddy City Problem

Union Find / Algorithm

Recursion forever

Recursion and Memoization