Почему нельзя декодировать строку?

Question

Уже всю голову сломал, но никак не могу понять, в чем проблема декодирования. Условия задачи (напишу в оригинале, потому как вдруг что-то перевел не так, и от этого утерялась какая нибудь деталь):

Suppose we know the process by which a string s was encoded to a string r (see explanation below). The aim of the kata is to decode this string r to get back the original string s.

Explanation of the encoding process:

input: a string s composed of lowercase letters from "a" to "z", and a positive integer num
we know there is a correspondence between abcde...uvwxyz and 0, 1, 2 ..., 23, 24, 25 : 0 <-> a, 1 <-> b ...
if c is a character of s whose corresponding number is x, apply to x the function f: x-> f(x) = num * x % 26, then find ch the corresponding character of f(x)
Accumulate all these ch in a string r
concatenate num and r and return the result

For example:

encode("mer", 6015)  -->  "6015ekx"

m --> 12,   12 * 6015 % 26 = 4,    4  --> e
e --> 4,     4 * 6015 % 26 = 10,   10 --> k
r --> 17,   17 * 6015 % 26 = 23,   23 --> x

So we get "ekx", hence the output is "6015ekx"

Task

A string s was encoded to string r by the above process. complete the function to get back s whenever it is possible.

Indeed it can happen that the decoding is impossible for strings composed of whatever letters from "a" to "z" when positive integer num has not been correctly chosen. In that case return "Impossible to decode".

Examples

decode "6015ekx" -> "mer"
decode "5057aan" -> "Impossible to decode"

Функцию декодирования я осилил, а вот предусмотреть то, что на вход будут подаваться неверные данные, пока не смог, потому что я в принципе не могу понять, что есть неверные данные и почему они считаются таковыми.

Функция декодирования:

def decode(r):
    num = int(''.join(map(str, [x for x in r if x.isdigit()])))  # отделяем число от кодированных символов
    res = ''
    for x in r[len(str(num)):]:  # цикл по строке без цифр
        res += chr({x * num % 26: x for x in range(26)}[ord(x)-97]+97)  # добавляю декодированный символ в результат
    return res

PS: Все тесты с корректными данными проходит успешно.

Answer 1

Если распечатать карту обратных преобразований для числа 5057:

{x * 5057 % 26: x for x in range(26)}

то получится такая картина:

{0: 24, 13: 25}

Отчего такое происходит? Оттого, что число 5057, как и число 26, делятся на 13 без остатка. Т.е. они взаимно сокращаются и формула как бы получается x * 389 % 2. Отсюда становится понятно, что таким числом можно однозначно закодировать только два значения.
Аналогично, для любого чётного числа словарь преобразований будет содержать только 13 вариантов, Например, для 1250:

{ 0: 13,
  2: 14,
  4: 15,
  6: 16,
  8: 17,
 10: 18,
 12: 19,
 14: 20,
 16: 21,
 18: 22,
 20: 23,
 22: 24,
 24: 25}

Ну а если число кратно 26, то словарь будет состоять всего из одного элемента.

Таким образом чтобы проверить, что обратное преобразование возможно, надо удостовериться, что число не делится ни на 13, ни на 2. Или тупо создать словарь преобразований и посмотреть, что его длина равна 26.

def decode(r):
    num = int(''.join([x for x in r if x.isdigit()]))  # отделяем число от кодированных символов
    if not num % 2 or not num % 13:
        return 'Impossible to decode'
    decode_map = {x * num % 26: x for x in range(26)}
    return ''.join(chr(decode_map[ord(x)-97]+97) for x in r[len(str(num)):])  # цикл по строке без цифр

БЛОГ НА HUSL

Почему нельзя декодировать строку?

Ответы (1 шт):