Aaron is a young game developer. He recently joined the development team of a game where the players select their character from a predefined set, aka "heroes". Unfortunately, the names of the existing heroes are not evenly distributed throughout the alphabet. For example, there are 6 heroes that have a name starting with C, but only 5 starting with A or B. Since the game will continue to add new heroes, and Aaron has a saying in how to name those, he is determined to try "smoothening" the distribution of hero names.
Of course, he cannot simply mathematically generate names as gap fillers, because those suggestions would be unpronounceable and thus rejected right away. Therefore, instead of calculating a name, Aaron opted to go with "just" a helper for his creative process that helps him to focus on the right things to do:
He will calculate the "distance" between each two names following each other in alphabetical order, and then print the top ten biggest gaps between two names. This way Aaron can try to focus on finding a name that comes in between those two, so he'll eventually create a smoother equidistant descend throughout the alphabet as the list of heroes continues to grow.
For a given list of names, generate the entries' keys that consist of only the uppercase form of the letters
[A-Za-z]. Calculate a distance between each two alphabetically adjacent keys.
The first key is additionally compared to the first possible key
"A", the last to the last possible key
Print the top ten (or all if there are less) biggest gaps in descending order with both names as given by the input and a measurement for the size of the gap. The "given name" of the borders is an empty string.
The list of names. Conditions as follows:
- The entries are guaranteed to only contain printable ASCII characters (sorry
Björn NUL LF)
- The characters may have any case (
"Tim", to be treated same as
- The entries have different lengths (
- The entries are guaranteed to not contain commas, so you can use that as safe delimiter for your outputs
- The entries do contain other characters such as spaces or dots, which do not change the key as stated above (
"Mr. T", to be treated same as
- The entries are guaranteed to give keys within 1 to 12 (inclusive) letters (entries won't be
"Gandalf the White")
- The entries explicitly may contain single quotes
'and double quotes
", in case this is important for escaping
- The entries are not guaranteed to come in any particular order (e. g.
"Eve", "Dr. Best", "Dracula", keys sorted
"DRACULA", "DRBEST", "EVE")
- The list is guaranteed to have at least one entry
- The list is guaranteed to have only entries with distinct keys
- The list will not (and must not!) contain any entries that will give the keys
This was done in Excel. I limited the maximum length of 7 letters though for practical reasons (see notes), but the point should be clear.
List: ["Tim", "Mr. T", "Anna", "Jon", "Eve", "Dr. Best", "Timo", "Dracula"] Keys: ["TIM", "MRT", "ANNA", "JON", "EVE", "DRBEST", "TIMO", "DRACULA"] Ordered: ["ANNA", "DRACULA", "DRBEST", "EVE", "JON", "MRT", "TIM", "TIMO"] Values: [595765044, 1808568406, 1809137970, 2255435604, 4096878669, 5305375503, 7884458676, 7884753921] Distances: [1212803362, 569564, 446297634, 1841443065, 1208496834, 2579083173, 295245] Distance from "ANNA" to "A": 208344555 Distance from "TIMO" to "ZZZZZZZ": 2575894526 Output (padding added for clarity, see "Rules #4"): [ Mr. T, Tim, 2579083173 ] [ Timo, , 2575894526 ] [ Eve, Jon, 1841443065 ] [ Anna, Dracula, 1212803362 ] [ Jon, Mr. T, 1208496834 ] [ Dr. Best, Eve, 446297634 ] [ , Anna, 208344555 ] [ Dracula, Dr. Best, 569564 ] [ Tim, Timo, 295245 ]
Interpretation: Aaron should focus on finding a name in the middle between "Mr. T" and "Tim". Welcome Pyrion, splitting
1261829394 + 1317253779, while sounding absolutely badass! This is not part of the challenge however, only the top ten pairs and their distance should be output.
- Ex falso sequitur quodlibet. If the input data does not conform to the rules set above, the program may do whatever, including crashing.
- You are free to chose your method of measurement for the distance, but it has to ensure the following:
AACare further apart than
AAAis closer to
A(so basically: all possible names are ordered lexicographically). This means the distance in the output could differ per answer, but the order of the pairs are strict.
- Range and precision of the gaps is arbitrary, as long as you have a non-zero distance between
"AAAAA AAAAA AA"and
"AAAAA AAAAA AB".
- The output has to contain the names as given (not the keys) and the distance. The precise formatting is up to you, as long as it's clear what belongs together.
Name1,Name2,Distanceis a safe bet.
- As mentioned earlier, if there are more than ten results, only output the top ten.
- The borders of
"ZZZZZZZZZZZZ"are empty strings in the output.
- Code golf, shortest code by bytes wins.
- The example above was done in Excel and uses a base 27 number system. It was limited to 7 letters, because for 12, the upper bound would be
27^13 - 1 = 4,052,555,153,018,976,266which exceeds Excel's internal number range. If you were to add a test-link for your code which times out for 12 letter keys, feel free to use a smaller value so your program can be verified in the test-link.
- I am aware that the "measurement of the gap size" may vary depending on the algorithm. Some might not even have "one number" to sum it up. Try your best to find something conveying that finding a name between
"Tim"helps a lot more than between
"Jon"on our road to more equidistant names.
- This is my first posting here, feel free to comment if I need to add or clarify something. I've been looking at other content and hope I did everything right.
- The problem is derived from an actual problem I had to solve lately and I thought it might be a fun one to post it here.