|
1
|
|
|
import operator as op |
|
2
|
|
|
from functools import reduce |
|
3
|
|
|
from itertools import chain, combinations, islice, permutations, product |
|
4
|
|
|
from random import shuffle |
|
5
|
|
|
|
|
6
|
|
|
|
|
7
|
|
|
flatten = lambda x: [j for i in x for j in i] |
|
8
|
|
|
|
|
9
|
|
|
|
|
10
|
|
|
def dominos(): |
|
11
|
|
|
return [(i, j) for i in range(7) for j in range(i, 7)] |
|
12
|
|
|
|
|
13
|
|
|
|
|
14
|
|
|
def tile_combinations(tiles, size, number): |
|
15
|
|
|
return [i for i in combinations(tiles, size // 2) if sum(map(sum, i)) == number] |
|
16
|
|
|
|
|
17
|
|
|
|
|
18
|
|
|
def combine_columns(columns, size, exception=set()): |
|
19
|
|
|
if size == 0: |
|
20
|
|
|
yield [] |
|
21
|
|
|
for i, v in enumerate(columns): |
|
22
|
|
|
new_exception = set(v) | exception |
|
23
|
|
|
sub_columns = [ |
|
24
|
|
|
item |
|
25
|
|
|
for item in columns[i + 1 :] |
|
26
|
|
|
if not any([tile in new_exception for tile in item]) |
|
27
|
|
|
] |
|
28
|
|
|
for j in combine_columns(sub_columns, size - 1, new_exception): |
|
29
|
|
|
# print(v) |
|
30
|
|
|
ret = [v] + j |
|
31
|
|
|
# print(ret) |
|
32
|
|
|
yield ret |
|
33
|
|
|
|
|
34
|
|
|
|
|
35
|
|
|
def row_sum_check(columns, number, size): |
|
36
|
|
|
for i in range(size): |
|
37
|
|
|
item_index, sub_item_index = i // 2, i % 2 |
|
38
|
|
|
if sum([i[item_index][sub_item_index] for i in columns]) != number: |
|
39
|
|
|
return False |
|
40
|
|
|
return True |
|
41
|
|
|
|
|
42
|
|
|
|
|
43
|
|
|
def diagonal_check(columns, number, size): |
|
44
|
|
|
diagonal_indexes = [] |
|
45
|
|
|
reversed_diagonal_indexes = [] |
|
46
|
|
|
for i in range(size): |
|
47
|
|
|
diagonal_indexes.append((i // 2, i % 2)) |
|
48
|
|
|
reversed_diagonal_indexes.append(((size - 1 - i) // 2, (size - 1 - i) % 2)) |
|
49
|
|
|
|
|
50
|
|
|
for i in permutations(columns): |
|
51
|
|
|
if ( |
|
52
|
|
|
sum( |
|
53
|
|
|
[ |
|
54
|
|
|
value[diagonal_indexes[row][0]][diagonal_indexes[row][1]] |
|
55
|
|
|
for row, value in enumerate(i) |
|
56
|
|
|
] |
|
57
|
|
|
) |
|
58
|
|
|
== number |
|
59
|
|
|
and sum( |
|
60
|
|
|
[ |
|
61
|
|
|
value[reversed_diagonal_indexes[row][0]][ |
|
62
|
|
|
reversed_diagonal_indexes[row][1] |
|
63
|
|
|
] |
|
64
|
|
|
for row, value in enumerate(i) |
|
65
|
|
|
] |
|
66
|
|
|
) |
|
67
|
|
|
== number |
|
68
|
|
|
): |
|
69
|
|
|
return i |
|
70
|
|
|
return False |
|
71
|
|
|
|
|
72
|
|
|
|
|
73
|
|
|
def brute_force(domino, number, size): |
|
74
|
|
|
shuffled_cols = [] |
|
75
|
|
|
for column in domino: |
|
76
|
|
|
element_list = [] |
|
77
|
|
|
for element in column: |
|
78
|
|
|
element_list.append(list(set([element, element[::-1]]))) |
|
79
|
|
|
|
|
80
|
|
|
# find out all possible permutations of a column |
|
81
|
|
|
col_possibilities = [] |
|
82
|
|
|
for i in permutations(element_list, len(element_list)): |
|
83
|
|
|
col_possibilities.append(product(*i)) |
|
84
|
|
|
col_possibilities = chain(*col_possibilities) |
|
85
|
|
|
shuffled_cols.append(col_possibilities) |
|
86
|
|
|
|
|
87
|
|
|
for i in product(*shuffled_cols): |
|
88
|
|
|
if row_sum_check(i, number, size): |
|
89
|
|
|
ret = diagonal_check(i, number, size) |
|
90
|
|
|
if ret: |
|
91
|
|
|
return ret |
|
92
|
|
|
|
|
93
|
|
|
|
|
94
|
|
|
def magic_domino(size, number): |
|
95
|
|
|
domino_tiles = dominos() |
|
96
|
|
|
columns = tile_combinations(domino_tiles, size, number) |
|
97
|
|
|
for i in combine_columns(columns, size): |
|
98
|
|
|
ret = brute_force(i, number, size) |
|
99
|
|
|
if ret: |
|
100
|
|
|
return list(zip(*[flatten(j) for j in ret])) |
|
101
|
|
|
|
|
102
|
|
|
|
|
103
|
|
|
if __name__ == '__main__': |
|
104
|
|
|
# These "asserts" using only for self-checking and not necessary for auto-testing |
|
105
|
|
|
import itertools |
|
106
|
|
|
|
|
107
|
|
|
def check_data(size, number, user_result): |
|
108
|
|
|
|
|
109
|
|
|
# check types |
|
110
|
|
|
def check_container_type(o): |
|
111
|
|
|
return any(map(lambda t: isinstance(o, t), (list, tuple))) |
|
112
|
|
|
|
|
113
|
|
|
def check_cell_type(i): |
|
114
|
|
|
return isinstance(i, int) |
|
115
|
|
|
|
|
116
|
|
|
if not ( |
|
117
|
|
|
check_container_type(user_result) |
|
118
|
|
|
and all(map(check_container_type, user_result)) |
|
119
|
|
|
and all(map(lambda row: all(map(check_cell_type, row)), user_result)) |
|
120
|
|
|
): |
|
121
|
|
|
raise Exception( |
|
122
|
|
|
"You should return a list/tuple of lists/tuples with integers." |
|
123
|
|
|
) |
|
124
|
|
|
|
|
125
|
|
|
# check sizes |
|
126
|
|
|
def check_size(o): |
|
127
|
|
|
return len(o) == size |
|
128
|
|
|
|
|
129
|
|
|
if not (check_size(user_result) and all(map(check_size, user_result))): |
|
130
|
|
|
raise Exception("Wrong size of answer.") |
|
131
|
|
|
|
|
132
|
|
|
# check is it a possible numbers (from 0 to 6 inclusive) |
|
133
|
|
|
if not all( |
|
134
|
|
|
map(lambda x: 0 <= x <= 6, itertools.chain.from_iterable(user_result)) |
|
135
|
|
|
): |
|
136
|
|
|
raise Exception("Wrong matrix integers (can't be domino tiles)") |
|
137
|
|
|
|
|
138
|
|
|
# check is it a magic square |
|
139
|
|
|
def seq_sum_check(seq): |
|
140
|
|
|
return sum(seq) == number |
|
141
|
|
|
|
|
142
|
|
|
diagonals_indexes = zip( |
|
143
|
|
|
*map(lambda i: ((i, i), (i, size - i - 1)), range(size)) |
|
144
|
|
|
) |
|
145
|
|
|
|
|
146
|
|
|
def values_from_indexes(inds): |
|
147
|
|
|
return itertools.starmap(lambda x, y: user_result[y][x], inds) |
|
148
|
|
|
|
|
149
|
|
|
if not ( |
|
150
|
|
|
all(map(seq_sum_check, user_result)) |
|
151
|
|
|
and all(map(seq_sum_check, zip(*user_result))) # rows |
|
152
|
|
|
and all( # columns |
|
153
|
|
|
map(seq_sum_check, map(values_from_indexes, diagonals_indexes)) |
|
154
|
|
|
) |
|
155
|
|
|
): # diagonals |
|
156
|
|
|
raise Exception("It's not a magic square.") |
|
157
|
|
|
|
|
158
|
|
|
# check is it domino square |
|
159
|
|
|
tiles = set() |
|
160
|
|
|
for x, y in itertools.product(range(size), range(0, size, 2)): |
|
161
|
|
|
tile = tuple(sorted((user_result[y][x], user_result[y + 1][x]))) |
|
162
|
|
|
if tile in tiles: |
|
163
|
|
|
raise Exception("It's not a domino magic square.") |
|
164
|
|
|
tiles.add(tile) |
|
165
|
|
|
|
|
166
|
|
|
check_data(4, 5, magic_domino(4, 5)) |
|
167
|
|
|
|
KenMercusLai /
checkio
