Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Solving the decanting problem in bc

By: a guest on Oct 23rd, 2012  |  syntax: C  |  size: 2.13 KB  |  views: 42  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. # SETUP
  2. n = 3   # number of jugs
  3. j[1] = 17 ; j[2] = 16 ; j[3] = 15  # capacity of jugs
  4. # note: jug #0 is the "tub", with unlimited capacity
  5.  
  6. # given a state, determine whether it's a goal state
  7. define isgoal(state) {
  8.     return (amt(state, 1) == 8) + (amt(state, 2) == 8) + (amt(state, 3) == 8) >= 2
  9. }
  10.  
  11. # a state is represented with one base-b digit for each jug's current amount.
  12. # state = 5b^2 + 4b + 3 means 3 in jug #1, 4 in jug #2, and 5 in jug #3
  13. b = 20
  14.  
  15. # given a state, return the amount currently in the xth jug
  16. define amt(state, x) { if (x == 0) return 9999 ; return state / b^(x-1) % b }
  17.  
  18. # given a state, return the remaining capacity in the xth jug
  19. define cap(state, x) { if (x == 0) return 9999 ; return j[x] - amt(state, x) }
  20.  
  21. define min(g, h) { if (g < h) return g ; return h }
  22.  
  23. # given a state, return the state you get pouring from x to y
  24. define pour(state, x, y) {
  25.     p = min(amt(state, x), cap(state, y))  # amount that actually gets poured
  26.     if (x) state -= p * b^(x-1)
  27.     if (y) state += p * b^(y-1)
  28.     return state
  29. }
  30.  
  31. # SOLVE THE PROBLEM
  32. q[0] = 0  # the starting state
  33. qk = 1  # current size of the queue
  34. for (qj = 0 ; qj < qk ; ++qj) {
  35.     state = q[qj]
  36.     if (isgoal(state)) break
  37.     for (x = 0 ; x <= n ; ++x) {       # the jug I'm pouring from
  38.         for (y = 0 ; y <= n ; ++y) {   # the jug I'm pouring to
  39.             if (x == y) continue
  40.             newstate = pour(state, x, y)
  41.             if (explored[newstate]) continue
  42.             explored[newstate] = 1
  43.             q[qk++] = newstate      # Add the new state to the queue
  44.             parent[newstate] = state
  45.             jfrom[newstate] = x
  46.             jto[newstate] = y
  47.         }
  48.     }
  49. }
  50.  
  51. # PRINT THE SOLUTION
  52. while (state) {
  53.     solution[sj++] = state
  54.     state = parent[state]
  55. }
  56. while (sj) {
  57.     state = solution[--sj]
  58.     x = jfrom[state] ; y = jto[state]
  59.     if (!x) print "Fill jug #", y, "                   "
  60.     if (!y) print "Empty jug #", x, "                  "
  61.     if (x && y) print "Pour from jug #", x, " to jug #", y, "    "
  62.     for (x = 1 ; x <= n ; ++x) print amt(state, x), "/", j[x], " "
  63.     print "\n"
  64. }
  65. halt