|
1
|
|
|
import operator as op |
|
2
|
|
|
from functools import reduce |
|
3
|
|
|
from itertools import combinations, islice, permutations, product |
|
4
|
|
|
|
|
5
|
|
|
|
|
6
|
|
|
def ncr(n, r): |
|
7
|
|
|
r = min(r, n - r) |
|
8
|
|
|
number = reduce(op.mul, range(n, n - r, -1), 1) |
|
9
|
|
|
denom = reduce(op.mul, range(1, r + 1), 1) |
|
10
|
|
|
return number // denom |
|
11
|
|
|
|
|
12
|
|
|
|
|
13
|
|
|
|
|
14
|
|
|
|
|
15
|
|
|
def vertical_combination(combination): |
|
16
|
|
|
columns = {} |
|
17
|
|
|
for i in combination: |
|
18
|
|
|
dominos = [tuple(sorted(i[j : j + 2])) for j in range(0, len(i), 2)] |
|
19
|
|
|
if len(dominos) == len((set(dominos))): |
|
20
|
|
|
columns[i] = dominos |
|
21
|
|
|
return columns |
|
22
|
|
|
|
|
23
|
|
|
|
|
24
|
|
|
def has_duplicate_tiles(status, columns): |
|
25
|
|
|
tiles = [] |
|
26
|
|
|
for i in status: |
|
27
|
|
|
tiles += columns[i] |
|
28
|
|
|
return len(tiles) != len(set(tiles)) |
|
29
|
|
|
|
|
30
|
|
|
|
|
31
|
|
|
def max_tile_duplicate(status, columns): |
|
32
|
|
|
for i in range(2, len(status) + 1): |
|
33
|
|
|
if has_duplicate_tiles(status[:i], columns): |
|
34
|
|
|
return i |
|
35
|
|
|
return 0 |
|
36
|
|
|
|
|
37
|
|
|
|
|
38
|
|
|
def brute_force(size, number, columns): |
|
39
|
|
|
total_column_combinations = len(columns) |
|
40
|
|
|
domino_combinations = combinations(columns.keys(), size) |
|
41
|
|
|
for i in domino_combinations: |
|
42
|
|
|
duplications = max_tile_duplicate(i, columns) |
|
43
|
|
|
if duplications: |
|
44
|
|
|
# skip |
|
45
|
|
|
skip_combinations = ( |
|
46
|
|
|
ncr(total_column_combinations - duplications, size - duplications) - 1 |
|
47
|
|
|
) |
|
48
|
|
|
islice(domino_combinations, skip_combinations) |
|
49
|
|
|
continue |
|
50
|
|
|
# row check |
|
51
|
|
|
row_sums = list(map(sum, list(zip(*i)))) |
|
52
|
|
|
if not (len(set(row_sums)) == 1 and row_sums[0] == number): |
|
53
|
|
|
continue |
|
54
|
|
|
# diangal check |
|
55
|
|
|
for diagonal_check in permutations(i): |
|
56
|
|
|
diagonal1 = [diagonal_check[j][j] for j in range(size)] |
|
57
|
|
|
diagonal2 = [diagonal_check[j][size - j - 1] for j in range(size)] |
|
58
|
|
|
if sum(diagonal1) == sum(diagonal2) == number: |
|
59
|
|
|
return diagonal_check |
|
60
|
|
|
|
|
61
|
|
|
|
|
62
|
|
|
def magic_domino(size, number): |
|
63
|
|
|
valid_number_combinations = number_combinations(size, number) |
|
|
|
|
|
|
64
|
|
|
columns = vertical_combination(valid_number_combinations) |
|
65
|
|
|
return list(zip(*brute_force(size, number, columns))) |
|
66
|
|
|
|
|
67
|
|
|
|
|
68
|
|
|
if __name__ == '__main__': |
|
69
|
|
|
# These "asserts" using only for self-checking and not necessary for auto-testing |
|
70
|
|
|
import itertools |
|
71
|
|
|
|
|
72
|
|
|
def check_data(size, number, user_result): |
|
73
|
|
|
|
|
74
|
|
|
# check types |
|
75
|
|
|
def check_container_type(o): |
|
76
|
|
|
return any(map(lambda t: isinstance(o, t), (list, tuple))) |
|
77
|
|
|
|
|
78
|
|
|
def check_cell_type(i): |
|
79
|
|
|
return isinstance(i, int) |
|
80
|
|
|
|
|
81
|
|
|
if not ( |
|
82
|
|
|
check_container_type(user_result) |
|
83
|
|
|
and all(map(check_container_type, user_result)) |
|
84
|
|
|
and all(map(lambda row: all(map(check_cell_type, row)), user_result)) |
|
85
|
|
|
): |
|
86
|
|
|
raise Exception( |
|
87
|
|
|
"You should return a list/tuple of lists/tuples with integers." |
|
88
|
|
|
) |
|
89
|
|
|
|
|
90
|
|
|
# check sizes |
|
91
|
|
|
def check_size(o): |
|
92
|
|
|
return len(o) == size |
|
93
|
|
|
|
|
94
|
|
|
if not (check_size(user_result) and all(map(check_size, user_result))): |
|
95
|
|
|
raise Exception("Wrong size of answer.") |
|
96
|
|
|
|
|
97
|
|
|
# check is it a possible numbers (from 0 to 6 inclusive) |
|
98
|
|
|
if not all( |
|
99
|
|
|
map(lambda x: 0 <= x <= 6, itertools.chain.from_iterable(user_result)) |
|
100
|
|
|
): |
|
101
|
|
|
raise Exception("Wrong matrix integers (can't be domino tiles)") |
|
102
|
|
|
|
|
103
|
|
|
# check is it a magic square |
|
104
|
|
|
def seq_sum_check(seq): |
|
105
|
|
|
return sum(seq) == number |
|
106
|
|
|
|
|
107
|
|
|
diagonals_indexes = zip( |
|
108
|
|
|
*map(lambda i: ((i, i), (i, size - i - 1)), range(size)) |
|
109
|
|
|
) |
|
110
|
|
|
|
|
111
|
|
|
def values_from_indexes(inds): |
|
112
|
|
|
return itertools.starmap(lambda x, y: user_result[y][x], inds) |
|
113
|
|
|
|
|
114
|
|
|
if not ( |
|
115
|
|
|
all(map(seq_sum_check, user_result)) |
|
116
|
|
|
and all(map(seq_sum_check, zip(*user_result))) # rows |
|
117
|
|
|
and all( # columns |
|
118
|
|
|
map(seq_sum_check, map(values_from_indexes, diagonals_indexes)) |
|
119
|
|
|
) |
|
120
|
|
|
): # diagonals |
|
121
|
|
|
raise Exception("It's not a magic square.") |
|
122
|
|
|
|
|
123
|
|
|
# check is it domino square |
|
124
|
|
|
tiles = set() |
|
125
|
|
|
for x, y in itertools.product(range(size), range(0, size, 2)): |
|
126
|
|
|
tile = tuple(sorted((user_result[y][x], user_result[y + 1][x]))) |
|
127
|
|
|
if tile in tiles: |
|
128
|
|
|
raise Exception("It's not a domino magic square.") |
|
129
|
|
|
tiles.add(tile) |
|
130
|
|
|
|
|
131
|
|
|
check_data(4, 5, magic_domino(4, 5)) |
|
132
|
|
|
|
KenMercusLai /
checkio
Loading history...