Check out the Pastebin Gadgets Shop. We have thousands of fun, geeky & affordable gadgets on sale :-)Want more features on Pastebin? Sign Up, it's FREE!
tweet

# Solving the decanting problem in bc

By: a guest on Oct 23rd, 2012  |  syntax: C  |  size: 2.13 KB  |  views: 45  |  expires: Never
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
clone this paste RAW Paste Data
Top