Pinky's Pipes Pickle: Solution

Have you fixed the pipes on our interactive puzzles yet? Remember you had to adjust the amount flowing along each pipe so that the maximum possible flows out of the outlet at the end. If you were struggling, here is a way to do it that dates back to the 1950s by two mathematicians called Lester Ford and Delbert Fulkerson. It's now known as the Ford-Fulkerson algorithm and is one of the most widely used ways of solving this maxflow problem (inventing a useful algorithm is a great way of having your name immortalized!)

So how does it go? Well here's a slightly simplified version. First make sure all the pipes are set to zero flow. Then keep doing the following until you can't anymore...

• Find a connected pathway of pipes from inlet to outlet that still has some capacity all the way, (the path can include pipes flowing the wrong way as long as they have some flow in them to remove).
• Note which pipe on the path has the smallest free capacity
• Increase the flow by that amount on all pipes on the path flowing in the right direction
• Decrease the flow by that amount on all pipes on the path flowing in the wrong direction
• Repeat these steps until you cannot find a path with some capacity left.

Notice that a path can include pipes going in the wrong direction. That's ok. Modifying a path like that is really just redirecting some of the flow a new way partially undoing an earlier step.

An Example

Here is an example, taking the first two steps of the algorithm.

Step 1

In the first step the player finds a path along the middle (capacity 7), up to the top (capacity 2), then to the outlet (capacity 6). That path can take at most a flow of 2, because of the middle pipe, so that amount of flow (2) is added along the path.

Step 2

In the next step, the person chooses a path with negative flow going up to the top (capacity 5), down to the middle (a used up capacity 2 in the other direction that can be undone) and across (capacity 5). That path can take at most a flow of 2 again because the middle step has only a flow of 2 to remove. 2 is removed from the middle and added to the other steps, to give the situation shown. Notice there is now more flow from in to out than before and it is a legal state for the flow to be in.