We all were presented with this problem – water jug problem, which – in the time of Football world cup 2026 – can be translated to any liquid. *hint hint* But the riddle is as logical as mathematical. With mathematics finding the greatest common divisor. In general, it can be used with state search or Depth First Search (DFS).

With DFS we can solve this with Bezout’s identity; which in general is a theorem which relates two arbitraty integers with their greatests common divisor; and used in algebraic language, finding common zeros of n-polznomials in n-indeterminates. So the common zeros equals the product of the degrees of the polynomials.

And now that the imagine splitting the 16L beer Giraffe in two 8L Giraffes but you are only using 11L and 7L empty giraffes

This is the proof that with beer, Algebra is more fun And because it is fun, we can also find greated common divisors using Breadth-First Search (BFS). And here is the code:

solve_jugs <- function(caps = c(16, 11, 7), start = c(16, 0, 0), goal = c(8, 8, 0)) {
  # BFS over all (a, b, c) states
  # Each state is a named integer vector of water = amount is each jug or ?????
  
  queue   <- list(list(state = start, path = list(start)))
  visited <- list()
  key     <- function(s) paste(s, collapse = "-")
  
  while (length(queue) > 0) {
    node  <- queue[[1]]
    queue <- queue[-1]
    s     <- node$state
    
    if (isTRUE(all(s == goal))) return(node$path)
    if (!is.null(visited[[key(s)]])) next
    visited[[key(s)]] <- TRUE
    
    n <- length(s)
    for (from in 1:n) {
      for (to in 1:n) {
        if (from == to || s[from] == 0 || s[to] == caps[to]) next
        
        pour    <- min(s[from], caps[to] - s[to])
        new_s   <- s
        new_s[from] <- s[from] - pour
        new_s[to]   <- s[to]   + pour
        
        if (is.null(visited[[key(new_s)]])) {
          queue <- c(queue, list(list(
            state = new_s,
            path  = c(node$path, list(new_s))
          )))
        }
      }
    }
  }
  NULL  # no solution; add message or smht :)
}

solution <- solve_jugs()

 
for (step in solution) {
  cat(sprintf("  %-4d  %-4d  %-4d\n", step[1], step[2], step[3]))
}
  

And the final solution will reveal the steps and actions:

  16    0     0   
  5     11    0   
  5     4     7   
  12    4     0   
  12    0     4   
  1     11    4   
  1     8     7   
  8     8     0   
  

Similar steps are presented on the animation above.

As always, the complete code is available on GitHub in  Useless_R_function repository. And code to the animation is here (same Github repository).

Check the repository for future updates!

Stay healthy, hydrated and happy R-coding!