How to create decrypt dictionary based on list of strings to encrypt by string

Question

I have some inputs inputs = ["and", "dick", "jane", "puff", "spot", "yertle"] than I have sentence composed from words from inputs encrypted_sentence ="bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn" but letters are changed in some pattern. For example "a"='x'; "n"='s'; "d"='b'..... Every letter in alphabet is replaced for some different letter in alphabet. I need to create dictionary where new 'letter' will be key and old letter will be value. Like this decrypt_dict={ "x":'a', "s":'n', "b":'d', "q":'a', "t":'t'} and so on... If amount of unique letters in inputs is different from amount of unique letters in sentence, print "ERROR"because it's not possible to create sentence from inputs If some letters are not used, nevermind, just skip them. It is not necessary to create dict with every char in alphabet, I just need the ones that were used in the encoding

this is my code so far (i used another test strings):


import itertools

def deduplicate(lst):
    elems = set()
    rest = []
    for el in lst:
        if el not in elems:
            elems.add(el)
            rest.append(el)
    return rest


def deduplicate_lists(lst_of_lists, differenet_lists=False):
    lst_of_lists.sort()
    if differenet_lists:
        return [lst for lst, _ in itertools.groupby(lst_of_lists)]
    else:
        return [*[lst for lst, _ in itertools.groupby(lst_of_lists)]]


def try_it_faster(lists_by_len_of_words, decrypt_dict):
    for key, val in lists_by_len_of_words.items():
        # print(ke, val)
        if len(val) == 1:
            for index, char in enumerate(val[0]):
                # print(char, index_for_word)
                decrypt_dict.update({char: key[index]})
    return decrypt_dict


def decrypt(string_to_decrypt, decrypt_dict):
    returner = None
    try:
        returner = "".join(decrypt_dict[i] for i in string_to_decrypt)
    except KeyError:
        pass
    return returner


def c_just_multiple_val_dict(dict, help_dict=None):
    copy_dict = dict.copy()
    for keys, values in copy_dict.items():
        # print(keys, values)
        if len(values) == 1:
            dict.pop(keys)

    if help_dict is not None:
        copy_dict = dict.copy()
        for word in copy_dict.keys():
            if all([char in help_dict.values() for char in word]):
                dict.pop(word)
    return dict


def move_items(lst):
    return lst[0:] + lst[0]


# timed
number = 6
inputs = ['all', 'and', 'apple', 'ass', 'gibble', 'horror', 'hound', 'love',
          'tie']  # input words default: "and", "dick", "jane", "puff", "spot", "yertle"
decrypt_dict = {' ': ' '}
encryption_as_string = "cvvli euynm dxggli euzzuz cnm bxi lupi cll cww"  # default: bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
encryption_key = encryption_as_string.split()  # create list from encrypted string
lists_by_len_of_words = {inp: deduplicate([a for a in encryption_key if len(a) == len(inp)]) for inp in
                         inputs}  # dict key=input word, deduplicated value=words from encryption_key with same length as input word
# timed

# print start values
print(f"1. {inputs}")
print(f"2. {encryption_key}")
print(f"3. {lists_by_len_of_words}")
print(f"4. {decrypt_dict}")

decrypt_dict = try_it_faster(lists_by_len_of_words,
                             decrypt_dict)  # if len of input words is unique, this will make it faster
secondary_decrypt_dict = decrypt_dict.copy()
print(f"4. After try_it_faster(): {decrypt_dict}")

# same_len_word_list = [word for word in lists_by_len_of_words.keys()]
inputs_sorted = sorted(inputs, key=len)  # input sorted
inputs_as_string = " ".join(inputs_sorted)  # sorted input to string

encryption_key_deduplicated_sorted = sorted(deduplicate(encryption_key),
                                            key=len)  # encryption_key sorted and deduplicated
encryption_key_as_string = " ".join(encryption_key_deduplicated_sorted)  # sorted encryption_key to string

# print sorted and deduplicated start values
print(f"1. Sorted input words as string: {inputs_as_string}")
print(f"2. Sorted and deduplicated encrypted words as list: {encryption_key_deduplicated_sorted}")
print(f"2. Sorted and deduplicated encrypted words as string: {encryption_key_as_string}")

mover_check = len(encryption_key_deduplicated_sorted)#*len(encryption_key_deduplicated_sorted)
mover = 0
# while decrypt(encryption_key_as_string, secondary_decrypt_dict) != inputs_as_string:
while decrypt(encryption_key_as_string, secondary_decrypt_dict) != inputs_as_string and mover < mover_check:
    print(f"Before clearing:{encryption_key_deduplicated_sorted}")
    for index_of_word, input_word in enumerate(inputs_sorted):
        print(index_of_word, input_word,
              decrypt(encryption_key_deduplicated_sorted[index_of_word], secondary_decrypt_dict))
        if decrypt(encryption_key_deduplicated_sorted[index_of_word], secondary_decrypt_dict) == input_word:
            for index_of_char, char in enumerate(encryption_key_deduplicated_sorted[index_of_word]):
                # print(index_of_char, char)
                decrypt_dict[char] = input_word[index_of_char]
            print(f"pop out {inputs_sorted[index_of_word]} a {encryption_key_deduplicated_sorted[index_of_word]}")
            inputs_sorted.pop(index_of_word)
            encryption_key_deduplicated_sorted.pop(index_of_word)

    print(f"After clearing:{encryption_key_deduplicated_sorted}")
    print(f"Work wi      :{inputs_sorted}")
    secondary_decrypt_dict.clear()
    secondary_decrypt_dict.update(decrypt_dict)
    # secondary_decrypt_dict.update(decrypt_dict)

    # print(encryption_key_deduplicated_sorted)
    for index_for_word, encryption_word in enumerate(encryption_key_deduplicated_sorted):
        print(index_for_word, encryption_word)
        for index_for_char, letter in enumerate(encryption_word):
            # print(letter)
            if secondary_decrypt_dict.get(letter) is None:
                print(f"secondary_dict nor contain:{letter}")
                if decrypt_dict.
                try:
                    print("".join(char for char in inputs_sorted[index_for_word])[index_for_char])
                    secondary_decrypt_dict.update(
                        {letter: "".join(char for char in inputs_sorted[index_for_word])[index_for_char]})
                    setter = False
                    # print(secondary_decrypt_dict)
                except IndexError:
                    setter = True
            else:
                # pass
                setter = False
                print(f"Contains:{letter}")
    encryption_key_deduplicated_sorted = encryption_key_deduplicated_sorted[1:] + encryption_key_deduplicated_sorted[:1]
    if setter:
        sorted(encryption_key_deduplicated_sorted, key=len)
    print(decrypt(encryption_key_as_string, secondary_decrypt_dict))
    mover += 1

print(secondary_decrypt_dict)


print(decrypt_dict)
final_dict = {**secondary_decrypt_dict, **decrypt_dict}

print(final_dict)
str = "cvvli euynm acqyg dxggli euzzuz cnm bxi lupi cll cww"
if decrypt(str, final_dict) is None:
    ret_str = ""
    for char in encryption_key_as_string:
        if char != " ":
            ret_str.__add__(char)
        else:
            ret_str.__add__(" ")
    print(ret_str)
else:
    print(decrypt(str, final_dict))

user_5237560 · Answer

A backtracking approach can be used to find a combination of letter mapping that produces matching words on a length-by-length basis.

To optimize this 'trial and error' combinatory traversal, each encrypted letter is assigned the potential clear letters it could map to based on the pairing of encrypted words with clear words of the same length.

knownWords = ["and", "dick", "jane", "puff", "spot", "yertle"]
encrypted  = "bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn"

letterMap = dict()
for word in encrypted.split():
    for kw in knownWords:                 # matching words 
        if len(kw)!=len(word): continue   # of same length
        for k,e in zip(kw,word):                  
             letterMap.setdefault(e,set()).add(k) # letter to letter options

def decrypt(w,mapping): return "".join(mapping.get(c,c) for c in w)

from collections import deque
finalMap = None
mapQ     = deque([[dict(),set(letterMap),set()]]) # mapping,remaining,usedClear
while mapQ and not finalMap:
    mapping,remaining,used = mapQ.pop()           # DFS mapping to complete
    letter = remaining.pop()                      # pick a letter to map
    for clearLetter in letterMap[letter]-used:        # select clear letters
        newMap    = {**mapping,letter:clearLetter}    # enhance mapping
        if remaining:                                 # more letters to map
            mapQ.append([newMap, remaining.copy(), used | {clearLetter}]) 
            continue
        if all(decrypt(w,newMap) in knownWords for w in encrypted.split()):
            finalMap = newMap                         # found mapping that works
            break

final result:

print(decrypt(encrypted, finalMap))
'dick and jane and puff and spot and yertle'

print(finalMap)
{'y': 'u', 'p': 'y', 'q': 'p', 't': 't', 'j': 'i', 'm': 'f', 'e': 'r',
 'f': 'l', 'g': 'k', 'h': 'j', 'a': 'o', 'v': 'c', 'n': 'e', 'x': 'a',
 'r': 's', 'b': 'd', 's': 'n'}

Other test case:

knownWords = ['all', 'and', 'apple', 'ass', 'gibble', 'horror', 'hound', 'love',
      'tie']
encrypted  = "cvvli euynm dxggli euzzuz cnm bxi lupi cll cww"

...

decrypt(encrypted, finalMap)
'apple hound gibble horror and tie love all ass'

decrypt("cvvli euynm acqyg dxggli euzzuz cnm bxi lupi cll cww",finalMap)
'apple hound aaqub gibble horror and tie love all ass'

Note that I used a strict condition to exit the search loop where all encrypted words are found in the known word list. This could be relaxed by tracking a "best match" and letting the loop exhaust the mapQ queue. Defining what "best match" means would be up to you. It could be measured in number of words, number of distinct words, character coverage, etc.

[EDIT] More efficient approach ...

I experimented with the above "best match" approach and found that the processing time would become extremely long. So I made a new (recursive) solution based on mappings of whole words instead of a letter by letter search. This gives much better results and is less complicated to manage for partial matches:

def decrypt(w,mapping): return "".join(mapping.get(c,c) for c in w)

def findMapping(knownWords,encrypted):
    if not encrypted: return {} # no more encrypted words, stop recursion
    if isinstance(encrypted,str): encrypted = list(set(encrypted.split()))
    bestMap   = findMapping(knownWords,encrypted[1:]) # track best
    bestMatch = sum(decrypt(w,bestMap) in knownWords for w in encrypted)
    eWord     = encrypted[0] # map first encrypted word
    for kWord in knownWords:
        if len(eWord) != len(kWord): continue # with word of same length
        mapping = {e:k for e,k in zip(eWord,kWord)}  # letter to letter
        if decrypt(eWord,mapping) != kWord: continue # one to one only
        unused   = str.maketrans('','',kWord)  # removed used letters
        subWords = [*filter(None,(kw.translate(unused) for kw in knownWords))]
        unmapped = str.maketrans('','',eWord)  # remove mapped letters
        subCrypt = [*filter(None,(ew.translate(unmapped) for ew in encrypted))]
        mapping.update(findMapping(subWords,subCrypt)) # Recurse subwords
        match = sum(decrypt(w,mapping) in knownWords for w in encrypted)
        if match>bestMatch: bestMap,bestMatch = mapping,match  # best match
    return bestMap # return mapping with best match (number of mapped words)

This solution picks an encrypted word and tries to map it to a known word of the same length.
This establishes a letters mapping (that must be one-to-one).
Letters from this mapping are removed from the encrypted words and from the known words before going down to the next level of recursion.
The next level of recursion thus has only a limited mapping to perform which will not overlap with the first word's letter mapping.
Doing this for every known word of the same length and, through recursion, processing all the encrypted words will produce word-to-word mappings that are compatible from a letter-to-letter perspective.
The mapping with the largest number of matching word is tracked and returned to the caller.
To support incomplete matches, the solution starts by recursing with the first encrypted word skipped. This establishes a baseline for selecting the best match.

output:

knownWords = ["and", "dick", "jane", "puff", "spot", "yertle"]
encrypted  = "bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn"
mapping    = findMapping(knownWords,encrypted)
print(decrypt(encrypted,mapping))
'dick and jane and puff and spot and yertle'
print(mapping)
{'r': 's', 'q': 'p', 'a': 'o', 't': 't', 'y': 'u', 'm': 'f', 'b': 'd',
 'j': 'i', 'v': 'c', 'g': 'k', 'p': 'y', 'n': 'e', 'e': 'r', 'f': 'l',
 'h': 'j', 'x': 'a', 's': 'n'}


knownWords = "apple hound gibble horror and tie love all ass".split()
encrypted  = "cvvli euynm acqyg dxggli euzzuz cnm bxi lupi upilucnm"
mapping    = findMapping(knownWords,encrypted)
print(decrypt(encrypted,mapping))
'apple hound aaqub gibble horror and tie love oveloand'
print(mapping)
{'b': 't', 'x': 'i', 'i': 'e', 'l': 'l', 'u': 'o', 'p': 'v', 'c': 'a',
 'v': 'p', 'd': 'g', 'g': 'b', 'e': 'h', 'y': 'u', 'n': 'n', 'm': 'd',
 'z': 'r'}

How to create decrypt dictionary based on list of strings to encrypt by string

1 Answers