Python ValueError: Substring not found

Question

I have been working on this code and I have tried to debug it for almost a day by now, but I can't seen to find where the problem lies.

I stop the debugger at line 66. When I step into or over the code I get an error message.

Traceback (most recent call last):
  File "/home/johan/pycharm-community-4.5.3/helpers/pydev/pydevd.py", line 2358, in <module>
    globals = debugger.run(setup['file'], None, None, is_module)
  File "/home/johan/pycharm-community-4.5.3/helpers/pydev/pydevd.py", line 1778, in run
    pydev_imports.execfile(file, globals, locals)  # execute the script
  File "/home/johan/sdp/lets_learn_python/20_a_star_algorithm.py", line 87, in <module>
    a.solve()
  File "/home/johan/sdp/lets_learn_python/20_a_star_algorithm.py", line 66, in solve
    closest_child.create_children()
  File "/home/johan/sdp/lets_learn_python/20_a_star_algorithm.py", line 48, in create_children
    child = StateString(val, self)
  File "/home/johan/sdp/lets_learn_python/20_a_star_algorithm.py", line 32, in __init__
    self.dist = self.get_dist()
  File "/home/johan/sdp/lets_learn_python/20_a_star_algorithm.py", line 40, in get_dist
    dist += abs(i - self.value.index(letter))
ValueError: substring not found

This is the code I have been working on. This is from a tutorial by Trevor Payne.

#!usr/bin/env python

from Queue import PriorityQueue


class State(object):
    def __init__(self, value, parent, start=0, goal=0):
        self.children = []
        self.parent = parent
        self.value = value
        self.dist = 0
        if parent:
            self.path = parent.path[:]
            self.path.append(value)
            self.start = parent.start
            self.goal = parent.goal
        else:
            self.path = [value]
            self.start = start
            self.goal = goal

    def get_dist(self):
        pass

    def create_children(self):
        pass


class StateString(State):
    def __init__(self, value, parent, start=0, goal=0):
        super(StateString, self).__init__(value, parent, start, goal)
        self.dist = self.get_dist()

    def get_dist(self):
        if self.value == self.goal:
            return 0
        dist = 0
        for i in range(len(self.goal)):
            letter = self.goal[i]
            dist += abs(i - self.value.index(letter))
        return dist

    def create_children(self):
        if not self.children:
            for i in xrange(len(self.goal)-1):
                val = self.value
                val = val[:i] + val[i+1] + val[i] + val[i+2]
                child = StateString(val, self)
                self.children.append(child)


class AStarSolver:
    def __init__(self,start, goal):
        self.path = []
        self.visited_queue = []
        self.priority_queue = PriorityQueue()
        self.start = start
        self.goal = goal

    def solve(self):
        start_state = StateString(self.start, 0, self.start, self.goal)
        count = 0
        self.priority_queue.put((0, count, start_state))
        while not self.path and self.priority_queue.qsize():
            closest_child = self.priority_queue.get()[2]
            closest_child.create_children()
            self.visited_queue.append(closest_child.value)
            for child in closest_child.children:
                if child.value not in self.visited_queue:
                    count += 1
                    if not child.dist:
                        self.path = child.path
                        break
                    self.priority_queue.put(child.dist, count)
        if not self.path:
            print "Goal of {0} is not possible!".format(self.goal)
        return self.path

# ================================
# MAIN

if __name__ == "__main__":
    start1 = "acbda"
    goal1 = "dabcd"
    print "Starting..."
    a = AStarSolver(start1, goal1)
    a.solve()
    for i in xrange(len(a.path)):
        print "%d) " % i + a.path[i]

I really hope someone could help me figure this out.

Answer 1

You should process the case when letter doesn't exist in self.value (line 41):

dist += abs(i - self.value.index(letter))

string.index raise an exception when the letter doesnt exist. Better use string.find instead, it gives -1 if the letter not found:

dist += abs(i - self.value.find(letter))

If you want to give another value than -1 , you should test it before using it:

f = self.value.find(letter)
if f == -1:
   # DO what you want