Nous avons tous été confrontés à ce problème – le problème de la carafe d’eau, qui – à l’époque de la Coupe du monde de football 2026 – peut se traduire par n’importe quel liquide. *indice indice* Mais l’énigme est aussi logique que mathématique. Les mathématiques trouvant le plus grand diviseur commun. En général, il peut être utilisé avec la recherche d’état ou la recherche en profondeur (DFS).

Avec DFS, nous pouvons résoudre ce problème avec l’identité de Bezout ; qui en général est un théorème qui relie deux entiers arbitraires avec leur plus grand diviseur commun ; et utilisé dans le langage algébrique, trouvant des zéros communs de n-polznomiaux dans n-indéterminés. Les zéros communs sont donc égaux au produit des degrés des polynômes.

Et maintenant, imaginez diviser la girafe de bière de 16 L en deux girafes de 8 L, mais vous n’utilisez que des girafes vides de 11 L et 7 L.

C’est la preuve qu’avec la bière, l’algèbre est plus amusante Et parce que c’est amusant, nous pouvons également trouver des diviseurs communs plus grands en utilisant la recherche en largeur d’abord (BFS). Et voici le 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]))
}
  

Et la solution finale révélera les étapes et 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   
  

Des étapes similaires sont présentées sur l’animation ci-dessus.

Comme toujours, le code complet est disponible sur GitHub dans le référentiel Useless_R_function. Et le code de l’animation est ici (même référentiel Github).

Consultez le référentiel pour les futures mises à jour !

Restez en bonne santé, hydraté et heureux du R-coding !

En rapport