Implementation of a NFA for moves on a 3X3 chess board

Question

I have the following chess board:

Each square is a state. The initial state is "a".

Given an user input of the color of the squares where he wants to move, the program needs to find all possible routes according to that input.

For example: if the input is W (for white) we go from "a" to "e". And if the input is R (for red) we go from "a" to "b" and "d" at the same time. Another more complex example: if the input is WR we go from "a" to "e" for W, then from "e" to "b", "d", "f" and "h" for R at the same time.

I have the following python program:

def chess (input):
    A = []
    current_state = "a"
    A.append ([current_state])
    switch = {"a": a, "b": b, "c": c, "d": d, "e": e, "f": f, "g": g, "h": h, "i": i}
    new_state = ""   

    for k in input:
        for j in current_state:
            new_state = new_state + switch [j] (k)
        A.append ([new_state])
        current_state = new_state
        new_state = ""
    for x in range (len (A)):
        print (A [x])

chess (input ())

The switch is a dictionary which contains separate functions for each state (square) of the board. These functions return a string of the states to which you can move according to some input.

For example for state a:

 def a (character):
    if character == 'R':
        return "bd"
    elif character == 'W':
        return "e"

The chess function prints a matrix containing the states in this fashion: For the input WR, it gives the following output:

['a']
['e']
['bdfh']

So far so good, but I need all the routes separated. For the same input I should have the following output:

Route 1 : a, e, b
Route 2 : a, e, d
Route 3 : a, e, f
Route 4 : a, e, h

Any ideas how to get that from the matrix?

Answer 1

The perfect Python device for this task is a recursive generator. The task is clearly recursive, and a generator is ideal when you need a function that can produce multiple solutions. Recursive generators can be a little daunting at first, but they are certainly worth investing the time necessary to become familiar with them if you want to do this kind of state machine work.

To store the state data I use a dictionary of dictionaries. I could have written code to create this data structure, but I decided it would be quicker to just hard-code it. That would probably not be the case with a larger matrix. ;)

switch = {
    'a': {'W': 'e', 'R': 'bd'},
    'b': {'W': 'ace', 'R': 'df'},
    'c': {'W': 'e', 'R': 'bf'},
    'd': {'W': 'aeg', 'R': 'bh'},
    'e': {'W': 'acgi', 'R': 'bdfh'},
    'f': {'W': 'cei', 'R': 'bh'},
    'g': {'W': 'e', 'R': 'dh'},
    'h': {'W': 'egi', 'R': 'df'},
    'i': {'W': 'e', 'R': 'fh'},
}

def routes(current, path):
    if not path:
        yield (current,)
        return
    first, *newpath = path
    for state in switch[current][first]:
        for route in routes(state, newpath):
            yield (current,) + route

def chess(path):
    print('Path:', path)
    for i, r in enumerate(routes('a', path), 1):
        print('Route', i, end=': ')
        print(*r, sep=', ')
    print()

# tests

chess('WR')
chess('WWW')
chess('RRR')

output

Path: WR
Route 1: a, e, b
Route 2: a, e, d
Route 3: a, e, f
Route 4: a, e, h

Path: WWW
Route 1: a, e, a, e
Route 2: a, e, c, e
Route 3: a, e, g, e
Route 4: a, e, i, e

Path: RRR
Route 1: a, b, d, b
Route 2: a, b, d, h
Route 3: a, b, f, b
Route 4: a, b, f, h
Route 5: a, d, b, d
Route 6: a, d, b, f
Route 7: a, d, h, d
Route 8: a, d, h, f

Note that we can pass a string, tuple or list as the path arg of routes. The assignment

first, *newpath = path

splits off the first item from the path, the subsequent items are assigned to newpath in the form of a list. That syntax works on recent Python 3 version; on earlier Python versions you will need to change that line to

first, newpath = path[0], path[1:]