Decanting Problems and Dijkstra's Algorithm (II)

Aug 8, 2016

In the previous post, Decanting Problems and Dijkstra’s Algorithm, we presented some scipy hackery to solve the Die Hard puzzle:

Two men have a full eight-gallon jug of wine, and also two empty jugs of five and three gallons capacity, respectively. Is it possible (within the restrictions of our problem) to divide the wine equally so each men can have four gallons of wine?

In this post we replicate the same technique, but this time using Julia’s Graphs package. First of all, make sure you have the package installed. If this is not the case, issue in an Ijulia session the command Pkg.add("Graphs"). Once installed, the functions of the package can be readily called.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

using Graphs

states = filter(x->x[1]+x[2]+x[3]==8 && 
                (x[1]==0 || x[1]==8 || x[2]==0 || x[2]==5 || x[3]==0 || x[3]==3) , 
                [(a,b,c) for a in 0:8, b in 0:5, c in 0:3])

G = graph(states, [], is_directed=true)

for node1 in G.vertices
    for node2 in G.vertices
        total_change = ((node1[1]-node2[1]), node1[2]-node2[2], node1[3]-node2[3])
                 # Check 1: one of the jugs is not affected
        check1 = (total_change[1]*total_change[2]*total_change[3]==0)
                 # Check 2: one of the jugs gets full
        check2 = (node2[1]==8 && total_change[1]!=0) || 
                 (node2[2]==5 && total_change[2]!=0) || 
                 (node2[3]==3 && total_change[3]!=0)
                 # Check 3: one of the jugs gets empty
        check3 = (node2[1]==0 && total_change[1]!=0) || 
                 (node2[2]==0 && total_change[2]!=0) || 
                 (node2[3]==0 && total_change[3]!=0)
        is_adjacent = check1 && (check2 || check3)
        if is_adjacent 
            add_edge!(G, node1, node2)
        end
    end
end

We are ready to fire Dijkstra’s algorithm on this graph now.

1
2
3
4
5
6
7
8
9
10
11

r = dijkstra_shortest_paths(G, ones(Int64,num_edges(G)), (8,0,0))

source = (4,4,0)
source_index = findfirst(G.vertices, (4,4,0))

while source!=(8,0,0)
    print(source)
    source = r.parents[source_index]
    source_index = r.parent_indices[source_index]
end
print(sourc)
(4,4,0)(1,4,3)(1,5,2)(6,0,2)(6,2,0)(3,2,3)(3,5,0)(8,0,0)

As in the previous solution, we found that the simplest way to divide the wine equally is in 7 steps as follows:

  1. Pour 5 gallons of wine into the second jug. \( (3,5,0) \)
  2. Pour 3 gallons from the second jug to the third. \( (3,2,3) \)
  3. Pour 3 gallons from the third to the first. \( (6,2,0) \)
  4. Pour all 2 gallons from the second to the third jug. \( (6,0,2) \)
  5. Pour five gallons from the first to the second jug. \( (1,5,2) \)
  6. Pour one gallon from the second to the third jug. \( (1,4,3) \)
  7. We are technically done, but we may pour now all three gallons from the third jug to the first, for a convenient transportation of the wine. \( (4,4,0) \)