ACSL Intermediate Number Transformation Problem

This article discusses and contains the Python code solution for the American Computer Science League (ACSL) Intermediate 2019-2020 Problem Number Transformation.

ACSL Intermediate 2019-2020 Number Transformation problem

Number Transformation problem

The Number Transformation problem was the first programming problem in the ACSL Intermediate Division 2019-2020.

Please read the Number Transformation 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.

Sample Input and Output

The sample input and output cases are included in the main function. The main function contains code to parse the test cases and run each test case by calling the function. The output of each test case is compared to the expected output provided.

Your job is to complete the function and make sure that the output returned is exactly the same as the one in the expected output. This includes data type. For example, if the expected output is integer 193648, your function should return an int 193648 and not a string 193648. They are different.

Programming Solution Logic

The input is a line of data of this format N P, where N can take any integer value under 10⁵.

This is the first test case:

296351 5

The output is an integer that contains the transformed value of the input.

First, find the P^{th digit. Next, slice the number into two parts, the left slice and the right slide.}

Iterate through each digit in the left slice and replace each digit with the value of that digit + the P^th digit. If the sum is a 2-digit number, use only the units digit.

Iterate through each digit in the right slice and replace each digit with the absolute value the difference between that digit and the P^th digit.

The P^th digit remains as it is.

We join the left slice, the P^th digit and the right slice and return this as output. That is the answer for each test case.

Now, let us write a Python-centric algorithm.

Algorithm

1. Create function number_transformation(n, p) that will accept 2 parameters, n and p.
2. Clone n into string variable str_n.
3. Replace n and p with int values of themselves.
4. Check for invalid value of p by returning null if string length of n is lesser than p, which is the position in n.
5. Create empty string variable str_n_ans.
6. Find the index of the P^th digit from the right and store it in i.
7. Slice the string version of n, which is str_n into 2 parts, str_n_left and str_n_right.
8. For the left part str_n_left, iterate through each digit.
9. For each digit in (8), add the int value of this digit to the P^th digit, and concatenate (join) the units place value with str_n_ans.
10. For the right part str_n_right, iterate through each digit.
11. For each digit in (10), find the absolute difference between the int value of this digit and the P^th digit, and concatenate (join) the units place value with str_n_ans.
12. Return str_n_ans to the main function.

My Python solution

This is my Python solution:

#!env python

#
# ACSL Intermediate Division - Number Transformation - 2019-2020
# Solution by Arul John
# 2020-11-22
#

# Function to do the number transformations
def number_transformation(n, p):
    str_n = n
    n = int(n)
    p = int(p)
    if len(str_n) < p:
        return
    str_n_ans = '' # answer

    # index of the Pth digit
    i = len(str_n) - p

    # Pth digit
    pth_digit = int(str_n[i:i+1])
    str_n_right = str_n[i+1:]
    str_n_left = str_n[:i]
    for c in str_n_left:
        str_n_ans += str((int(c) + pth_digit) % 10)
    str_n_ans += str(pth_digit)
    for c in str_n_right:
        str_n_ans += str(abs(int(c) - pth_digit))
    return int(str_n_ans)

# Tests
def test_number_transformation():
    test_data = [('296351 5', 193648),
                 ('762184 3', 873173),
                 ('45873216 7', 95322341),
                 ('19750418 6', 86727361),
                 ('386257914 5', 831752441)
                ]
    for test_input, answer in test_data:
        testlist = test_input.split(' ')
        # assert number_transformation(*testlist) == answer
        print(number_transformation(testlist[0], testlist[1]) == answer)

# Main
if __name__ == "__main__":
    test_number_transformation()

    # n, p = input().split()
    # print(number_transformation(n, p))

Decoding the program

I wrote this program in November 2020 as part of my ACSL Junior class.

In the main function, I created a list of tuples, with each tuple containing a string with n and p, and the expected output.

The function number_transformation(n, p) is called with the values of n and p as parameters.

Useful Python code snippets

There are many code snippets that can be used in competitive programming contests. These are a few. We will use the Python shell to run these individual snippets.

Use assert or == in tests

In the main function, we use this statement in line 41 to test if the returned output is the same as the expected output.

print(number_transformation(testlist[0], testlist[1]) == answer)

We can also use assert. In fact, when you start working in a professional environment and start writing tests, you will be using assert a lot more.

assert number_transformation(*testlist) == answer

Using assert will not print anything when it returns true, but when it returns false, it will scream.

For our tests, we will stick to == instead of assert.

String slicing

We did a lot of string slicing where we sliced the string to get its left and right slice.

To get the left slice from the first position up to and not including the i^th position, we used:

str_n[:i]

To get the right slice from the i+1^th position to the end of the string, we used:

str_n[i+1:]

String concatenation or joining

String concatenation or joining is accomplished with + between two strings.

If you are not familiar with string slicing, please practice this a lot. Many competitive programming problems would at some point require slicing.

There are several ways to do this. My personal favorite is using f-strings (not used in this program).

>>> planet = 'earth'
>>> print('I live on ' + planet)
I live on earth
>>>
>>> print(f'I live on {planet}')
I live on earth

Convert int to string and string to int

We used int() to convert a integer stored as a string to an integer.

Similarly, we used string() to convert an integer to a string.

abs() function

The math function abs() returns the absolute value of the number passed in as parameter.

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 number_transformation.py 
True
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.