|
1
|
|
|
from collections import defaultdict, deque |
|
2
|
|
|
from functools import reduce |
|
3
|
|
|
from itertools import product |
|
4
|
|
|
from operator import mul |
|
5
|
|
|
from typing import List, Dict, Iterable |
|
6
|
|
|
|
|
7
|
|
|
INDEX_MAPPING = [(0, 7, 63, 56), (1, 15, 62, 48), (2, 23, 61, 40), (3, 31, 60, 32), (4, 39, 59, 24), (5, 47, 58, 16), |
|
8
|
|
|
(6, 55, 57, 8), (7, 63, 56, 0), (8, 6, 55, 57), (9, 14, 54, 49), (10, 22, 53, 41), (11, 30, 52, 33), |
|
9
|
|
|
(12, 38, 51, 25), (13, 46, 50, 17), (14, 54, 49, 9), (15, 62, 48, 1), (16, 5, 47, 58), |
|
10
|
|
|
(17, 13, 46, 50), (18, 21, 45, 42), (19, 29, 44, 34), (20, 37, 43, 26), (21, 45, 42, 18), |
|
11
|
|
|
(22, 53, 41, 10), (23, 61, 40, 2), (24, 4, 39, 59), (25, 12, 38, 51), (26, 20, 37, 43), |
|
12
|
|
|
(27, 28, 36, 35), (28, 36, 35, 27), (29, 44, 34, 19), (30, 52, 33, 11), (31, 60, 32, 3), |
|
13
|
|
|
(32, 3, 31, 60), (33, 11, 30, 52), (34, 19, 29, 44), (35, 27, 28, 36), (36, 35, 27, 28), |
|
14
|
|
|
(37, 43, 26, 20), (38, 51, 25, 12), (39, 59, 24, 4), (40, 2, 23, 61), (41, 10, 22, 53), |
|
15
|
|
|
(42, 18, 21, 45), (43, 26, 20, 37), (44, 34, 19, 29), (45, 42, 18, 21), (46, 50, 17, 13), |
|
16
|
|
|
(47, 58, 16, 5), (48, 1, 15, 62), (49, 9, 14, 54), (50, 17, 13, 46), (51, 25, 12, 38), |
|
17
|
|
|
(52, 33, 11, 30), (53, 41, 10, 22), (54, 49, 9, 14), (55, 57, 8, 6), (56, 0, 7, 63), (57, 8, 6, 55), |
|
18
|
|
|
(58, 16, 5, 47), (59, 24, 4, 39), (60, 32, 3, 31), (61, 40, 2, 23), (62, 48, 1, 15), (63, 56, 0, 7)] |
|
19
|
|
|
|
|
20
|
|
|
|
|
21
|
|
|
def convert_to_matrix(text: str) -> List[str]: |
|
22
|
|
|
return [text[i * 8:i * 8 + 8] for i in range(8)] |
|
23
|
|
|
|
|
24
|
|
|
|
|
25
|
|
|
def find_candidates(positions_of_lookfor_text, lookfor): |
|
26
|
|
|
combinations = [positions_of_lookfor_text[i] for i in lookfor] |
|
27
|
|
|
return combinations |
|
28
|
|
|
|
|
29
|
|
|
|
|
30
|
|
|
def remove_impossibilities(possibilities: List[List[int]], allowed_indexes: Iterable[int]) -> List[List[int]]: |
|
31
|
|
|
for k, v in enumerate(possibilities): |
|
32
|
|
|
possibilities[k] = [i for i in v if i in allowed_indexes] |
|
33
|
|
|
for i in range(1, len(possibilities)): |
|
34
|
|
|
possibilities[i] = list(filter(lambda x: possibilities[i - 1][0] < x, possibilities[i])) |
|
|
|
|
|
|
35
|
|
|
for i in range(len(possibilities) - 2, -1, -1): |
|
36
|
|
|
possibilities[i] = list(filter(lambda x: x < possibilities[i + 1][-1], possibilities[i])) |
|
|
|
|
|
|
37
|
|
|
return possibilities |
|
38
|
|
|
|
|
39
|
|
|
|
|
40
|
|
|
def find_possible_positions(text: str, lookfor: str, allowed_indexes: Iterable[int] = range(64)) -> List[List[int]]: |
|
41
|
|
|
positions_of_lookfor_text = mapping_text_position(text, lookfor) |
|
42
|
|
|
possible_combinations = find_candidates(positions_of_lookfor_text, lookfor) |
|
43
|
|
|
return remove_impossibilities(possible_combinations, allowed_indexes) |
|
44
|
|
|
|
|
45
|
|
|
|
|
46
|
|
|
def mapping_text_position(text: str, lookfor: str) -> Dict: |
|
47
|
|
|
ret = defaultdict(list) |
|
48
|
|
|
[ret[v].append(i) for i, v in enumerate(text) if v in lookfor] |
|
49
|
|
|
return ret |
|
50
|
|
|
|
|
51
|
|
|
|
|
52
|
|
|
def get_decrypted_text(grille: List[int], cryptogram: str) -> str: |
|
53
|
|
|
return ''.join([cryptogram[i] for i in grille]) |
|
54
|
|
|
|
|
55
|
|
|
|
|
56
|
|
|
def punch_holes(grille: List[int]) -> str: |
|
57
|
|
|
ret = ['.'] * 64 |
|
58
|
|
|
for i in grille: |
|
59
|
|
|
ret[i] = 'X' |
|
60
|
|
|
return ''.join(ret) |
|
61
|
|
|
|
|
62
|
|
|
|
|
63
|
|
|
def calc_combination_number(possibles): |
|
64
|
|
|
return reduce(mul, (map(lambda x: len(x), possibles))) |
|
65
|
|
|
|
|
66
|
|
|
|
|
67
|
|
|
def pick_easiest(remained_0, remained_1, remained_2, remained_3) -> int: |
|
68
|
|
|
combinations = list(map(calc_combination_number, [remained_0, remained_1, remained_2, remained_3])) |
|
69
|
|
|
rotated = combinations.index(min(combinations)) |
|
70
|
|
|
return rotated |
|
71
|
|
|
|
|
72
|
|
|
|
|
73
|
|
|
def rotate(grille: List[int], times: int) -> List[int]: |
|
74
|
|
|
return sorted([INDEX_MAPPING[i][times] for i in grille]) |
|
75
|
|
|
|
|
76
|
|
|
|
|
77
|
|
|
def get_rotate_back(grille, rotated): |
|
78
|
|
|
new_index = [] |
|
79
|
|
|
for i in grille: |
|
80
|
|
|
indexes = deque(INDEX_MAPPING[i]) |
|
81
|
|
|
indexes.rotate(rotated) |
|
82
|
|
|
new_index.append(indexes[0]) |
|
83
|
|
|
return sorted(new_index) |
|
84
|
|
|
|
|
85
|
|
|
|
|
86
|
|
|
def all_rotations(grille, rotated): |
|
87
|
|
|
original = get_rotate_back(grille, rotated) |
|
88
|
|
|
return [original, rotate(original, 1), rotate(original, 2), rotate(original, 3)] |
|
89
|
|
|
|
|
90
|
|
|
|
|
91
|
|
|
def find_result(plaintext, cryptogram, grille_combinations, rotated): |
|
92
|
|
|
combinations_to_test = product(*grille_combinations) |
|
93
|
|
|
for i in combinations_to_test: |
|
94
|
|
|
rotations = all_rotations(i, rotated) |
|
95
|
|
|
if ''.join(list(map(lambda x: get_decrypted_text(x, cryptogram), rotations))) == plaintext: |
|
96
|
|
|
return rotations[0] |
|
97
|
|
|
|
|
98
|
|
|
|
|
99
|
|
|
def find_allowed_indexes(candidates): |
|
100
|
|
|
"""find possible indexes and rotate for the next iteration""" |
|
101
|
|
|
indexes = list(set(j for i in candidates for j in i)) |
|
102
|
|
|
return [INDEX_MAPPING[i][1] for i in indexes] |
|
103
|
|
|
|
|
104
|
|
|
|
|
105
|
|
|
def find_grille(plaintext: str, cryptogram: str) -> List[str]: |
|
106
|
|
|
candidates_0 = find_possible_positions(cryptogram, plaintext[:16]) |
|
107
|
|
|
candidates_1 = find_possible_positions(cryptogram, plaintext[16:32], find_allowed_indexes(candidates_0)) |
|
108
|
|
|
candidates_2 = find_possible_positions(cryptogram, plaintext[32:48], find_allowed_indexes(candidates_1)) |
|
109
|
|
|
candidates_3 = find_possible_positions(cryptogram, plaintext[48:], find_allowed_indexes(candidates_2)) |
|
110
|
|
|
possible_grille_combinations = [candidates_0, candidates_1, candidates_2, candidates_3] |
|
111
|
|
|
rotated = pick_easiest(*possible_grille_combinations) |
|
112
|
|
|
grille_combinations = possible_grille_combinations[rotated] |
|
113
|
|
|
grille = find_result(plaintext, cryptogram, grille_combinations, rotated) |
|
114
|
|
|
return convert_to_matrix(punch_holes(grille)) |
|
115
|
|
|
|
|
116
|
|
|
|
|
117
|
|
|
if __name__ == "__main__": |
|
118
|
|
|
print("Example:") |
|
119
|
|
|
print(find_grille("quickbrownfoxjumpsoverthelazydogandjackdawslovesmysphinxofquartz", |
|
120
|
|
|
"quicpsovkbroerthwnfoelazxjumydogmyspandjhinxackdofquawslartzoves", )) |
|
121
|
|
|
|
|
122
|
|
|
# These "asserts" are used for self-checking and not for an auto-testing |
|
123
|
|
|
assert find_grille("quickbrownfoxjumpsoverthelazydogandjackdawslovesmysphinxofquartz", |
|
124
|
|
|
"quicpsovkbroerthwnfoelazxjumydogmyspandjhinxackdofquawslartzoves", ) == ["XXXX....", "XXXX....", |
|
125
|
|
|
"XXXX....", "XXXX....", |
|
126
|
|
|
"........", "........", |
|
127
|
|
|
"........", |
|
128
|
|
|
"........", ] |
|
129
|
|
|
|
|
130
|
|
|
assert find_grille("weareallfromxanthcubesaidquicklyjustvisitingphazewewontbeforlong", |
|
131
|
|
|
"wejhewucuaeswtbrveeoisantsalilbifdteifrqunooigrmplxcakhonnlagtyz", ) == ["X...X...", ".X.....X", |
|
132
|
|
|
"..X...X.", "...X.X..", |
|
133
|
|
|
"X.....X.", "...X...X", |
|
134
|
|
|
"..X.X...", |
|
135
|
|
|
".X...X..", ] |
|
136
|
|
|
|
|
137
|
|
|
assert find_grille("theideaofcognitivebiasinpsychologyworksinananalogouswayacognitiv", |
|
138
|
|
|
"tgovgeubyhsiawseiinorkdepaswoasifcyncyaanaognconaginihlttoiivloo", ) == ["X.......", ".X.....X", |
|
139
|
|
|
"X.....XX", ".X..X...", |
|
140
|
|
|
"XX......", "..XXX...", |
|
141
|
|
|
"..X....X", |
|
142
|
|
|
"...X....", ] |
|
143
|
|
|
|
|
144
|
|
|
print("Coding complete? Click 'Check' to earn cool rewards!") |
|
145
|
|
|
|
KenMercusLai /
checkio
Loading history...