ACSL Junior Finals Run-Length Encoding Problem

This article discusses and contains the Python code solution for the American Computer Science League (ACSL) Junior Division 2023-2024 Finals #1 Problem Run-Length Encoding.

Run-Length Encoding problem

Run-Length Encoding problem

The Run-Length Encoding problem was the first programming problem in the ACSL Junior Division 2023-2024 Finals.

First, please read the Run-Length Encoding problem. Make sure you understand the problem. Read it many times, if necessary. Then, write the algorithm on paper before coding anything. For your algorithm, you can write either pseudocode or a diagrammatical flowchart.

Programming Solution Logic

The input is a line of data containing a code from one of these values E, EV, D and DV, and the message to be encoded to decoded.

The output is a line with either the encoded or decoded messages.

Assuming you have read the problem, we find that this is quite straightforward. There are 4 types of possible codes and we can work on each part separately.

Let us refer to the code as code and the message as s.

1) code = E

We have to encode the message. For every repeating letter, the new encoded message will have 1 less than the number of occurrences, in hexadecimal.

1. Create new variable new_s that will contain the encoded message.
2. Create new variable letter that will represent the current character.
3. Create new variable count that will contain the number of times letter has appeared in this sequence.
4. Now, loop through every character in message s.
5. If the character is the same as letter, increase the count by 1.
6. If the character is not the same as letter and this is not the first iteration started by loop at (4), we will convert the value of count - 1 to chunks of 16, and then to hexadecimal.
7. To convert the count to chunks of 16, subtract 16 repeatedly from the count - 1 value and write it as letter suffixed with F. The last value will be directly converted to hexadecimal.
8. For each of these, we append the character value of letter and hexadecimal uppercase value of the chunk to new_s.
9. Continue with the loop started at (4) until all characters in s are exhaused.

2) code = EV

We have to encode the message. This is similar to the previous Case 1 except that the new encoded message will contain the number of times, in hexadecimal. If the final count has 2 or more hexadecimal digits, this count is prefixed and suffixed by -.

1. Create new variable new_s that will contain the encoded message.
2. Create new variable letter that will represent the current character.
3. Create new variable count that will contain the number of times letter has appeared in this sequence.
4. Now, loop through every character in message s.
5. If the character is the same as letter, increase the count by 1.
6. If the character is not the same as letter and this is not the first iteration started by loop at (4), we will convert the value of count directly to hexadecimal.
7. If the value of count is greater than 16, convert count to hexadecimal, prefix and suffix it with -.
8. For each of these, we append the character value of letter and hexadecimal uppercase value of the chunk to new_s.
9. Continue with the loop started at (4) until all characters in s are exhaused.

3) code = D

We have to decode the message. This is the opposite of Case 1.

1. Create new variable new_s that will contain the decoded message.
2. Loop through message s two characters at a time; the first character is the current character letter and the second character is count, the number of times, in hexadecimal, the character letter is repeating.
3. For every iteration, we append count occurrences of the character letter. For example, dA will print dddddddddd because d is to be printed A₁₆, which is 10 times.
4. Append the string created in (3) to new_s.
5. Continue with the loop started at (2) until all characters in s are exhaused.

4) code = DV

We have to decode the message. This is the opposite of Case 2.

1. Create new variable new_s that will contain the decoded message.
2. Loop through message s two characters at a time.
3. If the second character count is a hyphen -, jump to step (9). Or else, go to step (4).
4. The first character is the current character letter and the second character is count, the number of times, in hexadecimal, the character letter is repeating.
5. For every iteration, we append count occurrences of the character letter. For example, dA will print dddddddddd because d is to be printed A₁₆, which is 10 times.
6. Append the string created in (4) to new_s.
7. Continue with the loop started at (2) until all characters in s are exhaused.
8. Jump to step (12).
9. At this point, count has a - instead of a hexadecimal number. We start another loop and capture the hexadecimal numbers from the first - to the next -.
10. For every hexadecimal digit found in (9), convert it to integer and append count occurrences of letter. For example, f-2F- will print f 2 * 16 + 15 times = 47 times. So this line will append 47 occurrences of f to new_s.
11. Continue with the loop started at (2) until all characters in s are exhaused.
12. End

My Python solution

I created the main function using the provided test cases with their output and function encode_decode(code, s).

This is my Python solution:

# Function to encode or decode the string
def encode_decode(code, s):
    new_s = ''
    if code.startswith('E'):
        letter = s[0]
        count = 0
        for i, x in enumerate(s):
            if i > 0 and letter != x:
                if code == 'E':
                    count -= 1
                    if count > 16:
                        while count > 16:
                            new_s += letter + 'F'
                            count -= 16
                        count = hex(count)[2:].upper()
                else:
                    if count > 16:
                        count = '-' + hex(count)[2:].upper() + '-'
                new_s += letter + str(count)
                letter = x
                count = 1
            else:
                count += 1
        # For the last letter count
        if code == 'E':
            count -= 1
            if count > 16:
                while count > 16:
                    new_s += letter + 'F'
                    count -= 16
                count = hex(count)[2:].upper()
        else:
            if count > 16:
                count = '-' + hex(count)[2:].upper() + '-'

        new_s += letter + str(count)
    elif code == 'D':
        letter = None
        count = 0
        s_len = len(s)
        for i in range(s_len // 2):
            letter = s[i * 2]
            count = int(s[i * 2 + 1], 16) + 1
            new_s = new_s + letter * count
    elif code == 'DV':
        i = 0
        while i < len(s) - 1:
            letter = s[i]
            count = s[i + 1]
            if count in '1234567890':
                new_s += letter * int(count)
            elif count in 'abcdefABCDEF':
                count = int(s[i + 1], 16)
                new_s = new_s + letter * count
            elif count == '-':
                i += 2
                hex_num = ''
                while s[i] != '-':
                    hex_num += s[i]
                    i += 1
                if hex_num != '':
                    i -= 1
                    count = int(hex_num, 16)
                    new_s += letter * count
            i += 2
    return new_s

# Main function
if __name__ == '__main__':
    input_data = '''
E ABBCEEEEAAAAAADDDAAACCCCCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBAA
EV ABBCEEEEAAAAAADDDAAACCCCCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBAA
D a0b1a2dAfFfFfEE2
DV a1b2a3dBf-2F-E3
'''
    output_data = '''
A0B1C0E3A5D2A2C4BFBDA1
A1B2C1E4A6D3A3C5B-1E-A2
abbaaadddddddddddfffffffffffffffffffffffffffffffffffffffffffffffEEE
abbaaadddddddddddfffffffffffffffffffffffffffffffffffffffffffffffEEE
'''
    sample_input = [x.split() for x in input_data.strip().split('\n')]
    expected_output = output_data.strip().split('\n')
    for i, (c, s) in enumerate(sample_input):
        print(expected_output[i] == encode_decode(c, s))

Decoding the program

In the main function, I created a string input_data with the test input, one test case per line.

Using list comprehension, I split it into a 2D list.

A second string output_data contains the expected output, one test case output per line.

The function encode_decode() is called and passes the code and message as parameters.

Useful Python code snippets

There are many code snippets that can be used in competitive programming contests. These are a few.

Use for loop with enumerate

While iterating through the string s, we need the index as well as the current character. So, we use enumerate().

Convert from integer to hexadecimal

Let us do this with an example. The number 123 is 7B₁₆ in hexadecimal. We will use hex(123) followed by string slicing from third character onwards using [2:] followed by.upper()` method. Try this on your Python shell.

>>> hex(123)
'0x7b'
>>> hex(123)[2:]
'7b'
>>> hex(123)[2:].upper()
'7B'

Convert from hexadecimal to integer

The number A10₁₆ in hexadecimal equals 2576 in decimal. We will use int('A10', 16) to convert to hexadecimal A10 to decimal.

>>> int('A10', 16)
2576

Check if a string with a single-digit contains a valid number

There are many ways of doing this. I prefer this block of code expression:

count in '1234567890'

Example:

>>> count = '5'
>>> count in '1234567890'
True

Check if a string with a single-digit contains a valid hexadecimal number from A through F

You can use this block of code expression:

count in 'abcdefABCDEF'

Example:

>>> count = 'e'
>>> count in 'abcdefABCDEF'
True
>>> count = 'E'
>>> count in 'abcdefABCDEF'
True

You can also use:

count.upper() in 'ABCDEF'

Print a repeated string using *

If you want to print the letter f 47 times, then this will work:

>>> print('f' * 47)
fffffffffffffffffffffffffffffffffffffffffffffff

Use the Python shell

We have already used the Python shell quite a few times here. When lost, just open up the Python shell and try random code there to see what options you have with the code you plan to use.

Do not be afraid to try different code styles.

Combine common code and DRY

Wherever possible, see if you can combine common code that repeats itself. DRY stands for don't repeat yourself. You can either use repeating code in a function with appropriate parameters. If you don't have time, or it's too late to make a clean fix, just leave it as it is, as long as it is working properly.

Running the Python code

Run the Python code from your Terminal. You do not need to use any input file because I added the input as a string in the main function.

When the program runs, this will be the output:

$ python run_length_encoding_decoding.py 
True
True
True
True

Conclusion

If there is anything you would like me to add to this article, feel free to comment below or contact me. Thanks.

Related Posts

If you have any questions, please contact me at arulbOsutkNiqlzziyties@gNqmaizl.bkcom. You can also post questions in our Facebook group. Thank you.