# Insert semi-sorted into unsorted array

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

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

• 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. Apr 7, 2016 at 14:30
• Dragonshy I just got it! Very nice :-D Apr 8, 2016 at 17:28
• @Lex It would be good to have one or two more test cases Apr 8, 2016 at 17:58

## 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.

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

# 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.

# 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)


# 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}


## Pyth, 545247 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)
• Z is autoinited to 0 which if I'm reading your code correctly can save you a space Apr 7, 2016 at 20:28
• 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. Apr 8, 2016 at 3:59
• You could use AQ instead of J@Q0K@Q1. Apr 8, 2016 at 5:48

# 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