ACSL Junior Duplicates Problem

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

ACSL Junior 2017-2018 Contest 4 Duplicates problem

Duplicates

The ACSL Strings and Things problem problem was the programming problem in ACSL Junior Division 2017-2018 Contest 4.

First, read the Duplicates 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 use either pseudocode or a flowchart.

Input and Output

The input is a bunch of lines with this format, number followed by a space and then a string. Each line represents one test case.

NUMBER STRING

Your ouput will be an integer.

Sample Input

This is the first input test case.

2 Computer

I wrote code to split multi-line input and compare it to each expected answer in a multi-line output. They are represented by input_data and output_data.

Sample Output

This is the output of the first input test case.

3

Programming Solution Logic

We will first split the input into two parts, based on the first space as delimiter -- (1) the number position, that represents the position, and (2) the string.

For each input text case, create an empty list, which will contain the sorted letters. Also, create an empty list which will contain the letters at position # position.

Compare each letter in the original string and arrange it appropriately in the list of sorted letters. In each iteration, save the letter at position position in the list of sorted letters into another list.

After all the iteration is completed, print the number of unique letters in the list of letters at position position. That gives the answer of this particular test case.

Tracing the first test case

We will trace the first test case. This is what we get for 2 Computer:

• Position = 2
• Computer becomes COMPUTER

C
CO
CMO
CMOP
CMOPU
CMOPTU
CEMOPTU
CEMOPRTU

Unique letters in the second position = O, M, E, so the answer is 3.

Algorithm

1. Read input and split the line into int position and string s.
2. Create a list words by splitting the string s on single space.
3. Remove all spaces in s and convert s to uppercase.
4. Create an empty list sorted_array which will contain the letters in sorted order.
5. Create an empty list position_letters which will contain letters at position # position.
6. Loop through each letter in string s.
7. Add the first letter of string s to the list sorted_array.
8. Set boolean flag inserted to False.
9. Start a second loop to loop through sorted_array and as long as inserted is False.
10. If the letter in the outer loop occurs earlier than the letter in the inner loop, add the letter in the outer loop ahead of the letter in the inner loop. Also, if the position is equal to the integer value of position, add it to the position_letters list.
11. Repeat inner loop by going to step 9.
12. At the end of the inner loop, if inserted is still False, append the letter from the outer loop to the end of sorted_array. And again, add the letter at position position to the position_letters list.
13. Create a set from position_letters, thereby retaining only unique letters.
14. Return the size of the set created in the last step as the answer for this test case.

My Python solution

This is my Python solution:

'''
ACSL Junior 2017-2018 Contest 4 Duplicates
Blog Post: https://aruljohn.com/blog/acsl-duplicates/
'''

# Function to write
def how_many_letters(input_line):
    answer = 0
    # Split the input line into number-space-string
    # Since we will split only on the first space, use .split(' ', 1)
    position, s = input_line.split(' ', 1)
    position = int(position)
    # Remove spaces from s, and make it uppercase
    s = s.replace(' ', '').upper()
    # Empty list
    sorted_array = []
    # List with letters at position 2
    position_letters = []
    # Iterate through all letters of s
    for s_letter in s:
        if len(sorted_array) < 1:
            sorted_array = [s_letter]
            continue
        else:
            i = 0
            inserted = False
            while i < len(sorted_array) and not inserted:
                x = sorted_array[i]
                if s_letter < x:
                    # Insert before
                    sorted_array.insert(i, s_letter)
                    # If 2 or more letters, then store it
                    if len(sorted_array) >= position:
                        position_letters.append(sorted_array[position-1])
                    inserted = True
                i += 1
            if not inserted:
                sorted_array.append(s_letter)
                if len(sorted_array) >= position:
                    position_letters.append(sorted_array[position-1])
    # Return number of unique letters in position 2
    answer = len(set(position_letters))
    return answer

# Main function
def main(input_data, output_data):
    input_lines = input_data.strip().split('\n')
    output_lines = list(map(int, output_data.strip().split('\n')))
    for i, input_line in enumerate(input_lines):
        answer = how_many_letters(input_line=input_line)
        if answer == output_lines[i]:
            print(f'{answer} ✅ Correct')
        else:
            print(f'{answer} ❌ Wrong, the correct answer is {putput_lines[i]}')

input_data = '''
2 Computer
2 COMPUTER bat
3 COMPUTER
4 ACSL is fun
9 the xylophone
'''

output_data = '''
3
5
2
3
4
'''

# Main function
if __name__ == '__main__':
    main(input_data, output_data)

Output

3 ✅ Correct
5 ✅ Correct
2 ✅ Correct
3 ✅ Correct
4 ✅ Correct

Useful Python code snippets

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

Split string based on single-space, but only for the first occurrence

We use this code to split the input string by the first single space.

>>> input_line = '4 ACSL is fun'
>>> position, s = input_line.split(' ', 1)
>>> print('POSITION=', position, '\nS=', s)
POSITION= 4 
S= ACSL is fun

Convert list to set

To convert list ['a', 'b', 'c', 'b', 'd'] to a set:

>>> l = ['a', 'b', 'c', 'b', 'd']
>>> set(l)
{'d', 'c', 'a', 'b'}

Use the Python shell

If you want to debug and see what string or numerical functions work, just run them 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.

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 in the main function.

When the program runs, this will be the output:

$ python duplicates.py 
3 ✅ Correct
5 ✅ Correct
2 ✅ Correct
3 ✅ Correct
4 ✅ Correct

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.