Как вывести все диагонали шириной в две клетки на матрице на Python?

Question

Как вывести все диагонали шириной в две клетки на матрице на Python?

Рейтинг: 3Ответов: 3Опубликовано: 13.04.2023

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

У меня имеется матрица, и из неё нужно записать в отдельный массив по значений цвета\света все диагонали в матрице по углам что ниже на картинке. Для каждой диагонали скорее всего нужна своя функция.То есть нужно проходя по строкам, а после и столбцам находить диагональ и добавлять её в свой массив для диагоналей. В итоге будет 4 массива в каждом из которых будет храниться свои значения для диагоналей.

Я смог найти, как находятся все обычные диагонали в матрице, но с такими не особо понимаю как работать.

Такой функцией я пользовался для нахождения всех обычных диагоналей слева направо:

def print_kolvos(arr):
    rows = len(arr)
    cols = len(arr[0])
    kolvo =[]
    kolvo1 =[]
    for i in range(rows):
        j = 0
        while i + j < rows and j < cols:
            kolvo.append(arr[i+j][j])
            j += 1
        kolvo1.append(kolvo)
        kolvo = []
    for j in range(1, cols):
        i = 0
        while i + j < cols and i < rows:
            kolvo.append(arr[i][i+j])
            i += 1
        kolvo1.append(kolvo)
        kolvo = []


    return kolvo1

Такой - справа налево:

def print_kolvos_reverse(arr):
    rows = len(arr)
    cols = len(arr[0])

    kolvo1 =[]

    for i in range(rows + cols - 1):
        kolvo =[]
        for j in range(cols):
            row = i - j
            col = j

            if 0 <= row < rows and 0 <= col < cols:
                kolvo.append(arr[row][col])
        kolvo1.append(kolvo)
    return kolvo1

Подскажите, как можно либо доработать, либо переписать функции для данной задачи.

В результате должно получиться вот по такой схеме:

где каждая диагональ является отдельным массивом, а все диагонали нужно записать в отдельный массив и будет массив с массивами.

python

Источник: Stack Overflow на русском

Answer 1

▲ 2Принят

Если наклон диагоналей гарантировано 2 к 1, можно сделать так:

def create_mtrx(n, m):
    return [[i * m + j for j in range(1, m + 1)] for i in range(n)]

def print_mtrx(mtrx, wdth=3):
    for row in mtrx:
        print("".join(f"{col: >{wdth}}" for col in row))

def find_diag_values(x, mtrx):
    lft_rght = []
    rght_lft = []
    for y in range(0, len(mtrx), 2):
        lft_rght.append(mtrx[y][x])
        lft_rght.append(mtrx[y + 1][x])

        rght_lft.append(mtrx[y][-(x + 1)])
        rght_lft.append(mtrx[y + 1][-(x + 1)])
        x += 1
    return lft_rght, rght_lft
        

mtrx = create_mtrx(8, 8)
print_mtrx(mtrx)
print("#" * 50)

# Отступ по оси x до начала диагонали
start_x = 2

vertical_diags_values = find_diag_values(start_x, mtrx)
# Чтобы не создавать отдельную функции для нахождения горизонтальных диагоналей
# передаём в функцию матрицу повёрнутую на 90°.
horizontal_diags_values = find_diag_values(start_x, list(zip(*mtrx)))

print("lft_rght", vertical_diags_values[0])
print("rght_lft", vertical_diags_values[1])
print("top_btm ", horizontal_diags_values[0])
print("btm_top ", horizontal_diags_values[1])

Output

Вариант функции `find_diag_values` для всех возможных диагоналей

Вертикальные диагонали:

И также горизонтальные - рисовать не стал.

def find_diag_values(mtrx):
    n, m = len(mtrx), len(mtrx[0])
    left_ans = []
    right_ans = []

    diag_begin_x = -(n // 2 - 1) 
    for diag_begin_y in range(1, n // 2 + m):
        left = []
        right = []
        x = max(diag_begin_x, 0)
        for y in range(max(n - diag_begin_y * 2, 0), n, 2):
            if x >= m:
                break
            left.append(mtrx[y][x])
            left.append(mtrx[y + 1][x])

            right.append(mtrx[y][-(x + 1)])
            right.append(mtrx[y + 1][-(x + 1)])

            x += 1
        left_ans.append(left)
        right_ans.append(right)
        diag_begin_x += 1

    return left_ans, right_ans

Тесты

tests = [
    (8, 8),
    (4, 4),
    (6, 2),
    (2, 6),
    (2, 2),
]
for r, c in tests:
    mtrx = create_mtrx(r, c)
    print("#" * 50)
    print_mtrx(mtrx)
    print("#" * 50)
    print()

    vertical_diags_values = find_diag_values(mtrx)
    horizontal_diags_values = find_diag_values(list(zip(*mtrx)))

    print("lft_rght", *vertical_diags_values[0], "\n", sep="\n", end="")
    print("rght_lft", *vertical_diags_values[1], "\n", sep="\n", end="")
    print("top_btm ", *horizontal_diags_values[0], "\n", sep="\n", end="")
    print("btm_top ", *horizontal_diags_values[1], "\n", sep="\n", end="")

Более прямолинейный вариант с использованием дополнительной памяти и без использования max():

def find_diag_values(mtrx):
    n, m = len(mtrx), len(mtrx[0])
    left_ans = []
    right_ans = []

    start_coords = [(y, 0) for y in reversed(range(0, n, 2))]
    start_coords += [(0, x) for x in range(1, m)]

    for s_y, s_x in start_coords:
        x = s_x 
        left = []
        right = []
        for y in range(s_y, n, 2): 
            if x >= m:
                break

            left.append(mtrx[y][x])
            left.append(mtrx[y + 1][x])

            right.append(mtrx[y][-(x + 1)])
            right.append(mtrx[y + 1][-(x + 1)])
            x += 1

        left_ans.append(left)
        right_ans.append(right)

    return left_ans, right_ans

Answer 2

▲ 1

Чтобы найти диагонали, нам достаточно простой тригонометрии. Диагональ у нас - это гипотенуза прямоугольного треугольника.

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

y = x * math.tan(angle)
# поскольку нам нужна ячейка под диагональю меняем на:
y = math.floor(x * math.tan(angle))

Мы знаем пропорции для диагонали 1,2 - это катеты. Угол легко вычислить из катетов:

d_shape = [1, 2]
a_b = d_shape[0] / d_shape[1]
angle = math.atan(a_b)

НО, как видно из кода выше, мы можем сократить tan и atan в вычислениях и использовать только пропорцию a_b:

y = math.floor(x * a_b)

Получаем диагонали из начала координат:

for j in range(size):
    i = math.floor(j * a_b)
    # vert diagonal
    starter_diagonals['vert'].append([i, j])
    # hor diagonal
    starter_diagonals['hor'].append([j, i])

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

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

end_coord = math.ceil((size - 1) * a_b)

# все диагонали слева направо
# просто смещаем их на 1 вправо
l_to_r = []
l_to_r.append(starter_diagonals['hor'])

for i in range(1, size - end_coord):
    tmp = []
    for x in range(size):
        tmp.append([starter_diagonals['hor'][x][0], starter_diagonals['hor'][x][1] + i])
    l_to_r.append(tmp)


# та же логика самое и для сверху вниз

Чтобы получить диагонали снизу вверх и справа налево, нам надо просто развернуть уже полученные:

# получить направления снизу вверх и справа налево
# просто разворачиваем уже посчитанные диагонали
r_to_l = []
for vals in l_to_r:
    tmp = []
    for val in vals:
        tmp.append([val[0], size - 1 - val[1]])
    r_to_l.append(tmp)

# та же логика и для снизу вверх

Ну и останется еще получить диагонали из нижнего угла, но там всё та-же логика. *

Итог

import math

size = 4
mat = []

val = 1
for i in range(size):
    row = []
    for j in range(size):
        row.append(val)
        val += 1
    mat.append(row)

d_shape = [1, 2]
a_b = d_shape[0] / d_shape[1]

# Получаем диагонали из начала координат
starter_diagonals = {'hor': [], 'vert': []}
for j in range(size):
    i = math.floor(j * a_b)
    # vert diagonal
    starter_diagonals['vert'].append([i, j])
    # hor diagonal
    starter_diagonals['hor'].append([j, i])

end_coord = math.floor((size - 1) * a_b)
# все диагонали слева направо
# просто смещаем их на 1 вправо
l_to_r = []
l_to_r.append(starter_diagonals['hor'])

for i in range(1, size - end_coord):
    tmp = []
    for x in range(size):
        tmp.append([starter_diagonals['hor'][x][0], starter_diagonals['hor'][x][1] + i])
    l_to_r.append(tmp)

# все диагонали сверху вниз
# просто смещаем на 1 вниз
t_to_b = []
t_to_b.append(starter_diagonals['vert'])

for i in range(1, size - end_coord):
    tmp = []
    for x in range(size):
        tmp.append([starter_diagonals['vert'][x][0] + i, starter_diagonals['vert'][x][1]])
    t_to_b.append(tmp)

# получить направления снизу вверх и справа налево
# просто разворачиваем уже посчитанные диагонали
r_to_l = []
for vals in l_to_r:
    tmp = []
    for val in vals:
        tmp.append([val[0], size - 1 - val[1]])
    r_to_l.append(tmp)

b_to_t = []
for vals in t_to_b:
    tmp = []
    for val in vals:
        tmp.append([val[0], size - 1 - val[1]])
    b_to_t.append(tmp)

print(l_to_r)
print(r_to_l)
print(t_to_b)
print(b_to_t)

## output:
[
    [[0, 0], [1, 0], [2, 1], [3, 1]],
    [[0, 1], [1, 1], [2, 2], [3, 2]],
    [[0, 2], [1, 2], [2, 3], [3, 3]]
]
[
    [[0, 3], [1, 3], [2, 2], [3, 2]],
    [[0, 2], [1, 2], [2, 1], [3, 1]],
    [[0, 1], [1, 1], [2, 0], [3, 0]]
]
[
    [[0, 0], [0, 1], [1, 2], [1, 3]], 
    [[1, 0], [1, 1], [2, 2], [2, 3]],
    [[2, 0], [2, 1], [3, 2], [3, 3]]
]
[
    [[0, 3], [0, 2], [1, 1], [1, 0]],
    [[1, 3], [1, 2], [2, 1], [2, 0]],
    [[2, 3], [2, 2], [3, 1], [3, 0]]
]

Answer 3

▲ 0

Делаете список перемещений на три шага

dir = [[[1, 0], [1, 0], [0, 1]], [[1, 0], [0, 1], [0, 1]]...]

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

Заметьте, что в порядке обхода ячеек есть неоднозначность. Для любого направления - три варианта.

Для одного направления:

for i in range(много):
    imod = i % 3
    x += dir[0][imod][0]
    y += dir[0][imod][1]
    if за пределами  решетки: break
    использовать a[y][x]

Как вывести все диагонали шириной в две клетки на матрице на Python?

Ответы

Вариант функции find_diag_values для всех возможных диагоналей

Итог

Вариант функции `find_diag_values` для всех возможных диагоналей