4
\$\begingroup\$

Introduction:

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.

The Challenge

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 "ZZZZZZZZZZZZ".

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.

Input data

The list of names. Conditions as follows:

Entries:

  • 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 "TIM")
  • The entries have different lengths ("Anna", "Jon")
  • 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 "MRT")
  • The entries are guaranteed to give keys within 1 to 12 (inclusive) letters (entries won't be "" or "-.-.-. -.--.-" or "Gandalf the White")
  • The entries explicitly may contain single quotes ' and double quotes ", in case this is important for escaping

List:

  • 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 "A" or "ZZZZZZZZZZZZ"

Example

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 2579083173 into 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.

Rules

  • 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: AAA and AAC are further apart than AAA and AAB. AAA is closer to AAB than to ABA. AA comes after 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,Distance is a safe bet.
  • As mentioned earlier, if there are more than ten results, only output the top ten.
  • The borders of "A" and "ZZZZZZZZZZZZ" are empty strings in the output.

Winner

  • Code golf, shortest code by bytes wins.

Notes

  • 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,266 which 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 "Mr. T" and "Tim" helps a lot more than between "Mr. T" and "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.
\$\endgroup\$

closed as unclear what you're asking by xnor, Xcali, Embodiment of Ignorance, Jo King, J42161217 Apr 30 at 7:32

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – DJMcMayhem May 1 at 14:23
4
\$\begingroup\$

Perl 6, 136 bytes

{$!=$;$/=1;(|.sort(&h),'').map({~$!,~($!=$_),-$/+($/=(sort('A'..'Z'x 12)....&h||'Z'x 12))}).sort(-*[2])[lazy ^10]}
my&h={S:g/<:!L>//.uc}

Try it online!

This is an anonymous code block that takes a list of strings and returns a list of lists. This uses a brute forcey method which takes far too long to attempt 12 letter names, so here is a link to a version with only 3 letter names.

Explanation:

my&h={              }  # Helper function. 
      S:g/<:!L>//      # This removes non-alpha characters
                 .uc   # Convert to uppercase

{              # Actual code block
  $!=$;        # Initialise the "first" element as an empty string
  $/=1;        # With value 1
  (|.sort(&h)  # Sort the input by the helper function
   ,'')        # And add the last string as an empty string
  .map({       # Map each value to
    ~$!,          # The previous name
    ~($!=$_),     # The current name
    -$/           # The negative of the previous value
       +($/=(     # Plus the new value, which is:
             sort('A'..'Z'x 12)     # From the lexographically sorted list of names
             ...                    # Get the sublist up to
                .&h                 # The current name
                   ||'Z'x 12        # Or the last name if the current is empty
        ))   # And get the length of the list
   }).sort(      # Sort each list
     *[2]        # By the third element
   )[lazy ^10]   # And get the first 10 or less items
\$\endgroup\$
  • 1
    \$\begingroup\$ Haha, I didn't even think about "brute forcing" it, but I like the idea. If that's shorter, why not... One question though: the order of elements seems to be correct, but it does not seem to output the second element per tuple? I'd expect (value aside) (gfd, qwe, #) (bcv, gfd, #) (uyt, zde, #) ... and your output is (gfd #) (bcv #) (uyt #) .... So it seems right, but the second half of the pair is missing. \$\endgroup\$ – LWChris Apr 30 at 7:08
  • \$\begingroup\$ @LWChris Ah, sorry. I removed a pair of brackets to golf it, but turned out to break that. This should be fixed now \$\endgroup\$ – Jo King Apr 30 at 8:39

Not the answer you're looking for? Browse other questions tagged or ask your own question.