25
\$\begingroup\$

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 , 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]
\$\endgroup\$
  • 5
    \$\begingroup\$ An easy way to check if a list is driftsortable is if sorted(l) is a contiguous sublist of l+l. \$\endgroup\$ – xnor Apr 21 '16 at 18:52
  • \$\begingroup\$ Just to clarify: If our language supports negative integers, they can occur in the input, yes? \$\endgroup\$ – Dennis Apr 21 '16 at 20:59
  • \$\begingroup\$ @Dennis that is correct. \$\endgroup\$ – Conor O'Brien Apr 21 '16 at 21:00
  • \$\begingroup\$ Shouldn't this be called shiftsort? \$\endgroup\$ – Filip Haglund Apr 24 '16 at 15:40
  • \$\begingroup\$ @FilipHaglund I thought about calling it that, but it may cause confusion with the shift operation that removes the first element of an array. \$\endgroup\$ – Conor O'Brien Apr 24 '16 at 15:56

31 Answers 31

9
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ Ahem, 19 bytes of UTF8. \$\endgroup\$ – rsaxvc Apr 21 '16 at 21:37
  • 11
    \$\begingroup\$ Jelly has a custom code page that encodes each of the 256 characters it understands as single bytes. (It's 16 bytes with UTF-8 btw.) \$\endgroup\$ – Dennis Apr 21 '16 at 21:39
  • 3
    \$\begingroup\$ @Dennis: you should copy/paste this in all your Jelly submissions to prevent us (ie, ones who didn't knew this before) from making the same comments ? ;) \$\endgroup\$ – Olivier Dulac Apr 22 '16 at 9:56
18
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ This is super clever, particularly the in-place rotate. Nice work! \$\endgroup\$ – Alex A. Apr 21 '16 at 18:26
  • \$\begingroup\$ Alas, my own Ruby answer has been bested. +1 \$\endgroup\$ – Value Ink Apr 21 '16 at 18:53
  • 3
    \$\begingroup\$ Ah yes, the old "sort it until you can tell if it's able to be sorted" technique. \$\endgroup\$ – corsiKa Apr 22 '16 at 15:13
14
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ [1, 3, 2, 4] only has one decrease among consecutive elements but it's not drift-sortable. \$\endgroup\$ – Neil Apr 21 '16 at 18:23
  • 1
    \$\begingroup\$ @Neil Oh shoot. \$\endgroup\$ – xnor Apr 21 '16 at 18:24
  • \$\begingroup\$ @Neil I think this fixes it. Could you please take a look? \$\endgroup\$ – xnor Apr 21 '16 at 18:35
  • 10
    \$\begingroup\$ Aw we <3 you too \$\endgroup\$ – Fund Monica's Lawsuit Apr 21 '16 at 19:25
  • \$\begingroup\$ I can't say I'm expert at Python but that seems reasonable assuming the <3 is to avoid having to precisely rotate the list. \$\endgroup\$ – Neil Apr 21 '16 at 20:11
10
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ I think you mean substrings (sublists) for .:. Combinations would include non-contiguous elements. \$\endgroup\$ – xnor Apr 21 '16 at 19:24
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Does the substring check handle [2, 3] not being a sublist of [12, 34]? \$\endgroup\$ – xnor Apr 21 '16 at 19:09
  • \$\begingroup\$ Yes, each integer array can also interpreted as string, where each number is treated as one character, no matter how big the number. \$\endgroup\$ – flawr Apr 21 '16 at 19:34
  • \$\begingroup\$ @flawr My interpretation is that strfind can work directly with numbers, not only with chars (even though that's not documented). If the numbers were being interpreted as chars they would be limited to 65535 (try for example +char(1e5)) \$\endgroup\$ – Luis Mendo Apr 22 '16 at 0:00
  • \$\begingroup\$ @LuisMendo You are right, it even works with floating point numbers. Note that numers above 65535 will just be displayed as a space when considered as part of a string. \$\endgroup\$ – flawr Apr 22 '16 at 6:24
5
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ See the edit ;) \$\endgroup\$ – Conor O'Brien Apr 21 '16 at 18:52
  • \$\begingroup\$ Call to sort for numbers is incorrect. Check on the sample [10, 2, 3, 4, 7]. \$\endgroup\$ – Qwertiy Apr 21 '16 at 20:28
  • \$\begingroup\$ This code also failes 3 tests: [1], [0, 0, 0, 0, 0, 0, 0] and [75, 230, 30, 42, 50]. \$\endgroup\$ – Qwertiy Apr 21 '16 at 20:43
  • \$\begingroup\$ @Qwertiy Sorry about the sort oversight, which caused the third test failure. The other two test failures were caused by me over-golfing; I've reverted to the previous version. \$\endgroup\$ – Neil Apr 21 '16 at 22:48
3
\$\begingroup\$

05AB1E, 12 bytes

Code:

DgFÀÐ{Qi,}}0

Uses CP-1252 encoding. Try it online!.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Can't you remove g? Or replace ng by a \$\endgroup\$ – Luis Mendo Apr 21 '16 at 21:02
  • \$\begingroup\$ @LuisMendo Can't replace with just an n because n could be > 1. a definitely works though. I figured there was a better way. Thanks! \$\endgroup\$ – Suever Apr 21 '16 at 21:03
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ I think you can save two bytes by using (x+[,x]) and a further byte by using ~ instead of 1+ in your condition. \$\endgroup\$ – Neil Apr 21 '16 at 22:57
  • \$\begingroup\$ @user6188402, yep, thank you. \$\endgroup\$ – Qwertiy May 9 '16 at 20:08
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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}
\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ @Dennis oh, looks like we came up with that independently. Thanks though. :) \$\endgroup\$ – Martin Ender Apr 21 '16 at 20:30
2
\$\begingroup\$

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.

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

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;
}
\$\endgroup\$
2
\$\begingroup\$

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

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

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
\$\endgroup\$
2
\$\begingroup\$

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.

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

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]
\$\endgroup\$
  • 1
    \$\begingroup\$ In Python 2, you can shorten this to lambda x,s=sorted:(`s(x)`[1:-1]in`x+x`)*s(x) for 44 bytes. \$\endgroup\$ – Dennis May 10 '16 at 19:18
1
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ It's not much, but l.append(l.pop(0))or g==l for _ in l saves a byte over the range-len approach. Using a lambda would save 14 additional bytes. \$\endgroup\$ – Dennis Apr 22 '16 at 7:06
1
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ I think you can already save some bytes by writing everything on one line and using input(''). Also avoid unnecessary spaces and parenthesis! And you can again shed some bytes by first defining f=@issorted. \$\endgroup\$ – flawr Apr 21 '16 at 19:41
1
\$\begingroup\$

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.

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

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ This sounds like a philosophical haiku: dup dup append \\ natural sort \\ dip subseq? Even fits the 4-4-3 pattern :) \$\endgroup\$ – Akiiino Apr 22 '16 at 5:30
  • \$\begingroup\$ @Akiiino :D point-free languages are so poetic. \$\endgroup\$ – cat Apr 22 '16 at 8:04
1
\$\begingroup\$

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";
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Golfing isn't just removing spaces. using namespace std; is 20 chars when std:: 6 times is 30. bool s = False; - why not =0? You can drop return 0;. Why are brackets here !s&&(c<=v.size())? Figure braces and no commas... \$\endgroup\$ – Qwertiy Apr 21 '16 at 21:05
  • \$\begingroup\$ Wow, thanks! A Lot of stuff (like std:: and return 0;) has become habit from programming classes. I really need to start checking my programs better. \$\endgroup\$ – Michelfrancis Bustillos Apr 21 '16 at 21:10
  • 1
    \$\begingroup\$ Also there is a set of bugs. Why do you read until zero and put that zero into data? Why do you output to size inclusive? Why True and False instead of true and false. ideone.com/kVTI25 - your version, ideone.com/y8s44A - fixed and prepared for golfing version. \$\endgroup\$ – Qwertiy Apr 21 '16 at 21:26
  • \$\begingroup\$ Thank you again! Caping True and False is from Python. I didn't even know you could write ifs like that! \$\endgroup\$ – Michelfrancis Bustillos Apr 21 '16 at 21:34
  • 1
    \$\begingroup\$ And much more shortened: ideone.com/Dsbs8W and golfed ideone.com/HAzJ5V (<s>255</s> 252 chars). Used C++14 for foreach loop. \$\endgroup\$ – Qwertiy Apr 21 '16 at 21:45
1
\$\begingroup\$

Mathcad, TBD

enter image description here

In Mathcad, 0 (scalar) == false.

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

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

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.

\$\endgroup\$
  • \$\begingroup\$ @MartinBüttner, Your suggestion failed in some of the test cases, specifically, #s 3,4,7,8. \$\endgroup\$ – DavidC Apr 22 '16 at 15:33
  • \$\begingroup\$ @DavidC Ah, damn, you're right, I mixed up the behaviour of @@ and /@ on empty lists. Join@@ should still be shorter than Flatten@ though. \$\endgroup\$ – Martin Ender Apr 22 '16 at 16:35
1
\$\begingroup\$

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));}
\$\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.