ACSL Senior Change Digits Problem

This article discusses and contains the Python code solution for the American Computer Science League (ACSL) Senior Division 2003-2004 Contest 1 Programming Problem Change Digits. If you have read the blog post about the Junior Change Digits problem, the Senior version has more rules.

Change Digits problem

The Change Digits problem was the programming problem in ACSL Senior Division 2003-2004 Contest 1. There are 3 versions of this, Junior, Intermediate and Senior. This is relatively the hardest version.

First, read the Change Digits problem. Make sure you understand the problem description. Read it many times, if necessary. Then, write your algorithm on paper before coding anything. For your algorithm, you can write either pseudocode or a flowchart.

Algorithm

1. From the original number, we will create a list of integers, where each digit in the number is an individual int item.
2. Next, we will find the median of the digits.
3. Loop through the digits, and find the digit closest to the median that is lesser or equal to the median. Pick only the first instance.
4. Start a new loop, iterate through the digits and search for the digit selected in the previous step.
5. When you find it: (i) if the digit equals 0, 1 or 2, replace it with the highest digit (ii) if the digit equals 3, 4 or 5, replace it with the smallest digit (iii) if the digit equals 6, 7 or 8, replace it with the units digit from the sum of the digits (iv) if the digit equals 9, replace it with 0
6. Create a new integer with the current digits of the int list and return it to the main function.

Sample Input

Save this sample input as a file change_digits_1.in

123
745
1689
9999

This file has 4 lines with integers, each less than 100,000. Each line is a test case.

Sample Output

Save this sample output as a file change_digits_1.out

133
744
1489
999

There are 4 output lines, one for each test case.

My Python solution

This is my working Python solution. Save it as a file change_digits.py.

'''
ACSL Senior Division 2003-2004 Contest 1 - CHANGE DIGITS
Blog Post: https://aruljohn.com/blog/acsl-senior-change-digits/
'''

def change_digits(n):
    answer = n
    digits = [int(digit) for digit in list(n)]
    median = sorted(digits)[len(digits) // 2]

    digit_closest_to_median = digits[0]
    diff = 1_000_000
    for digit in digits:
        if median > digit:
            if median - digit < diff:
                diff = median - digit
                digit_closest_to_median = digit

    for i, digit in enumerate(digits):
        if digit == digit_closest_to_median:
            if digit in (0, 1, 2):
                digits[i] = max(digits)
            elif digit in (3, 4, 5):
                digits[i] = min(digits)
            elif digit in (6, 7, 8):
                sum_digits = sum(digits) % 10
                digits[i] = sum_digits
            elif digit == 9:
                digits[i] = 0
            break

    answer = ''.join(str(digit) for digit in digits)

    return int(answer)

# Main program
if __name__ == "__main__":
    for _ in range(4):
        n = input()
        print(change_digits(n))

Method 1: How to run the program with diff and cat

If you are running this program on Linux or macOS, you can use regular Unix/Linux commands.

$ diff <(cat change_digits_1.in | python change_digits.py) <(cat change_digits_1.out)

Method 2: How to run the program the regular way

The regular way to run this program is:

python change_digits.py

Copy/paste the input lines and press ENTER or return.

123
745
1689
9999

Screenshot

$ python change_digits.py 
123
745
1689
9999
133
744
1489
999

Method 3: How to run the program using cat on the input file

On my Mac, I personally prefer running cat on the input file and pipe the output to the Python program.

cat change_digits_1.in | python change_digits.py

Screenshot

$ cat change_digits_1.in | python change_digits.py 
133
744
1489
999

Compare this output with the contents of change_digits_1.out. They should be identical.

Decoding the program

In the change_digits(n) function, we use list comprehension to create a list of digits of the the number n.

To find the median, we sort the digits list and find the middle item.

We use the list max() function to find the largest digit in the number n.

We use the list min() function to find the largest digit in the number n.

We iterate through the list containing the digits of n. In the for block, we check if the digit is same as the largest digit. If it is, then replace the corresponding list item with the appropriate digit.

At the end, convert each digit to string, do a join of the string digits and

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 test these individual snippets.

List comprehension

We take an integer in string form and create a list of integers of each digit.

digits = [int(digit) for digit in list(n)]

join()

You can join the list of integers using the join() function. Prior to join() being called, we convert each item to a string using str().

answer = ''.join(str(digit) for digit in digits)

Find the median in a list

You can find the median in a list digits like this:

median = sorted(digits)[len(digits) // 2]

sorted() function vs sort() list method

If you do not know or remember the difference between sorted() function and sort() list method,

sorted(nums) takes a list nums as argument and returns a sorted list. The original list is UNCHANGED.

nums.sort() is a method for list nums that sorts the list and stores it back into nums, it's an in-place method.

Use enumerate() if you want to loop through a list and change items

You can use for x in nums if you want to just read each item.

You use for i, x in enumerate(nums) if you want to read and alter items in the list by updating them with nums[i].

Use the Python shell

Feel free to test all the individual keywords and functions in the Python shell.

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.

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.