Dynamic Programming – How many ways to connect the pipes?

This is an interesting problem that can be solved using Dynamic Programming (DP). The question is to count how many ways to connect the pipes like the following (Pipes flow 1 direction and cannot overlap each other). Each connector takes two ports i.e. for only 1 pipe, there is zero ways to connect the pipe.

sub-problem-connecting-pipes

As shown above, we have a 4-numbered pipes in the order (from top to bottom, or left to right which doesn’t matter). The requirement is to merge these pipes into 1 flow, and in 2D, these connections should not overlap meaning that we cannot connect pipe 1 to pipe 3 directly because the connection will intersect the pipe 2. We can easily observe that the first steps are to connect the adjacent pipes.

We can easily come up that if we have 0 or 1 pipes, the answer is 0, if we have 2 pipes, the answer is 1. And if we have 3 pipes, there are 2 ways. So below are the case for four pipes.

sub-problem-pipe

Four pipes can have 5 possibilities, as shown above, in which, Case A and Case D are symmetric. Case C and E are symmetric.

If we use f(n) to denote the answer for n pipes, as said above, we have these known conditions:

1
2
3
4

f(0) = 0;
f(1) = 0;
f(2) = 1;
f(3) = 2;

f(0) = 0;
f(1) = 0;
f(2) = 1;
f(3) = 2;

The lighter blue boxes are the case for f(n-1) while the darker blue box is the case for f(n-2). It is also seen that the f(n-1) has their symmetrical solutions that is why we need to multiple by two.

So up to this point, the DP recurrence is obvious:

for any n larger or equal to 3.

You can do it using recursion + memorization but a iterative implementation seems trivial.

1
2
3
4
5
6
7
8
9
10
11
12

function CountPipes(int n) {
  int a = 0;
  int b = 1;
  if (n <= 1) return 0;
  if (n == 2) return 1;
  for (int i = 3; i <= n; i ++) {
     int c = a + 2 * b;
     a = b;
     b = c;
  }
  return b;
}

function CountPipes(int n) {
  int a = 0;
  int b = 1;
  if (n <= 1) return 0;
  if (n == 2) return 1;
  for (int i = 3; i <= n; i ++) {
     int c = a + 2 * b;
     a = b;
     b = c;
  }
  return b;
}

And the first few numbers are:

1
2
3

for (int i = 0; i <= 6; i ++) {
    cout << "f(" << i << ") = " << CountPipes(i) << endl;
}

for (int i = 0; i <= 6; i ++) {
    cout << "f(" << i << ") = " << CountPipes(i) << endl;
}

connecting-pipes-solution

Correct Solution

According to the comments below, it seems that the above solution is not right, with some missing possibilities. For example, for 5 pipes, the correct answer is 14 but the above prints 12.

For 5 pipes:
(1, (2, (3, (4, 5))))
(1, (2, ((3, 4), 5)))
(1, ((2, 3), (4, 5)))
(1, ((2, (3, 4)), 5))
(1, (((2, 3), 4), 5))
((1, 2), (3, (4, 5)))
((1, 2), ((3, 4), 5))
((1, (2, 3)), (4, 5))
(((1, 2), 3), (4, 5))
((1, (2, (3, 4))), 5)
((1, ((2, 3), 4)), 5)
(((1, 2), (3, 4)), 5)
(((1, (2, 3)), 4), 5)
((((1, 2), 3), 4), 5)

So we can see that the pipe connecting can be visualized as the ways of putting brackets. If we use f(n) to denote the number of ways of putting brackets for n pipes, we can recursively divide the n pipes into two subsets, which are k and n – k respectively for k from 1 to n-1. The answer would be to sum up all f(k)*f(n-k).

The first few numbers are still pre-computed i.e. f(0) = 0, f(2) = 1. However, in order for this to work, f(1) has to be set to 1 for convenience.

–EOF (The Ultimate Computing & Technology Blog) —