This technical log it's about my own personal problem of CodeJam. I decided to build a python code of Double or One Thing. When I started I was a little lost about how to break the problem. I checked the analysis to figout out what to do. I did 3 different tries one better than the next one. In the end, I built a code with efficency from O(n^2) to O(n).
CONTEXT
Google Jam Double or One Thing Double or One Thing
You are given a string of uppercase English letters. You can highlight any number of the letters (possibly all or none of them). The highlighted letters do not need to be consecutive. Then, a new string is produced by processing the letters from left to right: non-highlighted letters are appended once to the new string, while highlighted letters are appended twice.
Given a string, there are multiple strings that can be obtained as a result of this process, depending on the highlighting choices. Among all of those strings, output the one that appears first in alphabetical (also known as lexicographical) order.
Solution
"""
This class: groups the letters and their respective amount.
"""
class groupOfLetters():
def __init__(self):
self.letter = []
self.conter = []
def saveLetter(self, letter):
self.letter.append(letter)
def saveconter(self, amount):
self.conter.append(amount)
"""
This function receives the input to separate every letter and send them
to groupOfLetters class. Then it receives the data to make the new string
as a result.
conditions to make the string:
*result should be in alphabetic order
example inputs AAB ; BBA ; AAA
1-If the letter is smaller than the next letter, it should double
the letter( or group of letters): result AAAAB
2 -If the letter is bigger than the next letter, it
doesn't double the letter( or group of letters): result BBA
3-If the string that we receive contains the same group of letters,
it should result the same string: result AAA
"""
def doubleOrOneThing():
word = str(input())
result = ""
conter = 1
#change the input to uppercase
word= word.upper()
large = len(word)
data = groupOfLetters()
for i in range(large):
j= i+1
"""
condition to avoid the program breaks when index j is bigger than
the array's length
"""
if(j < (large )):
#if the comparision it's the same, we count how many times
#the letter is repeating
if(word[i] == word[j]):
conter += 1
else:
#if the letter changed, we save the data with the last letter
# and how many times it was repeated.
data.saveLetter(word[i])
data.saveconter(conter)
#reset the conter
conter = 1
else:
# if j is bigger than the array's lenght we save the last data
data.saveLetter(word[i])
data.saveconter(conter)
#For to make the new string with double letters or not
for i in range(len(data.letter)):
j= i+1
# condition 3: Is the same letter in the whole word
#we break the "for" and save time.
if(i == len(data.letter)):
result = str(data.letter[i] * data.conter[i])
break
"""
condition to avoid the program breaks when index j is bigger than
the array's length
"""
if (j < len(data.letter)):
#condition 1: double letter
if(data.letter[i] < data.letter[j]):
result += str(data.letter[i] * (data.conter[i] * 2))
else:
#condition 2: not double letter
result += str(data.letter[i] * data.conter[i])
else:
#the last data doesn't double because there's nothing to compare
#it means it is the biggest like condition 2
result += str(data.letter[i] * data.conter[i])
return result;
cases = int(input())
results = []
#Program stars here:
#loop into the number of cases
for case in range(cases):
results.append(doubleOrOneThing())
#Final step
#loop into the received answers in the list to print
for i in range(cases):
print(f"Case #{i + 1}: {results[i]}")
Back to the Top
The solution here is the result of two more tries. It took me some time to understand the problem and then when I did my first code wasn't completely right. My first approach was to make all the possible solutions and loop in them to select the one with alphabetic order. This program run well with short words but with larger words it was stuck.
Then, my second approach was better. It could do half of the solutions but I missed a pattern. We're taking this example --> AABBA. I missed this fact: when we have a group of words (same letter) next to a higher in alphabetical order letter, the group of letters could double but when the group was next to a lower it is supposed to stay in one. My mistake was that my code was checked letter by letter. It means that in a group of letters BBA my result was BBBA because I duplicate the first B because it was the same letter. The right result is BBA stays like that because B is bigger than A Then, when my code fails Codejame. I realized the fact that I need to do a comparison by groups of letters and duplicate by groups.
When I found that pattern I did the last solution and I improved the efficiency because I started to understand how Efficiency works. I had a nested for to loop and make the comparations by letter. I decided to build a class where I can save the letters and a counter to track by groups. Then I just built a Foor to loop in a list and I nested a condition to control the index when it reached the edge of the list. I based the code in 3 main conditions:
Result should be in alphabetic order example inputs AAB ; BBA ; AAA
- 1-If the letter is smaller than the next letter, it should double the letter( or group of letters): result AAAAB
- 2 -If the letter is bigger than the next letter, it doesn't double the letter( or group of letters): result BBA
- 3-If the string that we receive contains the same group of letters, it should result the same string: result AAA
Talking about the alternatives solutions
My tries in this code show me how many ways can exist to build a program. Also, the result code depends on how well you understand the needs. For me, it was one of the more difficult parts. I fix that, by reading about the analysis of the problem, looking at some videos explaining the dynamic movement of the variables, and building some Treemaps to understand the algorithm patterns.
I think there are more solutions to rich this problem. I made one of them with good efficiency. I think something I can improve is the organization of my code, the name of my variables. Well, in this blog my code looks badly organized but in my python file, it has comments and good indent. I can conclude that the best approach it's the code understandable and efficient in run time.