Introduction

This notebook demonstrates how to convert the “water jug problem” from a question on Mathematics Stack Exchange to a shortest path problem in a directed graph.

The problem is an instance of a classic math puzzle, around since at least my childhood. You start out with two (or more) empty containers of specified (integer) capacities, and an infinite supply of whatever goes into the containers. The goal is to finish with exactly a certain (integer) amount of content. Typically, the only authorized operations are filling or emptying a container, or shifting as much as is possible of the contents of one container into another (meaning the transfer continues until either the source container is empty or the destination container if full).

In the problem specified on Math SE, which is the instance I will solve here, the material is water, the “infinite” source is a lake, the containers are jugs, one with capacity seven liters and one with capacity three liters, and the goal is to end up with exactly five liters of water. I will assume that the lake contains at least seven liters of water, and that at termination we want all five liters in the larger jug (which adds at worst one pour to the solution, combining the two jugs into one).

To handle graph operations, we will use the igraph library. For querying data frames, we will use the sqldf library.

library(igraph)
library(sqldf)

Graph construction

The graph will contain 32 nodes, each of which represents a possible state of the system. The state is defined as the volume of water in each jug (0…7 liters in the larger jug, 0…3 in the smaller jug). An arc between two nodes represents one of six possible operations:

Problem dimensions

We start by specifying the problem data (the capacities of the two jugs and the target volume).

L <- 7L       # capacity of the large jug
S <- 3L       # capacity of the small jug
target <- 5L  # target volume

Nodes

We define a helper function to create labels for nodes based on their state.

# Inputs: the capacities of the large and small jugs
# Output: a label for the node
node_label <- function(large, small) paste0(large, "|", small)

So, for example, the node label “4|1” indicates the state in which the larger jug contains four liters and the smaller jug contains one liter.

Next, we create a data frame containing the \((L + 1) \times (S + 1)\) nodes, one for each state of the system. The columns will be the volume of water in the larger and smaller jugs and a label for the node. We need the label in the first column so that igraph will recognize it as such.

nodes <- data.frame(Label = "", Large = rep(0:L, each = (S + 1)), Small = rep(0:S, times = (L + 1)))
nodes$Label <- node_label(nodes$Large, nodes$Small)

Arcs

Now we create a data frame of arcs, one for each legal operation at each node. The first two columns give the labels of the source and sink nodes; the third column is the name of the operation (e.g., “FL” to fill the larger jug).

# For each node with a nonempty large jug, add an arc that empties it.
arcs <- sqldf("SELECT A.Label AS Source, B.Label AS Sink, 'EL' AS Operation FROM nodes AS A, nodes AS B WHERE A.Large > 0 AND B.Large = 0 AND A.Small = B.Small")
# For each node with a non-full large jug, add an arc that fills it.
arcs <- rbind(arcs,
              fn$sqldf("SELECT A.Label AS Source, B.Label AS Sink, 'FL' AS Operation FROM nodes AS A, nodes AS B WHERE A.Large < $L AND B.Large = $L AND A.Small = B.Small"))
# For each node with a nonempty small jug, add an arc that empties it.
arcs <- rbind(arcs,
              sqldf("SELECT A.Label AS Source, B.Label AS Sink, 'ES' AS Operation FROM nodes AS A, nodes AS B WHERE A.Small > 0 AND B.Small = 0 AND A.Large = B.Large"))
# For each node with a non-full small jug, add an arc that fills it.
arcs <- rbind(arcs,
              fn$sqldf("SELECT A.Label AS Source, B.Label AS Sink, 'FS' AS Operation FROM nodes AS A, nodes AS B WHERE A.Small < $S AND B.Small = $S AND A.Large = B.Large"))
# For each node where the large jug is not empty and the small jug is not full, add an arc that pours as much as possible from the large jug to the small jug.
arcs <- rbind(arcs,
              fn$sqldf("SELECT A.Label AS Source, B.Label AS Sink, 'PLS' AS Operation FROM nodes AS A, nodes AS B WHERE A.Large > 0 AND A.Small < $S AND B.Large = MAX(0, A.Large - ($S - A.Small)) AND B.Small = MIN($S, A.Small + A.Large)"))
# Finally, for each node where the small jug is not empty and the large jug is not full, add an arc that pours as much as possible from the small jug to the large jug.
arcs <- rbind(arcs,
              fn$sqldf("SELECT A.Label AS Source, B.Label AS Sink, 'PSL' AS Operation FROM nodes AS A, nodes AS B WHERE A.Small > 0 AND A.Large < $L AND B.Small = MAX(0, A.Small - ($L - A.Large)) AND B.Large = MIN($L, A.Small + A.Large)"))

Graph

We put this together in a digraph using igraph.

network <- graph.data.frame(arcs, directed = TRUE, vertices = nodes)

Next, we let igraph compute the shortest path from “0|0” to “|0”.

target_label <- paste0(target, "|", 0)
path <- unlist(get.shortest.paths(network, from = "0|0", to = target_label, mode = "out", output = 'epath')$epath)
cat(length(path), " operations needed:\n")
9  operations needed:
for (i in path) {
  cat(arcs[i, "Source"], "-", arcs[i, "Operation"], "-", arcs[i, "Sink"], "\n")
}
0|0 - FL - 7|0 
7|0 - PLS - 4|3 
4|3 - ES - 4|0 
4|0 - PLS - 1|3 
1|3 - ES - 1|0 
1|0 - PLS - 0|1 
0|1 - FL - 7|1 
7|1 - PLS - 5|3 
5|3 - ES - 5|0 
LS0tCnRpdGxlOiAiV2F0ZXIgSnVnIFByb2JsZW0iCm91dHB1dDogaHRtbF9ub3RlYm9vawphdXRob3I6IFBhdWwgQS4gUnViaW4gKHJ1YmluQG1zdS5lZHUpCmRhdGU6IDA0LzEyLzIwMjEKLS0tCgojIEludHJvZHVjdGlvbgoKVGhpcyBub3RlYm9vayBkZW1vbnN0cmF0ZXMgaG93IHRvIGNvbnZlcnQgdGhlICJ3YXRlciBqdWcgcHJvYmxlbSIgZnJvbSBhIFtxdWVzdGlvbl0oaHR0cHM6Ly9tYXRoLnN0YWNrZXhjaGFuZ2UuY29tL3F1ZXN0aW9ucy80MDk4NTg2L3NvbHZpbmctdGhlLXdhdGVyLWp1Zy1wcm9ibGVtLXVzaW5nLWR5bmFtaWMtcHJvZ3JhbW1pbmcvKSBvbiBNYXRoZW1hdGljcyBTdGFjayBFeGNoYW5nZSB0byBhIHNob3J0ZXN0IHBhdGggcHJvYmxlbSBpbiBhIGRpcmVjdGVkIGdyYXBoLgoKVGhlIHByb2JsZW0gaXMgYW4gaW5zdGFuY2Ugb2YgYSBjbGFzc2ljIG1hdGggcHV6emxlLCBhcm91bmQgc2luY2UgYXQgbGVhc3QgbXkgY2hpbGRob29kLiBZb3Ugc3RhcnQgb3V0IHdpdGggdHdvIChvciBtb3JlKSBlbXB0eSBjb250YWluZXJzIG9mIHNwZWNpZmllZCAoaW50ZWdlcikgY2FwYWNpdGllcywgYW5kIGFuIGluZmluaXRlIHN1cHBseSBvZiB3aGF0ZXZlciBnb2VzIGludG8gdGhlIGNvbnRhaW5lcnMuIFRoZSBnb2FsIGlzIHRvIGZpbmlzaCB3aXRoIGV4YWN0bHkgYSBjZXJ0YWluIChpbnRlZ2VyKSBhbW91bnQgb2YgY29udGVudC4gVHlwaWNhbGx5LCB0aGUgb25seSBhdXRob3JpemVkIG9wZXJhdGlvbnMgYXJlIGZpbGxpbmcgb3IgZW1wdHlpbmcgYSBjb250YWluZXIsIG9yIHNoaWZ0aW5nIGFzIG11Y2ggYXMgaXMgcG9zc2libGUgb2YgdGhlIGNvbnRlbnRzIG9mIG9uZSBjb250YWluZXIgaW50byBhbm90aGVyIChtZWFuaW5nIHRoZSB0cmFuc2ZlciBjb250aW51ZXMgdW50aWwgZWl0aGVyIHRoZSBzb3VyY2UgY29udGFpbmVyIGlzIGVtcHR5IG9yIHRoZSBkZXN0aW5hdGlvbiBjb250YWluZXIgaWYgZnVsbCkuCgpJbiB0aGUgcHJvYmxlbSBzcGVjaWZpZWQgb24gTWF0aCBTRSwgd2hpY2ggaXMgdGhlIGluc3RhbmNlIEkgd2lsbCBzb2x2ZSBoZXJlLCB0aGUgbWF0ZXJpYWwgaXMgd2F0ZXIsIHRoZSAiaW5maW5pdGUiIHNvdXJjZSBpcyBhIGxha2UsIHRoZSBjb250YWluZXJzIGFyZSBqdWdzLCBvbmUgd2l0aCBjYXBhY2l0eSBzZXZlbiBsaXRlcnMgYW5kIG9uZSB3aXRoIGNhcGFjaXR5IHRocmVlIGxpdGVycywgYW5kIHRoZSBnb2FsIGlzIHRvIGVuZCB1cCB3aXRoIGV4YWN0bHkgZml2ZSBsaXRlcnMgb2Ygd2F0ZXIuIEkgd2lsbCBhc3N1bWUgdGhhdCB0aGUgbGFrZSBjb250YWlucyBhdCBsZWFzdCBzZXZlbiBsaXRlcnMgb2Ygd2F0ZXIsIGFuZCB0aGF0IGF0IHRlcm1pbmF0aW9uIHdlIHdhbnQgYWxsIGZpdmUgbGl0ZXJzIGluIHRoZSBsYXJnZXIganVnICh3aGljaCBhZGRzIGF0IHdvcnN0IG9uZSBwb3VyIHRvIHRoZSBzb2x1dGlvbiwgY29tYmluaW5nIHRoZSB0d28ganVncyBpbnRvIG9uZSkuCgpUbyBoYW5kbGUgZ3JhcGggb3BlcmF0aW9ucywgd2Ugd2lsbCB1c2UgdGhlIGBpZ3JhcGhgIGxpYnJhcnkuIEZvciBxdWVyeWluZyBkYXRhIGZyYW1lcywgd2Ugd2lsbCB1c2UgdGhlIGBzcWxkZmAgbGlicmFyeS4KCmBgYHtyfQpsaWJyYXJ5KGlncmFwaCkKbGlicmFyeShzcWxkZikKYGBgCgojIEdyYXBoIGNvbnN0cnVjdGlvbgoKVGhlIGdyYXBoIHdpbGwgY29udGFpbiAzMiBub2RlcywgZWFjaCBvZiB3aGljaCByZXByZXNlbnRzIGEgcG9zc2libGUgc3RhdGUgb2YgdGhlIHN5c3RlbS4gVGhlIHN0YXRlIGlzIGRlZmluZWQgYXMgdGhlIHZvbHVtZSBvZiB3YXRlciBpbiBlYWNoIGp1ZyAoMC4uLjcgbGl0ZXJzIGluIHRoZSBsYXJnZXIganVnLCAwLi4uMyBpbiB0aGUgc21hbGxlciBqdWcpLiBBbiBhcmMgYmV0d2VlbiB0d28gbm9kZXMgcmVwcmVzZW50cyBvbmUgb2Ygc2l4IHBvc3NpYmxlIG9wZXJhdGlvbnM6CgotICAgZW1wdHlpbmcgdGhlIGxhcmdlciBqdWcgKGRlbm90ZWQgIkVMIik7Ci0gICBmaWxsaW5nIHRoZSBsYXJnZXIganVnIChkZW5vdGVkICJGTCIpOwotICAgZW1wdHlpbmcgdGhlIHNtYWxsZXIganVnIChkZW5vdGVkICJFUyIpOwotICAgZmlsbGluZyB0aGUgc21hbGxlciBqdWcgKGRlbm90ZWQgIkZTIik7Ci0gICBwb3VyaW5nIGFzIG11Y2ggYXMgcG9zc2libGUgZnJvbSB0aGUgbGFyZ2VyIGp1ZyB0byB0aGUgc21hbGxlciBqdWcgKGRlbm90ZWQgIlBMUyIpOyBvcgotICAgcG91cmluZyBhcyBtdWNoIGFzIHBvc3NpYmxlIGZyb20gdGhlIHNtYWxsZXIganVnIHRvIHRoZSBsYXJnZXIganVnIChkZW5vdGVkICJQU0wiKS4KCiMjIFByb2JsZW0gZGltZW5zaW9ucwoKV2Ugc3RhcnQgYnkgc3BlY2lmeWluZyB0aGUgcHJvYmxlbSBkYXRhICh0aGUgY2FwYWNpdGllcyBvZiB0aGUgdHdvIGp1Z3MgYW5kIHRoZSB0YXJnZXQgdm9sdW1lKS4KCmBgYHtyfQpMIDwtIDdMICAgICAgICMgY2FwYWNpdHkgb2YgdGhlIGxhcmdlIGp1ZwpTIDwtIDNMICAgICAgICMgY2FwYWNpdHkgb2YgdGhlIHNtYWxsIGp1Zwp0YXJnZXQgPC0gNUwgICMgdGFyZ2V0IHZvbHVtZQpgYGAKCiMjIE5vZGVzCgpXZSBkZWZpbmUgYSBoZWxwZXIgZnVuY3Rpb24gdG8gY3JlYXRlIGxhYmVscyBmb3Igbm9kZXMgYmFzZWQgb24gdGhlaXIgc3RhdGUuCgpgYGB7cn0KIyBJbnB1dHM6IHRoZSBjYXBhY2l0aWVzIG9mIHRoZSBsYXJnZSBhbmQgc21hbGwganVncwojIE91dHB1dDogYSBsYWJlbCBmb3IgdGhlIG5vZGUKbm9kZV9sYWJlbCA8LSBmdW5jdGlvbihsYXJnZSwgc21hbGwpIHBhc3RlMChsYXJnZSwgInwiLCBzbWFsbCkKYGBgCgpTbywgZm9yIGV4YW1wbGUsIHRoZSBub2RlIGxhYmVsICI0fDEiIGluZGljYXRlcyB0aGUgc3RhdGUgaW4gd2hpY2ggdGhlIGxhcmdlciBqdWcgY29udGFpbnMgZm91ciBsaXRlcnMgYW5kIHRoZSBzbWFsbGVyIGp1ZyBjb250YWlucyBvbmUgbGl0ZXIuCgpOZXh0LCB3ZSBjcmVhdGUgYSBkYXRhIGZyYW1lIGNvbnRhaW5pbmcgdGhlICQoTCArIDEpIFx0aW1lcyAoUyArIDEpJCBub2Rlcywgb25lIGZvciBlYWNoIHN0YXRlIG9mIHRoZSBzeXN0ZW0uIFRoZSBjb2x1bW5zIHdpbGwgYmUgdGhlIHZvbHVtZSBvZiB3YXRlciBpbiB0aGUgbGFyZ2VyIGFuZCBzbWFsbGVyIGp1Z3MgYW5kIGEgbGFiZWwgZm9yIHRoZSBub2RlLiBXZSBuZWVkIHRoZSBsYWJlbCBpbiB0aGUgZmlyc3QgY29sdW1uIHNvIHRoYXQgYGlncmFwaGAgd2lsbCByZWNvZ25pemUgaXQgYXMgc3VjaC4KCmBgYHtyfQpub2RlcyA8LSBkYXRhLmZyYW1lKExhYmVsID0gIiIsIExhcmdlID0gcmVwKDA6TCwgZWFjaCA9IChTICsgMSkpLCBTbWFsbCA9IHJlcCgwOlMsIHRpbWVzID0gKEwgKyAxKSkpCm5vZGVzJExhYmVsIDwtIG5vZGVfbGFiZWwobm9kZXMkTGFyZ2UsIG5vZGVzJFNtYWxsKQpgYGAKCiMjIEFyY3MKCk5vdyB3ZSBjcmVhdGUgYSBkYXRhIGZyYW1lIG9mIGFyY3MsIG9uZSBmb3IgZWFjaCBsZWdhbCBvcGVyYXRpb24gYXQgZWFjaCBub2RlLiBUaGUgZmlyc3QgdHdvIGNvbHVtbnMgZ2l2ZSB0aGUgbGFiZWxzIG9mIHRoZSBzb3VyY2UgYW5kIHNpbmsgbm9kZXM7IHRoZSB0aGlyZCBjb2x1bW4gaXMgdGhlIG5hbWUgb2YgdGhlIG9wZXJhdGlvbiAoZS5nLiwgIkZMIiB0byBmaWxsIHRoZSBsYXJnZXIganVnKS4KCmBgYHtyfQojIEZvciBlYWNoIG5vZGUgd2l0aCBhIG5vbmVtcHR5IGxhcmdlIGp1ZywgYWRkIGFuIGFyYyB0aGF0IGVtcHRpZXMgaXQuCmFyY3MgPC0gc3FsZGYoIlNFTEVDVCBBLkxhYmVsIEFTIFNvdXJjZSwgQi5MYWJlbCBBUyBTaW5rLCAnRUwnIEFTIE9wZXJhdGlvbiBGUk9NIG5vZGVzIEFTIEEsIG5vZGVzIEFTIEIgV0hFUkUgQS5MYXJnZSA+IDAgQU5EIEIuTGFyZ2UgPSAwIEFORCBBLlNtYWxsID0gQi5TbWFsbCIpCiMgRm9yIGVhY2ggbm9kZSB3aXRoIGEgbm9uLWZ1bGwgbGFyZ2UganVnLCBhZGQgYW4gYXJjIHRoYXQgZmlsbHMgaXQuCmFyY3MgPC0gcmJpbmQoYXJjcywKICAgICAgICAgICAgICBmbiRzcWxkZigiU0VMRUNUIEEuTGFiZWwgQVMgU291cmNlLCBCLkxhYmVsIEFTIFNpbmssICdGTCcgQVMgT3BlcmF0aW9uIEZST00gbm9kZXMgQVMgQSwgbm9kZXMgQVMgQiBXSEVSRSBBLkxhcmdlIDwgJEwgQU5EIEIuTGFyZ2UgPSAkTCBBTkQgQS5TbWFsbCA9IEIuU21hbGwiKSkKIyBGb3IgZWFjaCBub2RlIHdpdGggYSBub25lbXB0eSBzbWFsbCBqdWcsIGFkZCBhbiBhcmMgdGhhdCBlbXB0aWVzIGl0LgphcmNzIDwtIHJiaW5kKGFyY3MsCiAgICAgICAgICAgICAgc3FsZGYoIlNFTEVDVCBBLkxhYmVsIEFTIFNvdXJjZSwgQi5MYWJlbCBBUyBTaW5rLCAnRVMnIEFTIE9wZXJhdGlvbiBGUk9NIG5vZGVzIEFTIEEsIG5vZGVzIEFTIEIgV0hFUkUgQS5TbWFsbCA+IDAgQU5EIEIuU21hbGwgPSAwIEFORCBBLkxhcmdlID0gQi5MYXJnZSIpKQojIEZvciBlYWNoIG5vZGUgd2l0aCBhIG5vbi1mdWxsIHNtYWxsIGp1ZywgYWRkIGFuIGFyYyB0aGF0IGZpbGxzIGl0LgphcmNzIDwtIHJiaW5kKGFyY3MsCiAgICAgICAgICAgICAgZm4kc3FsZGYoIlNFTEVDVCBBLkxhYmVsIEFTIFNvdXJjZSwgQi5MYWJlbCBBUyBTaW5rLCAnRlMnIEFTIE9wZXJhdGlvbiBGUk9NIG5vZGVzIEFTIEEsIG5vZGVzIEFTIEIgV0hFUkUgQS5TbWFsbCA8ICRTIEFORCBCLlNtYWxsID0gJFMgQU5EIEEuTGFyZ2UgPSBCLkxhcmdlIikpCiMgRm9yIGVhY2ggbm9kZSB3aGVyZSB0aGUgbGFyZ2UganVnIGlzIG5vdCBlbXB0eSBhbmQgdGhlIHNtYWxsIGp1ZyBpcyBub3QgZnVsbCwgYWRkIGFuIGFyYyB0aGF0IHBvdXJzIGFzIG11Y2ggYXMgcG9zc2libGUgZnJvbSB0aGUgbGFyZ2UganVnIHRvIHRoZSBzbWFsbCBqdWcuCmFyY3MgPC0gcmJpbmQoYXJjcywKICAgICAgICAgICAgICBmbiRzcWxkZigiU0VMRUNUIEEuTGFiZWwgQVMgU291cmNlLCBCLkxhYmVsIEFTIFNpbmssICdQTFMnIEFTIE9wZXJhdGlvbiBGUk9NIG5vZGVzIEFTIEEsIG5vZGVzIEFTIEIgV0hFUkUgQS5MYXJnZSA+IDAgQU5EIEEuU21hbGwgPCAkUyBBTkQgQi5MYXJnZSA9IE1BWCgwLCBBLkxhcmdlIC0gKCRTIC0gQS5TbWFsbCkpIEFORCBCLlNtYWxsID0gTUlOKCRTLCBBLlNtYWxsICsgQS5MYXJnZSkiKSkKIyBGaW5hbGx5LCBmb3IgZWFjaCBub2RlIHdoZXJlIHRoZSBzbWFsbCBqdWcgaXMgbm90IGVtcHR5IGFuZCB0aGUgbGFyZ2UganVnIGlzIG5vdCBmdWxsLCBhZGQgYW4gYXJjIHRoYXQgcG91cnMgYXMgbXVjaCBhcyBwb3NzaWJsZSBmcm9tIHRoZSBzbWFsbCBqdWcgdG8gdGhlIGxhcmdlIGp1Zy4KYXJjcyA8LSByYmluZChhcmNzLAogICAgICAgICAgICAgIGZuJHNxbGRmKCJTRUxFQ1QgQS5MYWJlbCBBUyBTb3VyY2UsIEIuTGFiZWwgQVMgU2luaywgJ1BTTCcgQVMgT3BlcmF0aW9uIEZST00gbm9kZXMgQVMgQSwgbm9kZXMgQVMgQiBXSEVSRSBBLlNtYWxsID4gMCBBTkQgQS5MYXJnZSA8ICRMIEFORCBCLlNtYWxsID0gTUFYKDAsIEEuU21hbGwgLSAoJEwgLSBBLkxhcmdlKSkgQU5EIEIuTGFyZ2UgPSBNSU4oJEwsIEEuU21hbGwgKyBBLkxhcmdlKSIpKQpgYGAKCiMjIEdyYXBoCgpXZSBwdXQgdGhpcyB0b2dldGhlciBpbiBhIGRpZ3JhcGggdXNpbmcgYGlncmFwaGAuCgpgYGB7cn0KbmV0d29yayA8LSBncmFwaC5kYXRhLmZyYW1lKGFyY3MsIGRpcmVjdGVkID0gVFJVRSwgdmVydGljZXMgPSBub2RlcykKYGBgCgpOZXh0LCB3ZSBsZXQgYGlncmFwaGAgY29tcHV0ZSB0aGUgc2hvcnRlc3QgcGF0aCBmcm9tICIwXHwwIiB0byAiPHRhcmdldD5cfDAiLgoKYGBge3J9CnRhcmdldF9sYWJlbCA8LSBwYXN0ZTAodGFyZ2V0LCAifCIsIDApCnBhdGggPC0gdW5saXN0KGdldC5zaG9ydGVzdC5wYXRocyhuZXR3b3JrLCBmcm9tID0gIjB8MCIsIHRvID0gdGFyZ2V0X2xhYmVsLCBtb2RlID0gIm91dCIsIG91dHB1dCA9ICdlcGF0aCcpJGVwYXRoKQpjYXQobGVuZ3RoKHBhdGgpLCAiIG9wZXJhdGlvbnMgbmVlZGVkOlxuIikKZm9yIChpIGluIHBhdGgpIHsKICBjYXQoYXJjc1tpLCAiU291cmNlIl0sICItIiwgYXJjc1tpLCAiT3BlcmF0aW9uIl0sICItIiwgYXJjc1tpLCAiU2luayJdLCAiXG4iKQp9CmBgYAo=