Mici funcții R inutile-utile – Rezolvator jug ​​cu identitatea lui Bezout

Cu toții ni s-a prezentat această problemă – problema ulciorului cu apă, care – pe vremea Cupei Mondiale de Fotbal 2026 – poate fi tradusă în orice lichid. *hint hint* Dar ghicitoarea este la fel de logică ca și matematică. Cu matematica găsind cel mai mare divizor comun. În general, poate fi utilizat cu căutarea de stat sau căutarea în profunzime (DFS).

Cu DFS putem rezolva asta cu identitatea lui Bezout; care în general este o teoremă care leagă două numere întregi arbitrare cu cel mai mare divizor comun al lor; și folosit în limbaj algebric, găsind zerouri comune ale n-polznomiilor în n-nedeterminate. Deci zerourile comune sunt egale cu produsul gradelor polinoamelor.

Și acum că imaginați-vă că împărțiți girafa de bere de 16 litri în două girafe de 8 litri, dar folosiți doar girafe goale de 11 litri și 7 litri.

Aceasta este dovada că, cu berea, Algebra este mai distractivă Și pentru că este distractiv, putem găsi și divizori comuni mari folosind Breadth-First Search (BFS). Și iată codul:

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  %-4dn", step(1), step(2), step(3)))
}
  

Iar soluția finală va dezvălui pașii și acțiunile:

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

Pași similari sunt prezentați în animația de mai sus.

Verificați depozitul pentru actualizări viitoare!

Rămâi sănătos, hidratat și fericit cu codificarea R!