28
\$\begingroup\$

Is solving Sudoku too hard? Even the brute force version? Here's a coding exercise that's a little easier. I hope. :-P

Write the shortest function to implement bogosort. In specific, your function should:

  • Take an array (or your language's equivalent) as input
  • Check if its elements are in sorted order; if so, return the array
  • If not, shuffle the elements, and start again

The shortest entry wins. In the case of a tie, a function that supports a custom comparator (and/or pseudorandom number generator) is favoured. Any remaining ties are resolved by favouring the earlier submission.


Clarifications: You can use any element type you want, as long as there's some way to order them, of course. Also, the shuffling has to be uniform; none of this "I'll just quicksort it and call it shuffled" business. :-)

\$\endgroup\$
12
  • \$\begingroup\$ What are the element types? int or strings? \$\endgroup\$ – Alexandru Feb 2 '11 at 21:39
  • \$\begingroup\$ @Alexandru: Either is fine. You choose. \$\endgroup\$ – Chris Jester-Young Feb 2 '11 at 21:40
  • \$\begingroup\$ Adding a custom comparator will increase the code length so a winning entry will not have a custom comparator. I think breaking the tie doesn't make sense. \$\endgroup\$ – Alexandru Feb 2 '11 at 21:57
  • 1
    \$\begingroup\$ It's possible that this algorithm can fail when using pseudo random generator. eg when the length of the list exceeds say 2000, there are 2000! states for the list which may exceed the number of interal states of the prng. \$\endgroup\$ – gnibbler Feb 2 '11 at 22:38
  • 2
    \$\begingroup\$ Yes, the relevant quote from wikipedia "However, if a pseudorandom number generator is used in place of a random source, it may never terminate, since these exhibit long-term cyclic behavior." \$\endgroup\$ – gnibbler Feb 2 '11 at 23:30

44 Answers 44

1
2
0
\$\begingroup\$

C (203 chars, no input loop: only the func)

#include <stdio.h>
#define P (int*a,int n){
#define F for(i=0;i<n;i++){
int i,j,v;s P F if(a[i]>a[i+1])return 0;}return 1;}void h P F v=a[i];a[i]=a[j=rand()%n];a[j]=v;}}void b P while(!s(a,n-1))h(a,n);}

This is the same as the following, where we also read the array from stdin and write out the sorted array. Since the Q asked for the function and not a whole program...

C (296 chars)

#include <stdio.h>
#define P (int*a,int n){
#define F for(i=0;i<n;i++){
int i,j,n,v,x[999];s P F if(a[i]>a[i+1])return 0;}return 1;}void h P F j=rand()%n;v=a[i];a[i]=a[j];a[j]=v;}}void b P while(!s(a,n-1))h(a,n);}main(){while(scanf("%d",&v)==1)x[n++]=v;if(!s(x,n))b(x,n);F printf("%d\n",x[i]);}}

Compiling may give warning (implicit declarations). Hardencoded array size limit of 999 elements. Fragile.

if there's no need to pre-check if the array is sorted, it can be done in 284.

C (251 chars, was 284)

#include <stdio.h>
#define F for(i=0;i<n;i++){
int i,j,n,v,a[999];s(int n){F if(a[i]>a[i+1])return 0;}return 1;}void h(){F v=a[i];a[i]=a[j=rand()%n];a[j]=v;}}void b(){while(!s(n-1))h();}main(){while(scanf("%d",&a[n++])>0);b();F printf("%d\n",a[i]);}}

(using globals instead of function args).

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

R, 82 characters

Since I wrote it for this question I thought I'll add it there as well. Slightly modified here to accomodate question criteria.

b=function(a){while(any(apply(embed(a,2),1,function(x)x[1]<x[2]))){a=sample(a)};a}
\$\endgroup\$
0
\$\begingroup\$

JavaScript (using Array.sort()): 91

Utilising Array.sort():

function s(a){while((a=a.sort(function(){return 2-Math.random()*4|0}))!=a.sort());return a}

JavaScript (avoiding Array.sort()): 186

Not using the built-in .sort() method (randomising method stolen from here):

function s(a){while(function(b,c,d){for(;c<b.length-1;){d&=b[c]<=b[++c]}return!d}(function(t,n,i){i=a.length;while(i--){n=Math.random()*i|0,t=a[i],a[i]=a[n],a[n]=t}}()||a,0,1));return a}
\$\endgroup\$
0
\$\begingroup\$

Python, 71 characters

from random import*
def b(l):
 while l!=sorted(l):shuffle(l)
 return(l)

Not the shortest one, but it works.

Ungolfed:

from random import *
def bogosort(list):
    while list != sorted(list):
        shuffle(list)

    return(list)

Usage:

Input: b([1, 7, 3, 9, 2])

Output: [1, 2, 3, 7, 9]

\$\endgroup\$
2
  • \$\begingroup\$ Return isn't a function, you don't need parenthesis... \$\endgroup\$ – FlipTack Feb 12 '17 at 21:25
  • \$\begingroup\$ you can use l<sorted(l) instead of != \$\endgroup\$ – gnibbler Feb 12 '17 at 23:10
0
\$\begingroup\$

Java - 207 bytes

boolean sorted(Integer[] n,int i){while(i-->1)if(n[i]<n[i-1])return false;return true;}void bogo(Integer[] n){List<Integer>l=Arrays.asList(n);while(!sorted(n,n.length)){Collections.shuffle(l);l.toArray(n);}}

Ungolfed try online

boolean sorted(Integer[] n,int i)
{
    while(i --> 1) // i..1
        if(n[i] < n[i-1]) // ascending order
            return false;

    return true;
}

void bogo(Integer[] n)
{
    List<Integer>l = Arrays.asList(n);

    while(!sorted(n, n.length))
    {
        Collections.shuffle(l); // shuffle
        l.toArray(n); // re-fill the array
    }
}
\$\endgroup\$
0
\$\begingroup\$

Java, 147 bytes

import java.util.*;void A(List<Long>b){for(;;){for(int B=1;B++<b.toArray().length;){if(b.get(B-1)>b.get(B))break;return;}Collections.shuffle(b);}}

This sorts in ascending order, To make it sort in descending order, simply replace b.get(B-1)>b.get(B) with b.get(B-1)<b.get(B).

Ungolfed:

import java.util.*;

void A(List<Long> b) {
    for (;;) {
        for (int B = 1; B++ < b.toArray().length;) {
            if (b.get(B - 1) > b.get(B))
                break;
            return;
        }
        Collections.shuffle(b);
    }
}

Making this function compilable costs 9 bytes, resulting in a 156-byte program:

import java.util.*;class a{void A(List<Long>b){for(;;){for(int B=1;B++<b.toArray().length;){if(b.get(B-1)>b.get(B))break;return;}Collections.shuffle(b);}}}

Java (lambda expression), 111 bytes

(b,B)->{for(;;){for(B=1;B++<b.toArray().length;){if(b.get(B-1)>b.get(B))break;return;}Collections.shuffle(b);}}

This is a java.util.function.BiConsumer<java.util.List<Long>, Integer>.

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

Pushy, 8 bytes

Non competing as the language postdates the challenge.

[oSog?_i

Try it online!

Alternatively, run this version to see it print each shuffle as it goes along! The code works like this:

[          \ Infinitely:
 oS        \   Shuffle the stack
   og?     \   If it's sorted (ascendingly):
      _i   \     Print and terminate

If you want to sort descendingly, just replace og with oG.

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

C, 111 bytes

This answer takes bogus sort one step further: It doesn't shuffle the entire array before rechecking, it just makes a singe random swap before rechecking. For extra measure, that single random swap always swaps with the first entry, so the general random swap actually takes two iterations. Inefficient, yes, but hey, it's bogus sort, and it saves one call to rand()!

#include<stdlib.h>
t,r;b(int*d,int s){r=rand()%s;t=*d;*d=d[r];d[r]=t;for(r=s-1;r--;)d[r]>d[r+1]&&(b(d,s),r=0);}

Note that since the mixing loop is implemented via recursion, this will crash for larger input arrays (= more than eight elements on my machine) due to stack exhaustion.

Ungolfed:

void b(int*data,int size){
    //First, swap random element with the first element.
    int randomIndex = rand()%size;
    int temp = *data;
    *data = data[randomIndex];
    data[randomIndex] = temp;

    //Check if array is sorted
    for(int i = size-1;i--;) {
        if(data[i]>data[i+1]) {
            //array is not sorted, start over
            b(data,size);
            i = 0;  //don't resume loop on return
        }
    }
}

Test with

int main(){
    int data[] = {8, 7, 6, 5, 4, 3, 2, 1};
    int size = sizeof(data)/sizeof(*data);
    for(int i = 0; i < size; i++) printf("%d ", data[i]);
    printf("\n");

    b(data, size);

    for(i = 0; i < size; i++) printf("%d ", data[i]);
    printf("\n");
}
\$\endgroup\$
0
\$\begingroup\$

SmileBASIC, 104 81 bytes

DEF B A@D
SWAP A[0],A[RND(LEN(A))]FOR I=0TO LEN(A)-2IF A[I]<A[I+1]GOTO@D
NEXT
END
\$\endgroup\$
0
\$\begingroup\$

05AB1E, 6 bytes

œ.ΔD{Q

Try it online!

Explanation

œ       Create list with all permutations
 .Δ     Return the first element that satisfies the followng:
   D{Q  Check if element is sorted.
\$\endgroup\$
0
\$\begingroup\$

Husk, 8 bytes

ΩS=O§!←P

Try it online!

Husk does not have random numbers, so this uses the array itself to get a permutation. I genuinely don't know whether this would complete.

Explanation

ΩS=O§!←P
Ω        Until
 S=O     the argument is ordered
       P take it's permutations
      ←  take its first element
    §!   return that permutation
\$\endgroup\$
1
  • \$\begingroup\$ Given that it looks like the §!←P part just returns the list as is (as the permutations returned always has the original list as the first element), this will only finish if the list is inputted sorted \$\endgroup\$ – caird coinheringaahing Oct 30 '20 at 13:24
0
\$\begingroup\$

CJam, 14 bytes

{{__$=!}{mr}w}

Try it online!

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

Pyth, 13 11 bytes

WnSQKO.pQ;K

Previous Solution

L?n.SbSbybb
y

Try it online!

WnSQKO.pQ;K
      .pQ    Generate a list of all permutations of input
    KO.pQ    K = random permutation in the list
WnSQK    ;   While(sorted(input) != K): do nothing
          K  print K

Previous Solution:
Compiled to python:

assign('Q',eval_input())
@memoized
def subsets(b):
 return (subsets(b) if ne(shuffle(b),Psorted(b)) else b)
imp_print(subsets(Q))

Basically:
Shuffle the list, if it isn't equal to the sorted list:
recursively call.
Else:
Return it

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

05AB1E, 8 bytes

[Ð{Q#.r

Try it online!

Explanation:

[        # Infinite Loop start
 Ð       # Push input
  {Q#    # If input is sorted, break loop
     .r  # Otherwise, shuffle
\$\endgroup\$
1
2

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.