44
\$\begingroup\$

Challenge

Given a non-empty array of integers, e.g.:

[5, 2, 7, 6, 4, 1, 3]

First sever it into arrays where no item is larger than the previous (i.e. non-ascending arrays):

[5, 2] [7, 6, 4, 1] [3]

Next, reverse each array:

[2, 5] [1, 4, 6, 7] [3]

Finally, concatenate them all together:

[2, 5, 1, 4, 6, 7, 3]

This should be what your program outputs/function returns. Repeat this procedure enough times and the array will be fully sorted.

Rules

  • Input and output may be given through any standard methods, and may be in any reasonable array format.
  • The input array will never be empty, but may contain negatives and/or duplicates.
  • The absolute value of each integer will always be less than 231.

Test cases

Hopefully these cover all edge cases:

[1] -> [1]
[1, 1] -> [1, 1]
[1, 2] -> [1, 2]
[2, 1] -> [1, 2]
[2, 3, 1] -> [2, 1, 3]
[2, 1, 3] -> [1, 2, 3]
[2, 1, 2] -> [1, 2, 2]
[2, 1, 1] -> [1, 1, 2]
[3, 1, 1, 2] -> [1, 1, 3, 2]
[3, 2, 1, 2] -> [1, 2, 3, 2]
[3, 1, 2, 2] -> [1, 3, 2, 2]
[1, 3, 2, 2] -> [1, 2, 2, 3]
[1, 0, 5, -234] -> [0, 1, -234, 5]
[1, 0, 1, 0, 1] -> [0, 1, 0, 1, 1]
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]
[5, 4, 3, 2, 1] -> [1, 2, 3, 4, 5]
[2, 1, 5, 4, 3] -> [1, 2, 3, 4, 5]
[2, 3, 1, 5, 4] -> [2, 1, 3, 4, 5]
[5, 1, 4, 2, 3] -> [1, 5, 2, 4, 3]
[5, 2, 7, 6, 4, 1, 3] -> [2, 5, 1, 4, 6, 7, 3]
[-5, -2, -7, -6, -4, -1, -3] -> [-5, -7, -2, -6, -4, -3, -1]
[14, 5, 3, 8, 15, 7, 4, 19, 12, 0, 2, 18, 6, 11, 13, 1, 17, 16, 10, 9] -> [3, 5, 14, 8, 4, 7, 15, 0, 12, 19, 2, 6, 18, 11, 1, 13, 9, 10, 16, 17]

Scoring

This is , so the shortest code in bytes wins.

\$\endgroup\$
  • 4
    \$\begingroup\$ What's the big-o of this sorting method? \$\endgroup\$ – mbomb007 Dec 21 '16 at 22:08
  • 1
    \$\begingroup\$ @mbomb007 I don't understand big-o notation very well, but I think a single iteration is O(n). Multiply that by worst-case n iterations and you get O(n^2) (worst-case; best-case would be O(n), I think, for a single iteration). \$\endgroup\$ – ETHproductions Dec 21 '16 at 22:23
  • 1
    \$\begingroup\$ That sounds right to me, however it's worth pointing out that reversing an array isn't a very efficient operation, so it's a slow O(n^2) \$\endgroup\$ – DJMcMayhem Dec 21 '16 at 22:45
  • 2
    \$\begingroup\$ @WheatWizard reversing an array doesn't require room for a copy of the array, only room for a single element. and is O(n). swap first and last elements then swap second and second last elements etc, when you get to the middle stop. \$\endgroup\$ – Jasen Dec 22 '16 at 11:27
  • \$\begingroup\$ Reversing is O(n), but reversing can be built right into the algorithm (that's what my JS answer does); since each iteration loops over each item in the array once, a single iteration is O(n). (I think...) \$\endgroup\$ – ETHproductions Dec 22 '16 at 14:27

25 Answers 25

19
\$\begingroup\$

JavaScript (ES6), 64 bytes

f=([n,...a],z=[],q=[n,...z])=>a+a?n<a[0]?[...q,...f(a)]:f(a,q):q

Recursion FTW! The basic algorithm in use here is to keep track of the current non-ascending run in an array, "returning" it whenever an ascending element is found. We do this recursively, continually concatenating the results, until we run out of items. By creating each run in reverse ([n,...z] instead of [...z,n]), we can avoid the lengthy .reverse() at no cost.

Test snippet

f=([n,...a],z=[],q=[n,...z])=>a+a?n<a[0]?[...q,...f(a)]:f(a,q):q

g=a=>console.log("Input:",`[${a}]`,"Output:",`[${f(a)}]`)

g([1])
g([1,1])
g([1,2])
g([2,1])
g([3,2,1])
g([3,1,2])
g([3,1,1,2])
g([5,2,7,6,4,1,3])
<input id=I value="5, 2, 7, 6, 4, 1, 3">
<button onclick="g((I.value.match(/\d+/g)||[]).map(Number))">Run</button>

\$\endgroup\$
  • \$\begingroup\$ Can you explain how your array gets parsed into your first parameter [n,...a]. What is n? Is that just the first item in your array? \$\endgroup\$ – Oliver Dec 22 '16 at 0:05
  • 1
    \$\begingroup\$ @obarakon Correct. n is the first item in the array, and a is the rest of the array. You can find more info here. \$\endgroup\$ – ETHproductions Dec 22 '16 at 0:12
  • \$\begingroup\$ Thank you. That was very helpful. Since your first parameter is an array, why do you need to include the ...a? Is that just so you can take advantage of n? One more thing, when you call f(a,q), does q get set to the parameter z? \$\endgroup\$ – Oliver Dec 22 '16 at 0:21
  • 1
    \$\begingroup\$ @obarakon Well, f=([n])=>... would only capture the first element, and f=([n,a])=>... would capture only the first in n and the second in a. Another way to do what f=([n,...a])=>,,, does would be f=a=>(n=a.unshift(),.... \$\endgroup\$ – ETHproductions Dec 22 '16 at 4:49
  • 1
    \$\begingroup\$ And since z is the second parameter in the function, when f(a,q) is called, f sees it as z. Hope this helps! \$\endgroup\$ – ETHproductions Dec 22 '16 at 4:50
14
\$\begingroup\$

Python 3, 63 bytes

f=lambda x,*p:x[:1]>p>()and p+f(x)or x and f(x[1:],x[0],*p)or p

Try it online!

\$\endgroup\$
11
\$\begingroup\$

Jelly, 8 bytes

Ṁ;<œṗ³UF

Try it online!

Explanation:

Ṁ;         Prepend the list [a1, a2… an] with its maximum.
  <        Elementwise compare this with the original list:
           [max(a) < a1, a1 < a2, …, a(n-1) < an, an]
           The first element is always 0.
   œṗ³     Partition the original list (³) at the indices
           of the non-zero values in the working list.
           (The spurious `an` at the end of the left argument,
           resulting from comparing lists of different sizes,
           is ignored by this operation, thankfully.)
      U    Reverse each part.
       F   Flatten.
\$\endgroup\$
  • 1
    \$\begingroup\$ I was on the verge of hitting Save Edits when I saw your answer... Well done. \$\endgroup\$ – Dennis Dec 22 '16 at 0:09
  • \$\begingroup\$ @Dennis Heh, so you added Dyalog partitioned enclose, but what about APL2 partition? \$\endgroup\$ – Adám Dec 22 '16 at 9:09
11
\$\begingroup\$

JavaScript (ES6), 70 bytes

Sure, this is already beaten by ETHproductions answer, but that's the best I could come up with so far without using recursion.

a=>a.map((n,i)=>a[x=[...o,...r=[n,...r]],i+1]>n&&(o=x,r=[]),r=o=[])&&x

Note: Initializing both r and o to the exact same object with r = o = [] may look like a hazardous idea. But it is safe to do so here because r is immediately assigned its own instance (containing the first element of a) on the first iteration with r = [n, ...r].

Test cases

let f =

a=>a.map((n,i)=>a[x=[...o,...r=[n,...r]],i+1]>n&&(o=x,r=[]),r=o=[])&&x

console.log(JSON.stringify(f([1])));
console.log(JSON.stringify(f([1, 1])));
console.log(JSON.stringify(f([1, 2])));
console.log(JSON.stringify(f([2, 1])));
console.log(JSON.stringify(f([2, 3, 1])));
console.log(JSON.stringify(f([2, 1, 3])));
console.log(JSON.stringify(f([2, 1, 2])));
console.log(JSON.stringify(f([2, 1, 1])));
console.log(JSON.stringify(f([3, 1, 1, 2])));
console.log(JSON.stringify(f([3, 2, 1, 2])));
console.log(JSON.stringify(f([3, 1, 2, 2])));
console.log(JSON.stringify(f([1, 3, 2, 2])));
console.log(JSON.stringify(f([1, 0, 5, -234])));
console.log(JSON.stringify(f([1, 0, 1, 0, 1])));
console.log(JSON.stringify(f([1, 2, 3, 4, 5])));
console.log(JSON.stringify(f([5, 4, 3, 2, 1])));
console.log(JSON.stringify(f([2, 1, 5, 4, 3])));
console.log(JSON.stringify(f([2, 3, 1, 5, 4])));
console.log(JSON.stringify(f([5, 1, 4, 2, 3])));
console.log(JSON.stringify(f([5, 2, 7, 6, 4, 1, 3])));
console.log(JSON.stringify(f([-5, -2, -7, -6, -4, -1, -3])));
console.log(JSON.stringify(f([14, 5, 3, 8, 15, 7, 4, 19, 12, 0, 2, 18, 6, 11, 13, 1, 17, 16, 10, 9])));

\$\endgroup\$
  • 2
    \$\begingroup\$ No worries, I love seeing different approaches. And one often ends up becoming shorter than another after golfing :-) \$\endgroup\$ – ETHproductions Dec 21 '16 at 23:17
8
\$\begingroup\$

MATL, 15 bytes

lidO>vYsGhXSOZ)

Input is a column vector, with the format [5; 2; 7; 6; 4; 1; 3] (semicolon is the row separator).

Try it online!

Take input [5; 2; 7; 6; 4; 1; 3] as an example.

Explanation

l     % Push 1
      % STACK: 1
i     % Push input
      % STACK: 1, [5; 2; 7; 6; 4; 1; 3]
d     % Consecutive differences
      % STACK: 1, [-3; 5; -1; -2; -3; 2]
O>    % Test if greater than 0, element-wise
      % STACK: 1, [0; 1; 0; 0; 0; 1]
v     % Concatenate vertically
      % STACK: [1; 0; 1; 0; 0; 0; 1]
Ys    % Cumulative sum
      % STACK: [1; 1; 2; 2; 2; 2; 3]
G     % Push input again
      % STACK: [1; 1; 2; 2; 2; 2; 3], [5; 2; 7; 6; 4; 1; 3]
h     % Concatenate horizontally
      % STACK: [1 5; 1 2; 2 7; 2 6; 2 4; 2 1; 3 3]
XS    % Sort rows in lexicographical order
      % STACK: [1 2; 1 5; 2 1; 2 4; 2 6; 2 7; 3 3]
OZ)   % Get last column. Implicitly display
      % STACK: [2; 5; 1; 4; 6; 7; 3]
\$\endgroup\$
  • \$\begingroup\$ I translated your answer to Octave saved me 31 bytes! \$\endgroup\$ – rahnema1 Dec 23 '16 at 4:47
7
\$\begingroup\$

Mathematica, 30 27 bytes

3 bytes saved due to @Martin Ender.

Join@@Sort/@Split[#,#>#2&]&

Anonymous function. Takes a list of numbers as input and returns a list of numbers as output.

\$\endgroup\$
  • \$\begingroup\$ Beat me to it! :) \$\endgroup\$ – Greg Martin Dec 22 '16 at 18:55
5
\$\begingroup\$

Python 2, 100 bytes

A really terrible golf, but I wanted to post my solution (one does not simply outgolf Dennis)...

d=input();L=[];x=0;d+=-~d[-1],
for i in range(1,len(d)):
 if d[i]>d[i-1]:L+=d[x:i][::-1];x=i
print L

Test on repl.it!

Input should be given as a Python list literal, such as [5, 3, 4, 2, 6, 1].

The basic idea is to make heavy use of Python's slicing syntax, slicing each necessary section from the array, reversing it, and adding it to the new array.

\$\endgroup\$
  • \$\begingroup\$ I think the first line can be d,L,x=input(),[],0;d+=.... \$\endgroup\$ – Daniel Dec 22 '16 at 6:16
  • \$\begingroup\$ @Dopapp that's exactly the same byte count \$\endgroup\$ – FlipTack Dec 22 '16 at 6:51
4
\$\begingroup\$

Pyke, 11 8 bytes (old version)

$0m<fm_s

Try it here! (works on latest version)

$        -     delta(input)
 0m<     -    map(i<0 for i in ^)
    f    -   split_at(input, ^)
     m_  -  map(reverse, ^)
       s - sum(^)
\$\endgroup\$
4
\$\begingroup\$

Retina, 163 bytes

Yes, I know how horrid this is. Supporting zeros and negatives was super fun. Byte count assumes ISO 8859-1 encoding.

\d+
$*
(?<=-1*)1
x
-

x,1
x¶1
\b(1+),(1+\1)\b
$1¶$2
,,1
,¶1
x,(¶|$)
x¶¶
(?<=\b\1x+(?=,(x+))),\b
¶
O%$#`.(?=(.*))
$.1
+`¶
,
\bx
-x
(\w+)
$.1
^,
0,
,$
,0
,,
,0,
^$
0

Try it online

Explanation:

\d+                         # Convert to unary
$*
(?<=-1*)1                   # Replace negatives with x's instead of 1's
x
-                           # Remove minus sign

x,1                         # Separate if negative before positive
x¶1
\b(1+),(1+\1)\b             # or greater positive follows a positive
$1¶$2
,,1                         # or positive follows a zero
,¶1
x,(¶|$)                     # or zero follows a negative
x¶¶
(?<=\b\1x+(?=,(x+))),\b     # or negative follows a negative of greater magnitude.
¶
O%$#`.(?=(.*))              # Swear at the input, then reverse each line
$.1
+`¶                         # Remove breaks, putting commas back
,
\bx                         # Put the minus signs back
-x
(\w+)                       # Replace unary with length of match (decimal)
$.1
^,                          # Do a bunch of replacements to resurrect lost zeros
0,
,$
,0
,,
,0,
^$
0
\$\endgroup\$
4
\$\begingroup\$

05AB1E, 19 18 16 14 bytes

Saved 2 bytes using Luis Mendo's sorting trick

ü‹X¸ì.pO¹)ø{ø¤

Try it online!

Explanation

Example input [5, 2, 7, 6, 4, 1, 3]

ü‹               # pair-wise less-than
                 # STACK: [0, 1, 0, 0, 0, 1]
  X¸ì            # prepend a 1
                 # STACK: [1, 0, 1, 0, 0, 0, 1]
     .p          # prefixes
       O         # sum
                 # STACK: [1, 1, 2, 2, 2, 2, 3]
        ¹        # push input
                 # STACK: [1, 1, 2, 2, 2, 2, 3], [5, 2, 7, 6, 4, 1, 3]
         )       # wrap stack in list
                 # STACK: [[1, 1, 2, 2, 2, 2, 3], [5, 2, 7, 6, 4, 1, 3]]
          ø      # zip
                 # STACK: [[1, 5], [1, 2], [2, 7], [2, 6], [2, 4], [2, 1], [3, 3]]
           {     # sort
                 # STACK: [[1, 2], [1, 5], [2, 1], [2, 4], [2, 6], [2, 7], [3, 3]]
            ø    # zip
                 # STACK: [[1, 1, 2, 2, 2, 2, 3], [2, 5, 1, 4, 6, 7, 3]]
             ¤   # tail
                 # OUTPUT: [2, 5, 1, 4, 6, 7, 3]

Previous 16 byte solution

Dü‹X¸ì.pO.¡€g£í˜
\$\endgroup\$
  • \$\begingroup\$ Those linebreaks explained it wonderfully... :-P \$\endgroup\$ – Stewie Griffin Dec 21 '16 at 23:09
  • \$\begingroup\$ @StewieGriffin: Yeah, I changed up the code and posted before I had rewritten the explanation :P \$\endgroup\$ – Emigna Dec 21 '16 at 23:10
4
\$\begingroup\$

JavaScript (ECMA 6), 121 128 125 119 108 bytes

f=a=>{p=a[0],c=[],b=[];for(e of a){e>p&&b.push(c.reverse(c=[]));c.push(p=e)}return[].concat.call([],...b,c)}

Lambda expression takes a single Array parameter, a.

Thanks to @ETHproductions for helping me see my first mistake.

\$\endgroup\$
  • \$\begingroup\$ Nice! I think you can do return(b+","+c).split`,` to save a few bytes at the end. \$\endgroup\$ – ETHproductions Dec 21 '16 at 23:27
  • 1
    \$\begingroup\$ Better yet, you can use c.unshift instead of c.push to remove the need to reverse c. After doing this, I got 94 bytes. \$\endgroup\$ – ETHproductions Dec 21 '16 at 23:31
3
\$\begingroup\$

Ruby, 60 55 bytes

s=->x{x.slice_when{|p,q|p<q}.map{|z|z.reverse}.flatten} 

Pretty much what the challenge asked for. I defined a lambda s, that takes an array x, and sever (slices) it into smaller pieces where the following element would be greater than. This gives back an enumerator, which we can call map on and reverse the order of the pieces, before finally bringing it all together with flatten, which concatenates the elements in the defined order into one array.

Tests

p s[[1]]===[1]
p s[[1, 1]]===[1, 1]
p s[[1, 2]]===[1, 2]
p s[[2, 1]]===[1, 2]
p s[[2, 3, 1]]===[2, 1, 3]
p s[[2, 1, 3]]===[1, 2, 3]
p s[[2, 1, 2]]===[1, 2, 2]
p s[[2, 1, 1]]===[1, 1, 2]
p s[[3, 1, 1, 2]]===[1, 1, 3, 2]
p s[[3, 2, 1, 2]]===[1, 2, 3, 2]
p s[[3, 1, 2, 2]]===[1, 3, 2, 2]
p s[[1, 3, 2, 2]]===[1, 2, 2, 3]
p s[[1, 0, 5, -234]]===[0, 1, -234, 5]
p s[[1, 0, 1, 0, 1]]===[0, 1, 0, 1, 1]
p s[[1, 2, 3, 4, 5]]===[1, 2, 3, 4, 5]
p s[[5, 4, 3, 2, 1]]===[1, 2, 3, 4, 5]
p s[[2, 1, 5, 4, 3]]===[1, 2, 3, 4, 5]
p s[[2, 3, 1, 5, 4]]===[2, 1, 3, 4, 5]
p s[[5, 1, 4, 2, 3]]===[1, 5, 2, 4, 3]
p s[[5, 2, 7, 6, 4, 1, 3]]===[2, 5, 1, 4, 6, 7, 3]
p s[[-5, -2, -7, -6, -4, -1, -3]]===[-5, -7, -2, -6, -4, -3, -1]
p s[[14, 5, 3, 8, 15, 7, 4, 19, 12, 0, 2, 18, 6, 11, 13, 1, 17, 16, 10, 9]]===[3, 5, 14, 8, 4, 7, 15, 0, 12, 19, 2, 6, 18, 11, 1, 13, 9, 10, 16, 17]
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome, nice <s>first</s> second answer, check this: codegolf.stackexchange.com/questions/363/… \$\endgroup\$ – G B Dec 22 '16 at 8:40
  • \$\begingroup\$ Thanks a lot. Turned this into a lambda, as suggested in the link you provided, and saved 5 bytes that way. \$\endgroup\$ – manonthemat Dec 22 '16 at 16:05
2
\$\begingroup\$

Brachylog, 10 bytes

~c:{>=r}ac

Try it online!

Explanation

~c            Deconcatenate the Input
  :{>=r}a     Each resulting sublist must be non-increasing, and then reverse it
         c    Concatenate
\$\endgroup\$
  • \$\begingroup\$ Does Brachylog's c, when run in reverse, necessarily try splits into fewer lists first? \$\endgroup\$ – user62131 Dec 25 '16 at 3:26
  • \$\begingroup\$ @ais523 yes, it does. \$\endgroup\$ – Fatalize Dec 25 '16 at 13:07
1
\$\begingroup\$

Dyalog APL, 7 15 bytes

Requires ⎕ML←3, which is default on many systems.*

{∊⌽¨⍵⊂⍨1+⍵-⌊/⍵}

enlist (flatten)

⌽¨ each-reversed

⍵⊂⍨ the argument partitioned* by cutting where each corresponding element is larger than its predecessor in

1+ one plus

⍵- the argument minus

⌊/⍵ the smallest element of the argument


Old 7 byte solution fails with non-positive integers:

Requires ⎕ML←3, which is default on many systems.*

∊⌽¨⊆⍨⎕

enlist (flatten) the

⌽¨ each-reversed

⊂⍨ self-partitioned*


* Partition () is a function which cuts its right argument where the corresponding left argument is larger than the preceding one. (Unfortunately it only accepts non-negative integers, and zero has special meaning.) From version 16, this functionality of is available on all systems (even those where ⎕ML≠3), using the glyph .

\$\endgroup\$
1
\$\begingroup\$

Haskell, 49 bytes

(a:b)%l|any(<a)l=l++b%[a]|1<2=b%(a:l)
_%l=l
(%[])

Usage example: (%[]) [5,2,7,6,4,1,3] -> [2,5,1,4,6,7,3].

Recursive approach. The function % takes the input list as its first parameter and an accumulator l which keeps track of the non-ascending chunk so far (in reverse order). The base case is reached when the input list is empty and then the result is the accumulator. If the input list is not empty and the first element a doesn't fit in the current chunk (any(<a)l), return the accumulator and append a recursive call on the rest of the list and a as the new accumulator (l++b%[a]). Else, make a recursive call on the rest of the list and a prepended to tha accumulator (b%(a:l)). The main function (%[]) calls % with an empty accumulator.

\$\endgroup\$
1
\$\begingroup\$

Retina, 98 bytes

Byte count assumes ISO 8859-1 encoding.

$

-(\d+)
$1$*-/
\d+
$*
S-`(?<=(-+)/ )(?!\1)|(?=\b(1+))(?<!\2 )
O%`\S* 
¶

((-)|1)*/? 
$2$#1 
 $

Try it online!

\$\endgroup\$
1
\$\begingroup\$

R, 64 bytes

cat(unlist(lapply(split(x<-scan(),cumsum(c(F,diff(x)>0))),rev)))

Reads input from stdin. We split the input into a list of vectors using split() which requires a factor variable that groups the input. The factor is created by taking the cumulative sum of the the logical vector for which the difference is positive.

Consider the vector:

x=c(5, 2, 7, 6, 4, 1, 3)

Now taking the difference and prepending F by running y=c(F,diff(x)>0) would produce the following logical vector:

[1] FALSE FALSE  TRUE FALSE FALSE FALSE  TRUE

Taking the cumulative sum cumsum(y) produces a vector where each group is represented by a unique factor upon which we can combine with the split function:

[1] 0 0 1 1 1 1 2
\$\endgroup\$
  • \$\begingroup\$ 60 bytes using diffinv rather than cumsum. \$\endgroup\$ – Giuseppe Nov 20 '18 at 21:57
1
\$\begingroup\$

Octave, 75 44 bytes

Based on MATL answer of @LuisMendo

@(a)sortrows([cumsum([1;diff(a)>0]),a])(:,2)

Try it Online!

Previous answer

@(a)[fliplr(mat2cell(f=fliplr(a),1,diff(find([1,diff(f)<0,numel(a)])))){:}]

Try it Online!

reverse the array

f=fliplr(a)

take first difference of f

d = diff(f);

find position of where the next element is less than the previous element

p=find([1,diff(f)<0,numel(a)])

first difference of the positions returns length of each sub array

len=diff(p)

use length of each sub array in mat2cell to split the array to nested list of arrays

nest = mat2cell(f,1,len);

reverse the nested list

rev_nest = fliplr(nest) 

flatten the nested list

[rev_nest{:}]
\$\endgroup\$
0
\$\begingroup\$

Pyth - 15 bytes

s_McQf<@QtT@QTU

Try it online here.

\$\endgroup\$
0
\$\begingroup\$

Perl 6, 59 bytes

{map |+«*.[0].reverse,m/:s([(\-?\d+)<?{[>=] $0}>] +)+/[0]}

Regex-based solution.
Because this is Sparta Perl!!

  • m/ /: Stringify the input array, and match a regex against it.
  • (\-? \d+): Match a number, and capture it as $0.
  • <?{ [>=] $0 }>: Zero-width assertion that only matches if all $0 captured so far in the current sub-match are in non-ascending order.
  • ([ ] +)+: Repeat the last two steps as often as possible, otherwise start a new sub-match.
  • map , [0]: Iterate over the sub-matches.
  • |+«*.[0].reverse: For each one, take the list of values matched by $0, reverse it, coerce the values to numbers (), and slip them into the outer list (|).

Perl 6, 63 bytes

sub f(\a){flat $_,f a[+$_..*]with first {[<=] $_},:end,[\R,] a}

Recursive list processing solution.
More laborious than I had hoped.
Even though the language has lots of convenient built-ins, there seem to be none for list partitioning (e.g. like Ruby's slice_when or Haskell's takeWhile).

\$\endgroup\$
0
\$\begingroup\$

Stacked, noncompeting, 34 bytes

Still constantly developing this language.

{e.b:e b last<}chunkby$revmap flat

Argument lies on TOS. Try it here!

chunkby takes a function and collects arrays of contiguous data that satisfy the function. The function then is:

{e.b:e b last<}
{e.b:         }  function with arguments [e, <unused>, b]--the element, <the index>, and the
                 chunk being built
     e       <   check if e is less than
       b last    the last element of b

This gives a strictly decreasing array.

$revmap is basically [rev]map and reverses each item.

flat finally flattens the array.


Some fun for actually sorting the array:

[{e.b:e b last<}chunkby$revmap flat] @:sortstep
[$sortstep periodloop] @:sort

10:> @arr
arr out
arr shuf @arr
arr out
arr sort out

This outputs (for example):

(0 1 2 3 4 5 6 7 8 9)
(4 5 1 0 6 7 2 8 9 3)
(0 1 2 3 4 5 6 7 8 9)
\$\endgroup\$
0
\$\begingroup\$

Python, 151 139 Bytes

Saved 12 Bytes thanks to @Flp.Tkc!

Nowhere near @Flp.Tkc, let alone...

def s(l):
 r=[];i=j=0
 while j<len(l)-1:
  if l[j+1]>l[j]:r+=l[i:j+1][::-1],;i=j+1
  j+=1
 r+=l[i:j+1][::-1],;return[i for s in r for i in s]
\$\endgroup\$
  • \$\begingroup\$ Instead of using append, use += data, the trailing comma implicitly constructs a tuple, which is then concatenated with the list, adding the data as the last element in the list. In this context, do r+=l[i:j+1][::-1], \$\endgroup\$ – FlipTack Dec 22 '16 at 16:22
0
\$\begingroup\$

Python 2, 74 bytes

b=[];c=[];a+=9e9,
for i in a[:-1]:
 b=[a.pop(0)]+b
 if b[0]<a[0]:c+=b;b=[]

Input in a, output in c

\$\endgroup\$
0
\$\begingroup\$

Python 3, 191 Bytes

a=[int(i)for i in input().split()]
while a!=sorted(a):
 b=[[]]
 for i,j in enumerate(a):
  if a[i-1]<j:b+=[[j]]
  else:b[-1]+=[j]
 a=[]
 for l in[k[::-1]for k in b]:a+=[k for k in l]
print(a)

I'm not sure if using the sorted function to check is allowed here, but I couldn't think of a good reason against it, and it brought down my byte count by ~30 Bytes.

\$\endgroup\$
0
\$\begingroup\$

Clojure, 105 bytes

#(filter number?(mapcat reverse(partition-by not(mapcat(fn[[a b]][a(< b a)])(partition 2 1(conj % 1))))))

Partitions into pairs on consecutive numbers, puts true or false between them, partitions on not to true and numbers become false and false true, reverses partitions and keeps numerical values.

\$\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.