# Challenge

## Premise

I've got multiple pretty numbers all in a row. Each is a decimal digit.

0s are weakly attracted to 0s, 1s are attracted to 1s a little more strongly and so on until 9. I don't know why — it must be something I ate. As a result, a sort of two-way sideways sedimentation occurs until the higher values are closer to the middle and the lower values closer to the sides.

Specifically, this happens:

1) Find all instances of digits having the highest value. If there's an even number $$\2p\$$ of them, go to step 2a. If there's an odd number $$\2q+1\$$ of them, go to step 2b.

2a) Consider the $$\p\$$ instances on the left and the $$\p\$$ instances on the right. Continue to step 3.

2b) Consider the $$\q\$$ instances on the left of the middle instance, and the $$\q\$$ instances on its right. Continue to step 3.

3) Each member of the former subset will move right by swapping places with the digit directly on its right as long as this other digit is smaller, and members of the latter subset will move left in a similar fashion. All such swaps happen simultaneously. If exactly one lower-value digit is enclosed by two high-value digits (one on each side), always move this lower-value digit to the right instead.

4) Repeat step 3 until all digits of this value are directly side-by-side.

5) Repeat steps 1 to 4 for smaller and smaller values until the values are exhausted.

Here's a detailed example.

2101210121012 | begin
1201120211021 | four 2s; the two on the left move right, the two on the right move left
1021122011201 | conflict, resulting in change from 202 to 220 (see step 3); meanwhile,
the two other 2s move inwards
1012122012101 | no remarks
1011222021101 | no remarks
1011222201101 | 2s are done
0111222210110 | six 1s, but exactly one on the left of the chain of 2s moves right, and
exactly two on the right move left. observe 1s can never pass through 2s
because 2 is not smaller than 1 (see step 3)
0111222211010 | no remarks
0111222211100 | end; 1s and 0s are done at the same time


Let's find the end state with the power of automation!

Input: an integer sequence where each element is between 0 and 9 inclusive. The sequence is of length $$\3\leq n\leq10000\$$.

Output: in any format, the end state that would be reached by following the instructions in the section 'Premise'. Shortcut algorithms that give you the correct answer are allowed.

### Examples

Input -> output
0 -> 0
40304 -> 04430
3141592654 -> 1134596542
2101210121012 -> 0111222211100
23811463271786968331343738852531058695870911824015 -> 01111122233333333445556666777888888999887554211100


# Remarks

• I'm having trouble following what's going on in the third test case (3141592654 ). From my understanding, the 9,6,4,3, and 2 shouldn't move since there is only one of each. The 5s and 1s shouldn't move because they are blocked by a higher number. Yet the 1s and 2 end up on the edges, can you explain? Apr 25 '20 at 16:38
• Is this equivalent to: move maximum digits together, then sort remaining digits on the left and reverse sort remaining digits on the right, or is that just what has happened to have happened with the chosen test cases? Apr 25 '20 at 17:14
• In the 40304 case the second set of swaps of 4s cant happen simultaneously, it appears you have chosen right-first - is that what we should do or is 03440 also an acceptable output? Apr 25 '20 at 17:20
• Just making sure, does 213 becomes 213? If so, I'd suggest that as a test case, since the result is not "sorted on the left and reverse sorted on the right". Apr 25 '20 at 19:23
• @SurculoseSputum Based on how the algorithm is presented it would seem that 213 becomes 213. If that were the case, am I right to say that most if not all of the answers fail? And that the test case 3141592654 -> 1134596542 is incorrect also? Apr 25 '20 at 20:14

# JavaScript (ES8), 186 bytes

A direct transformation of the input.

s=>(g=s=>s.join)([...b=g((a=s.split(n=Math.max(...s)))[S='slice'](0,(k=a[L='length'])/2))+(m=a[k>>1])[S](0,k&1&&m[L]/2)].sort())+''.padEnd(k-1,n)+g([...g(a)[S](b[L])].sort((a,b)=>b-a))


Try it online!

MÆṁ$ĊœṖ⁸Ṣ€U2¦;/  A monadic link accepting a list (of any orderable items) which yields a list. Try it online! # J, 4442 bytes (/:~@{.,\:~@}.)~[:(#{2#]<.@-:@+|.)@I.>./=]  Try it online! The meat of the problem is finding the right point to split the input. After that, you just sort the left side up and the right side down, and cat them together (/:~@{.,\:~@}.). We'd like to avoid treating "odd number of max elements" and "even number of max elements" as two special cases. To do this, notice that given the indices of the max elements (I.>./=]), you can add that list elementwise with its reverse and average each element (]<.@-:@+|.). Next, duplicate each element of that list in place (2#), and pull from the result the element at index "length of original list" (#{). All together, this gives us the "midpoint" of the original list, where "midpoint" is defined as "the actual midpoint" in the odd case, and "the average of the two middle-ish" elements in the even case. This is exactly where the algorithm tells us to split the input. # Retina 0.8.2, 135 bytes $
¶¶$¶ O\G. +((.)¶.*)¶(.*?\2)(.*)(\2.*)¶$1$3¶$4¶$5 ((.)¶.*)¶(.*)\2(.*)¶$1$3¶$2¶$4 1A +¶(.)(.*)(.)¶$1¶$2¶$3
2=¶

%O^.
O\G.
¶



Try it online! Link includes test cases. Explanation:

$¶¶$¶


Make a working area with a copy of the input surrounded by blank lines.

O\G.


Sort the digits of the original input.

+((.)¶.*)¶(.*?\2)(.*)(\2.*)¶
$1$3¶$4¶$5


Move minimal suffixes and prefixes of the copy of the input to the blank lines. Each moved minimal suffix must end with the largest digit and each moved minimal prefix must start with the largest digit.

((.)¶.*)¶(.*)\2(.*)¶
$1$3¶$2¶$4


If there is an odd number of the largest digit, move its exclusive prefix and suffix too.

1A


Delete the sorted copy of the digits.

+¶(.)(.*)(.)¶
$1¶$2¶\$3


If there was an even number of the largest digit, move individual digits from the remainder of the copy of the input to the prefix and suffix areas.

2=¶



Move the last digit (if any) or the odd largest digit to the suffix.

%O^.


Sort both the prefix and the suffix descending.

O\G.


Reverse the prefix.

¶



Join the prefix and suffix together.

# Charcoal, 49 bytes

≔⌕Ａθ⌈θη≔…θ÷ΣＥ²§η÷⁻Ｌηι²¦²η⭆χ×Ｉι№ηＩι⮌⭆χ×Ｉι⁻№θＩι№ηＩι


Try it online! Link is to verbose version of code. Explanation:

≔⌕Ａθ⌈θη


Find all the positions of the maximum digit.

≔…θ÷ΣＥ²§η÷⁻Ｌηι²¦²η


Take the average of the middle two (or the middle position duplicated if there are an odd number of positions) and chop the input to this length.

⭆χ×Ｉι№ηＩι


Sort the chopped input. (Because we know the range of characters, we just repeat each character by the number of times it appears in the desired string.)

⮌⭆χ×Ｉι⁻№θＩι№ηＩι


Calculate the number of each digit remaining to give the sorted remainder, and then print that reversed so that the sort is descending.