DjangoBB LoFi version

Полная версия: проверка последовательности равных целых чисел в квадратной матрице

Начало » Python для новичков » проверка последовательности равных целых чисел в квадратной матрице

1 2

Silentium

Апрель 15, 2015 15:08:51

Есть матрица NxN где 4<=N<=10. Как проверить есть ли в ней последовательность 4х одинаковых чисел по горизонтали, вертикали и в главных и дополнительных диагоналях?
Например матрица:

 a=([
    [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

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

terabayt

Апрель 15, 2015 15:33:16

а это зачем?

 == True

Silentium
просто натолкнуть на мысль с чего начать построение алгоритма

Silentium
пробегать по строкам, столбцам и диагоналям

по-простому делаете 4 цикла и просматриваете по горизонтали и т.д.

Silentium
главных и дополнительных

главная и дополнительная они по одной!

Silentium
чтобы мне не громоздить огромный говнокод

ну вы напишите свой код, пото подуайте как его оптимизировать и покажите нам, а мы что-то исправим, что-то подскажем или напишем как будет лучше

py.user.next

Апрель 15, 2015 23:52:11

Silentium
Как проверить есть ли в ней последовательность 4х одинаковых чисел по горизонтали, вертикали и в главных и дополнительных диагоналях?

Нужно написать одну функцию поиска 4-х одинаковых элементов в последовательности и передавать в неё сначала каждую строку, потом каждый столбец, а потом каждую диагональ.

Silentium

Апрель 16, 2015 15:03:28

Нужно написать одну функцию поиска 4-х одинаковых элементов в последовательности и передавать в неё сначала каждую строку, потом каждый столбец, а потом каждую диагональ.

Попробовал что-то типа:

def matrix(a):
    x = 0
    
    n=len(a)
    m=len(a[x])
    fl=0
    # compare rows
    for x in range(n-1):
        for a1,a2 in [(a[x][i],a[x][i+1]) for i in range(m-1)]:
            if a1==a2:
                fl+=1
            if fl==3:
                return True
        fl=0 
     # compare cols   
    for x in range(n-1):
        for a1,a2 in [(a[i][x],a[i+1][x]) for i in range(m-1)]:
            if a1==a2:
                fl+=1
            if fl==3:
                return True
        fl=0 
    #compare general diag
    for x in range(n-1):
        for a1,a2 in [(a[i][i],a[i+1][i+1]) for i in range(m-1)]:
            if a1==a2:
                fl+=1
            if fl==3:
                return True
        break
        fl=0 
return False
if __name__ == '__main__':
    assert matrix([[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

Всю голову сломал с обратной диагональю. Можете подсказать как осуществить row+1 и col-1 за один проход? Я понимаю что все крутится около range, но всеже как осуществить проверку в дополнительных диагоналях? Прошу сильно не ругать, я только осваиваюсь. Ну и возможно есть более простой и короткий способ решения?!

terabayt

Апрель 17, 2015 03:57:33

def f(a):
    for i in a:
        for j, k in enumerate(i[:-3]):
            if all(l == k for l in i[j+1: j+4]):
                return True
def d(a):
    return [[a[i][i] for i in range(len(a))]]
def matrix(a):
    return f(a) or f(zip(*a)) or f(d(a)) or f(d(a[::-1])) or False

по вашему коду:
1) он даже не запускается!
2)

if a1==a2:
    fl+=1
if fl==3:
    return True

это неправильно
если будет строка

[1, 1, 1, 7, 1, 1, 1]

ваш код выдаст True

а что вы подразумеваете под “главных диагоналях”? диагонали две
главная и дополнительная!
ОДНА главная и ОДНА дополнительная

Silentium

Май 5, 2015 15:51:55

terabayt
по вашему коду:
1) он даже не запускается!

Сори, забыл объявить в коде x=0

terabayt
а что вы подразумеваете под “главных диагоналях”? диагонали две
главная и дополнительная!
ОДНА главная и ОДНА дополнительная

я имею ввиду что должно выполняться например условие

a= ([
    [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

где начиная со второго списка-элемента и до предпоследнего создается диагональ из пятерок
[1, 1, 7, 3, 1, 5],
[2, 3, 1, 2, 5, 1],
[1, 1, 1, 5, 1, 4],
[4, 6, 5, 1, 3, 1],

+ не могли бы Вы пояснить про функцию f(a) , новичку трудно представить что и как она делает.

kampella

Май 8, 2015 21:43:33

Вам нужно использовать numpy библиотеку для таких вычислений.

sander

Май 9, 2015 00:28:39

kampella
зачем numpy? потому что кто то где то слышал, что numpy может в матрицы?

doza_and

Май 9, 2015 09:57:49

sander
что numpy может в матрицы

Какая прелесть! Можно я это на литературный факультет МГУ отправлю?

В numpy будет проще указанные объекты выделить.
http://docs.scipy.org/doc/numpy/reference/generated/numpy.diagonal.html

def chk(v):
     return 4 in dict(Counter(v)).values()
a=numpy.array(input_list)
for i in a:
    chk(i)
for i in a.T:
    chk(i)
chk(a.diagonal())
chk(numpy.flipud(a).diagonal())

sander

Май 9, 2015 13:57:35

doza_and
задача с checkio, там нет numpy, все задачи решаются с помощью стандартной библиотеки