3X3棋盘上移动的 NFA的实现

I have the following chess board: enter image description here

每个方块都是一个状态,初始状态是“a”。

给定用户输入他想要移动的正方形的颜色,程序需要根据该输入找到所有可能的路线。

例如:如果输入为 W(白色),则从“a”到“e”。如果输入为 R(红色),则同时从“a”到“b”和“d”。另一个更复杂的示例:如果输入为 WR,则对于 W,我们从“a”到“e”,然后对于 R,从“e”到“b”,“d”,“f”和“h”。

我有以下 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 ())

开关是一个字典,其中包含用于板的每个状态(正方形)的单独函数。这些函数返回您可以根据某些输入移动到的状态字符串。

例如,对于状态 a:

 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

任何想法如何从矩阵中得到?

2

这个任务的完美 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')
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

请注意,我们可以将字符串,元组或列表作为routespatharg 传递。赋值

first, *newpath = path

从路径中拆分第一个项目,后续项目以列表的形式分配给 newpath。该语法适用于最新的 Python 3 版本;在早期的 Python 版本中,您需要将该行更改为

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

本站系公益性非盈利分享网址,本文来自用户投稿,不代表码文网立场,如若转载,请注明出处

(16)
使用“pointer-events:none”时添加CSS游标属性
上一篇
将单元格引用到不同工作表中的区域(formula to reference cell a1 from alpha workshe
下一篇

相关推荐

发表评论

登录 后才能评论

评论列表(11条)