Реализация NFA для ходов на шахматной доске 3X3

Question

У меня есть следующая шахматная доска:

Каждый квадрат - это состояние. Начальное состояние - "а".

Учитывая пользовательский ввод цвета квадратов, куда он хочет переместиться, программе необходимо найти все возможные маршруты в соответствии с этим вводом.

Например: если ввод W (для белого), мы переходим от "а" к "е". И если на входе R (для красного), мы переходим от "a" к "b" и "d" одновременно. Еще один более сложный пример: если ввод WR, мы переходим от "a" к "e" для W, затем от "e" к "b", "d", "f" и "h" для R одновременно,

У меня есть следующая программа Python:

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 ())

Переключатель представляет собой словарь, который содержит отдельные функции для каждого состояния (квадрата) платы. Эти функции возвращают строку состояний, в которые вы можете перейти в соответствии с некоторыми входными данными.

Например для состояния а:

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

Шахматная функция печатает матрицу, содержащую состояния следующим образом: для ввода WR она дает следующий вывод:

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

Пока все хорошо, но мне нужно, чтобы все маршруты разошлись. Для того же ввода у меня должен быть следующий вывод:

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

Есть идеи, как получить это из матрицы?

Answer 1

Идеальным устройством Python для этой задачи является рекурсивный генератор. Задача явно рекурсивная, и генератор идеален, когда вам нужна функция, которая может дать несколько решений. Поначалу рекурсивные генераторы могут показаться немного сложными, но им, безусловно, стоит потратить время, необходимое для ознакомления с ними, если вы хотите выполнять этот тип работы с конечным автоматом.

Для хранения данных о состоянии я использую словарь словарей. Я мог бы написать код для создания этой структуры данных, но я решил, что быстрее будет просто жестко закодировать его. Это, вероятно, не будет иметь место с большей матрицей.;)

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')

выход

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

Обратите внимание, что мы можем передать строку, кортеж или список в качестве path аргумент routes, Назначение

first, *newpath = path

отделяет первый элемент от пути, последующие элементы назначаются newpath в виде списка. Этот синтаксис работает в последней версии Python 3; в более ранних версиях Python вам нужно будет изменить эту строку на

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