Как можно вращать фигуры

Question

У меня есть txt файл, который содержит

5
5
6 0 4 0 5 -1 5 -1 4
5 4 2 4 1 4 0 3 1 3 2 3 0 2 1 2 0
2 6 4 7 4 7 3
3 -2 9 -3 9
4 7 10 8 10 8 11 9 10 6 10 5 10
1 4 14 4 13

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

Например, фигура цветом 6 имеет форму квадрата 2х2

[6, 6, 0, 0, 0]
[6, 6, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]

Фигура цветом 5 имеет форму

[5, 5, 0, 0, 0]
[5, 5, 5, 0, 0]
[5, 5, 5, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]

Вот код, он помещает все фигуры

import copy


filename = 'stones.txt'
with open(filename, 'r') as f:
    n_row = int(f.readline().strip())
    n_col = int(f.readline().strip())
    st = [[*map(int, l.split())] for l in f.readlines()]

def tetr(matr, stones):
    if not stones:
        return matr
    c, *coords = stones.pop()
    f = lambda x,y: [i-y for i in x]
    row, col = f(coords[::2],min(coords[::2])), f(coords[1::2],min(coords[1::2]))
    
    for x in range(n_row-len(set(row))+1):
        for y in range(n_col-len(set(col))+1):
            if all(matr[i+x][j+y]==0 for i,j in zip(row,col)):
                matr2 = [m.copy() for m in matr]
                for i,j in zip(row,col):
                    matr2[i+x][j+y] = c
                res = tetr(matr2, stones.copy())
                if res:
                    return res
    return None

field = [[0]*n_col for _ in range(n_row)] 
res = tetr(field, st)

print(*res or ['Нет вариантов'], sep = '\n')

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

Как вариант, можно попробовать вот эти камни

5
5
1 13 0 13 1 13 -1 13 2
2 3 -2 3 -1 2 -2 2 -3 3 -3 2 -4 4 -1 2 -1 2 0 3 0 4 0 4 -2 4 -3 5 0
3 -3 10 -2 11 -1 10 -3 11 -2 10 -1 11 0 10

Answer 1

Пишем функцию вращения фигуры:

def get_variants_with_rotation(row, col):
    mr, mc = max(row), max(col)
    variants = set(map(tuple, map(sorted, zip(*(((x,y), (y,mr-x), (mr-x,mc-y), (mc-y,x)) for x, y in zip(row,col))))))
    return list(map(lambda x: tuple(zip(*x)), variants))

Сначала определяем максимумы по x и y. Они будут нужны чтобы сдвигать повёрнутые фигуры к началу координат.
Затем генерируем пары координат каждой части фигуры в четырёх положениях (с поворотом 0°, 90°, 180° и 270°), группируем в 4 фигуры, в каждой фигуре сортируем пары координат и при помощи set оставляем только уникальные фигуры (ибо, к примеру, квадрат сколько не крути, он квадратом и останется).
Ну и возвращаем список фигур, где пары координат опять разбиты на два подсписка row,col, как было на входе функции.

Теперь осталось добавить ещё один цикл по вариантам:

    for row, col in get_variants_with_rotation(f(coords[::2],min(coords[::2])), 
                                               f(coords[1::2],min(coords[1::2]))):

вместо строки row, col = f(coords[::2],min(coords[::2])), f(coords[1::2],min(coords[1::2])).

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

[1, 1, 1, 1, 2]
[3, 3, 2, 2, 2]
[3, 3, 2, 2, 2]
[3, 3, 2, 2, 2]
[3, 2, 2, 2, 2]

БЛОГ НА HUSL

Как можно вращать фигуры

Ответы (1 шт):