ACSL Junior Numble Problem

This article discusses and contains the Python code solution for the American Computer Science League (ACSL) Junior Division 2013-2014 Contest 4 Programming Problem Numble.

ACSL Junior 2013-2014 Contest 4 Numble problem

Numble problem

The Numble problem was the programming problem in ACSL Junior Division 2013-2014 Contest 4.

First, read the Numble problem. Make sure you understand what you are supposed to do. 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 of this format:

XXXXXXX, L

where XXXXXXX is a 7-digit number and L is the length of the output.

The output is a numerical string of size L that contains the largest sum of digits that is a multiple of 5.

Let us call the 7-digit number n and the number of digits d. We have to pick d digits. To maximize the sum of these digits, our first step can be to rearrange the digits in descending order.

For example, in the first test case, n = 9678415 and d = 7, so we must use all the 7 digits. After sorting the digits, we get n = 9876541.

Next, we have to find all the possible combinations of the n digits while grouping d at a time. In math, this is ⁿC_r, this is what I learned in India growing up in the 1980s. The notation for Permutations and Combinations may be different in your school. Store each of these combinations as a separate array.

Once you have an array of arrays with combinations, add up each inner array and check if the sum is divisible by 5. The sequence of digits with the largest sum is the answer.

Now, let us write a Python-centric algorithm.

Algorithm

1. Create function largest_sum_of_digits(n, d) that will accept 2 parameters, n and d.
2. Convert the data type of each digit from string to int and sort them; save the sorted int list in variable digits.
3. Use the function combinations in the Python library itertools to generate a list of lists of possible combinations using digits. Save this list in variable nums.
4. Iterate through every list in nums.
5. Find the sum of each list.
6. If this sum is divisible by 5, create a string from this list and return it. This number will be the greatest multiple of 5, so you do not have to sort anything. Go to (9).
7. Continue the for loop in (4).
8. At this point in the function, there are no values. Return string NONE.
9. Print the value returned by the function.

My Python solution

This is my Python solution:

"""
ACSL Junior 2013-2014 Contest 4 Numble
Blog Post: https://aruljohn.com/blog/acsl-numble/
"""

from itertools import combinations

# Function to find the maximum sum of digits that is a multiple of 5
def largest_sum_of_digits(n, d):
    digits = sorted([int(x) for x in list(n)])[::-1]
    nums = list(combinations(digits, int(d)))
    for num in nums:
        if sum(num) % 5 == 0:
            return ''.join([str(x) for x in num])
    return 'NONE'

# Main function
if __name__ == '__main__':
    input_data = '''
9678415, 7
9678415, 6
9678415, 5
9678415, 4
2678515, 3
4361842, 7
9143675, 6
1473518, 5
8264123, 4
7439264, 3
'''
    output_data = '''
9876541
987641
98765
9876
875
NONE
976431
87541
8642
974
'''
    sample_input = [x.split(', ') for x in input_data.strip().split('\n')]
    expected_output = output_data.strip().split('\n')
    for i, (n, d) in enumerate(sample_input):
        print(expected_output[i] == largest_sum_of_digits(n, d))

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 list.

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

The function largest_sum_of_digits() is called and passes the number and number of digits 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 for loop with enumerate

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

Create combinations using itertools

itertools is a great library and includes functions permutations() and combinations(), which can be very useful in competitive programming contests.

This code snippet shows you all possible combinations with digits 1, 3, 5, 7, 9 grouped by 4 at a time. It returns a generator, so to convert it to a list, we enclose it with a list().

>>> from itertools import combinations
>>> 
>>> print(list(combinations([1, 3, 5, 7, 9], 4)))
[(1, 3, 5, 7), (1, 3, 5, 9), (1, 3, 7, 9), (1, 5, 7, 9), (3, 5, 7, 9)]

Convert string with integers separated by a space to list of integers

List comprehension is the fastest way to do this. It can be combined with split() and int().

>>> s = '2 4 6 8 10'
>>> nums = [int(x) for x in s.split()]
>>> print(nums)
[2, 4, 6, 8, 10]

We can also use map() and int().

>>> s = '2 4 6 8 10'
>>> nums = list(map(int, s.split()))
>>> print(nums)
[2, 4, 6, 8, 10]

Check if a number is divisible by 5 using mod operator %

This is straightforward.

>>> 17 % 5 == 0
False
>>> 15 % 5 == 0
True

Reverse a string using [::-1]

You can reverse a string using [::-1]

>>> planet = 'Neptune'
>>> print(planet[::-1])
enutpeN

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