User Defined Types as Dictionary Keys

Question

I've been struggling with the concept of hash tables and dictionaries for the last few days and couldn't find a proper solution to my problem. I hope you will forgive me for my beginner (and probably duplicated) question and spare the time to answer me.

During the initialization of my "World" (FSM as part of solving the classic GridWorld MDP problem, but this is not the issue here) I've created various instances of State, each of them has a unique and characterizing tuple (row, column). My question is how can I store and refer to these instances.

To be more specific...

I have created several states with the following code (using lists for storing them after failing several other alternatives, e.g. dictionaries, sets and NumPy arrays):

(rows, columns) = (3, 4)
s = [[] for _ in range(rows)]
for r in range(rows):
    for c in range(columns):
        s[r].append(State(r, c))

where the class is defined by:

class State:
    def __init__(self, row, col):
        self.row = row
        self.col = col

    def __hash__(self):
        return hash((self.row, self.col))

    def __eq__(self, other):
        return (self.row == other.row) & (self.col == other.col)

    # __hash__ and __eq__ are here because I know they should,
    # though I currently don't know how to use them.
    # I believe that is actually the real question here...

Later in my code I wish to assign to each state an attribute neighbours, which is a list of the actual states close to it on the grid. By "actual" I mean that they are not copies of the states or some representation of the states, but rather the states themselves. Below you can find my not-what-I-was-looking-for implementation:

def add_neighbours(self):
    if self.row == 0:
        if self.col == 0:
            self.neighbours = [(0, 1), (1, 0)]
        elif self.col == 1:
            self.neighbours = [(0, 0), (0, 2)]
        elif self.col == 2:
            self.neighbours = [(0, 1), (1, 2), (0, 3)]
        elif self.col == 3:
            self.neighbours = [(0, 2), (1, 3)]
    elif self.row == 1:
        if self.col == 0:
            self.neighbours = [(0, 0), (2, 0)]
        elif self.col == 1:
            self.neighbours = []  # Pit, N/A
        elif self.col == 2:
            self.neighbours = [(0, 2), (1, 3), (2, 2)]
        elif self.col == 3:
            self.neighbours = [(0, 3), (1, 2), (2, 3)]
    elif self.row == 2:
        if self.col == 0:
            self.neighbours = [(1, 0), (2, 1)]
        elif self.col == 1:
            self.neighbours = [(2, 0), (2, 2)]
        elif self.col == 2:
            self.neighbours = [(2, 1), (1, 2), (2, 3)]
        elif self.col == 3:
            self.neighbours = [(2, 2), (1, 3)]

This definition of neighbours allows me to call the relevant states from s, but it is not a pretty sight and surly not elegant. What I look for is something of the sort:

def add_neighbours(self):
    if self.row == 0:
        if self.col == 0:
            self.neighbours = [State((0, 1)), State((1, 0))]
        elif self.col == 1:
            self.neighbours = [State((0, 0)), State((0, 2))]
        elif self.col == 2:
            self.neighbours = [State((0, 1)), State((1, 2)), State((0, 3))]
etc...

where State((r, c)) is the actual state (or I should say reference to state) called again and again.

Any comment will be much appreciated. Thanks.

Note: I am aware of detailed attempts for explanations (e.g. this Stack Overflow question and this Python Wiki reference, but unfortunately I failed to work them out and had to ask for more explanations.

Answer 1

This is a planar graph and where each node can be positioned and indexed with a matrix.

What you can do is:

1. Create a backing indexing structure to store each individual cell, so you can reference a cell by its coordinates.
2. Create each empty individual cell and store in the backing indexing structure.
3. Once each empty cell was created, link each cell to its neighbors.

You need to first create each State empty, because you can't reference an object which was not yet created.

In code:

# 1. Backing index
table = {}

# 2. Each State is empty.
table[(0, 0)] = State(0, 0)
table[(0, 1)] = State(0, 1)
table[(1, 0)] = State(1, 0)
table[(1, 1)] = State(1, 1)
# ...

# 3. Initialize each State.
table[(0, 0)].initialize()
table[(0, 1)].initialize()
# ...

class State:
  def initialize(self):
    if ...:
      # self.neighbours is a list of States.
      self.neighbours = [table[(x, y)], table[(a, b)], table[(p, q)]]