12-05-2023.md

Algorithms: Coding Puzzles

Title:

Question 5: What do I say when I am decoded?

Language:

Python

Algorithm:

1. The given codebook represents each character in the original string with a unique bit pattern.

2. The encoded string is a sequence of bits that represent the characters in the original string using the bit patterns from the codebook.

3. The function loops through each bit in the encoded string and concatenates it to a current_code variable. It then iterates through the key-value pairs in the codebook dictionary and checks if current_code matches any of the codes. If a match is found, the corresponding symbol is appended to a decoded variable, current_code is reset to an empty string, and the loop continues with the next bit of the encoded string.

4. If current_code does not match any of the codes and is not a prefix of any of the codes, the function raises a ValueError indicating that the encoding is invalid. Once all of the bits in the encoded string have been processed, the function returns the decoded message as a string.

5. The code you see is a simplified version of the original decode function that achieves the same functionality in a more concise way. It uses a while loop instead of a for loop and eliminates the need for a current_code variable by checking for matches with the startswith method. If a match is found, it removes the matched code from the start of the encoded string and adds the corresponding symbol to the decoded variable. If no match is found, it raises a ValueError.

Code:

from typing import Dict
def decode(encoded: str, codebook: dict) -> str:
    decoded = ""
    while encoded:
        for symbol, code in codebook.items():
            if encoded.startswith(code):
                decoded += symbol
                encoded = encoded[len(code):]
                break
        else:
            raise ValueError("Invalid encoding")
    return decoded
  
codebook = {
    'a': '00',
    'b': '01',
    'c': '10',
    'd': '1100',
    'e': '1101',
    'f': '1110',
    'g': '111100',
    'h': '111101',
    'i': '111110',
    'j': '1111110000',
    'k': '1111110001',
    'l': '1111110010',
    'm': '1111110011',
    'n': '1111110100',
    'o': '1111110101',
    'p': '1111110110',
    'q': '1111110111',
    'r': '1111111000',
    's': '1111111001',
    't': '1111111010',
    'u': '1111111011',
    'v': '1111111100',
    'w': '1111111101',
    'x': '1111111110',
    'y': '1111111111',
    'z': '11111111110000',
    ' ': '11111111110001'
}

encoded_string = "1111101111111111000111111100101111110101111111110011011111111111000100111111010" \
                 "0111100110111111100101111010010111111000111111111110001101111110101110011011111" \
                 "1111110001101111010011111100101111110010110111111101001111001101111111111100010" \
                 "11101100011111110111111111001110111111111110001111110111111101011111111110001111" \
                 "11011111110011111111111000111101111111011111111010011111111110001001111110100110" \
                 "01111111111000111011111111110101111101111111010111110111111010011110011111111110" \
                 "00100111111010011001111111111000111111011111111110001110011111011111110011111110" \
                 "01011111011111100011101111111111100011111111010111101110111111111110001111111110" \
                 "11111110101111111100011001111111111000111111111110001111111111100011111111010111" \
                 "1010011111110101111111111000100111111011011111101101101001111111000111111100111" \
                 "11111111100011111011111101001111111111000111111110101111011101111111111100011111" \
                 "11011011110111111110000011111110011101"

decoded_string = decode(encoded_string, codebook)
print(decoded_string)

Solution:

i love angelhack code challenge because it is fun and exciting and i dislike the word yab that appears in the phrase

The yab represents space (' '). i.e yab is equivalent to 11111111110001 from the codebook.