Water Jug problem, using state space search

water_jug_state_space_search.py

#Written by: Anish Mashankar
#Blog: http://techieanish.blogspot.com

class WaterJug:
        
    def __init__(self, x, y, goal_x, goal_y):
        self.JUG_1 = x
        self.JUG_2 = y
        self.j_1 = 0
        self.j_2 = 0
        self.goal = goal
        self.paths = list()
        self.next_states = list()
        self.path = list()
        self.goal_x = goal_x
        self.goal_y = goal_y
                 
    def display_paths(self):        
        for path in self.paths:
            for state in path:
                print "-> {0}".format(state)
            print
        no_of_paths = len(self.paths)
        print
        if no_of_paths > 0:
            print 'Total number of possible solutions: ' + str(len(self.paths))
            min_len = len(self.paths[0])
            locations = []
            x = 0
            for path in self.paths:
                if len(path) < min_len:
                    min_len = len(path)
                    locations.append(x)
                x+=1
            print
            print 'Most optimal paths: '
            for location in locations:
                path = self.paths[location]
                for state in path:
                    print "-> {0}".format(state)
                print
        else:
            print 'No possible solution exists'
        
        
    def get_path(self, new_state): 
        if new_state not in self.path:
            self.path.append(new_state)
            self.j_1 = new_state[0]
            self.j_2 = new_state[1]
        else:
            return
        
        if self.j_1 == self.goal_x and self.j_2 == self.goal_y:
            success_path = list(self.path)
            self.paths.append(success_path)
            self.path.pop()
            return
        
        next_act = list()
        visited = list()
        self.next_state(next_act)
        while len(next_act)!=0:
            new_state = next_act.pop()
            if new_state not in visited:
                visited.append(new_state)
                self.get_path(new_state)
        self.path.pop()
        return
            
    def next_state(self, next_act):
        
        if self.j_1 < self.JUG_1:
            next_act.append([self.JUG_1, self.j_2]) 
            
        if self.j_2 < self.JUG_2:
            next_act.append([self.j_1, self.JUG_2])
            
        if self.j_1 > 0:
            next_act.append([0, self.j_2])
            
        if self.j_2 > 0:
            next_act.append([self.j_1, 0])
            
        if self.j_1 + self.j_2 >= self.JUG_1 and self.j_2 > 0:
            next_act.append([self.JUG_1, self.j_2 - (self.JUG_1 - self.j_1)])
            
        if self.j_1 + self.j_2 >= self.JUG_2 and self.j_1 > 0:
            next_act.append([self.j_1- (self.JUG_2 - self.j_2), self.JUG_2])
            
        if self.j_1 + self.j_2 <= self.JUG_1 and self.j_2 > 0:
            next_act.append([self.j_1 + self.j_2, 0])
            
        if self.j_1 + self.j_2 <= self.JUG_2 and self.j_1 > 0:
            next_act.append([0, self.j_1 + self.j_2])
    
if __name__ == "__main__":
    x = int(raw_input( "Enter the capacity of first Water jug : "))
    y = int(raw_input("Enter the Capacity of the second water jug : "))
    x_goal = int(raw_input("Enter the amount you want in the first jug : "))
    y_goal = int(raw_input("Enter the amount you want in the second jug : "))
    problem = WaterJug(x, y, x_goal, y_goal)
    problem.get_path([0,0])
    problem.display_paths()