1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
| from collections import defaultdict
from random import seed, randrange
import sys
def display_grid():
print(' ', '-' * (2 * dim + 3))
for row in grid:
print(' |', *row, '|')
print(' ', '-' * (2 * dim + 3))
try:
for_seed, density, dim = (int(x)
for x in input('Enter three integers, '
'the second and third ones '
'being strictly positive: '
).split()
)
if density <= 0 or dim <= 0:
raise ValueError
except ValueError:
print('Incorrect input, giving up.')
sys.exit()
seed(for_seed)
grid = [['*' if randrange(density) != 0 else ' ' for _ in range(dim)]
for _ in range(dim)
]
print('Here is the grid that has been generated:')
display_grid()
results = defaultdict(list)
dict_position = defaultdict(list)
middle_position = defaultdict(list)
sparse_matrix = [[1 if cell == '*' else 0 for cell in row] for row in grid]
def RL(row, col, size):
return [(row + k, col - k) for k in range(size + 1)]
def LR(row, col, size):
return [(row + k, col + k) for k in range(size + 1)]
def find_points(coordinates_list, size):
min_idx = 0
max_idx = len(coordinates_list)
tmp = []
max_l_r = 0
for idx in range(min_idx + 1, max_idx - 1, 2):
point1 = coordinates_list[idx]
point2 = coordinates_list[idx + 1]
x, y1 = point1
x, y2 = point2
if abs(y1 - y2) > max_l_r:
max_l_r = abs(y1 - y2)
max_l_r_position = [(x, y1), (x, y2)]
for y_idx in range(y1, y2 + 1):
tmp.append((x, y_idx))
tmp.insert(0, coordinates_list[0])
tmp.append(coordinates_list[-1])
cur = [tmp[len(tmp) // 2], tmp[0], tmp[-1]]
cur.extend(max_l_r_position)
dict_position[size].append(cur)
dict_size = defaultdict(list)
row = len(sparse_matrix)
col = len(sparse_matrix[0])
all_group = []
for i in range(row):
for j in range(col):
if i >= 0 and i < row and j > 0 and j < col:
if sparse_matrix[i][j] == 1:
for size in range(1, row):
points_list = []
left = RL(i, j, size)
points_list.extend(left)
if left[-1][0] < 0 or left[-1][1] < 0 or left[-1][0] >= row or left[-1][1] >= col:
break
right = LR(i, j, size)
points_list.extend(right)
if right[-1][0] < 0 or right[-1][1] < 0 or right[-1][0] >= row or right[-1][1] >= col:
break
left_ = LR(left[-1][0], left[-1][1], size)
points_list.extend(left_)
if left_[-1][0] < 0 or left_[-1][1] < 0 or left_[-1][0] >= row or left_[-1][1] >= col:
break
right_ = RL(right[-1][0], right[-1][1], size)
points_list.extend(right_)
if right_[-1][0] < 0 or right_[-1][1] < 0 or right_[-1][0] >= row or right_[-1][1] >= col:
break
all_group.append((size, points_list))
for single in all_group:
points_set = set(single[1])
flag = 0
for single_item in points_set:
if sparse_matrix[single_item[0]][single_item[1]] == 0:
flag = 1
if flag == 0:
dict_size[single[0]].append(points_set)
for k in sorted(dict_size.keys(), reverse=True):
for item in dict_size[k]:
point_sorted_list = sorted(item, key=lambda x: (x[0], x[1]))
find_points(point_sorted_list, k)
for k, single_part in dict_position.items():
for item in single_part:
flag = 0
key, middle, up, down, left, right = k, item[0], item[1], item[2], item[3], item[4]
if key == list(dict_position.keys())[0]:
middle_position[key].append(middle)
else:
to_append = []
for ky, md in middle_position.items():
for item in md:
md_l, md_r = item[0], item[1]
if abs(up[0] - md_l) + abs(up[1] - md_r) > ky or abs(down[0] - md_l) + abs(
down[1] - md_r) > ky or abs(left[0] - md_l) + abs(left[1] - md_r) > ky or abs(
right[0] - md_l) + abs(right[1] - md_r) > ky:
to_append = [key, middle]
else:
flag = 1
if to_append and flag == 0:
middle_position[to_append[0]].append(to_append[1])
if flag == 0:
results[key].append(up)
print('Here are the rhombuses that are not included in any other:')
for size in sorted(results):
print(f'Of size {size}:')
for (i, j) in results[size]:
print(f' - with top vertex at location ({i}, {j})')
|