0

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

Вот код для основной и дополнительных диагоналей идущих сверху слева вниз направо:

    def finder(row,n):
       steck=[]
       for i in row:
          if not steck or steck==i:
             steck.append(i)
          else:
             if len(steck)>=n:
                break
             else:
                steck=[]
                steck.append(i)
       #print(len(steck)>=n)         
       return len(steck)>=n
    def horizontal(n,m):
       for row in m:
         if finder(row,n):
           return True
       return False
    def vertical(n,m):
       for col in zip(*m):
         if  finder(col,n):
            return True
       return False  
    def diagonal_dopoln_left(n,m):
       N=len(m)
       for counter in range(1,N):
          diag_len=N-counter
          list1=[m[i][i+counter] for i in range(diag_len)]
          print('list1',list1)
          list2=[m[i+counter][i] for i in range(diag_len)]
          print('list2',list2)      
          if finder(list1,n):
            return True
          if finder(list2,n):
            return True      
       return False 
    def diagonal_left(n,m):
       left_main_diag=[m[i][i] for i in range(len(m))]
       if finder(left_main_diag,n):
          return True 
       return False 
    def checkio(matrix):
      if diagonal_dopoln_left(4,matrix):
         return True
      return False




    if __name__ == '__main__':
       print(checkio([[11,12,14,17],
                      [14,15,16,10],
                      [10,18,12,11],
                      [10,81,12,11]
                ]))
       #Ответ:
       #list1 [14, 10]
       #list2 [10, 81]
       #list1 [17]
       #list2 [10]
       #False

Нашел дополнительные диагонали идущие сверху от основной которая идет справа сверху вниз таким кодом:

def finder(row,n):
    steck=[]
    for i in row:
        if not steck or steck==i:
            steck.append(i)
        else:
            if len(steck)>=n:
                break
            else:
                steck=[]
                steck.append(i)
    #print(len(steck)>=n)         
    return len(steck)>=n

def diagonal_right(n,m):
    left_main_diag=[m[i][-(i+1)] for i in range(len(m))]
    print('left_main_diag:',left_main_diag)
    if finder(left_main_diag,n):
        return True 
    return False 

def diagonal_dopoln_right(n,m):
    N=len(m)
    for counter in range(1,N):
        diag_len=N-counter
        list1=[m[i][-(i+counter)] for i in range(diag_len+1)]
        print('list1',list1)
        #list2=[m[i][-(i+1)] for i in range(diag_len+1)]
        #print('list2',list2)      
        #if finder(list1,n):
            #return True
        #if finder(list2,n):
            #return True      
    return False 


def checkio(matrix):
    n=4
    if diagonal_dopoln_right(n,matrix):
        return True
    return False

if __name__ == '__main__':
   print(checkio([[11,12,14,17],
                  [14,15,16,10],
                  [10,18,12,11],
                  [10,81,12,11]                               
                     ]))
   #Ответ:
   #list1 [17, 16, 18, 10]
   #list1 [14, 15, 10]
   #list1 [12, 14]
   #False 

Как найти такие диагонали снизу от основной, надо как-то правильно расставить индексы, пробовал по разному-return -1 )

2
  • При этом надо найти идущие строго подряд 4 и более элементов. - можете пояснить, что это значит? В диагонали среди элементов должны быть 4 или более последовательных числа?
    – user247581
    13 июн 2018 в 11:06
  • 1
    Да, в диагонали должны быть строго подряд идущие равные элементы(числа),у меня в коде это обеспечивает функция finder(),но мне нужно нижние диагонали от "правой основной" в списковую компановку list2 выделить. 13 июн 2018 в 15:24

1 ответ 1

0

Пусть есть произвольная матрица n x n. Рассмотрим, чему равны суммы индексов на диагоналях, идущих из левого нижнего угла в правый верхний (иначе говоря, на побочных диагоналях). На рисунке у меня n == 3, в клетках записаны суммы индексов элемента. matrix

Можно увидеть, что для элементов, находящихся на самой длинной побочной диагонали сумма индексов равна n-1; номера строк при этом (в которых встречаются элементы из этой диагонали) идут в диапазоне [0, n-1]. Для тех побочных диагоналей, что стоят выше неё, сумма индексов меньше: для соседней - меньше на единицу, для следующей - на двойку и т.д. (сумма = n-1 - distance); номера строк, содержащих элементы этой диагонили, пробегают значения [0, n-1-distance] (distance - расстояние от самой длинной побочной диагонали до рассматривоемой, причём расстояние между соседними диагоналями понимается равным единице). Для диагоналей снизу от самой длинной сумма индексов наоборот возрастает (сумма = n-1 + distance), а номера строк, в которых стоят элементы из этих диагоналей, меняются как [distance, n-1]. Теперь можно легко написать функцию, которая найдёт все побочные диагонали, пробегаясь по строкам, в которых есть элементы для данной диагонали, получая номер столбца из номера строки:

def checkio_2(matrix):
    n = len(matrix)    # размер квадратной матрицы
    all_diags = []     # здесь будут храниться все найденные
                       #     побочные диагонали
    for distance in range(1, n):    # distance - расстояние от главной диагонали
        sum_tl = n - 1 - distance    # сумма индексов (верхний-левый угол)
        sum_br = n - 1 + distance    # сумма индексов (нижний-правый угол)
        all_diags.extend([
            [matrix[i][sum_tl - i] for i in range(n - distance)], # верх-лев диаг
            [matrix[i][sum_br - i] for i in range(distance, n)]   # ниж-прав диаг
        ])
    return all_diags    # возвращаем все побочные диагонали

Теперь встаёт вопрос фильтрации полученных значений. Насколько я могу судить, Ваша функция finder плоховато для этого подходит:

def finder(row,n):
    steck=[]
    for i in row:
        if not steck or steck==i:    # steck==i - сравнивать список и число
                                     #     вряд ли хорошая идея;
                                     #     к тому же, на нулевой итерации
                                     #     попадём сюда, т.к. not steck == True
            steck.append(i)          # теперь steck == [i, ]
        else:                        # на второй итерации идём сюда
            if len(steck)>=n:        # len(steck) == 1
                break
            else:                    # поэтому
                steck=[]             # опустошаем steck
                steck.append(i)      # теперь steck == [i, ] снова
                                     # и ходим по этой ветке
    return len(steck)>=n             # вернём False, ведь len(steck) == 1

То есть, независимо от того, что в найденных диагоналях, возвращается False. Я бы предложил сделать иначе (для произвольного n, где n - нужная длина последовательности идущих подряд возрастающих или убывающих элементов). Если нужно, чтоб поиск происходил лишь среди последовательных элементов диагонали, можно написать так:

def finder_2(row, n=4):
    for idx in range(len(row)-(n-1)):
        n_increasing = 0    # столько раз следующий элемент больше предыдущего
        n_decreasing = 0    # а столько раз - наоборот
        for i in range(idx, idx+n-1):
            if row[i+1] - row[i] == 1:    # возрастание
                n_increasing += 1
            elif row[i] - row[i+1] == 1:  # убывание
                n_decreasing += 1
        if n-1 in [n_increasing, n_decreasing]: # если все возрастают
                                                # или все убывают
            return True
    return False    # если не найдено строго монотонной 
                    # последовательности нужной длины

Таким образом, можно проверить с помощью finder_2 все найденные в checkio_2 диагонали. Если нужно проверить, есть среди элементов диагонали четыре (или произвольное n) число последовательных чисел, не обязательно встречающихся в самой диагонали подряд, нужно в finder_2 передавать отсортированную диагональ.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.