DjangoBB LoFi version

Полная версия: Поиск серий повторяющихся значений в 2-мерном списке

Начало » Python для новичков » Поиск серий повторяющихся значений в 2-мерном списке

lupanton

Апрель 30, 2018 16:41:18

Добра всем!
Никак не могу разобраться в задаче. Дана квадратная матрица размера NxN (4≤N≤10). Необходимо проверить есть ли здесь последовательность 4 или более одинаковых цифр. Последовательность должна неразрывно располагаться горизонтально, вертикально или по диагоналям (основным и дополнительным).
Входные данные: Матрица, как список (list) списков с целыми числами.
Выходные данные: Есть ли здесь последовательность, как булево значение (bool).
Предусловия:
0 ≤ len(matrix) ≤ 10
all(all(0 < x < 10 for x in row) for row in matrix)
Вот мое решение:

 def checkio(matrix):
    def podr(*args):
        for arg in args:
            if not arg:
                return 1
            else:
                prev = -1
                curr_rep_len = 0
                max_rep_len = 0
                element = arg[0]
                for element in arg:
                    if prev == element:
                        curr_rep_len += 1
                    else:
                        prev = element
                        max_rep_len = max(max_rep_len, curr_rep_len)
                        curr_rep_len = 1
                max_rep_len = max(max_rep_len, curr_rep_len)
            return max_rep_len
    def add(x, y):
        return list(map(lambda a, b: a + b, x, y))
    
    from collections import defaultdict
    d = defaultdict(list)
    d1 = defaultdict(list)
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if matrix[i][j] not in d:
                if matrix[i][j] not in d1:
                    d[matrix[i][j]].append((i,j))
                else:
                    d1[matrix[i][j]].append((i,j))
            else:
                d1[matrix[i][j]].append((i,j))
                p = (d.pop(matrix[i][j]))[0]
                d1[matrix[i][j]].append(p)
    #print('d:',d)
    print('d1:',d1)
    TF = []
    lst_X = []
    lst_Y = []
    for key, val in d1.items():
        #print(key,':', val)
        if len(val) >= 4:
            for tuple in val:
                x, y = tuple[0], tuple[1]
                #print('x=',x,'y=',y)
                lst_X.append(x)
                lst_Y.append(y)
        lst_all = add(lst_X, lst_Y)
        lst_all_100 = [100 for i in range(1,len(lst_all)) if lst_all[i]==lst_all[i-1]+2] 
        #print(lst_X)
        #print(lst_Y)
        #print(lst_all)
        #print(lst_all_100)
        if podr(sorted(lst_X)) >= 4 or podr(sorted(lst_Y)) >= 4 or podr(sorted(lst_all)) >= 4 or podr(sorted(lst_all_100)) >= 4:
            TF.append(True)
        else:
            TF.append(False)
        lst_X.clear()
        lst_Y.clear()
        lst_all.clear()
        lst_all_100.clear()
        #print(val,'lst_X=',lst_X)
        #print(val,'lst_Y=',lst_Y)
        #print(TF)
    if True in TF:
        return True
    else:
        return False
    
if __name__ == '__main__':
    #These "asserts" using only for self-checking and not necessary for auto-testing
    assert checkio([
        [1, 2, 1, 1],
        [1, 1, 4, 1],
        [1, 3, 1, 6],
        [1, 7, 2, 5]
    ]) == True, "Vertical"
    assert checkio([
        [7, 1, 4, 1],
        [1, 2, 5, 2],
        [3, 4, 1, 3],
        [1, 1, 8, 1]
    ]) == False, "Nothing here"
    assert checkio([
        [2, 1, 1, 6, 1],
        [1, 3, 2, 1, 1],
        [4, 1, 1, 3, 1],
        [5, 5, 5, 5, 5],
        [1, 1, 3, 1, 1]
    ]) == True, "Long Horizontal"
    assert checkio([
        [7, 1, 1, 8, 1, 1],
        [1, 1, 7, 3, 1, 5],
        [2, 3, 1, 2, 5, 1],
        [1, 1, 1, 5, 1, 4],
        [4, 6, 5, 1, 3, 1],
        [1, 1, 9, 1, 2, 1]
    ]) == True, "Diagonal"
    assert checkio([
        [1, 7, 6, 1, 8, 5, 1],
        [7, 1, 1, 7, 2, 8, 6],
        [5, 1, 1, 5, 8, 8, 3],
        [8, 6, 3, 1, 7, 6, 9],
        [9, 8, 9, 8, 1, 8, 2],
        [1, 7, 2, 4, 9, 3, 8],
        [9, 9, 8, 6, 9, 2, 6]
    ]) == False, "Test"

Рассуждал так: формирую словарь: ключ - значение элемента матрицы, значения - “координаты” соответствующего элемента, в словаре ищу соответствие располагающимся подряд значениям. Последний тест 7Х7 не проходит.
Насколько вообще целесообразен мой код?
Где ошибка?
Как можно сделать проще?

py.user.next

Апрель 30, 2018 17:20:32

lupanton
Как можно сделать проще?

Нужно сделать функцию, которая принимает список и минимальное количество повторов и возвращает истину, если в нём есть такое количество повторов.
А дальше нужно брать каждую строку матрицы и передавать в эту функцию.
А дальше нужно брать каждый столбец матрицы и передавать в эту функцию.
А дальше нужно брать каждую диагональ матрицы и передавать в эту функцию.

Внутри функции сортируешь список, потом выполняешь для него itertools.groupby() и потом в результате сравниваешь количество каждого элемента с переданным в функцию.

Rodegast

Апрель 30, 2018 17:49:22

Вот тебе пример того как можно это сделать. Для диагоналей доделай сам.

 >>> m = [[1,1,1,1,2],
...     [1,2,3,4,5],
...     [1,2,3,4,5],
...     [1,2,3,4,5],
...     [0,0,0,0,0]]
>>> def test(s):
...     return "111" in "".join(map(lambda (x,y): "1" if  x == y else "0", zip(s[1:], s[:-1])))
# Для строк
>>> any( test(x) for x in m )
True
# Для столбцов
>>> any( test([ m[x][y] for x in xrange(len(m)) ]) for y in xrange(len(m)) )
True

lupanton

Май 2, 2018 14:14:24

Написал код и он работает, но выглядит ужасно. Не разобрался еще как налету обработать диагонали в 1 строчку.

 def checkio(m):
    def podr(*args):
        for arg in args:
            if not arg:
                return 1
            else:
                prev = -1
                curr_rep_len = 0
                max_rep_len = 0
                element = arg[0]
                for element in arg:
                    if prev == element:
                        curr_rep_len += 1
                    else:
                        prev = element
                        max_rep_len = max(max_rep_len, curr_rep_len)
                        curr_rep_len = 1
                max_rep_len = max(max_rep_len, curr_rep_len)
            if max_rep_len >= 4:
                return True
            else:
                return False
    from collections import defaultdict
    a = defaultdict(list)
    b = defaultdict(list)
    c = defaultdict(list)
    d = defaultdict(list)
    for i in range(len(m)):
        for j in range(len(m[i])):
            a[i].append(m[i][j])
            b[i].append(m[j][i])
            for n in range(-len(m), len(m)):
                if i == j + n:
                    c[n].append(m[i][j])
            for n in range(0, len(m) * 2):
                if i + j == n:
                    d[n].append(m[i][j])
    rez = []
    #print(a)
    #print(b)
    #print(c)
    #print(d)
    for value in a.values():
        if len(value) > 3:
            #print(podr(value))
            rez.append(podr(value))
    for value in b.values():
        if len(value) > 3:
            #print(podr(value))
            rez.append(podr(value))
    for value in c.values():
        if len(value) > 3:
            #print(podr(value))
            rez.append(podr(value))
    for value in d.values():
        if len(value) > 3:
            #print(podr(value))
            rez.append(podr(value))
    if True in rez:
        return True
    else:
        return False
        
    
if __name__ == '__main__':
    #These "asserts" using only for self-checking and not necessary for auto-testing
    assert checkio([
        [1, 2, 1, 1],
        [1, 1, 4, 1],
        [1, 3, 1, 6],
        [1, 7, 2, 5]
    ]) == True, "Vertical"
    assert checkio([
        [7, 1, 4, 1],
        [1, 2, 5, 2],
        [3, 4, 1, 3],
        [1, 1, 8, 1]
    ]) == False, "Nothing here"
    assert checkio([
        [2, 1, 1, 6, 1],
        [1, 3, 2, 1, 1],
        [4, 1, 1, 3, 1],
        [5, 5, 5, 5, 5],
        [1, 1, 3, 1, 1]
    ]) == True, "Long Horizontal"
    assert checkio([
        [7, 1, 1, 8, 1, 1],
        [1, 1, 7, 3, 1, 5],
        [2, 3, 1, 2, 5, 1],
        [1, 1, 1, 5, 1, 4],
        [4, 6, 5, 1, 3, 1],
        [1, 1, 9, 1, 2, 1]
    ]) == True, "Diagonal"

Кроме того, что же это будет, если матрица 1000 Х 1000?