Driftsort an array

Question

Driftsort is a simple way to "sort" an array. It works by "sliding" or "rotating" the elements over in the array until the array is sorted, or until the array fails to be sorted.

Let's walk through two examples. First, consider the array [10, 2, 3, 4, 7]. Since the array is not sorted, we rotate it once. (This can happen in either direction, so long as it remains the same direction.) Then, the array becomes:

[7, 10, 2, 3, 4]

This is not sorted, so we rotate again.

[4, 7, 10, 2, 3]

And again:

[3, 4, 7, 10, 2]

And a final time:

[2, 3, 4, 7, 10]

And it's sorted! So the array [10, 2, 3, 4, 7] is driftsortable. Here are all the rotations of the array, for clarity:

[10, 2, 3, 4, 7]
[7, 10, 2, 3, 4]
[4, 7, 10, 2, 3]
[3, 4, 7, 10, 2]
[2, 3, 4, 7, 10]

Consider now the array [5, 3, 9, 2, 6, 7]. Look at its rotations:

[5, 3, 9, 2, 6, 7]
[7, 5, 3, 9, 2, 6]
[6, 7, 5, 3, 9, 2]
[2, 6, 7, 5, 3, 9]
[9, 2, 6, 7, 5, 3]
[3, 9, 2, 6, 7, 5]

None of these arrays are sorted, so the array [5, 3, 9, 2, 6, 7] is not driftsortable.

---

Objective Given a nonempty array/list of integers as input to a program/function, implement driftsort on the input and output it, or output a falsey value (or an empty array/list) if it cannot be driftsorted. The integers are bound to your languages max/min, but this must be at least 255 for the max, and 0 for the min.

You may use built-in sorting methods, but not a built-in which solves the challenge.

This is a code-golf, so the shortest program in bytes.

Test cases

input => output
[1] => [1]
[5, 0, 5] => [0, 5, 5]
[3, 2, 1] => false
[0, 9, 3] => false
[1, 2, 3, 4] => [1, 2, 3, 4]
[4, 1, 2, 3] => [1, 2, 3, 4]
[0, 2, 0, 2] => false
[5, 3, 9, 2, 6, 7] => false
[0, 0, 0, 0, 0, 0, 0] => [0, 0, 0, 0, 0, 0, 0]
[75, 230, 30, 42, 50] => [30, 42, 50, 75, 230]
[255, 255, 200, 200, 203] => [200, 200, 203, 255, 255]

Answer 1

Ruby, 33

->a{a.any?{a.sort==a.rotate!}&&a}

a.any? fires up to once for each element in the array, except it stops (and returns true) as soon as the array has been mutated into a sorted state. If this happens, we return the mutated array. Otherwise we return the false value that any? returns.

Answer 2

Python 2, 51 bytes

lambda l:sorted(l)*(map(cmp,l[-1:]+l,l).count(1)<3)

Doesn't bother rotating. Instead, sorts the list, then sees if the original is drift-sortable by checking if there's at most one decrease among consecutive elements of the cyclified list. The count is <3 because map pads the shorter list with None at the end, adding a fake decrease.

Answer 3

Pyth, 9 bytes

*SQ}SQ.:+

Explanation:

           - Q = eval(input())
         + -    Q+Q
       .:  -   sublists(^)
   }       -  V in ^
    SQ     -   sorted(Q)
*SQ        - ^ * sorted(Q) (return sorted(Q) if ^ True)

Try it here!

Or use a test suite!

Answer 4

Jelly, 6 bytes

ṙỤċṢȧṢ

Try it online! or verify all test cases.

How it works

ṙỤċṢȧṢ  Main link. Argument: A (list)

 Ụ      Grade up; return the indices of A, sorted by their corresponding values.
ṛ       Rotate A by each index, yielding the list of all rotations.
   Ṣ    Yield A, sorted.
  ċ     Count the number of times sorted(A) appears in the rotations.
        This gives 0 if the list isn't driftsortable.
    ȧṢ  Logical AND with sorted(A); replaces a positive count with the sorted list.

Answer 5

Matlab, 61 47 41 bytes

Thanks @Suever for -6 bytes!

@(a)sort(a)+0*min(strfind([a,a],sort(a)))

If strfind([a,a],sort(a)) tries to find the sorted input vector as a 'substring' of the unsorted, that was appended to itself. If true, the input is driftsortable and we get a vector of length 2, if not we get a empty vector. min just transforms this to an number / empty vector. Adding the sorted vector to 0 just displays it, adding it to an empty vector throws an error.

Answer 6

Julia, 71 66 52 bytes

x->(y=sort(x))∈[circshift(x,i)for i=1:endof(x)]&&y

This is an anonymous function that accepts an array and returns an array or a boolean. To call it, assign it to a variable.

For an input array x, we construct the set of all rotations of x and check whether the sorted version x is an element of that list. If it is, we return x sorted, otherwise we return false.

Saved 19 bytes thanks to Dennis!

Answer 7

Pip, 15 + 1 = 17 16 bytes

Ugh, the other golfing languages are blowing this out of the water. However, since I've already written it...

L#gI$<gPBPOgYgy

Takes input as space-separated command-line arguments. Requires -p or another array-formatting flag to display the result legibly rather than concatenated. The false case outputs an empty string, which is visible by virtue of the trailing newline.

                 Implicit: g is array of cmdline args; y is empty string
L#g              Loop len(g) times:
         POg       Pop the first item from g
      gPB          Push it onto the back of g
    $<             Fold on < (true if g is now sorted)
   I        Yg     If true, yank g into y
              y  Autoprint y

Answer 8

JavaScript (ES6), 72 70 65 bytes

a=>a.map(y=>{c+=x>y;x=y},x=a.slice(c=-1))|c<1&&a.sort((a,b)=>a-b)

Returns 0 on failure. Previous 85 83 80-byte version avoided calling sort:

a=>a.map((y,i)=>{x>y&&(c++,j=i);x=y},x=a.slice(c=-1))|c<1&&a.splice(j).concat(a)

Edit: Saved 2 bytes by initialising c to -1 instead of 0. Saved 5 bytes by switching from reduce to map, sigh...

Answer 9

05AB1E, 12 bytes

Code:

DgFÀÐ{Qi,}}0

Uses CP-1252 encoding. Try it online!.

Answer 10

Snowman 1.0.2, 27 bytes

((}#AsO|##aC,as|aLNdE`aR*))

This is a subroutine that takes input from and outputs to the current permavar.

Try it online!

((                       ))  subroutine
  }                          set our active variables b, e, and g:
                              .[a] *[b] .[c]
                              .[d]      *[e]    (* represents an active variable)
                              .[f] *[g] .[h]
   #                         store the input in variable b
    AsO                      sort in-place
       |                     swap b with g; now sorted input is in g
        ##                   store the input again in b and e
          aC                 concat; now the input doubled is in b and e is empty
            ,                swap e/g; now b has 2*input and e has sorted input
             as              split 2*input on sort(input) and store result in g
               |             bring the result up to b (we no longer care about g)
                aLNdE        take length and decrement; now we have 0 in b if the
                               array is not driftsortable and 1 if it is
                     `aR     repeat e (the sorted array) b times:
                               if b is 0 (nondriftsortable), returns [] (falsy)
                               otherwise (b=1), returns sorted array unchanged
                        *    put this back into the permavar

Answer 11

MATL, 13 12 10 9 bytes

SGthyXfa*

The same idea as @flawr's answer where we hijack strfind (Xf) to find the sorted version of the input within the concatenation of two copies of the input.

Try it Online!

Explanation

        % Implicitly get input
S       % Sort the input
Gth     % Explicitly grab the input again and concatenate with itself
y       % Copy the sorted version from the bottom of the stack
Xf      % Look for the sorted version as a subset
a       % Gives a 1 if there were matches and 0 otherwise
*       % Multiply by the sorted array. Yields all zeros for no match and the
        % sorted array when a match was found
        % Implicitly display the stack contents

Answer 12

Julia, 33 bytes

x->sum(diff([x;x]).<0)<3&&sort(x)

Try it online!

How it works

This concatenates the array x with itself and counts the number of pairs that are out of order, i.e. the number of contiguous subarrays [a, b] for which b - a < 0. If c is the number of unordered pairs of x itself and t is 1 if x's last element is larger than its first, sum will return 2c + t.

The array x is driftsortable iff (c, t) = (1, 0) (x has to be rotated to the smaller value of the only unordered pair), (c, t) = (0, 1) (x is sorted) or (c, t) = (0, 0) (x is sorted and all of its elements are equal), which is true iff 2c + t < 3.

Answer 13

Javascript ES6, 48 45 43 chars

x=>~(x+[,x]).indexOf(x.sort((a,b)=>a-b))&&x

Test:

f=x=>~(x+[,x]).indexOf(x.sort((a,b)=>a-b))&&x
;`[1] => [1]
[5, 0, 5] => [0, 5, 5]
[3, 2, 1] => false
[0, 9, 3] => false
[1, 2, 3, 4] => [1, 2, 3, 4]
[4, 1, 2, 3] => [1, 2, 3, 4]
[0, 2, 0, 2] => false
[5, 3, 9, 2, 6, 7] => false
[0, 0, 0, 0, 0, 0, 0] => [0, 0, 0, 0, 0, 0, 0]
[75, 230, 30, 42, 50] => [30, 42, 50, 75, 230]
[255, 255, 200, 200, 203] => [200, 200, 203, 255, 255]`
.split`
`.map(t => t.replace(/^(.*) => (.*)$/, "f($1)+'' == $2")).every(eval)

Answer 14

Brachylog, 39 bytes

l:0re:?{[0:L],!L.|rh$(L,?h-1=:L:1&.}.o.

I really need to add an optional argument to $( - circular permute left to permute more than once... this would have been 13 bytes. This will wait after implementing a stable new transpiler in Prolog.

Explanation

l:0re                                     I = a number between 0 and the length of Input
     :?{[0:L],!L.|rh$(L,?h-1=:L:1&.}      All this mess is simply circular permutating the
                                          input I times
                                    .o.   Unify the Output with that circular permutation
                                          if it is sorted, else try another value of I

Answer 15

Ruby, 47 bytes

Recursive function. Returns nil if the input array cannot be driftsorted.

f=->a,i=0{a.sort==a ?a:a[i+=1]?f[a.rotate,i]:p}

Answer 16

CJam, 17 13 bytes

Thanks to Dennis for saving 4 bytes.

{_$\_+1$#)g*}

An unnamed block (function) which takes and returns a list.

Test suite.

Explanation

This essentially uses xnor's observation that the sorted list appears in twice the original list if its drift sortable:

_$   e# Duplicate input and sort.
\_+  e# Get other copy and append to itself.
1$   e# Copy sorted list.
#    e# Find first position of sorted list in twice the original,
     e# of -1 if it's not found.
)g   e# Increment and take signum to map to 0 or 1.
*    e# Repeat sorted array that many times to turn it into an empty
     e# array if the input was not drift sortable.

Answer 17

C++ 14, 242 chars

#include<iostream>
#include<vector>
#include<algorithm>
#define b v.begin()
using namespace std;int main(){vector<int>v;int x,n=0;for(;cin>>x;++n)v.push_back(x);for(x=n;x--;rotate(b,b+1,b+n))if(is_sorted(b,b+n)){for(x:v)cout<<x<<' ';return 0;}}

If I can't leave output empty, 252 chars http://ideone.com/HAzJ5V

#include<iostream>
#include<vector>
#include<algorithm>
#define b v.begin()
using namespace std;int main(){vector<int>v;int x,n=0;for(;cin>>x;++n)v.push_back(x);for(x=n;x--;rotate(b,b+1,b+n))if(is_sorted(b,b+n)){for(x:v)cout<<x<<' ';return 0;}cout<<'-';}

Ungolfed version http://ideone.com/Dsbs8W

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

#define b v.begin()

int main()
{
  vector <int> v;
  int x, n=0;

  for(;cin>>x;++n)
    v.push_back(x);

  for(x=n;x--;rotate(b,b+1,b+n))
    if(is_sorted(b,b+n))
    {
      for(x:v) cout<<x<<' ';
      return 0;
    }

  cout << '-';
}

PS: Based on @MichelfrancisBustillos's idea.

Answer 18

Java 7, 207 bytes

int[]D(int[]i){int x,z;z=x=-1;int[]d=new int[i.length];while(++x<i.length)if(i[x]>i[(x+1)%i.length])if(z<0)z=(x+1)%i.length;else return null;if(z<0)z=0;x=-1;while(++x<d.length)d[x]=i[z++%i.length];return d;}

Detailed try here

// driftsort in ascending-order
int[] D(int[]i)
{
    int x = -1,z = -1;
    int[] d = new int[i.length];

    while ((++x) < i.length)
    {
        if (i[x] > i[(x+1)%i.length])
        {
            if(z < 0) z = (x+1)%i.length;
            else return null; // not driftsortable
        }
    }

    if(z < 0) z = 0;
    x = -1;
    while ((++x) < d.length)
    {
        d[x] = i[(z++)%i.length];
    }

    return d;
}

Answer 19

Java 175

prints out the output as space separated values, or prints f for a falsey value.

void d(int[]a){String s;for(int v,w,x=-1,y,z=a.length;++x<z;){v=a[x];s=""+v;for(y=0;++y<z;v=w){w=a[(x+y)%z];if(v>w){s="f";break;}s+=" "+w;}if(y==z)break;}System.out.print(s);}

goes through all the combinations of the array of integers until it finds the valid sequence or runs out of combinations. the array isn't modified, but instead the driftsorted sequence is stored as a space delimited string.

a bit more readable:

void driftsort(int[]array){
    String str;
    for(int previous,current,x=-1,y,len=array.length;++x<len;){
        previous=array[x];
        s=""+previous;
        for(y=0;++y<len;previous=current){
            current=array[(y+x)%len];
            if(previous>current){
                str="false";
                break;
            }
            str+=" "+current;
        }
        if(y==len)break;
    }
    System.out.print(str);
}

try it online

Answer 20

C, 105 bytes

i,s;main(c,v)char**v;{c--;while(i++<c)if(atoi(v[i])>atoi(v[i%c+1]))c*=!s,s=i;while(--i)puts(v[s++%c+1]);}

This accepts the input integers as separate command-line arguments and prints the output list as one integer per line.

If the list isn't driftsortable, the program exits prematurely due to a floating point exception, so its empty output represents an empty list.

Verification

$ gcc -o driftsort driftsort.c 2>&-
$ ./driftsort 1 | cat
1
$ ./driftsort 5 0 5 | cat
0
5
5
$ ./driftsort 3 2 1 | cat
$ ./driftsort 0 9 3 | cat
$ ./driftsort 1 2 3 4 | cat
1
2
3
4
$ ./driftsort 4 1 2 3 | cat
1
2
3
4
$ ./driftsort 0 2 0 2 | cat
$ ./driftsort 5 3 9 2 6 7 | cat
$ ./driftsort 0 0 0 0 0 0 0 | cat
0
0
0
0
0
0
0
$ ./driftsort 75 230 30 42 50 | cat
30
42
50
75
230
$ ./driftsort 255 255 200 200 203 | cat
200
200
203
255
255

Answer 21

Ruby, 28

->a{(a*2*?,)[a.sort!*?,]&&a}

Returns either the sorted array, or nil (which is a falsy value) if the input is not drift-sortable.

Answer 22

Python, 53 bytes

s,N=sorted,lambda x:s(x)*(str(s(x))[1:-1]in str(x+x))

If you want to test this head over to https://www.repl.it/languages/python3 and copy paste this:

s,N=sorted,lambda x:s(x)*(str(s(x))[1:-1]in str(x+x))
print(N([1,2,3,4,5,0]))

How it works:

• s is a variable storing the sorted python function which sorts lists
• N is the main function
• The input list sorted: s(x) is multiplied by whether or not the list is driftsortable str(s(x))[1:-1]in str(x+x) (thanks to @xnor)
  • This works because [1,2,3,4]*false results in an empty list []
  • and [1,2,3,4]*true results in [1,2,3,4]

Answer 23

Python, 83 bytes

def f(l):g=sorted(l);return g if any(l[x:]+l[:x]==g for x in range(len(l)))else 1>2

This got put to shame by the other python answers, but I might as well post it anyway. I really dislike the

range(len(l)))

part. Is there a faster way to iterate through the list?

Answer 24

MATLAB/Octave, 118 bytes

function r(a)
i=0
while (~issorted(a) && i<length(a))
    a=a([2:end 1]),i=i+1
end
if issorted(a)
    a
else
    0
end

Answer 25

PowerShell v2+, 87 80 bytes

param($a)0..($a.length-1)|%{if($a[$_-1]-gt$a[$_]){$c--}};(0,($a|sort))[++$c-ge0]

Steps through the input list $a, checking each pairwise element (including the last and first) to see if there is more than one decreasing pair. If the particular pair is decreasing, we decrement $c. Outputs either the sorted list, or single element 0, based on the value of $c at the end. If more than one "bad" pair is present, then ++$c will still be negative, otherwise it will be at least 0, so the second element of the pseudo-ternary is chosen ($a|sort).

I see xnor did something similar, but I came up with this independently.

Answer 26

Factor, 47 bytes

[ dup dup append [ natural-sort ] dip subseq? ]

join the sequence onto itself, then check if the sorted rendition of the original is a subsequence.

Answer 27

C++, 313 359 370 bytes

Huge shoutout to @Qwertiy for getting this working and teaching me some great golfing methods!

Golfed:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){vector<int> v;int x,c=0,s=0,y;while(cin>>x)v.push_back(x);do if(rotate(v.begin(),v.begin()+1,v.end()),c++,is_sorted(v.begin(),v.end()))s=1;while(!s&c<=v.size());if(s)for(y=0;y<v.size();y++)cout<<v[y]<<" ";else cout<<"False";}

Ungolfed:

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
  vector <int> v;
  int x, c=0, s=0, y;

  while(cin>>x)
    v.push_back(x);

  do 
    if (
      rotate(v.begin(),v.begin()+1,v.end()),
      c++,
      is_sorted(v.begin(),v.end())
    ) s = 1;
  while(!s & c <= v.size());

  if (s)
    for(y=0; y<v.size(); y++)
      cout<<v[y]<<" ";
  else
    cout<<"False";
}

Answer 28

Mathcad, TBD

In Mathcad, 0 (scalar) == false.

(Equivalent) byte count is TBD until counting method agreed. Approx 52 bytes using a byte = operator / symbol keyboard equivalence.

Answer 29

Mathematica 55 50 61 58 bytes

With 3 bytes saved thanks to Martin Büttner.

My earlier attempts did not pass all of the test case. I needed to add Union to avoid repetitions in list that were input in order.

Join@Union@Cases[NestList[RotateRight,#,Length@#],Sort@#]&

Tests

Join@Union@Cases[NestList[RotateRight,#,Length@#],Sort@#]&/@
{{1},{5,0,5},{3,2,1},{0,9,3},{1,2,3,4},{4,1,2,3},{0,2,0,2},{5,3,9,2,6,7},
{0,0,0,0,0,0,0},{75,230,30,42,50},{255,255,200,200,203}}

{{1}, {0, 5, 5}, {}, {}, {1, 2, 3, 4}, {1, 2, 3, 4}, {}, {}, {0, 0, 0, 0, 0, 0, 0}, {30, 42, 50, 75, 230}, {200, 200, 203, 255, 255}}

---

Explanation

Right rotate the input list from 1 to n times, where n is the length of the input list. If the sorted input list is among the output rotated lists, return it; otherwise return an empty list.

Answer 30

PHP, 98 bytes

Outputs a 1 if driftsortable, else nothing

$a=$argv[1];$b=$a;sort($a);foreach($a as $v){echo($a===$b?1:'');array_unshift($b, array_pop($b));}