After the first post I made earlier about learning how to 'think like a programmer' (You can check it out here), I started practicing a on lot of problems on CodeWars. Mostly the easier ones, and a few that are a bit more difficult and would take me about an hour to solve.
Well, that was what I was doing until recently.
This time, I was feeling quite good and confident about myself and how far I've gone, so I decided to see how far I can push myself.
Here's a picture of a computer with an IDE open because why not. Photo by James Harrison on Unsplash
According to the CodeWars ranking system, I usually attempt problems that are ranked between 8 kyu (being the lowest rank) and 6 kyu. Maybe 5 kyu on rare occasions.
But this time, I will be attempting a problem with a rank of 4 kyu called "ParseInt() reloaded."
The question is pretty straight forward. It involves making a program that represents numbers in words as integers. For example:
three thousand two hundred and forty-six -> 3246
Once again, I will be using Python to solve this problem since it is the only language I'm really familiar with right now. I also know a bit of C++, but it's been years since I've ever written a single line of code with that language.
Now, we begin...
At first, because of how simple and straight to the point the question seemed, I thought that I had aced this one already. However, a while later, I realized that this is way harder than it seems.
After thinking about how the program would run, I decided that if the program was going to convert words to numbers, the entire string would have to be iterated through. For this to be possible, the number word has to be broken up into separate, individual words. A dictionary would be created, containing the essential numerical words like from one to twenty, then thirty, forty, all the way up to ninety. From this point, I managed to get a rough initial idea on how the program would run.
1. Create a dictionary containing core integers like 1, 2, 3, etc.
2. Separate the string into individual words
3. Add individual words to a separate list
4. Iterate through the list and add matching integer from the list to a variable
5. Repeat step 4 until there are no more words left
6. Print the final integer
Creating the dictionary was not much of an issue.
numbers = {
"zero": "0",
"one": "1",
...
"nineteen": "19",
"twenty": "20",
"thirty": "30",
"forty": "40",
...
"ninety": "90",
"hundred": "00",
"thousand": "000",
"million": "000000"
}
This was how I made the first dictionary. Now that I look back at it, I always wonder why I did this.
I think I did this way because I forgot about math and thought of appending zeros to numbers in the case of hundreds, thousands and millions instead of using multiplication.
After separating the string, I noticed that some words from a few test cases were paired with a hyphen like 'forty-six' for instance.
I wanted to avoid this because this would make me head back to the dictionary and add a whole lot of stuff that I do not have the strength to add. So, I made a little section that goes through the words and if there's a hyphen in it, it gets separated again.
# This separates the initial string
separated_str = string.split()
for word in sepated_str:
# Checks if there's a hyphen in the word
if '-' in word:
mini_sep_str = word.split('-')
for word2 in mini_sep_str:
pure_str.append(word2)
else:
pure_str.append(word)
And luckily, it works.
And now for the meat of the matter, the part that adds the numbers together.
(When I think back to this moment, even I don't fully understand the thought process I put into this.)
How I planned this part was by creating a result variable that holds string data types, mainly because of the hundreds and thousands. If it was adding a unit number like eight or five, the result and the current number to be added (gotten from the dictionary created) would get converted into an integer, then the current number would be added to the result. After this, the result will be changed back to a string.
In the case of hundreds and thousands, the current number will be concatenated to the result which is currently a string.
(Yeah, I don't know why and how I thought of this...)
This is the entire code of everything that I just explained:
for word3 in pure_str:
current_num = number[word3]
if word3 == "and":
continue
elif word3 == "hundred" or word3 == "thousand" or word3 == "million":
result = str(result)
result += current_num
else:
result = int(result)
current_num = int(current_num)
result += current_num
Well, all of this surprisingly worked. Well... kinda.
This method worked until the number reaches the thousands range. A problem that occurred was that if I was supposed to generate the number for, let's say "eight thousand eight hundred and eighty-eight", instead of generating it as '8888', it comes out as '800888'.
After going through the code several times, I realized that eight gets added to the result after adding the zeros for the thousand. Then another set of zeros are added for the hundred to the end of the result, which was not what I wanted.
After thinking about how to fix the problem, I finally reclaimed the ability to do math and remembered that multiplication still exists. With that, I modified the dictionary again by changing all the values of the keys to integers this time.
And with that, I had to refactor the code so that it can work with integers.
At first, I observed that I was still getting the same problem as earlier, then I thought that it would probably be a better idea to make a separate variable that will be used to sort out the hundreds and thousands and then add them to the final result when it's done.
for word3 in pure_str:
if word3 == 'and':
continue
current = numbers[word3]
if current >= 1000:
cur_num *= current
result += cur_num
cur_num = 0
elif current >= 100:
cur_num *= current
result += cur_num
if pure_str.count("hundred") > 1:
continue
else:
cur_num = 0
else:
cur_num += numbers[word3]
return result + cur_num
I put the if-else statement when the current number is a hundred because if I didn't do that, the final result turns into a 5-digit number when it's meant to be a 6-digit number. This didn't fix the issue much, however.
I don't even know how to explain what happened here.
At the end of the day, the program I made could only work within the range of 1 to 99,999. I had to take the L and abandon the problem.
The question to me, probably. Source
After a couple of days, I gave up on trying to solve this problem by myself and decided to search online for any help on this problem.
The solution I found online made the dictionary of numbers to contain a tuple (like (x, y)) where x is a multiplier and y is the increment (x will be multiplied by the result and y will be added to the result).
Values like one, two, seventeen, thirty, and the rest had a multiplier of one and an increment depending on the number word, while scales like hundred, thousand and million had increasing powers of 10 as their multiplier effect and zero as the increment. So, they can only be used to multiply.
And here is the final code:
def parse_int(string):
numbers = {}
units = [
'zero','one','two','three','four','five','six','seven','eight','nine', 'ten','eleven','twelve','thirteen','fourteen','fifteen','sixteen','seventeen','eighteen','nineteen'
]
tens = ['','','twenty','thirty','forty','fifty','sixty','seventy','eighty','ninety']
others = ['hundred','thousand','million']
for ind, val in enumerate(units):
numbers[val] = (1, ind)
for ind, val in enumerate(tens):
numbers[val] = (1, ind * 10)
for ind, val in enumerate(others):
numbers[val] = (pow(10, (ind * 3 or 2)), 0)
current = result = 0
spl_str = string.replace('-', ' ').split()
for word in spl_str:
if word == 'and':
continue
if word not in numbers:
raise Exception(f"Invalid Word: {word}")
scale, increment = numbers[word]
current = current * scale + increment
if scale > 100:
result += current
current = 0
return result + current
I took some time to study the code instead of just pushing the control, c and v button without knowing what I was doing, studying how the code worked was quite fascinating in itself. Luckily, this one worked without any issues.
After submitting the final result, I saw a certain answer that I liked immediately. I was surprised that I wasn't able to think of this.
ONES = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine', 'ten', 'eleven', 'twelve', 'thirteen', 'fourteen', 'fifteen', 'sixteen', 'seventeen', 'eighteen', 'nineteen']
TENS = ['twenty', 'thirty', 'forty', 'fifty', 'sixty', 'seventy', 'eighty', 'ninety']
def parse_int(string):
print(string)
numbers = []
for token in string.replace('-', ' ').split(' '):
if token in ONES:
numbers.append(ONES.index(token))
elif token in TENS:
numbers.append((TENS.index(token) + 2) * 10)
elif token == 'hundred':
numbers[-1] *= 100
elif token == 'thousand':
numbers = [x * 1000 for x in numbers]
elif token == 'million':
numbers = [x * 1000000 for x in numbers]
return sum(numbers)
It was really interesting to tackle this question. This one was really different from the stuff I usually do. I hope to be able to solve several problems like this later on, but within a day next time.
Well, that's all for now and thanks for reading!