Ciphers

Encryption

Introduction

For centuries, people have tried to encrypt texts so that outsiders could not easily understand them. In this task you will have to decipher a text produced by a group of preschoolers who decided to encrypt part of the contents of their parents' library by covering the letters in selected lines with stickers.

Task

The children began by preparing $n$ bags: one for each unique character in the whole library. The boys drew $3n$ different pictures, and the girls printed stickers with these pictures: each picture was printed in some unknown and possibly different number of copies. There are, however, so many stickers that they will not run out during the game. Next, into each of the prepared bags the children poured the stickers corresponding to exactly three pictures. Altogether, every sticker ended up in one of the bags.

During the game, the children decided to encrypt some of the lines in the books. For each character they came across, they drew a random sticker from the bag belonging to that character and stuck it in the character's place. Children being children, they got bored, so not all lines of the books were processed in this way. Unfortunately, the pictures cannot be peeled off in any way, but perhaps, by analysing the arrangements of letters in the texts that were not covered, we will be able to reconstruct the text of the covered lines.

Write a function decipher_corpus(clear_corpus, ciphered_corpus) that takes two arguments:

• clear_corpus: a list containing unencrypted strings $-$ lines that the children did not touch. For example:

clear_corpus = ["a tajną . u rzymian niewolnika , który ukradł , ", 
    "środka : tam wszystko jasno oświetlone . * i widzę ", 
    "się do góry , utracił własność * dążącą do centru ",
    "chciałabym widzieć tego malca tylko na chwilę . słyszałem , ",
    "mości notę , prosząc o uwolnienie z tej usługi , "]

• ciphered_corpus: a list of encrypted lines $-$ lines covered with stickers. For example:

ciphered_corpus = ["🥥🖕👼🥥🔀🛠👡🐌💸🐌📩🖕🧇🤿🧰🦆🥨🥥🦨🐌🚕🔻🥅🐘🚒🗣🛠🔻🚄🥥🤳🥺🐌🚄👼👲🐤🧰🤳📩🚄🔒🥥🧵🐈🖕🥺🖕",
    "🥤🔒🚒🚔🚄🦫🐌🦒🐌👼🦫🦆🖕🐘🦓🤿💣🦓🚷👱🧔🖕💐🥥🚭🚕🚒🐌🙉🥤🐘🥨🗿👼🗣🚒🦨🔶🤳💑🖕📈🐌🔻🖕🖊🔻🚔🐅👽🐌",
    "🦓🔻👽🐌🧵🚒🤳🚥🐛🐤💁🖕🖈🤳🔖👼🧇🦫💯🕰👂🤳🐘👂🥥🚭🛠🚒🚚🛰🤳🧚🐌🧵👠🦔🕶🦈👡🐌🚓🙉🐌🦈🗿🦨🚷🐤🧍🐌"]

This function should decipher the list of lines ciphered_corpus, written in the picture cipher, using the other, unencrypted lines clear_corpus. The function should return a list of deciphered lines.

Evaluation

For this task you can receive a score between 0 and 1 point. Your function decipher_corpus(clear_corpus, ciphered_corpus) will be tested on 4 test cases: independent ciphers. The scoring criterion for a given cipher will be the percentage of correctly deciphered characters in the text (the number of correctly deciphered characters divided by the number of all characters in the text). A model achieving a classification accuracy below 50% will receive 0 points.

The final score will be the mean of the scores for all tests and will be computed according to the formula:

$$\mathrm{score} = \frac{1}{4} \sum_{i=1}^4 2 \cdot \max(\mathrm{accuracy}_i - 0.5, 0)$$

Constraints

• Running all of your code with the FINAL_EVALUATION_MODE flag set to True should take no longer than 5 minutes on Google Colab with a GPU.

• Your solution will be tested without internet access.

Data

The data available to you in this task are:

• clear_lines.txt - a file containing lines from books that the children did not touch - unencrypted text;
• ciphered_lines.txt - a file containing 30000 lines from books, encrypted in the way described above; this is the set on which you can evaluate your solution;
• ciphered_lines_ground_truth.txt - a file containing the deciphered lines from that file.

Remarks and hints

• All characters were encrypted, including spaces, except for the newline character (there are none in any of the sets).
• The three pictures assigned to a letter do not necessarily have equal probability of being stuck in place of that letter, i.e. some pictures may have been used more often than the others in the triple.
• This may be useful:

  from gensim.models import Word2Vec as Letter2Vec
  

Submission files

Only this notebook.

Evaluation

Remember that during grading the FINAL_EVALUATION_MODE flag will be set to True. Using the validation_script.py script, you will be able to make sure that your solution will run correctly during grading.

Starter code

Loading the data

Your solution

This is the only section in which you need to do anything.

Evaluation

During the grading of the solution, your function decipher_corpus will be called in a way similar to the one below. Different, test data will be used, however.

Before submitting, make sure that, after setting the flag FINAL_EVALUATION_MODE = True, the whole notebook runs from start to finish (the Run All command) without errors and without user intervention. You can also run the validation script validation_script.py, which executes the whole notebook and scores the decipher_corpus function defined in it.