Related Tags

python
coding challenge

# How to solve the Names Scores problem

## Problem Introduction

The Names Scores problem is a coding problem that asks you to find the total value of a large number of names stored in this file in a programmatically efficient way.

The value of a name is equal to the sum of all its letters multiplied by the position of the name in the list of names (when sorted alphabetically). The numeric value of a letter in this exercise is not equal to its ASCII equivalent like it is according to coding norms. Instead, it is equal to the position of that letter in the alphabet. For instance, A is 1, B is 2, and so on.

## Solution

This solution was written in Python and C++; however, it will be similar in other programming languages as well.

main.py
names.txt
from queue import PriorityQueue

file = open('names.txt')
file.close()

fileContents = fileContents.replace('"', '') #Removing quotation marks
names = fileContents.split(',') #Separating names using commas as a separator

#Sorting names using a priority queue
queue = PriorityQueue()
for x in names:
queue.put(x)

#Calculating the total value of the names
count = 1
sumVar = 0
while not queue.empty():
item = queue.get()
itemSum = 0
for index in range(len(item)): #Calculating the value of individual names
itemSum = itemSum + ord(item[index]) - 64
sumVar = sumVar + (itemSum * count)
count = count + 1

print(sumVar)

The solution can be divided into three main parts:

2. Sorting into alphabetical Order
3. Name Score Calculation

As you can see in the file, the names are surrounded by quotation marks (") and separated by commas (,). Therefore, to get rid of the quotation marks, we replace them with empty strings using replace('"','') or the erase() function in C++. We then use split(',') to separate the names by entering the comma character as the separator. C++ has no built-in split() function, which is why the string had to be manually parsed using a combination of the find(), substr(), and erase() functions.

A Priority Queue is used to sort the names alphabetically. A single insert operation, using the put() or push() function, has a time complexity of $O(log N)$. Given that this is repeated for every word, the overall time complexity for this step becomes $O(Nlog N)$.

To calculate the name scores, individual names are fetched from the priority queue using the get() or top() function. While get() also removes the fetched name from the queue, in C++ the pop() function is called to do so. These names are iterated over in the nested for loop, and the values of individual letters are summed up. Since all letters are in capital form, the ASCII equivalent of the letter in decimal form is found using the ord() function, and then subtracted with 64 since A begins at decimal 65 in ASCII.

An equivalent to the ord() function was not required in C++ as it automatically converts characters to their ASCII decimal values when casting to integers.

This value is then multiplied by the count of the name within the queue and summed into the total name score. This process is repeated until the queue is empty. When the queue is empty, queue.empty() returns true, which is negated by the not or ! operator and causes the while loop to exit.

RELATED TAGS

python
coding challenge