Recursive function with strings and integers

Question

I'm not able to solve an exercise. The statement is as follows:

A word was compressed to an integer using the following algorithm:

Each capital letter from A to Z was mapped to a number between 1 and 26, with the letter A represented by the number 1, the letter B by the number 2 and so on.
The value of the first letter of the word was placed in the first 5 bits, the least significant, of the integer, the second letter was placed in the next 5 bits and so on, until the last letter of the word.
After placing each letter in the integer, the remaining bits of the integer were left as 0.

Your task is to recover the original word, given the integer that represents it. To do this, implement a recursive function called decompress that takes the integer x as an argument and returns the original word.

Input
There is no data entry, the function is called for arbitrary values defined in test cases with integer values 0 < x

Output
The function must return a string containing the original word represented by the integer x supplied to the function.

Note
In the first example, the value 65 when divided by 2⁵ generates remainder 1. This value represents the letter 'A'. The same value 65 when the entire division by 2⁵ generates a value of 2. Therefore, the algorithm is executed recursively. In the second execution, the rest of the division of 2 by 2⁵ generates a value of 2 representing the letter 'B'. The entire division generates a zero value indicating end of execution.

For example:

|-----------------------------|------------------|
|         Test                |      Result      |
|-----------------------------|------------------|
|print(decompress(65))        |        AB        |
|-----------------------------|------------------|
|print(decompress(54579234))  |        BATATA    |
|-----------------------------|------------------|
|print(decompress(6040945729))|        ABACATE   |
|-----------------------------|------------------|

How can I do it using only one recursive function? So far I've only managed to use two functions, one of which calculates in relation to the integers of which represent the letters of the alphabet and the other to show the formed word

restos = []
palavra_formada = []
alfabeto = {
    1: 'A',2: 'B',3: 'C',4: 'D',5: 'E',6: 'F',7: 'G',8: 'H',9: 'I',10: 'J',11: 'K',12: 'L',
    13: 'M',14: 'N',15: 'O',16: 'P',17: 'Q',18: 'R',19: 'S',20: 'T',21: 'U',22: 'V',23: 'W',
    24: 'X',25: 'Y',26: 'Z',
}

def aux(n):
    if n == 0:
        return 0
    elif n == 1:
        restos.append(n % 32)
        return 1
    else:
        restos.append(n % 32)
        return aux(n // 32)

def decompress(n):
    aux(n)
    palavra_resultante = ""
    for i in restos:
        palavra_formada.append(alfabeto[i])
    for j in palavra_formada:
        palavra_resultante += j

    return palavra_resultante

You can do the number to letter conversion in aux as well, produce the result as a string instead of a list, and return it instead of storing it in a global variable. Then you don't need decompress anymore (so you can rename aux to decompress). — Thomas
– Thomas, Commented Nov 1, 2020 at 9:55
@Thomas , that's exactly what I'm wanting to do, but I'm not able to formulate the logic completely to make this implementation — Vinicius Vasconcelos
– Vinicius Vasconcelos, Commented Nov 1, 2020 at 10:02
Note that you can use the string module (.ascii_uppercase?) instead of writing out the alphabet — Joshua Nixon
– Joshua Nixon, Commented Nov 2, 2020 at 13:36

Karaldo · Accepted Answer · 2020-11-02 13:33:11Z

You may use bitwise operators:

# Define the length of the code word in bits
# Normaly i would expect the encoding word 
# length as a parameter of the function or as a member of a relating class.
word_length = 5

# Define the bitmask: 0000 0000  0000 0000  0000 0000  0000 0000  0001 1111 
bitmask = 2 ** word_length - 1


def decompress(n):
    result = ''
    if n > 0:
        # Take the only the last n bit by a and with the bitmask
        letter_code = n & bitmask
        # Decode the resulting code
        result += alphabet[letter_code]
        # recursively call the function without the current letter
        # by using a bitwise right shift with the word length
        result += aux(n >> word_length)
    return result

But if you have to use the division and modulo operators:

word_length = 5

max_letters_count = 2 ** word_length


def decompress(n):
    result = ''
    if n > 0:
        # Take the only the last n bit by taking the modulo with the max_letters_count 
        letter_code = n % max_letters_count 
        # Decode the resulting code
        result += alphabet[letter_code]
        # recursively call the function without the current letter
        # by using a integer division with the max_letters_count 
        result += aux(n // max_letters_count )
    return result

Now you can make these functions tail recursive (https://en.wikipedia.org/wiki/Tail_call):

def aux_tail_recursive(result_string, code):
    if code <= 0:
        return result_string
    result_string += alphabet[code & bitmask]
    next_code = code >> word_length
    return aux_tail_recursive(result_string, next_code)

or

def decompress_tail_recursive(result_string, code):
    if code <= 0:
        return result_string
    result_string += alphabet[code % max_value]
    code_next = code // max_value
    return decompress_tail_recursive(result_string, code_next)

Man, with this tip you give and your codes, I was able to develop in a simpler way. I'll post the code here and then you tell me what you think.

Vinicius Vasconcelos · Accepted Answer · 2020-11-09 21:00:45Z

With Karaldo's tips, I was able to think of a way to optimize my code so that it would be simpler and still maintain recursion.


NUM_BITS = 5


def letra(numero):
    # Numerical representation of the letter
    cod_letra = ord('A') + numero - 1
    # Symbolic representation of the letter
    return chr(cod_letra)


def decompress(x):
    if x == 0:
        return ''

    bits = x % (2 ** NUM_BITS)  # Value stored in the least significant NUM_BITS
    x = x // (2 ** NUM_BITS)  # Shift of the least significant bits

    return f'{letra(bits)}{decompress(x)}'

# # Bit manipulation version
# def decompress(x):
#     if x == 0:
#         return ''

#     bits = x & (2 ** NUM_BITS - 1)
#     x = x >> NUM_BITS

#     return f'{letra(bits)}{decompress(x)}'

Collectives™ on Stack Overflow

Recursive function with strings and integers

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related