Finger Exercise: Update book cipher by creating new book

Question

I'm working my way through the finger exercises in John Guttag's book Introduction to Python Programming, third edition. The following finger exercise on page 143 describes encryption/decryption with a book cipher. The first exercise was to implement decoder and decrypt in the same style as encryption is working.

The book mentions this bug and gives the task to implement a solution like they hinted at:

The bug:

When a character occurs in plain text but not in the book, something bad happens. The code_keys dictionary assigns -1 to each such character, and decode_keys assigns -1 to the last character in the book, whatever that may be.

The solution:

Create a new book by appending something to the original book.

My solution new_book uses a lambda function to be in line with the rest of the code. But this overturns the principle of encryption, if the plain text is needed during encryption and decryption

# Mapping individual, unique letters of plaintext to index number
gen_code_keys = (lambda book, plain_text:
                 {c: str(book.find(c)) for c in plain_text})

# Slicing operator at the end to remove the first '*' at the beginning
encoder = (lambda code_keys, plain_text:
           "".join(["*" + code_keys[c] for c in plain_text])[1:])

# Encrypt plain_text by giving the encoder a book for indexing
encrypt = (lambda book, plain_text:
           encoder(gen_code_keys(book, plain_text), plain_text))

# Decode key generator analogue to gen_code_keys
gen_decode_keys = (lambda book, cipher:
                   {c: book[int(c)] for c in cipher.split("*")})

# Implement decoder by looping through all numbers in cipher
decoder = (lambda decode_keys, cipher:
           "".join((decode_keys[c] for c in cipher.split("*"))))

# Decrypting the cipher analog to encrypt function
decrypt = (lambda book, cipher:
           decoder(gen_decode_keys(book, cipher), cipher))

Don_Quixote = "In a village of La Mancha, the name of which I have no " \
    "desire to call to mind, there lived not long since one of those " \
    "gentlemen that keep a lance in the lance-rack, an old buckler, a lean " \
    "hack, and a greyhound for coursing."

# --------------- My Solution --------------- #
# Creating new book with missing letters in book to fix cipher bug
new_book = (lambda book, plain_text:
            book + "".join([c for c in plain_text if c not in book]))

# plain text contains the letters: !ABENQjx
plain_text = "No joke, Abraham Boston had six beer. Everyone it Q!"

# Create new book by appending missing letter from plain_text
book = new_book(Don_Quixote, plain_text)

print(plain_text)
cipher = encrypt(book, plain_text)
print(cipher)
print(decrypt(book, cipher))

Ok, so I changed my code so far that I create the updated book with the missing characters appended before encrypting/decrypting. Thus I removed the function call new_book inside the encrypt and decrypt function. With that at least I don't need the plain_text in my decrypt function.

Are there further improvements I could make?

Answer 1

It is difficult to answer this question. There is so much about the code I hate, but I have to restrict my review to only your code: the code after the # —- My solution -- # comment marker.

Forget lambda

lambda functions have their uses. This is not one of them. Compare this:

new_book = (lambda book, plain_text:
            book + "".join([c for c in plain_text if c not in book]))

with this:

def new_book(book, plain_text):
    return book + "".join([c for c in plain_text if c not in book])

They both do exactly the same thing: they create a function accepting two parameters, and assign that function to the identifier new_book. In my opinion, the latter is clearer; the reader can immediately tell a function is being defined. The indentation is less, and a level of parentheses has been removed.

Additionally, several language features are available with the def version - type-hints and """docstrings""" - which can further improve understandability.

def new_book(book: str, plain_text: str) -> str:
    """
    Create a new “book” to use for encryption and decryption,
    will is a duplicate of the original book, plus any letters
    in the `plain_text` message which are missing from the original
    book.
    """

    return book + "".join([c for c in plain_text if c not in book])

O(mn)

Your book has a certain number of characters. Let’s call that m. Your plain_text has a certain number of characters. Let’s call than n.

[c for c in plain_text if c not in book]

This loops n times, going through all of the letters of plain_text, and for each letter, it searches book for an occurrence of that letter. If a letter is not found in book, that is only determined after scanning through all m letters of the book. n outer loops iterations with up to m iterations in the inner loop means this is has a worst case of \$O(m*n)\$ operations. Potentially quite slow!

This worse case bound can be improved, but it requires a bit of preprocessing … which is easy with the def version of the function:

def new_book(book, plain_text):
    book_letters = set(book)
    return book + "".join([c for c in plain_text if c not in book_letters])

Turning book into a set of letters is an \$O(m)\$ operation. With that, c not in book_letters becomes an \$O(1)\$ operation. Repeated in the loop n times makes it \$O(n)\$, so the entire function becomes \$O(m + n)\$ … considerably faster.

But wait! While we’re at it, what is with the temporary list of characters [c …]? It is created just to be iterated over in the join(…). Why not just iterate without the temporary list creation?

def new_book(book, plain_text):
    book_letters = set(book)
    return book + "".join(c for c in plain_text if c not in book_letters)

Better solutions

Why add plain_text to the book? If you and you friend (or spy) have exchanged a book, and then you need to send a message with letters which were not in the book, you have to send a complete new_book to your friend (spy) … which could be intercepted making the encryption useless.

Plus, if a second message is sent with still different letters, yet another book would be necessary. A third message would require a third book, and so on! Decoding the cipher would require knowing which book was used to encode it (book1, book2, book3, …) — information which is not given.

It is a simple matter to expand the book without relying on plain_text. Just unconditionally add string.printable to the original book. This easily takes care of your missing !ABENQjx characters.

Except, it is still not a complete solution. Résumé would still result in -1 encodings. Adding the entire Unicode character set to book would be required, if you stayed with this approach. Instead, why not record the maximum value your book encoder returns, and return that value plus ord(c) for characters not in the book? When an encoded value exceeds the maximum value the book can decode, subtract that maximum, and use chr(#) to convert it back to the required character.