Formulating the search problem

In a file searching application, we start searching from the current directory, so our initial state is the current directory. Now, let's write the code for the state and the initial state, as follows:

Figure 16

In the preceding screenshot, we have created two Python modules, State.py and StateTest.py. The State.py module will contain the code for the three search ingredients mentioned in the previous section. The StateTest module is a file where we can test these ingredients.

Let's go ahead and create a constructor and a function that returns an initial state, as shown in the following code:

....
import os 

class State:
    '''
    This class retrieves state information for search application
    '''
    
    def __init__(self, path = None):
        if path == None:
            #create initial state
            self.path = self.getInitialState()
        else:
            self.path = path
    
    def getInitialState(self):
        """
        This method returns the current directory
        """
        initialState = os.path.dirname(os.path.realpath(__file__))
        return initialState
 ....

In the preceding code, the following apply:

• We have the constructor (the constructor name) and we have created a property called path, which stores the actual path of the state. In the preceding code example, we can see that the constructor takes path as an argument. The if...else block suggests that if the path is not provided, it will initialize the state as the initial state, and if the path is provided, it will create a state with that particular path.
• The getInitialState() function returns the current working directory.

Now, let's go ahead and create some sample states, as follows:

...
from State import State
import os
import pprint

initialState = State()
print "initialState", initialState.path

interState = State(os.path.join(initialState.path, "d2", "d21"))
goalState = State(os.path.join(initialState.path, "d2", "d21", "f211.txt"))

print "interState", interState.path
print "goalState", goalState.path
....

In the preceding code, we have created the following three states:

• initialState, which points to the current directory
• interState, which is the intermediate function that points to the d21 folder
• goalState, which points to the f211.txt folder

Next, we will look at the successor function. If we're in a particular folder, the successor function should return the folders and files inside of that folder, and, if you're currently looking at a file, it should return an empty array. Considering the following diagram, if the current state is d2, it should return paths to the d21 and d22 folders:

Figure 17

Now, let's create the preceding function with the following code:

...
    def successorFunction(self):
        """
        This is the successor function. It generates all the possible
         paths that can be reached from current path.
        """

        if os.path.isdir(self.path):
            return [os.path.join(self.path, x) for x in         
            sorted(os.listdir(self.path))]
        else:
            return []
...

The preceding function checks whether the current path is a directory. If it is a directory, it gets a sorted list of all of the folders and files inside it, and prepends the current path to them. If it is a file, it returns an empty array.

Now, let's test this function with some input. Open the StateTest module and take a look at the successors to the initial state and intermediate state:

...
initialState = State()
print "initialState", initialState.path

interState = State(os.path.join(initialState.path, "d2", "d21"))
goalState = State(os.path.join(initialState.path, "d2", "d21", "f211.txt"))

print "interState", interState.path
print "goalState", goalState.path
...

As shown in the preceding code, the successors to the current directory (or the initial state) are the LiClipse project files and the folders d1, d2, and d3, and the successor of the intermediate state is the f211.txt file.

The output of running the preceding code is shown in the following screenshot:

Figure 18

Finally, we will look at the goal function. So, how do we know that we have found the target file, f211.txt? Our goal function should return False for the d21 folder, and True for the f211.txt file . Let's look at how to implement this function in code:

...
def checkGoalState(self):
        """
        This method checks whether the path is goal state 
        """ 
        #check if it is a folder
        if os.path.isdir(self.path):
            return False
        else:
            #extract the filename
            fileSeparatorIndex = self.path.rfind(os.sep)
            filename = self.path[fileSeparatorIndex + 1 : ]
            if filename == "f211.txt":
                return True
            else:
                return False
...

As shown in the preceding code, the function checkGoalState() is our goal function; this checks whether the current path is a directory. Now, since we are looking for a file, this returns False if it's a directory. If it is a file, it extracts the filename from the path. The filename is the substring of the path from the last occurrence of a slash to the end of the string. So, we extract the filename and compare it with f211.txt. If they match, we return True; otherwise, we return False.

Again, let's test this function for the states that we've created. To do so, open the StateTest module, as shown in the following screenshot:

Figure 19

As you can see, the function returns False for the current directory, it returns False for the d21 folder, and it returns True for the f211.txt file.

Now that we understand the three ingredients in search algorithms, in the next section, we will look at building search trees with nodes.