Python. Как найти подматрицу в математической матрице?

Question

[whynoti]

Всем добрый вечер. В программе матрица считывается из файла. Суть задания в том, что надо найти непрерывную подматрицу, в которой находятся только нечетные цифры и на выход выписать:
количество элементов этой подматрицы
координату крайней левой верхней точки этой подматрицы (ряд, столбец)
координату крайней правой нижней точки этой подматрицы(ряд, столбец)

пример:

.
 1  9  2  8  6  1
 8  1 11  7  6  4
10 12  1  9 12 14
 8 10  3  5 17  8
 6  4 10 13 16 19

Вывод:
6 (количество элементов подматрицы)
1, 2 (крайняя левая верхняя)
3, 3 (крайняя правая нижняя)

Спасибо заранее. Буду благодарен любой помощи

Answer 1

[Dimonchik]

дальше сам

Answer 2

[TopestKek]

Если я ничего не упустил из условий, то ответ очевиден)
Надо сделать

a = matrix
print(len(a) * len(a[0]))
print('0, 0')
print(len(a), ', ', len(a[0]))

Если ответ не подходит, то надо дополнить условия

Comments

[whynoti]

ну, не совсем так, ведь по вашему решению он будет просто писать количество элементов в матрице, нулевую координату и количество строк и столбцов, а нужно, чтобы он внутри матрицы нашел подматрицу, в которой только нечетные числа и выписал количество элементов этой подматрицы, верхнюю левую координату, и правую нижнюю координату этой подматрицы
например:
если матрица
1 9 2 8 6 1
8 1 11 7 6 4
10 12 1 9 12 14
8 10 3 5 17 8
6 4 10 13 16 19

нужная нам подматрица это:
11 7
1 9
3 5

координаты верхней левой точки: 1, 2 (потому что начинается счет с 0)
координаты нижней правой точки:3, 3
количество элементов подматрицы:6

[TopestKek]

whynoti, В условии нет ни слова про только нечетные цифры. Там написано

самое большое количество нечетных цифр

Таким образом, мое решение верное

[whynoti]

TopestKek, прошу прощения, под то условие да, немного подкорректировал его

[TopestKek]

whynoti,

import numpy as np
arr = np.array([
    [1, 9, 2, 8, 6, 1],
    [8, 1, 11, 7, 6, 4],
    [10, 12, 1, 9, 12, 14],
    [8, 10, 3, 5, 17, 8],
    [6, 4, 10, 13, 16, 19],
])
max_val = (0, ((0, 0,), (0, 0)))

class GTFO(Exception):
    pass


def check(arr):
    for row in arr:
        for val in row:
            if val % 2 == 0:
                return False
    return True

for i in range(len(arr)):
    for j in range(len(arr[0])):
        try:
            for k in range(i, len(arr)):
                for l in range(j, len(arr[0])):
                    arr_slice = arr[i:k + 1, j:l + 1]
                    if check(arr_slice):
                        if len(arr_slice)*len(arr_slice[0]) > max_val[0]:
                            max_val = (len(arr_slice)*len(arr_slice[0]), ((i, j), (k, l)))
                    else:
                        if l == j:
                            raise GTFO
                        else:
                            break
        except GTFO:
            pass

print(max_val)
print(arr[max_val[1][0][0]:max_val[1][1][0]+1, max_val[1][0][1]:max_val[1][1][1]+1])

Хватай. Будут вопросы - спрашивай.
Numpy использую чтоб срез добыть
Вывод сам сделай в удобной форме)

[whynoti]

TopestKek, спасибо большое, если не сложно, пара вопросов:1)можно ли модуль numpy.array написать отдельной функцией (система куда сдаю не принимает какие-либо модули кроме sys) 2)как можно сделать, чтобы программа принимала на ввод файл с матрицей?Заранее спасибо

[TopestKek]

whynoti,
1) брр, ну раз numpy там нужен ради срезов, то вполне можно написать функцию, которая давала бы срез.
2) Ну это уж совсем) Это прям самые азы питона) Сделайте хоть что-нибудь сами))

[whynoti]

TopestKek, руки пока до написания отдельной функции не дошли, разбираюсь с кодом, такой вопрос: если считывать ввод с файла, то программа перестает производить вычисления из-за большого количества указателей, как с этим бороться?

заранее спасибо

[longclaps]

TopestKek, numpy - это хорошо, а вот хреновая асимптотика решения - это плохо.

m = [[1, 9, 2, 8, 6, 1],
     [8, 1, 11, 7, 6, 4],
     [10, 12, 1, 9, 12, 14],
     [8, 10, 3, 5, 17, 8],
     [6, 4, 10, 13, 16, 19]]
mm = [[0] * (len(m[0]) + 1)]
for row in m:
    r, t = [0], 0
    for i, x in enumerate(row, 1):
        t += x & 1
        r.append(t + mm[-1][i])
    mm.append(r)
res = []
for bottom in range(len(mm)):
    for right in range(len(mm[0])):
        for top in range(bottom):
            for left in range(right - 1, -1, -1):
                s = mm[bottom][right] + mm[top][left] - \
                    mm[top][right] - mm[bottom][left]
                if s == (bottom - top) * (right - left):
                    res.append((s, top, left, bottom, right))
                else:
                    break
s, top, left, bottom, right = max(res)
print("%d\n%d %d\n%d %d" % (s, top, left, bottom - 1, right - 1))
for row in m[top:bottom]:
    print(row[left:right])

[whynoti]

longclaps, а если вместо значения m надо ввод с файла сделать и он выдает

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

заранее спасибо

[longclaps]

whynoti, если тебе непонятен смысл сообщения об ошибке - может, ошибка в том, что ты взялся не за своё дело?

[whynoti]

longclaps, смысл сообщения об ошибке то мне понятен, мне не очень понятно как это исправить

[Nuta_nu]

whynoti,
на случай если не разобрался как открыть файл...
с остальным не помогу сама с этой домашкой бьюсь... хотя тебе подкинули хорошие варианты =)

matrix = []
file = sys.argv[1]
with open(file, 'r') as f:
    for line in f:
        matrix.append(list(map(int, line.split())))

или

matrix = []
f=open('rectangle.txt','r')
for line in f:
    matrix.append(list(map(int, line.split())))

[whynoti]

Nuta_nu, спасибо, но уже разобрался)тоже над этим заданием?

[Nuta_nu]

whynoti, да, зависла в середине кода не знаю как идти дальше, а придумывать заново алгоритм и писать снова не хочу

[whynoti]

Nuta_nu, ты с ЧВУТ что ли?

[Nuta_nu]

whynoti, да ) второй курс кир =)

[whynoti]

Nuta_nu, 1 курс кира)

[Nuta_nu]

найди меня на фб что ли ) Anna Sereda )

[TopestKek]

longclaps, красиво.
Это решение написано под текущую задачу или есть название методологии, по которому можно погуглить отдельно?

[longclaps]

TopestKek, не думаю, что есть какое-то спец. название, но видел множество олимпиадных задачек, в которых нужно именно обеспечить асимптотику - или не пролезешь по времени.

[TopestKek]

longclaps, не, про обеспечение асимптотики это понятно) Просто метод нахождения подматрицы интересный, я такое не смог придумать)

[longclaps]

TopestKek, чота стормознул - это можно назвать "динамическим программированием" - хотя это не самый типичный случай.

[TopestKek]

longclaps, благодарю

[longclaps]

TopestKek, захотел дать развёрнутый ответ в примерах )
1. Есть длинный массив l, надо ответить на 100500 запросов вида "сумма подмассива от lo до hi". Приём - создать массив частичных сумм [sum(l[:0]),sum(l[:1]),....sum(l[:-1]),sum(l)], это линейно и по времени и по памяти. Как называется приём - не знаю.
2. На прямую накидывают случайным образом отрезки и закрашивают черным, какова суммарная длина черного. Решение:
sum(отрезков)-sum(перекрытий отрезков)+sum(участков, накрытых в 3 слоя)-sum(...4 слоя)-...
Как называется приём - не знаю, у других нахватался, а коректность доказывается по индукции.