|
1
|
|
|
from itertools import product, permutations, combinations, islice |
|
2
|
|
|
import operator as op |
|
3
|
|
|
from functools import reduce |
|
4
|
|
|
|
|
5
|
|
|
|
|
6
|
|
|
def ncr(n, r): |
|
7
|
|
|
r = min(r, n-r) |
|
8
|
|
|
numer = reduce(op.mul, range(n, n-r, -1), 1) |
|
9
|
|
|
denom = reduce(op.mul, range(1, r+1), 1) |
|
10
|
|
|
return numer // denom |
|
11
|
|
|
|
|
12
|
|
|
|
|
13
|
|
|
def number_combinations(size, number): |
|
14
|
|
|
return [i for i in product(*[list(range(7))] * size) if sum(i) == number] |
|
15
|
|
|
|
|
16
|
|
|
|
|
17
|
|
|
def vertical_combination(combination): |
|
18
|
|
|
columns = {} |
|
19
|
|
|
for i in combination: |
|
20
|
|
|
dominos = [tuple(sorted(i[j:j + 2])) for j in range(0, len(i), 2)] |
|
21
|
|
|
if len(dominos) == len((set(dominos))): |
|
22
|
|
|
columns[i] = dominos |
|
23
|
|
|
return columns |
|
24
|
|
|
|
|
25
|
|
|
|
|
26
|
|
|
def has_duplicate_tiles(status, columns): |
|
27
|
|
|
tiles = [] |
|
28
|
|
|
for i in status: |
|
29
|
|
|
tiles += columns[i] |
|
30
|
|
|
return len(tiles) != len(set(tiles)) |
|
31
|
|
|
|
|
32
|
|
|
|
|
33
|
|
|
def max_tile_duplicate(status, columns): |
|
34
|
|
|
for i in range(2, len(status) + 1): |
|
35
|
|
|
if has_duplicate_tiles(status[:i], columns): |
|
36
|
|
|
return i |
|
37
|
|
|
return 0 |
|
38
|
|
|
|
|
39
|
|
|
|
|
40
|
|
|
def brute_force(size, number, columns): |
|
41
|
|
|
total_column_combinations = len(columns) |
|
42
|
|
|
domino_combinations = combinations(columns.keys(), size) |
|
43
|
|
|
for i in domino_combinations: |
|
44
|
|
|
duplications = max_tile_duplicate(i, columns) |
|
45
|
|
|
if duplications: |
|
46
|
|
|
# skip |
|
47
|
|
|
skip_combinations = ncr(total_column_combinations-duplications, size-duplications)-1 |
|
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 diagnal_check in permutations(i): |
|
56
|
|
|
diagnal1 = [diagnal_check[j][j] for j in range(size)] |
|
57
|
|
|
diagnal2 = [diagnal_check[j][size - j - 1] for j in range(size)] |
|
58
|
|
|
if (sum(diagnal1) == sum(diagnal2) == number): |
|
59
|
|
|
return diagnal_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
|
|
View Code Duplication |
def check_data(size, number, user_result): |
|
|
|
|
|
|
73
|
|
|
|
|
74
|
|
|
# check types |
|
75
|
|
|
check_container_type = lambda o: any(map(lambda t: isinstance(o, t), (list, tuple))) |
|
|
|
|
|
|
76
|
|
|
check_cell_type = lambda i: isinstance(i, int) |
|
77
|
|
|
if not (check_container_type(user_result) and |
|
78
|
|
|
all(map(check_container_type, user_result)) and |
|
79
|
|
|
all(map(lambda row: all(map(check_cell_type, row)), user_result))): |
|
80
|
|
|
raise Exception("You should return a list/tuple of lists/tuples with integers.") |
|
81
|
|
|
|
|
82
|
|
|
# check sizes |
|
83
|
|
|
check_size = lambda o: len(o) == size |
|
84
|
|
|
if not (check_size(user_result) and all(map(check_size, user_result))): |
|
85
|
|
|
raise Exception("Wrong size of answer.") |
|
86
|
|
|
|
|
87
|
|
|
# check is it a possible numbers (from 0 to 6 inclusive) |
|
88
|
|
|
if not all(map(lambda x: 0 <= x <= 6, itertools.chain.from_iterable(user_result))): |
|
89
|
|
|
raise Exception("Wrong matrix integers (can't be domino tiles)") |
|
90
|
|
|
|
|
91
|
|
|
# check is it a magic square |
|
92
|
|
|
seq_sum_check = lambda seq: sum(seq) == number |
|
93
|
|
|
diagonals_indexes = zip(*map(lambda i: ((i, i), (i, size - i - 1)), range(size))) |
|
94
|
|
|
values_from_indexes = lambda inds: itertools.starmap(lambda x, y: user_result[y][x], inds) |
|
95
|
|
|
if not (all(map(seq_sum_check, user_result)) and # rows |
|
96
|
|
|
all(map(seq_sum_check, zip(*user_result))) and # columns |
|
97
|
|
|
all(map(seq_sum_check, map(values_from_indexes, diagonals_indexes)))): # diagonals |
|
98
|
|
|
raise Exception("It's not a magic square.") |
|
99
|
|
|
|
|
100
|
|
|
# check is it domino square |
|
101
|
|
|
tiles = set() |
|
102
|
|
|
for x, y in itertools.product(range(size), range(0, size, 2)): |
|
103
|
|
|
tile = tuple(sorted((user_result[y][x], user_result[y + 1][x]))) |
|
104
|
|
|
if tile in tiles: |
|
105
|
|
|
raise Exception("It's not a domino magic square.") |
|
106
|
|
|
tiles.add(tile) |
|
107
|
|
|
|
|
108
|
|
|
check_data(4, 5, magic_domino(4, 5)) |
|
109
|
|
|
|
KenMercusLai /
checkio
Loading history...