Блог

Главная - Вопросы по программированию - поиск L в таблице

поиск L в таблице

#python #algorithm

#python #алгоритм

Вопрос:

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

 [['*', '*', '.', '*', '*'],
 ['*', '*', '.', '*', '*'],
 ['*', '*', '.', '*', '*'],
 ['*', '*', '.', '*', '*'],
 ['*', '*', '.', '*', '*'],
 ['*', '*', '.', '*', '*'],
 ['*', '*', '.', '*', '*']]

in this matrix we have 8 L.(here's two Ls:[(0,0), (1,0), (2,0), (3,0), (3,1)], [(1,0), (2,0), (3,0), (4,0), (4,1)])
  
 [['*', '.', '.', '.', '.'],
 ['*', '.', '.', '.', '.'],
 ['*', '.', '.', '.', '.'],
 ['*', '*', '.', '.', '.'],
 ['*', '*', '.', '.', '.'],
]

in this matrix we have 2 L
  
 [['*', '.', '.', '.', '.'],
 ['*', '.', '.', '.', '.'],
 ['*', '.', '.', '.', '.'],
 ['*', '*', '.', '.', '.'],
]

just 1 L

и вот мой код, но я думаю, что в нем есть ошибка.

 L_counter = 0

def find_L(star_row, star_column):
    global my_list
    global L_counter

    if my_list[star_row 1][star_column] == '*':
        if my_list[star_row 2][star_column] == '*':
            if my_list[star_row 3][star_column] == '*':
                if my_list[star_row 3][star_column 1] == '*':
                    L_counter  = 1
                    

my_list = [['*', '*', '.', '*', '*'],
           ['*', '*', '.', '*', '*'],
           ['*', '*', '.', '*', '*'],
           ['*' ,'*', '.', '*', '*'],
           ['*', '*', '.', '*', '*'],
           ['*', '*', '.', '*', '*'],
           ['*', '*', '.', '*', '*']
           ]

for row, i  in enumerate(my_list[:-3]):
    for column, j in enumerate(i[:-1]):
        if j == '*':
            find_L(row, column)

print(L_counter)

Комментарии:

1. Итак, вы хотите определить прямые углы, начиная с ячейки и двигаясь вниз по соседям, а затем поперек? Пройдитесь по каждой ячейке, игнорируя последнюю строку и последние столбцы, спуститесь вниз и убедитесь, что у вас нет соседей слева, и если есть один под ним, проверьте, есть ли у него один под ним, иначе переместитесь вправо. Если вы разветвляетесь, вам придется учитывать каждую ветвь.

2. Что заставляет вас думать, что в нем есть ошибка? Была ли какая-то конкретная матрица, в которой произошел сбой?

3. find_L проверяет только четыре звезды, должно быть пять

4. было бы намного чище с массивами numpy. Фактически, это сведется к однострочной свертке. Дайте мне знать, если вам нужен пример

5. @tylerstoney есть сайт, на который мы отправили код. они протестировали код и сказали, что это неправильно, не объясняя причины. 🙁

Ответ №1:

Не так элегантно, как должно быть, но лучшее, что я мог бы сделать без numpy:

 # approach: look for the vertical 4-bar plus one star in the 'foot'
sum(foot=='*' and all(row[col_num]=='*' for row in rows)
    for rows in zip(*(my_list[j:] for j in range(4))) 
    for col_num, foot in enumerate(rows[-1][1:])
)