Перебирайте элементы многомерного массива и находите соседей - нет numpy или импорт - PullRequest
0 голосов
/ 08 марта 2020

В python как мне пройти по элементам многомерного массива и найти его соседей без использования numpy или каких-либо импортов, только рекурсия? Например, minesweeper_board = [[[0, 'b'], [0, 0], [0, 0]], [[0, 0], [0, 0], ['b', 0]], [[0, 0], [0, 0], [0, 0]], [[0, 0], [0, 0], [0, 0]]] с 'b', отмечающим бомбу, и я хочу обновить количество бомб вокруг каждого из нулей (как в игре тральщика).

1 Ответ

1 голос
/ 09 марта 2020

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

minesweeper_board = [ [ [0, 'b'], [0, 0], [0, 0]   ],
                      [ [0, 0],   [0, 0], ['b', 0] ],
                      [ [0, 0],   [0, 0], [0, 0]   ],
                      [ [0, 0],   [0, 0], [0, 0]   ]
                    ]

rows      = 4
cols      = 3
offsets   = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]

def inBoard(r,c): return r in range(rows) and c in range(cols)

def getNeighbours(r,c): return [(r+v,c+h) for v,h in offsets if inBoard(r+v,c+h)] 

links = { (r,c):getNeighbours(r,c) for r in range(rows) for c in range(cols) }

, используя словарь ссылок:

for (r,c),neighbours in links.items():
    bombCount = sum('b' in minesweeper_board[nr][nc] for nr,nc in neighbours) 
    if bombCount:
        print(f"there are {bombCount} bombs near {(r,c)}")

вывод:

there are 2 bombs near (0, 1)
there are 1 bombs near (0, 2)
there are 1 bombs near (1, 0)
there are 2 bombs near (1, 1)
there are 1 bombs near (2, 1)
there are 1 bombs near (2, 2)

[EDIT] Обобщение для многомерных плат.

Я изначально неправильно понял вопрос, но вышеприведенное решение можно обобщить, создав рекурсивные функции доступа n-размерности. Структура списка или списков Python не подходит для индексации по нескольким измерениям: board[1][2][3] немного громоздка по сравнению с board[1,2,3] numpy, но мы можем компенсировать это, используя функции (или создавая совершенно новый класс, который будет больше работы):

# access the value at a specific coordinate
def getCell(board,pos,*rest):
    return getCell(board[pos],*rest) if rest else board[pos]

# assign the value at a specific coordinate
def setCell(board,pos,*rest,value):
    if rest : setCell(board[pos],*rest,value=value)
    else:     board[pos] = value 

# get the values of the cell and all its neighbours at a coordinate 
def getNeighbours(board,pos,*rest):
    for nPos in (pos-1,pos,pos+1):
        if nPos not in range(len(board)): continue
        if not rest: yield board[nPos]; continue
        for value in getNeighbours(board[nPos],*rest):
            yield value

# iterate over the whole board returning coordinates and values    
def iterate(board):
    if not isinstance(board,list): yield ([],board); return
    for i,subBoard in enumerate(board):
        for coord,value in iterate(subBoard):
            yield ([i] + coord,value)

# assign counts of nearby bombs to each coordinate that is not a bomb
def countBombs(board):
    for coord,value in iterate(board):
        if value == "b": continue
        count = [*getNeighbours(board,*coord)].count("b")
        setCell(board,*coord,value=count)

вывод:

minesweeper_board = [ [ [0, 'b'], [0, 0], [0, 0]   ],
                      [ [0, 0],   [0, 0], ['b', 0] ],
                      [ [0, 0],   [0, 0], [0, 0]   ],
                      [ [0, 0],   [0, 0], [0, 0]   ]
                    ]

countBombs(minesweeper_board)
print(minesweeper_board)

[
   [ [1, 'b'], [2, 2], [1, 1]   ],
   [  [1, 1],  [2, 2], ['b', 1] ],
   [  [0, 0],  [1, 1], [1, 1]   ],
   [  [0, 0],  [0, 0], [0, 0]   ]
]


getCell(minesweeper_board,1,2,0) # 'b'
getCell(minesweeper_board,1,1,1) # 2
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...