Key k returned by dict.keys() causes KeyError when doing dict[k]: KeyError on existing key

Question

The following code

for k in list(g_score.keys()):
    print(g_score[k])

returns a KeyError for me:

Traceback (most recent call last):
  File "./np.py", line 134, in <module>
    main()
  File "./np.py", line 131, in main
    NPuzzle(n).solve()
  File "./np.py", line 116, in solve
    print(g_score[k])
KeyError: 3

I don't understand how this is possible when print(list(g_score.keys())) is [4, 3, 7]. 3 is clearly in the dict.

---

For context, I'm trying to implement an A* search for the N-Puzzle problem (and I'm not even sure if the A* is implemented correctly since I can't get past this error), and have the following State class and solve function:

class State:
    def __init__(self, blank_idx, puzzle, g=0, h=0):
        self.blank_idx = blank_idx
        self.puzzle = puzzle
        self.f = g + h

    def __eq__(self, other):
        return self.puzzle == other.puzzle

    def __hash__(self):
        return self.f + self.blank_idx

    def __lt__(self, other):
        return self.f < other.f

    def __repr__(self):
        return str(self.f)

...

class NPuzzle:

    # ...other stuff

    def solve(self):
      start_state = State(
          self.puzzle.index(' '),
          self.puzzle,
          0,
          self.cost(self.puzzle)
      )

      g_score = {start_state: 0}
      open_set = [start_state]
      path = {}

      while open_set:
          state = open_set[0]

          if state.puzzle == self.goal_state:
              break

          heappop(open_set)
          for next_state in self.neighbors(state):
              g = g_score[state] + 1
              if next_state in g_score and g >= g_score[next_state]:
                  continue

              path[next_state] = state
              g_score[next_state] = g
              next_state.f = g + self.cost(next_state.puzzle)
              heappush(open_set, next_state)

and I first encountered the error on the line where I have:

g = g_score[state] + 1

I'm not sure really why this KeyError is occurring, but I'm assuming maybe it has to do with my custom __hash()__ function.

Answer 1

Ok so turns out the issue was that I was immediately changing the properties of the State instance that the hash function depended on...oops:

My __hash()__ function for State is:

return self.f + self.blank_idx

and the way I was storing State in g_score is below:

g_score[next_state] = g
next_state.f = g + self.cost(next_state.puzzle)

Turns out the above breaks everything since it uses next_state.f to put next_state into g_score, but then immediately on the next line I mutate next_state.f

Switching the order of the two statements like so:

next_state.f = g + self.cost(next_state.puzzle)
g_score[next_state] = g

fixes my issue.