5
\$\begingroup\$

I wrote a solution for a jug problem (given two jugs of water of different sizes find the steps needed to get specific amount of water in one of the jugs). I'm hoping for some input on my code. How can I make it better? More readable?

Optional - Is there a faster or more efficient solution I should look into?

#!/usr/bin/env python

import graph
import heapq


def build_gallon_graph(g, jug1, jug2, jug1_size, jug2_size):
    """Build a graph for solving a jug problem. Recursive function.

    Arguments:
        g -- graph.Graph() object.
        jug1 -- Amount of water in a first jug.
        jug2 -- Amount of water in a second jug.
        jug1_size -- Size of the first jug.
        jug2_size -- Size of the second jug.
    """
    # Fill jug 1.
    if jug1 < jug1_size:
        new_jug1, new_jug2 = jug1_size, jug2
        _add_connection(g, jug1, jug2, new_jug1, new_jug2,
                        jug1_size, jug2_size)

    # Fill jug 2.
    if jug2 < jug2_size:
        new_jug1, new_jug2 = jug1, jug2_size
        _add_connection(g, jug1, jug2, new_jug1, new_jug2,
                        jug1_size, jug2_size)

    # Pour jug 1 to jug 2.
    if jug1 > 0 and jug2 < jug2_size:
        new_jug1 = jug1 - jug2_size + jug2
        if new_jug1 < 0:
            new_jug1 = 0
        new_jug2 = jug2 + jug1 if jug1 + jug2 <= jug2_size else jug2_size
        _add_connection(g, jug1, jug2, new_jug1, new_jug2,
                        jug1_size, jug2_size)

    # Pour jug 2 to jug 1.
    if jug2 > 0 and jug1 < jug1_size:
        new_jug1 = jug2 + jug1 if jug1 + jug2 <= jug1_size else jug1_size
        new_jug2 = jug2 - jug1_size + jug1
        if new_jug2 < 0:
            new_jug2 = 0
        _add_connection(g, jug1, jug2, new_jug1, new_jug2,
                        jug1_size, jug2_size)

    # Empty jug 1.
    if jug1 > 0:
        new_jug1, new_jug2 = 0, jug2
        _add_connection(g, jug1, jug2, new_jug1, new_jug2,
                        jug1_size, jug2_size)

    # Empty jug 2.
    if jug2 > 0:
        new_jug1, new_jug2 = jug1, 0
        _add_connection(g, jug1, jug2, new_jug1, new_jug2,
                        jug1_size, jug2_size)


def _connection_exists(g, jug1, jug2, new_jug1, new_jug2):
    if (new_jug1, new_jug2) not in g.vertices or (jug1, jug2) not in g.vertices:
        return False
    if g.vertices[(new_jug1, new_jug2)] in g.vertices[(jug1, jug2)].neighbors:
        return True
    if g.vertices[(jug1, jug2)] in g.vertices[(new_jug1, new_jug2)].neighbors:
        return True
    return False


def _add_connection(
        g, jug1, jug2, new_jug1, new_jug2, jug1_size, jug2_size):
    if not _connection_exists(g, jug1, jug2, new_jug1, new_jug2):
        g.add_edge((jug1, jug2), (new_jug1, new_jug2))
        build_gallon_graph(g, new_jug1, new_jug2, jug1_size, jug2_size)


def find_correct_order_of_actions(g, start, finish):
    """This is based on Dijkstra's shortest path alogirthm."""
    g.vertices[start].distance = 0
    queue = [(v.distance, v) for v in g.vertices.values()]
    heapq.heapify(queue)
    while queue:
        _, vertex = heapq.heappop(queue)
        for neighbor in vertex.neighbors:
            distance = vertex.distance + vertex.neighbors[neighbor]
            if distance < neighbor.distance:
                neighbor.distance = distance
                neighbor.predecessor = vertex
                heapq._siftdown(queue, neighbor, distance)
    path = []
    vertex = g.vertices[finish]
    while vertex.predecessor is not None:
        path.append(vertex)
        vertex = vertex.predecessor
    path.append(vertex)
    return reversed(path)

jug1, jug2 = 0, 0
jug1_size, jug2_size = 4, 3
jug2_result, jug1_result = 2, 0

g = graph.Graph()
g.add_vertex((jug1, jug2))
build_gallon_graph(g, jug1, jug2, jug1_size, jug2_size)
path = find_correct_order_of_actions(
        g, (jug1, jug2), (jug1_result, jug2_result))
for vertex in path:
    print '({}-gallon jug: {}, {}-gallon jug: {})'.format(
            jug1_size, vertex.key[0], jug2_size, vertex.key[1])

And here's the output for 4-gallon jug and 3-gallon jug in order to get 2 gallons of water in the 4-gallon jug:

(4-gallon jug: 0, 3-gallon jug: 0)
(4-gallon jug: 4, 3-gallon jug: 0)
(4-gallon jug: 1, 3-gallon jug: 3)
(4-gallon jug: 1, 3-gallon jug: 0)
(4-gallon jug: 0, 3-gallon jug: 1)
(4-gallon jug: 4, 3-gallon jug: 1)
(4-gallon jug: 2, 3-gallon jug: 3)
(4-gallon jug: 2, 3-gallon jug: 0)
(4-gallon jug: 0, 3-gallon jug: 2)
\$\endgroup\$
2
  • 2
    \$\begingroup\$ What's import graph? I don't have this. Also, are those if's not chained elifs? \$\endgroup\$ Jan 26, 2015 at 5:02
  • \$\begingroup\$ @f.rodrigues graph is a module I wrote that implements a graph. Each graph has graph.Graph.vertices, each graph.Vertex has key, predecessor and distance properties. graph.Graph is very trivial, so I decided it's not worth including. The ifs are meant to be not chained, since I'm building a graph of all possible combinations. \$\endgroup\$ Jan 26, 2015 at 5:26

3 Answers 3

5
\$\begingroup\$
  • Dijkstra's algorithm is an unnecessary complication when all the edges have the same cost. A simple breadth first search could be used instead.
  • Building the graph in breadth first order would allow you to set the predecessors on the same pass. Then you would be able to answer different queries directly by following the predecessors from the final state, as long as the jug sizes and start state are the same. If you only need to answer a single query you could even stop building the graph as soon as you produce the target node.
  • This calculation

    # Pour jug 1 to jug 2.
    if jug1 > 0 and jug2 < jug2_size:
        new_jug1 = jug1 - jug2_size + jug2
        if new_jug1 < 0:
            new_jug1 = 0
        new_jug2 = jug2 + jug1 if jug1 + jug2 <= jug2_size else jug2_size    
    

    could be written in a simpler way:

    # Pour jug 1 to jug 2.
    measure = min(jug1, jug2_size - jug2)
    if measure > 0:
        new_jug1 = jug1 - measure
        new_jug2 = jug2 + measure
    
  • In build_gallon_graph the same call to _add_connection repeats many times. One way to avoid that would be to refactor into a generator:

    def transitions(jug1, jug2, jug1_size, jug2_size):
    
        # Fill jug 1.
        if jug1 < jug1_size:
            yield jug1_size, jug2
    
        # Fill jug 2.
        if jug2 < jug2_size:
            yield jug1, jug2_size
    
        # Pour jug 1 to jug 2.
        measure = min(jug1, jug2_size - jug2)
        if measure > 0:
            yield jug1 - measure, new_jug2 = jug2 + measure
    
        # Pour jug 2 to jug 1.
        measure = min(jug1_size - jug1, jug2)
        if measure > 0:
            yield jug1 + measure, new_jug2 = jug2 - measure
    
        # Empty jug 1.
        if jug1 > 0:
            yield 0, jug2
    
        # Empty jug 2.
        if jug2 > 0:
            yield jug1, 0
    
    def build_gallon_graph(g, jug1, jug2, jug1_size, jug2_size):
        for new_jug1, new_jug2 in transitions(jug1, jug2, jug1_size, jug2_size):
            _add_connection(g, jug1, jug2, new_jug1, new_jug2,
                            jug1_size, jug2_size) 
    
\$\endgroup\$
2
  • \$\begingroup\$ Constructing the entire graph may make sense outside of toy cases. For example if the jugs are fixed size, the state space is large and there are many queries against it. At some point it may even make sense to just run an all-pairs shortest path. \$\endgroup\$ Jan 26, 2015 at 17:24
  • \$\begingroup\$ @benrudgers True. I revised my answer slightly. \$\endgroup\$ Jan 26, 2015 at 18:15
3
\$\begingroup\$

The problem with Dijkstra’s Algorithm here is that there is no guarantee that the target node is connected to the graph, and the code does not appear to handle unreachable goals in an informative way, e.g.

  jug1, jug2 = 0, 0
  jug1_size, jug2_size = 4, 3
  jug2_result, jug1_result = 5, 7

It looks like it will just return the nearest value when Dijkstra runs out of nodes.

Ideally validation should be done in the Pouring Water code, even if it is via an external library call to a connected component module.

This suggests that modularity would be improved if the general purpose Dijkstra's Algorithm lived in its own module. This would simplify and reduce the size of the Pouring Water code while abstracting away implementation details.

\$\endgroup\$
1
\$\begingroup\$

Great job on this! You did many things right. You made you variable names the same across all functions, told what each input was, and (mostly) was uncluttered.

These are just some minor fixes.

  1. Change jug2_result, jug1_result = 2, 0 to jug1_result, jug2_result = 2, 0 to keep in line with the rest of the declarations.

  2. Instead of "{}".format(value1), I like to use "%s" %(value1). Just personal preference, and it's shorter.

  3. What's with

    vertex = g.vertices[finish]
    while vertex.predecessor is not None:
        path.append(vertex)
    vertex = vertex.predecessor
    path.append(vertex)
    return reversed(path)
    

You reverse path with your loop, then return it reversed again? No! Just iterate through g.vertices.

Again, most of these are minor, and this is probably not the best answer. Happy coding!

\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.