14
\$\begingroup\$

Welcome to your first day at PPCG Inc. As our newest junior assistant document sorter, you are responsible for making sure all documents we sent down to you are archived in alphabetical order. It's so easy a monkey can do it. Well, metaphorically speaking, as we did hire a monkey to do it. Guess what? Turns out monkeys lack an understanding of our alphabet. Anyway, there's no time to fix the mess there is right now, so just try to not make the situation any worse, ok? Then get to it! If you get hungry, there's bananas over by the water cooler. Good luck!

Job Description

Input

  • You will receive a list of strings (the archive) and a string that needs to be added to that list (the document)
  • All strings will contain only uppercase letters, lowercase letters and spaces
  • Strings will always start and end with a letter

Task

Determine the target position of the document: the position it should receive in the archive. The target position can be determined as follows:

  • For each position:
    • Count the amount of strings in the archive before that position that are alphabetically before the document
    • Count the amount of strings in the archive after that position that are alphabetically after the document
    • Define the score of the position as the sum of the above two counts
  • The target position of the document is the position with the highest score
  • In case of a tie, all positions with the highest score are equally valid as target position. Only one needs to be selected.

When sorting:

  • Uppercase and lowercase letters are equivalent
  • Spaces come before letters

Output

  • The archive with the document added to it in any form

OR

  • The target position of the document, in either a 0-based or 1-based index

Job evaluation

Fewest bytes wins!

Example I/O

Archive:
    Applebuck Season
    Friendship is Magic
    The Ticket Master
    Griffon the BrushOff
    Boast Busters
    Bridle Gossip

Document: Dragonshy

Position scores (0-based index):
0: 0 + 3 = 3
1: 1 + 3 = 4
2: 1 + 2 = 3
3: 1 + 1 = 2
4: 1 + 0 = 1
5: 2 + 0 = 2
6: 3 + 0 = 3

Target position: 1
\$\endgroup\$
  • 5
    \$\begingroup\$ Welcome to PPCG, this seems like a nice first post! :) Your instructions in the "Task" section are kind of hard to read, though. Horizontal scrolling is annoying:I'd consider using a bullet list instead. We have a handy Sandbox where you can post challenges for the community to review, if you want. \$\endgroup\$ – FryAmTheEggman Apr 7 '16 at 14:30
  • \$\begingroup\$ Dragonshy I just got it! Very nice :-D \$\endgroup\$ – Luis Mendo Apr 8 '16 at 17:28
  • \$\begingroup\$ @Lex It would be good to have one or two more test cases \$\endgroup\$ – Luis Mendo Apr 8 '16 at 17:58
4
\$\begingroup\$

JavaScript (ES6), 81 bytes

(a,d)=>a.map((e,i)=>d[l="toLowerCase"]()<e[l]()?s--:++s>m&&(++m,p=++i),m=s=p=0)|p

Ungolfed:

function position(archive, document) {
    var score = 0;
    var max = 0;
    var pos = 0;
    var i = 0;
    while (i < archive.length) {
        if (archive[i++].toLowerCase() > document.toLowerCase()) {
            score--;
        } else {
            score++;
            if (score > max) {
                max++;
                pos = i;
            }
        }
    }
    return pos;
}

Edit: Saved a lot of bytes thanks to @user81655.

\$\endgroup\$
  • \$\begingroup\$ Also replacing the indexOf with a result variable that is set during the map would be shorter as well. \$\endgroup\$ – user81655 Apr 7 '16 at 19:51
  • \$\begingroup\$ Agreed, but it hardly looks like my solution any more... \$\endgroup\$ – Neil Apr 7 '16 at 20:54
3
\$\begingroup\$

Pyth, 40 38 bytes

Credits to @Katenkyo for teaching me that A xnor B is basically A==B. (A xor B is also A!=B)

AQJ+],k0.e,rb0hkGteh.Msmq<hdrH0<edeZJJ

Try it online!

How it works:

It sums the XNOR of whether the entry is smaller than the document, and whether the entry's index is smaller than the document's index.

It finds the position in which this sum is the maximum, then outputs it.

\$\endgroup\$
2
\$\begingroup\$

Python 3, 135 167 Bytes

def a(b,c):a=[sum(map(lambda x:x.lower()>c.lower(),b[i:]))+sum(map(lambda x:x.lower()<c.lower(),b[:i]))for i in range(0,len(b)+1)];b.insert(a.index(max(a)),c);print(b)
\$\endgroup\$
1
\$\begingroup\$

Ruby, 97 bytes

Anonymous function, returns the target position.

->a,d{d.upcase!;(0...a.size).max_by{|i|a[0,i].count{|s|s.upcase<d}+a[i..-1].count{|s|s.upcase>d}}}

When actually inserting into the archive, 110 bytes:

->a,d{t=d.upcase;a.insert (0...a.size).max_by{|i|a[0,i].count{|s|s.upcase<d}+a[i..-1].count{|s|s.upcase>d}},d}
\$\endgroup\$
1
\$\begingroup\$

Pyth, 54 52 47 45 bytes

AQVhlG=Ys+m>rH0rd0:G0Nm<rH0rd0gGNI>YZ=ZY=kN;k

Expect input is a list, first element is a list of strings (archive), second element is a string (document)

AQ                                            # initialize G and H with the archive and the document
  VhlG                                        # iterate over the indexes on archive
      =Ys+                                    # concatenate and sum the following scores
          m>rH0rd0:G0N                        # map a string comparison between the document and the archives up to the index, returning true(1) for lower, and false(0) for higher
                      m<rH0rd0gGN             # same as above, but starts at the index and goes up to the end of the archive, returning false(0) for lower, and true(1) for higher
                                 I>YZ         # Check if score is higher than highest
                                     =ZY      # update highest score
                                        =kN;  # update index
                                            k # print index

Test here

  • Saved 5 bytes on input initialization (thanks @Kenny Lau)
\$\endgroup\$
  • \$\begingroup\$ Z is autoinited to 0 which if I'm reading your code correctly can save you a space \$\endgroup\$ – Maltysen Apr 7 '16 at 20:28
  • \$\begingroup\$ Using ["Applebuck Season","Friendship is Magic","The Ticket Master","Griffon the BrushOff","Boast Busters","Bridle Gossip"]\n "Dragonshy" as input and using E instead of @Q0 and @Q1 can save you four bytes. \$\endgroup\$ – Leaky Nun Apr 8 '16 at 3:59
  • \$\begingroup\$ You could use AQ instead of J@Q0K@Q1. \$\endgroup\$ – Leaky Nun Apr 8 '16 at 5:48
1
\$\begingroup\$

MATL, 32 bytes

hk4#S4#S%2#0)>t0whYsw~0hPYsP+K#X>

Input is a cell array of strings (several strings separated by spaces and enclosed in curly braces) for the archive, and a string for the document. Output is 1-based. In case of a tie the first position is returned.

Try it online!

Explanation

h      % Concatenate archive and document as a cell array of strings
k      % Convert all strings to lowercase
4#S    % Sort and output the indices of the sorting
4#S    % Again. This gives the indices that applied to the concatenated
       % array would make it sorted
2#0)   % Separate last index (document) from the others (archive)
>      % Is it greater? Gives zero/one array the size of the archive
t      % Duplicate that array
0wh    % Prepend a 0
Ys     % Cumulative sum. This is first part of the score
w~     % Swap. Negate zero/one array
0h     % Postpend a 0
PYsP   % Reverse, cumulative sum, reverse. Second part of the score
+      % Add. This is the score of each position
K#X>   % Arg max
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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