Decrypt Message

KEY : enc[n] = dec[n] + sum[n - 1] - 26 * m (where m > 0)

LEARNT: DON"T NEED TO PROCESS IN REVERSE ORDER, SAME ORDER PLUS NEGATION IS FINE

An infamous gang of cyber criminals named “The Gray Cyber Mob”, which is behind many hacking attacks and drug trafficking, has recently become a target for the FBI. After intercepting some of their messages, which looked like complete nonsense, the agency learned that they indeed encrypt their messages, and studied their method of encryption.

Their messages consist of lowercase latin letters only, and every word is encrypted separately as follows:

Convert every letter to itsASCII value. Add1to the first letter, and then for every letter from the second one to the last one, add the value of the previous letter. Subtract26from every letter until it is in the range of lowercase lettersa-zin ASCII. Convert the values back to letters.

For instance, to encrypt the word“crime”

The FBI needs an efficient method to decrypt messages. Write a function nameddecrypt(word)that receives a string that consists of small latin letters only, and returns the decrypted word.

Explain your solution and analyze its time and space complexities.

Examples:

input:  word = 
"dnotq"

output: 
"crime"


input:  word = 
"flgxswdliefy"

output: 
"encyclopedia"

Since the function should be used on messages with many words, make sure the function is as efficient as possible in both time and space. Explain the correctness of your function, and analyze its asymptotic runtime and space complexity.

Note:Most programing languages have built-in methods of converting letters to ASCII values and vica versa. You may search the internet for the appropriate method.

Constraints:

• [time limit] 5000ms

• [input] stringword

  • The ASCII value of every char is in the range of lowercase letters a-z .

• [output] string

Hints&Tips

• The most useful way to tackle these kind of problems are in reverse engineering. And for that your peer needs many examples, more than provided.
• One way to build examples, is by generating them manually. A much more efficient way, would be simply implementing an encryption function (which is straightforward), and using it for test. Encourage your peer to do so.
• The simplest solution to this question decrypting one letter at a time, every time using the letters already decrypted. If your peer is stuck, advise him or her to try finding the relations between the previous decrypted letter, and the current encrypted one.
• If your peer needs further assistance, try guiding him towards the equation: enc[n] = dec[n] + secondStep[n-1] + 26m , which is fully explained in the solution.
• Your peer should be given full score, only if they succeed building and testing an efficient decryption function, without any hints. The function should O(N) in both time and space complexities.
• Make sure your peer gives an accurate complexity analysis, and whether the function they implemented is more efficient when used once on one long word, or many times when used on rather short words.

Solution

First of all, notice that the first letter is very easy to decrypt:

1. Convert the first letter back to its ASCII value.
2. Subtract 1 from it.
3. Move the value to be in the range of a-z ASCII values ( 97-122 ), by adding 26 .
4. Convert the result back to a character.

The decryption of the rest of the letters is done by almost the same algorithm - given the decrypted previous letterprev, and its value after the second step of encryption - denotedsecondStepPrev:

1. Convert the current letter back to its ASCII value.
2. Subtract secondStepPrev from it.
3. Move the value to be in the range of a-z ASCII value ( 97-122 ), by adding multiples of 26 .
4. Convert the result back to a character. Store its ASCII value in prev , and add its value to secondStepPrev (for the decryption of the next letter).

Let’s examine the algorithm using the following notation:dec[n]- the n’th letter before encryption.enc[n]- the n’th letter before encryption.secondStep[n]- the n’th letter immediately after step 2 in the encryption.

The encryption algorithm gives the following relation for some integerm(which represents the number of times we need to add 26 to get to an ascii value):enc[n] = dec[n] + secondStep[n-1] + 26mBy isolating dec[n], we get:dec[n] = enc[n] - secondStep[n-1] - 26mThough the value ofmisn’t initially known, since the value of the decrypted letter must be in the ASCII range ofa-z, the decrypted letter is easily found adding 26’s toenc[n] - secondStep[n]until it is in the right range.

Pseudocode:

function decrypt(word):
    secondStep = 1
    decryption = ""

    for i from 0 to word.length - 1:
        newLetterAscii = asciiValue(word[i])
        newLetterAscii = newLetterAscii - secondStep

        while (newLetterAscii < asciiValue('a')):
            newLetterAscii += 26

        decryption = decryption + asciiToChar(newLetterAscii)
        secondStep += newLetterAscii

    return decryption

• asciiValue(chr)
  • returns the ASCII value of a given char.
• asciiToChar(chr)
  • returns the char of a given ASCII value. When your peer programs their solution, it is preferable they use one of the built in functions in the language of their choice, rather than implementing them themselves.

Time Complexity:the function’s asymptotic time complexity isO(N), whereNis the length of the input string. the loop that iterates through the letters in the input is performedNtimes. In the loop, almost every step is done inO(1), except for the loop that is supposed to move the decrypted letter back to the range ofa-z. Theoretically, thesecondStepmay grow linearly with the size of the input. There are two ways to deal with this:

1. Instead of secondStep itself, we may only keep its remainder after being divided by 26 (since we add/subtract multiples of 26 anyway, the equation dec[N] = enc[N] - (secondStep[N-1] % 26)- 26M still holds, only for a different M ). This way all values in every iteration are kept in a constant range.
2. Note that since in practice this function is used only for words in the English language, the input is bounded and we therefore may ignore the growth of the secondStep anyway.

Space Complexity:the space usage is alsoO(N)since the output is the same size of the input, and we only keep the output and the second step in storage.

Good luck! and remember…