Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Find first/last occurence of a sub-string, rotations to filter candidates solution in Speedy category for Grille Cipher Attack by Phil15
# 0.017 second to pass all tests on my computer
# Here on tests: size == 8 and length == 64 and part_length == 16.
from collections import Counter
def find_substring(part: str, text: str, last: bool = False) -> list[int]:
"""
`part` being a sub-string of `text`, return the indexes of the first
(or last if `last` is True) occurence of `part` in `text`.
"""
# Examples: Substrings "llllllllllllllll" and "lllllmmmmmmmmmmm" in
# "lllllllllllllllllllllmllllllmmllllllllmmllllllmmmmllllllmmllllll"
# XXXXXXXXXXXXXXXX................................................ first
# ..........................................XXXX....XXXXXX..XXXXXX last
# XXXXX................X......XX........XX......XXXX......XX...... first
# ................XXXXXX......XX........XX......XXXX......XX...... last
if last: # The last occurence is the first when looking at reversed texts.
part = part[::-1]
text = text[::-1]
result = []
idx = -1
for ch in part:
idx = text.index(ch, idx + 1)
result.append(idx)
if last:
result = [len(text) - 1 - idx for idx in result[::-1]]
return result
def find_grille(plaintext: str, cryptogram: str, hole: str = 'X', hidden: str = '.') -> list[str]:
"""Find the grille cipher key that transform plaintext into cryptogram."""
size = round(len(plaintext) ** 0.5)
assert not size % 2, 'size must be even'
length = size ** 2
assert len(plaintext) == len(cryptogram) == length
part_length = length // 4
# For each letter, list indexes of it in the cryptogram.
letter2indexes: dict[str, list[int]] = {}
for i, letter in enumerate(cryptogram):
letter2indexes.setdefault(letter, []).append(i)
# result[i][j] (0 <= i < 4, 0 <= j < part_length) is a list of possible
# indexes for the j-th letter of i-th part of the plaintext.
# The goal is to reduce all those lists to a single element/index.
# First, we look for first and last occurences of "part" in "cryptogram".
# It filters the initial list of indexes we had previously for each letter.
result = [
[
[idx for idx in letter2indexes[letter] if first_idx <= idx <= last_idx]
for letter, first_idx, last_idx in zip(
part,
find_substring(part, cryptogram),
find_substring(part, cryptogram, last=True),
strict=True, # length check (py3.10+)
)
]
for i in range(4)
for part in [plaintext[i * part_length: (i + 1) * part_length]]
]
# One rotation: (row r, column c) --> (row c, column size - 1 - r).
rotate1 = [c * size + size-1-r for r in range(size) for c in range(size)]
rotate2 = [rotate1[n] for n in rotate1]
rotate3 = [rotate1[n] for n in rotate2]
# Filter candidates as well as possible.
while True:
all_candidates = [i for p in result for idxs in p for i in idxs]
if len(all_candidates) == size ** 2:
break # Solved!
fail = True
candidates_count = Counter(all_candidates)
for i in range(4):
next1 = set().union(*result[(i + 1) % 4])
next2 = set().union(*result[(i + 2) % 4])
next3 = set().union(*result[(i + 3) % 4])
for j in range(part_length):
if len(result[i][j]) == 1:
continue # Only one candidate: no need to filter.
i0 = min(result[i][j - 1]) if j else -1
i1 = max(result[i][j + 1]) if j + 1 < part_length else length
res_ij = []
for idx in result[i][j]:
if candidates_count[idx] == 1:
# `idx` can only be here.
res_ij = [idx]
break
# Indexes of a substring candidate must be increasing.
# Rotations must be compatible with the 3 other parts.
if (
i0 < idx < i1
and rotate1[idx] in next1
and rotate2[idx] in next2
and rotate3[idx] in next3
):
res_ij.append(idx)
if result[i][j] != res_ij:
result[i][j] = res_ij
fail = False
if fail:
raise RuntimeError('I am useless! Send me to the void!!')
# Format the result into a list of strings with "X" and ".".
grid = [[hidden] * size for _ in range(size)]
for idxs in result[0]:
if len(idxs) == 1:
r, c = divmod(idxs[0], size)
grid[r][c] = hole
return list(map(''.join, grid))
Jan. 2, 2022
Comments:
