Форум программистов
 
О проблемах, например, с регистрацией пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail, а тут можно восстановить пароль.

Вернуться   Форум программистов > Скриптовые языки программирования > Python
Регистрация

Восстановить пароль
Повторная активизация e-mail

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Ответ
 
Опции темы
Старый 14.10.2020, 19:48   #1
Петр1992
Новичок
Джуниор
 
Регистрация: 14.10.2020
Сообщений: 2
Вопрос Задача на чтение матрицы по спирали с ограничениями на время и память

Добрый день!

Уже второй день бьюсь над следующей задачей:

Дан файл ".txt". Первая строка содержит целое нечётное число m в диапазоне от 1 до 1000 — количество строк и столбцов матрицы. В каждой из следующих m строк даны m целых чисел в диапазоне от -1000 до 1000, разделённых пробелом.
Необходимо прочитать значения матрицы по спирали, начиная от центра вверх и далее по часовой стрелке.


Язык - Python 3.7.3
Ограничение времени - 1.5 секунд
Ограничение памяти - 38Mb

Пример:
Ввод
3
9 10 7
0 7 7
8 3 4
Вывод
7
10
7
7
4
3
8
0
9

Из всех придуманных решений, прикладываю два наиболее удачных, однако оба решения не проходят либо по памяти, либо по времени

Решение 1 (не проходим по памяти)
Код:
rows = []
started = True
with open('input.txt', 'r') as file:
    for row in file:
        if started is True:
            n = int(row.strip())
            started = False
        else:
            rows.append(row.strip().split(' '))

result = []
circle = 0
center_point = int((n-1)/2)
for _ in range(center_point):
    left, right, upper, lower = [], [], [], []
    n_1_circle = n-1-circle
    
    for i in range(circle, n-circle):
        left.append(rows[i][circle])
        right.append(rows[i][n_1_circle])
        if i == circle:
            upper = rows[i][circle+1:n_1_circle]
        if i == n_1_circle:
            lower = rows[i][circle+1:n_1_circle]
    right.reverse()
    upper.reverse()
    
    result += left
    result += lower
    result += right
    result += upper

    circle += 1

result.append(rows[center_point][center_point])

result.reverse()
with open('output.txt', 'w') as file:
    file.write('\n'.join(result))
Решение 2 (не проходим по скорости)
Код:
with open('input.txt', 'r') as file:
    rows = file.readlines()
    
n = int(rows[0])
rows = [row.strip() for row in rows[1:]]

result = []
circle = 0
center_point = int((n-1)/2)
for _ in range(center_point):
    left, right, upper, lower = [], [], [], []
    n_1_circle = n-1-circle
    
    for i in range(circle, n-circle):
        temp = rows[i].split(' ')
        left.append(temp[circle])
        right.append(temp[n_1_circle])
        if i == circle:
            upper = temp[circle+1:n_1_circle]
        if i == n_1_circle:
            lower = temp[circle+1:n_1_circle]
    right.reverse()
    upper.reverse()
    
    result += left
    result += lower
    result += right
    result += upper

    circle += 1

result.append(rows[center_point].split(' ')[center_point])

result.reverse()
with open('output.txt', 'w') as file:
    file.write('\n'.join(result))
Очень прошу помочь найти правильное решение задачи.
Петр1992 вне форума Ответить с цитированием
Старый 14.10.2020, 21:08   #2
BDA
Модератор
Заслуженный модератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 5,718
По умолчанию

А так?
Код:
with open("input.txt", "r") as file:
    rows = file.readlines()    
n = int(rows[0])
rows = [row.strip().split(" ") for row in rows[1:]]
cp = (n - 1) // 2
with open("output.txt", "w") as file:
    file.write(rows[cp][cp] + "\n")
    for i in range(1, cp + 1):
        l, r = cp - i, cp + i
        for j in range(l + 1, r + 1):
            file.write(rows[l][j] + "\n")
        for j in range(l + 1, r + 1):
            file.write(rows[j][r] + "\n")
        for j in range(r - 1, l - 1, -1):
            file.write(rows[r][j] + "\n")
        for j in range(r - 1, l - 1, -1):
            file.write(rows[j][l] + "\n")
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )

Последний раз редактировалось BDA; 14.10.2020 в 21:13.
BDA на форуме Ответить с цитированием
Старый 14.10.2020, 21:31   #3
Петр1992
Новичок
Джуниор
 
Регистрация: 14.10.2020
Сообщений: 2
По умолчанию

BDA,
Решение не проходит по памяти
Петр1992 вне форума Ответить с цитированием
Старый 15.10.2020, 03:46   #4
BDA
Модератор
Заслуженный модератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 5,718
По умолчанию

Если судить по замерам memory_profiler и timeit, то должно укладываться в лимиты. Можно код причесать покрасивее.
Код:
with open("input.txt", "r") as file:
    rows = file.readlines()    
n = int(rows[0])
rows = [row.strip() for row in rows[1:]]
cp = (n - 1) // 2
substrs = [""]
for i in range(cp + 1):
    spl_row = rows[i].split(" ")
    substrs[0] = spl_row[0] + "\n" + substrs[0]
    if i == 0:
        substrs.append("\n".join(spl_row[i + 1:]))
    elif i < cp:
        substrs.append("\n".join(spl_row[i + 1:-i]))
    for j in range(1, i + 1):
        substrs[j] = spl_row[j] + "\n" + substrs[j] + "\n" + spl_row[-j]
for i in range(cp + 1, n):
    spl_row = rows[i].split(" ")
    k = n - i - 1
    if k > 0:
        substrs[-2] = substrs[-1] + "\n" + "\n".join(spl_row[i:k - 1:-1]) + "\n" + substrs[-2]
    else:
        substrs[-2] = substrs[-1] + "\n" + "\n".join(spl_row[::-1]) + "\n" + substrs[-2]
    substrs.pop()
    for j in range(k):
        substrs[j] = spl_row[j] + "\n" + substrs[j]
        substrs[j + 1] = substrs[j + 1] + "\n" + spl_row[-j - 1]
with open("output.txt", "w") as file:
    file.write(substrs[0])
Например:
Код:
with open("input.txt", "r") as file:
    n = int(file.readline())
    cp = (n - 1) // 2
    substrs = [""]
    for i, row in enumerate(file): 
        spl_row = row.strip().split(" ")
        if i == 0:
            substrs[0] = spl_row[0] + "\n" + substrs[0]
            substrs.append("\n".join(spl_row[i + 1:]))
        elif i < cp + 1:
            substrs[0] = spl_row[0] + "\n" + substrs[0]
            if i < cp:
                substrs.append("\n".join(spl_row[i + 1:-i]))
            for j in range(1, i + 1):
                substrs[j] = spl_row[j] + "\n" + substrs[j] + "\n" + spl_row[-j]
        elif i < n - 1:
            k = n - i - 1
            substrs[-2] = substrs[-1] + "\n" + "\n".join(spl_row[i:k - 1:-1]) + "\n" + substrs[-2]
            substrs.pop()
            for j in range(k):
                substrs[j] = spl_row[j] + "\n" + substrs[j]
                substrs[j + 1] = substrs[j + 1] + "\n" + spl_row[-j - 1]
        elif i == n - 1:
            substrs[-2] = substrs[-1] + "\n" + "\n".join(spl_row[::-1]) + "\n" + substrs[-2]
            substrs.pop()
    with open("output.txt", "w") as file:
        file.write(substrs[0])
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )

Последний раз редактировалось BDA; 15.10.2020 в 06:29.
BDA на форуме Ответить с цитированием
Ответ

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Опции темы


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Обход матрицы по спирали pal_palich Паскаль, Turbo Pascal, PascalABC.NET 5 28.03.2017 13:24
Задача ЛП с двусторонними ограничениями ibisx Фриланс 1 19.12.2011 18:10
Задача ЛП с двусторонними ограничениями ibisx Помощь студентам 0 16.12.2011 18:06
вывод матрицы по спирали С++ Poccoxa Помощь студентам 1 29.10.2010 17:37
Чтение матрицы по спирали AlexLAN Общие вопросы C/C++ 1 21.12.2008 07:50


Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru
Пеллетный котёл Emtas
котлы EMTAS
Здесь нужно купить рекламу за 7 тыс руб в месяц! )
пишите сюда - alarforum@yandex.ru
ИКС 840