Stuck on Python "KeyError: <exception str() failed>" in BFS code of a water jug scenario

Question

Intended Function of code: Takes a user input for the volume of 3 jars(1-9) and output the volumes with one of the jars containing the target length. jars can be Emptied/Filled a jar, or poured from one jar to another until one is empty or full. With the code I have, i'm stuck on a key exception error . Target length is 4 for this case

Code:

`

class Graph:

    class GraphNode:
        def __init__(self, jar1 = 0, jar2 = 0, jar3 = 0, color = "white", pi = None):
            self.jar1 = jar1
            self.jar2 = jar2
            self.jar3 = jar3
            self.color = color
            self.pi = pi

        

        def __repr__(self):
            return str(self)

    def __init__(self, jl1 = 0, jl2 = 0, jl3 = 0, target = 0):
        self.jl1 = jl1
        self.jl2 = jl2
        self.jl3 = jl3
        self.target = target
        self.V = {}
        for x in range(jl1 + 1):
            for y in range(jl2 + 1):
                for z in range(jl3 + 1):
                    node = Graph.GraphNode(x, y, z, "white", None)
                    self.V[node] = None

    def isFound(self, a: GraphNode) -> bool:
        if self.target in [a.jar1, a.jar2, a.jar3]:
            return True
        return False
        pass

    def isAdjacent(self, a: GraphNode, b: GraphNode) -> bool:
        if self.V[a]==b:
            return True
        return False
        pass

    def BFS(self) -> [] :
        start = Graph.GraphNode(0, 0, 0, "white")
        queue=[]
        queue.append(start)
        while len(queue)>0:
            u=queue.pop(0)
            for v in self.V:
                if self.isAdjacent(u,v):
                    if v.color =="white":
                        v.color == "gray"
                        v.pi=u
                        if self.isFound(v):
                            output=[]
                            while v.pi is not None:
                                output.insert(0,v)
                                v=v.pi
                                return output
                            else:
                                queue.append(v)
            u.color="black"
        return []
        
#######################################################
j1 = input("Size of first jar: ")
j2 = input("Size of second jar: ")
j3 = input("Size of third jar: ")
t = input("Size of target: ")

jar1 = int(j1)
jar2 = int(j2)
jar3 = int(j3)
target = int(t)

graph1 = Graph(jar1, jar2, jar3, target)
output = graph1.BFS()

print(output)

` **Error: **

line 37, in isAdjacent
    if self.V[a]==b:
KeyError: <exception str() failed>

Can you provide values for the jars that you entered when you got this error (I get a different error). — Bill
– Bill, Commented Dec 3, 2022 at 5:11
Even better, replace the input statements in your code with the values you are using. — Bill
– Bill, Commented Dec 3, 2022 at 5:14
See my answer below. This is a difficult exception to debug. It is nothing to do with the BFS algorithm. Consider changing the title to "KeyError: <exception str() failed>" so others will also come here when they get this. I could not find much when googling this. — Bill
– Bill, Commented Dec 3, 2022 at 22:02

Bill · Accepted Answer · 2022-12-03 22:07:54Z

Strange but when I first ran this in the IPython interpreter I got a different exception:

... :35, in Graph.isAdjacent(self, a, b)
     34 def isAdjacent(self, a: GraphNode, b: GraphNode) -> bool:
---> 35     if self.V[a]==b:
     36         return True
     37     return False

<class 'str'>: (<class 'RecursionError'>, RecursionError('maximum recursion depth exceeded while getting the str of an object'))

When I run it as a script or in the normal interpreter I do get the same one you had:

... line 35, in isAdjacent
    if self.V[a]==b:
KeyError: <exception str() failed>

I'm not sure what this means so I ran the debugger and got this:

  File "/Users/.../stackoverflow/bfs1.py", line 1, in <module>
    class Graph:
  File "/Users/.../stackoverflow/bfs1.py", line 47, in BFS
    if self.isAdjacent(u,v):
  File "/Users/.../stackoverflow/bfs1.py", line 35, in isAdjacent
    if self.V[a]==b:
KeyError: <unprintable KeyError object>
Uncaught exception. Entering post mortem debugging
Running 'cont' or 'step' will restart the program
> /Users/.../stackoverflow/bfs1.py(35)isAdjacent()
-> if self.V[a]==b:
(Pdb) type(a)
<class '__main__.Graph.GraphNode'>
(Pdb) str(a)
*** RecursionError: maximum recursion depth exceeded while calling a Python object

So it does seem like a maximum recursion error. (The error message you originally got is not very helpful). But the words <unprintable KeyError object> are a clue. It looks like it was not able to display the KeyError exception...

The culprit is this line in your class definition:

        def __repr__(self):
            return str(self)

What were you trying to do here?

The __repr__ function is called when the class is asked to produce a string representation of itself. But yours calls the string function on the instance of the class so it will call itself! So I think you actually generated a second exception while the debugger was trying to display the first!!!.

I replaced these lines with

        def __repr__(self):
            return f"GraphNode({self.jar1}, {self.jar2}, {self.jar3}, {self.color}, {self.pi})"

and I don't get the exception now:

Size of first jar: 1
Size of second jar: 3
Size of third jar: 6
Size of target: 4
Traceback (most recent call last):
  File "/Users/.../stackoverflow/bfs1.py", line 77, in <module>
    output = graph1.BFS()
  File "/Users/.../stackoverflow/bfs1.py", line 45, in BFS
    if self.isAdjacent(u,v):
  File "/Users/.../stackoverflow/bfs1.py", line 33, in isAdjacent
    if self.V[a]==b:
KeyError: GraphNode(0, 0, 0, white, None)

This exception is easier to interpret. Now it's over to you to figure out why this GraphNode was not found in the keys of self.V!

Collectives™ on Stack Overflow

Stuck on Python "KeyError: <exception str() failed>" in BFS code of a water jug scenario

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related