### About

Date: 2018-08-05### Contents

# Three And Five Liters¶

There is this classic riddle where you are given two containers, one has a capacity of three liters and the other five liters. Your task is to extract exactly four liters. There are no further markings on the containers.

To measure two liters, it is quite straightforward: Fill the five liter container, transfer to the three liter container until the latter is full. Then there will be two liters remaining in the five liter container. To obtain one or four liters takes more steps. I wondered what results are possible with this setup. Can you achieve any amount of liquid in both of the containers?

## Matrices and vectors¶

This problem can be expressed with simple matrices and vectors. First we have
to choose a basis for this problem. The following is just the outer product of
the possible fill levels for two containers, now labeled with *C3* and *C5*:

ID | C3 | C5 |
---|---|---|

1 | 0 | 0 |

2 | 1 | 0 |

3 | 2 | 0 |

4 | 3 | 0 |

5 | 0 | 1 |

6 | 1 | 1 |

7 | 2 | 1 |

8 | 3 | 1 |

9 | 0 | 2 |

10 | 1 | 2 |

11 | 2 | 2 |

12 | 3 | 2 |

13 | 0 | 3 |

14 | 1 | 3 |

15 | 2 | 3 |

16 | 3 | 3 |

17 | 0 | 4 |

18 | 1 | 4 |

19 | 2 | 4 |

20 | 3 | 4 |

21 | 0 | 5 |

22 | 1 | 5 |

23 | 2 | 5 |

24 | 3 | 5 |

There are 24 basis states as the first container has four states (0, 1, 2, and 3 liters) and the second one has six states (0, 1, 2, 3, 4, and 5 liters). There are the following operations:

- F3
- Fill C3
- F5
- Fill C5
- D3
- Dump the contents of C3
- D5
- Dump the contents of C5
- T35
- Transfer liquid from C3 into C5 until C5 is full or C3 is empty
- T53
- Transfer from C5 to C3

We already know that there are at most 24 different states that our system of two containers can be in. We start with both containers empty. Now we can apply each operation to this state and see which state we then obtain. We repeat that with each operator on each intermediate result until we do not get a state that was not encountered before. Due to the finite nature of the elements we are sure that eventually this algorithm will terminate.

In the little program `three-and-five-liters.R`

all possible states
are constructed. Here are the possible resulting states of the systems as well
as the operations needed to obtain from the empty state:

C3 | C5 | Sum | Operations |
---|---|---|---|

0 | 0 | 0 | |

0 | 1 | 1 | F3 T35 F3 T35 D5 T35 |

0 | 2 | 2 | F5 T53 D3 |

0 | 3 | 3 | F3 T35 |

0 | 4 | 4 | F5 T53 D3 T53 F5 T53 D3 |

0 | 5 | 5 | F5 |

1 | 0 | 1 | F3 T35 F3 T35 D5 |

1 | 5 | 6 | F3 T35 F3 T35 |

2 | 0 | 2 | F5 T53 D3 T53 |

2 | 5 | 7 | F5 T53 D3 T53 F5 |

3 | 0 | 3 | F3 |

3 | 1 | 4 | F5 T53 D3 T53 F5 T53 D3 T53 |

3 | 2 | 5 | F5 T53 |

3 | 3 | 6 | F3 T35 F3 |

3 | 4 | 7 | F5 T53 D3 T53 F5 T53 |

3 | 5 | 8 | F5 F3 |

One can see that we can create any sum between 0 and 8. Some end states might be obtainable via multiple ways.

## Graph viewpoint¶

An alternative view onto this problem is via graph theory. The operators expressed as matrices can be interpreted as adjacency relations. We want to know which vertices (states of the system) can be reached from the start vertex.

In order to find the connected part of the graph we express an operator like T53 as this matrix:

```
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
```

In order to get the whole connections between the vertices, we just sum all the matrix representations of the operators. Values greater than 1 are just set to 1 as we are interested in the connectivity only. The result is the following adjacency matrix:

```
1 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0
0 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0
0 0 1 0 0 1 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0
1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 0 1 0 0 0 1
0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 0
0 0 0 1 0 0 1 0 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 0
1 0 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1
0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 1 0 0 1 0 0
0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1
```

Using a proper graph library like igraph, one can
further investigate this graph. We convert the adjacency matrix into a graph
with `g <- graph_from_adjacency_matrix(adj_matrix)`

. Then using
`all_simple_paths(g, 1, 4)`

we can obtain all paths that start at vertex 1
(the all empty state) and go to state 4, which is [3, 0]. By looping over the
final vertex we can find out if there is at least one path to the desired
state. The list of reachable states turns out to be exactly the same as before.

Looking at the shortest possible path for each of the states, I found that in order to reach state 7, the [3, 1] one, only seven operations are needed, not eight. My naive algorithm has given me this:

```
F5 T53 D3 T53 F5 T53 D3 T53
```

The graph library however has found this shorter path:

```
F3 T35 F3 T35 D5 T35 F3
```

## Conclusion¶

This simple riddle has a rather intricate structure to it, using vectors and matrices we were able to find all possible results. Using graph theory an even more elegant formulation is found, which allows retrieval of the shortest paths between any two states of the system.