Description
Note: I've edited the code enhance the comprehension of the code flow. Please use the new one instead.
Note: If you don't want to read a long story, please skip to the line that says "End of the Story".
In Taiwan, there is a temple called Lungshan Temple in Wanhua. It is one of Taipei's oldest and most prominent temples. One of the gods worshipped here is Yue Lao, the god of love and marriage who binds lovers' souls together, ensuring they meet and fall in love. It is said that the success rate here is pretty high. One of the couples, Mr. and Mrs. Chen, also met here and got married a few years afterwards.
Well, there had been a lot of things going on since their marriage. A year after settling into their new life together, Mrs. Chen discovered she was expecting their first child. The news filled their home with excitement and joy, and they couldn’t wait to welcome their little one into the world. However, there was one problem: they couldn't come up with a good name for their child. Of course, they couldn't really ask the baby what name it wanted, so they ended up consulting someone else. For most people, that someone else would be some knowledgeable person in a neighborhood, a fortune teller, grandparents at home, or a priest, but for some reason, Mr and Mrs Chen chose to consult me.
"So, you want me to name your child?" I asked, confused.
"Of course!" Mrs. Chen replied eagerly. "We’ve been going back and forth about names, but nothing feels quite right. We really want something special, something that reflects our hopes for our child’s future."
"Wouldn't it be better to ask someone else? You know, someone knowledgable or something," I objected.
"You are studying at NTHU, aren't you? Then there's no one more knowledgeable than you!" Mr. Chen added.
"Seriously? I'm studying computer science, not—"
"—It's okay! Just give him any name you think it's good!"
I sighed. "What kind of name do you want?"
Mrs Chen thought for a while. "Auspicious ones. Something that will lead to a very long life."
"Hm... What about something related to tortoises? I heard it can live up to ten thousand years or something."
"Just ten thousand? So that means he's going to die after ten thousand years?" Mr Chen frowned. "What an unfilial son... you'll die before us, huh...?"
I shook my head slightly. "How long are you planning to live, seriously?"
"As a human, I might live something like eighty years or something, but even at that time, I still want to see him living happily from beyond my grave," Mr Chen said with a serious expression. "Isn't there a name that will make him immortal?"
"That's a tall order!" I exclaimed. "Well, I kinda understand how you feel. If you're looking for something that symbolizes endless life, I can come up with a few."
"Like what?"
"For example, 'Jugemu' means unlimited life, or 'Gokou no Surikire' meaning five kalpa[注1] of rubbing off, or 'Kaijarisuigyo' meaning..." I typed out the names on my laptop.
"Isn't that Japanese?" Mrs. Chen objected.
"It's fine. If anything gives our son a long life, it will do," replied Mr Chen.
"Okay, I've got the list of names here. Have a look at it," I cut in.
"Oh, that's a lot! What should we do? I can't really decide which one to use..." Mrs Chen leaned in to see the names.
"What if we put all of them together into one big name?" Suggested Mr. Chen.
"Heck no! Do you really want to name your kid Jugemu Jugemu Gokou no Surikire Kaijarisuigyo no Suigyoumatsu Unraimatsu Fuuraimatsu Kuunerutokoro ni Sumutokoro Yaburakouji no Burakouji Paipopaipo Paipo no Shuuringan Shuuringan no Guurindai Guurindai no Ponpokopii no Ponpokonaa no Choukyuumei no Chousuke!?" I objected.
"What's wrong with naming him Jugemu Jugemu Gokou no Surikire Kaijarisuigyo no Suigyoumatsu Unraimatsu Fuuraimatsu Kuunerutokoro ni Sumutokoro Yaburakouji no Burakouji Paipopaipo Paipo no Shuuringan Shuuringan no Guurindai Guurindai no Ponpokopii no Ponpokonaa no Choukyuumei no Chousuke?"
"Everything! Just imagine him doing exams! Everyone finished doing the exam, but your Jugemu Jugemu Gokou no Surikire Kaijarisuigyo no Suigyoumatsu Unraimatsu Fuuraimatsu Kuunerutokoro ni Sumutokoro Yaburakouji no Burakouji Paipopaipo Paipo no Shuuringan Shuuringan no Guurindai Guurindai no Ponpokopii no Ponpokonaa no Choukyuumei no Chousuke is still busy writing Jugemu Jugemu Gokou no Surikire Kaijarisuigyo no Suigyoumatsu Unraimatsu Fuuraimatsu Kuunerutokoro ni Sumutokoro Yaburakouji no Burakouji Paipopaipo Paipo no Shuuringan Shuuringan no Guurindai Guurindai no Ponpokopii no Ponpokonaa no Choukyuumei no Chousuke... huff, huff...is that really okay?"
Mrs Chen thought for a moment. "Point taken."
"But we really don't know which one to choose!" Objected Mr. Chen.
"That's why... I'm going to use my programming skills to help you choose the perfect name for your son!" I promised.
[注1]: a long period of time in Hindu and Buddhist cosmology. The exact length varies, but it is generally said to be the time from the creation of the universe to its recreation.
End of the Story
Okay, so here is the problem: I don't know what "perfect" is. There are so many ways to test if something is "better" than the other, and there is no objectively better way. This is why I chose a flexible option: to write a function that selects the best name based on a criterion that will be passed to the function at runtime:
The criterion, which I named comparing_function, is a function pointer that points to a function that takes in two constant string arguments. All criterion functions share the same traits: they take in two strings and should return a negative value if the first string is considered "better", positive if "worse," and zero if "equal".
Also, there is this utility function:
This function is called every time the number of the old list is getting full. What it should do is create a new list that holds new_capacity strings, move the strings from the original list to the list as well as deallocate the original one, then return the new list.
Lastly, there are two criterion functions I didn't implement:
This function should compare the two strings in alphabetical order but with the strings written in reverse. The word that comes first is considered better. For example, the word ZEBRA backward is ARBEZ and HORSE backward is ESROH, so ZEBRA should be better than HORSE.
This function should compare the two strings in alphabetical order but the case is only used as a tiebreaker when the spelling is the same. A shorter string whose characters match those of a longer one is also considered coming before. For example, the following strings are in order:
BILL > Bill > bILL > bill >> BILL LOUIS > bill louis >> Louis >> Louisiana
However, I'm already exhausted from reading that name. This is why I'm delegating this task to you: to implement the four functions mentioned.
For your reference, here is the summary of the criteria used.
| Criteria Name | Meaning | Example (Bolded one is prioritized) |
|---|---|---|
|
AlphabeticalSum |
The summation of the order of each character in the string. The name with a larger sum is prioritized. |
"KNOWLEDGE" : 11 + 14 + 15 + 23 + 12 + 5 + 4 + 7 + 5 = 96 "ATTITUDE" : 1 + 20 + 20 + 9 + 20 + 21 + 4 + 5 = 100 |
|
BackwardsString |
The name that, written backward, comes before alphabetically is prioritized. |
"ZEBRA" : ARBEZ, "HORSE" : ESROH |
|
Conciseness |
The shorter name is prioritized. |
"A": 1 character, "JUGEMU": 6 characters |
| Dictionary | The name that comes before alphabetically is prioritized. The case is used as a tiebreaker. |
"ZEBRA" "HORSE" |
|
EnglishOrder |
The name that comes before alphabetically is prioritized. |
"ZEBRA" "HORSE" |
|
Length |
The longer name is prioritized. |
"A": 1 character, "JUGEMU": 6 characters |
|
Qwerty |
The name is compared based on the position of its characters on a QWERTY keyboard. The top row is prioritized over the bottom row, and the key on the left is prioritized over the right on the same row. |
"SUN WUKONG" "ZHU BAJIE" |
|
ReverseEnglishOrder |
The name that comes after alphabetically is prioritized. |
"ZEBRA" "HORSE" |
|
ScrabbleScore |
The name that has a higher score for Scrabble, calculated by the sum of the points of each tile, is prioritized. The points tor the tiles are as follows:
|
"KNOWLEDGE" : 5 + 1 + 1 + 4 + 1 + 1 + 2 + 2 + 1 = 18 "ATTITUDE" : 1 + 1 + 1 + 1 + 1 + 1 + 2 + 1 = 9 |
|
Zhuyin |
(Limited to the name written in Hanyu Pinyin) The name that comes before in bopomofo is prioritized. It is guaranteed this won't appear when there's a name written in other systems than Hanyu Pinyin in the list. Please see Figure 1 for the Zhuyin - Pinyin conversion table. |
"SUN WUKONG" : ㄙㄨㄣ ㄨ ㄎㄨㄥ "ZHU BAJIE" : ㄓㄨ ㄅㄚ ㄐㄧㄝ |
Figure 1: Zhuyin - Pinyin conversion table.
Input
The input contains a list of commands. There are three types of commands:
ADD command:
[NAME]
This command indicates that the program should add a name to the list, namely at the very end. Each name has at most 999 characters, spaces included.
QUERY command:
[CRITERION]
This command indicates that the program should search for the best name in the list based on the criterion. If two strings are "equal", the one that came before is prioritized. It is guaranteed that the QUERY command will be called only when there is at least one name in the list.
END command:
This command appears exactly once in the last line of the test case. It indicates the program should terminate.
Output
The best names found from the queries, all trailed by an end-line character.