Как вывести все диагонали шириной в две клетки на матрице на Python?
Мне нужно написать программу, чтобы можно было найти все диагонали по рисунку ниже.
У меня имеется матрица, и из неё нужно записать в отдельный массив по значений цвета\света все диагонали в матрице по углам что ниже на картинке. Для каждой диагонали скорее всего нужна своя функция.То есть нужно проходя по строкам, а после и столбцам находить диагональ и добавлять её в свой массив для диагоналей. В итоге будет 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
Подскажите, как можно либо доработать, либо переписать функции для данной задачи.
В результате должно получиться вот по такой схеме:
где каждая диагональ является отдельным массивом, а все диагонали нужно записать в отдельный массив и будет массив с массивами.
Ответы (3 шт):
Делаете список перемещений на три шага
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]
Чтобы найти диагонали, нам достаточно простой тригонометрии. Диагональ у нас - это гипотенуза прямоугольного треугольника.
Поэтому чтоб определить координаты нужной ячейки, можно воспользоваться формулой:
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]]
]
Если наклон диагоналей гарантировано 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