title: Sort a list of numbers

text:
# Question
Title: Sort a list of numbers
About Code-Bowling:

> In golf, you try to get the lowest score (smallest application, most elegant, etc). In Bowling, you try to get the highest score. So if you follow, the goal of a Code-Bowling challenge is to make the biggest, most bastardized, hardest to maintain piece of code that still meets the requirements of the challenge. However, there's no point in making source longer just for the sake of it. It needs to seem like that added length was from design and not just padding.

**The Challenge:**

Create a program that sorts a list of numbers in ascending order.

**Example:**

*Input:* 1, 4, 7, 2, 5

*Output:* 1, 2, 4, 5, 7

*Code:* Obviously this wouldn't be a good answer, since there aren't many WTFs in there

```
function doSort(array $input) {
    sort($input);
    return $input;
}

```

**Rules:**

There are no real rules. As long as the program functions, have at it!

**Remember:** This is code-bowling, not golf. The objective is to make the worst, most bastardized code that you can! Bonus points for code that looks good, but is actually deceptively evil...

# Answer
Sorting by user input. What can be worse?

```
function sort(array) {
    newArray = new Array
    notSorted = true;
    while (notSorted) {
        sortfail = false;
        i = -1
        for (;;) {
            if ((++i + 1) == array.length) break;
            if (confirm("is " + array[i] + " less than " + array[i + 1])) {
                newArray[i] = array[i]
                newArray[i + 1] = array[i + 1]
            } else {
                newArray[i] = array[i + 1]
                newArray[i + 1] = array[i]
                array[i] = newArray[i]
                array[i + 1] = newArray[i + 1]
                sortfail = true
            }
        }
        array = newArray;
        if (!sortfail) notSorted = false
    }
    return array
}

console.log(sort([2,1,3]))

```

See live example
> 22 votes

# Answer
```
class Array
  def sort
    self.permutation.min
  end
end

```

Ah, the elegance of Ruby... self.permutation results in an enumerator. No harm done, yet. The innocent looking .min however sucks this enumerator into an array. This array's size explodes when the number of elements rises. Not to mention this ruines a fine pre-existing sort.
> 17 votes

# Answer
## Bogosort!

```
import random

def is_sorted(seq):
    for x, y in zip(seq[:-1], seq[1:]):
        if x > y:
            return False
    return True

def sort(seq):
    while not is_sorted(seq):
        random.shuffle(seq)

```
> 16 votes

# Answer
# Perl Bubble Sort

```
push(@m,'0');$a=<>;push(@m,$a);
$a=pop@m;push(@c,$a);
push(@m,'p');$a=pop@m;$b=pop@m;$hash{$a}=$b;
$a=pop@c;push(@c,$a);for(1..$a){$a=<>;push(@m,$a);
push(@m,'p');$a=pop@m;push(@m,$hash{$a});
$a=pop@m;$b=pop@m;$hash{$a}=$b;
push(@m,'p');$a=pop@m;push(@m,$hash{$a});
push(@m,'1');$a=pop@m;$b=pop@m;push(@m,$b+$a);
push(@m,'p');$a=pop@m;$b=pop@m;$hash{$a}=$b;
}$a=pop@c;push(@m,$a);
push(@m,'2');$a=pop@m;$b=pop@m;for(1..$a){push(@m,$b);};
$a=pop@m;$b=pop@m;push(@m,$b*$a);
$a=pop@m;push(@c,$a);
$a=pop@c;push(@c,$a);for(1..$a){push(@m,'1');$a=pop@m;push(@m,-$a);
push(@m,'p');$a=pop@m;$b=pop@m;$hash{$a}=$b;
$a=pop@c;push(@c,$a);for(1..$a){push(@m,'p');$a=pop@m;push(@m,$hash{$a});
push(@m,'1');$a=pop@m;$b=pop@m;push(@m,$b+$a);
push(@m,'p');$a=pop@m;$b=pop@m;$hash{$a}=$b;
push(@m,'p');$a=pop@m;push(@m,$hash{$a});
$a=pop@m;push(@m,$hash{$a});
push(@m,'p');$a=pop@m;push(@m,$hash{$a});
push(@m,'1');$a=pop@m;push(@m,-$a);
$a=pop@m;$b=pop@m;push(@m,$b+$a);
$a=pop@m;push(@m,$hash{$a});
$a=pop@m;$b=pop@m;if($b < $a){push(@c,1)}else{push(@c,0)};
$a=pop@c;push(@c,$a);for(1..$a){push(@m,'p');$a=pop@m;push(@m,$hash{$a});
$a=pop@m;push(@m,$hash{$a});
push(@m,'t');$a=pop@m;$b=pop@m;$hash{$a}=$b;
push(@m,'p');$a=pop@m;push(@m,$hash{$a});
push(@m,'1');$a=pop@m;push(@m,-$a);
$a=pop@m;$b=pop@m;push(@m,$b+$a);
$a=pop@m;push(@m,$hash{$a});
push(@m,'p');$a=pop@m;push(@m,$hash{$a});
$a=pop@m;$b=pop@m;$hash{$a}=$b;
push(@m,'t');$a=pop@m;push(@m,$hash{$a});
push(@m,'p');$a=pop@m;push(@m,$hash{$a});
push(@m,'1');$a=pop@m;push(@m,-$a);
$a=pop@m;$b=pop@m;push(@m,$b+$a);
$a=pop@m;$b=pop@m;$hash{$a}=$b;
}$a=pop@c;push(@m,$a);
$a=pop@m;
}}push(@m,'0');push(@m,'p');$a=pop@m;$b=pop@m;$hash{$a}=$b;
$a=pop@c;push(@c,$a);for(1..$a){push(@m,'p');$a=pop@m;push(@m,$hash{$a});
$a=pop@m;push(@m,$hash{$a});
$a=pop@m;print$a;
push(@m,'p');$a=pop@m;push(@m,$hash{$a});
push(@m,'1');$a=pop@m;$b=pop@m;push(@m,$b+$a);
push(@m,'p');$a=pop@m;$b=pop@m;$hash{$a}=$b;
}

```

I was going for the "every single line looks like the same piece of line noise" look. The first line of input (on STDIN) tells the program how many numbers there are, while the next N number of lines contain one number that needs to be sorted.
> 14 votes

# Answer
# Generic, multithreaded bogosort in Java

### 46 seconds to sort 4 numbers

I thought it would be elegant with support for generics. Also, multithreading is always nice, so I use that instead of randomization: This program generates one thread for each number to be sorted. Each thread tries to insert its element into an array object, and when all elements have been inserted, the program will check if the array is sorted. If not, try again. Off course this insertion needs to be synchronized.

### ElementInserter

This will be the class that we use for the threads. This class holds one element and tries to insert it into its `sortedArray`:

```
class ElementInserter<E extends Comparable<? super E>> implements Runnable {
    E element;
    SortedArray<? super E> target;

    ElementInserter(E e, SortedArray<? super E> a) {
        element = e;
        target = a;
    }

    @Override
    public void run() {
        target.insert(element);
    }
}

```

### sortedArray

Sports a straight-forward insert method. When last element has been inserted, it checks if the array is sorted.

```
class SortedArray<E extends Comparable<? super E>> {
    boolean sorted; int i = 0; E[] a;

    SortedArray(E[] e) { a = e; }

    synchronized public void insert(E e) {
        while (!sorted) {
            a[i++] = e;

            if (i == a.length) {
                sorted = true;

                for (int j = 1; j < i; ++j)
                    if (a[j-1].compareTo(a[j]) > 0) {
                        sorted = false;
                        i = 0;
                        notifyAll();
                    }

                if (sorted) {
                    for (int j = 0; j < a.length; ++j) System.out.print(a[j]+" ");
                    System.out.println();
                    notifyAll(); // allow all threads to terminate
                }

            } else
                try { wait(); }
                catch(InterruptedException x) { }
        }
    }
}

```

### Main method

Parses command line arguments as Integers, creates a new array and a new thread for each Integer:

```
    public static void main (String[] args) {
        Integer[] i = new Integer[args.length];
        SortedArray<Integer> c = new SortedArray<Integer>(i);

        for (String s : args)
            new Thread(new ElementInserter<Integer>(Integer.parseInt(s), c)).start();
    }

```

### Test run

Execution time will depend on the original order of the elements and your scheduler implementation. This is on a dual-core 2.9 GHz Intel i7 MacBook Pro:

```
$ time java Main 3 1 2 4
1 2 3 4

real    0m46.307s
user    0m14.629s
sys     0m26.207s

```
> 13 votes

# Answer
## JavaScript (with animation!). 8172 chars. Few hours for 6 numbers.

We like lottery, right? Similar to Bogosort by dan04, but using physics and **animation**...

```
(function(){var e={},v=!1,G=/abc/.test(function(){abc})?/\b_super\b/:/.*/,H=function(c,a,b){return function(){var l=this._super,s;this._super=b[c];try{s=a.apply(this,arguments)}finally{this._super=l}return s}};e.Class=function(){};e.Class.extend=function a(b){var l=this.prototype;v=!0;var s=new this;v=!1;for(var c in b)s[c]="function"===typeof b[c]&&"function"===typeof l[c]&&G.test(b[c])?H(c,b[c],l):b[c];b=function(){!v&&this.init&&this.init.apply(this,arguments)};b.prototype=s;b.prototype.constructor=
b;b.extend=a;return b};e.Events={};var k=e.Events,z,A,w=Object.prototype.toString,I=document.createEvent,r=Date.now;k.EventListener=e.Class.extend({handleEvent:function(){},init:function(a){this.handleEvent=a}},"EventListener");z=k.EventListener;k.Event=e.Class.extend({timeStamp:0,type:"",target:null,cancelable:!1,defaultPrevented:!1,preventDefault:function(){this.cancelable&&(this.defaultPrevented=!0)},initEvent:function(a,b){this.type=a;this.target=b;this.timeStamp=r()}},"Event");A=k.Event;var t=
Object.create(null);e.createEventType=function(a,b){t[a]=A.extend(b,a);return t[a]};e.createEvent=function(a){return null!=t[a]?(a=new t[a],a.timeStamp=r(),a):I(a)};k.EventTarget=e.Class.extend({_listeners:{},addEventListener:function(a,b,l){var c=this._listeners[a];if(!(null!=c&&function(){for(var a="object"===typeof l?l:null,d,e=0,f=c.length;e<f;e++)if(d=this.listeners[e],d.listener.handleEvent===b&&d.scope===a)return!0;return!1}())){var d={listener:"object"===typeof b&&b.handleEvent?b:new z(b),
scope:"object"===typeof l?l:null};"[object Array]"===w.call(c)?c.push(d):this._listeners[a]=[d]}},removeEventListener:function(a,b,c){a=this._listeners[a];if("[object Array]"===w.call(a)){c="object"===typeof c?c:null;for(var d=0,e=a.length;d<e;d++)if(a[d].listener.handleEvent===b&&a[d].scope===c){a.splice(d,1);break}}},dispatchEvent:function(a){a.target||(a.target=this);var b=0,c=this._listeners[a.type],d=c.length,e;if("[object Array]"===w.call(c))for(;b<d;b++)e=c[b].listener.handleEvent,e.call(c[b].scope,
a);return a.defaultPrevented}},"EventTarget");for(var B=0,k=["ms","moz","webkit","o"],h=0;h<k.length&&!window.requestAnimationFrame;++h)window.requestAnimationFrame=window[k[h]+"RequestAnimationFrame"],window.cancelAnimationFrame=window[k[h]+"CancelAnimationFrame"]||window[k[h]+"CancelRequestAnimationFrame"];window.requestAnimationFrame||(window.requestAnimationFrame=function(a){var b=r(),c=Math.max(0,16-(b-B)),d=window.setTimeout(function(){a(b+c)},c);B=b+c;return d});window.cancelAnimationFrame||
(window.cancelAnimationFrame=function(a){clearTimeout(a)});var x=window.clearInterval,C=window.setInterval,D=e.Class.extend({fn:function(){},args:[],thisArg:window,sleepTime:0,init:function(a,b,c){this.method=a||function(){};this.thisArg=b||window;this.args=c||[]}},"FunctionToCall"),r=Date.now,u=Object.create(null);u.animation=0;u.steady=1;u.as_fast_as_possible=2;e.Timer=e.Events.EventTarget.extend({ANIMATION:0,STEADY:1,AS_FAST_AS_POSSIBLE:2,TimerEvent:e.createEventType("TimerEvent",{FPS:0,targetFPS:0,
delta:0,initEvent:function(a,b){if(null==b.getFPS||null==b.targetFPS||null==b.dt)throw notATimerException;this.FPS=b.getFPS();this.targetFPS=b.targetFPS;this.delta=b.dt;this._super(a,b)}}),_clearIntervalFlag:!1,_recursionCounter:0,_tickHandlersFromMethod:Object.create(null),running:!1,paused:!1,mode:0,autoStartStop:!0,setAutoStartStop:function(a){this.autoStartStop=a},prevTime:0,dt:0,maxDelta:0.05,setMaxDelta:function(a){this.maxDelta=a},sysTimerId:-1,targetFPS:50,setFPS:function(a){this.targetFPS=
a;if(this.running&&this.mode===this.STEADY){x(this.sysTimerId);var b=this;this.sysTimerId=C(function(){b.tick()},1E3/a)}},getFPS:function(){return 1/this.dt},queue:[],addToQueue:function(a,b,c){var d=new D(a,b,c),e;this.queue.push(d);var f=function J(f){0<d.sleepTime?d.sleepTime-=f.delta:(e=a.apply(b,[f].concat(c)),"number"===typeof e&&0<e?d.sleepTime=e:!0!==e&&(this.removeEventListener("tick",J,this),this.queue.splice(this.queue.indexOf(d),1)))};null==this._tickHandlersFromMethod[a]?this._tickHandlersFromMethod[a]=
[f]:this._tickHandlersFromMethod[a].push(f);this.addEventListener("tick",f,this);this.autoStartStop&&!this.running&&this.startLoop()},removeFromQueue:function(a){var b=this._tickHandlersFromMethod[a];a=this.queue.indexOf(a);if(-1!==a){for(var c=0,d=b.length;c<d;c++)this.removeEventListener("tick",b[c],this);return this.queue.splice(a,1)}},getQueue:function(){return this.queue.slice(0)},pause:function(){this._clearIntervalFlag=this.paused=!0;this.dt=0},resume:function(){this.paused=!1;this.startLoop()},
startLoop:function(){this.prevTime=r();this.running=!0;if(this.mode===this.steady){var a=this;this.sysTimerId=C(function(){a.tick()},1E3/this.targetFPS)}else this.tick()},tick:function(){if(this._clearIntervalFlag&&-1!==this.sysTimer)x(this.sysTimerId),this.sysTimerId=-1,this._clearIntervalFlag=!1;else if(!this.paused){var a=r();this.dt=(a-this.prevTime)/1E3;this.dt>this.maxDelta&&(this.dt=this.maxDelta);if(0===this.dt&&4>this._recursionCounter)this._recursionCounter++,this.tick();else{0<this._recursionCounter&&
(this._recursionCounter=0);var b=e.createEvent("TimerEvent");b.initEvent("tick",this);this.dispatchEvent(b);this.prevTime=a;a=!(this.autoStartStop&&0>=this.queue.length);if(this.mode===this.AS_FAST_AS_POSSIBLE&&a){var c=this;setTimeout(function(){c.tick()},0)}if(this.mode===this.ANIMATION&&a){var d=this;requestAnimationFrame(function(){d.tick()})}a||(this.running=!1,this.mode===this.STEADY&&-1!==this.sysTimerId&&(x(this.sysTimerId),this.sysTimerId=-1))}}},init:function(a){this.mode="number"===typeof a?
a:u[a];if(null==this.mode||0>this.mode||2<this.mode)this.mode=0}},"Timer");e.Timer.ANIMATION=0;e.Timer.STEADY=1;e.Timer.AS_FAST_AS_POSSIBLE=2;e.Timer.FunctionToCall=D;var j=[2,3,5,8,4,6],m=new (e.Class.extend({displace:0,velocity:0,drag:0.01,tickInterval:10,update:function(a){this.displace+=this.velocity*a.delta;this.velocity*=1-this.drag},init:function(){}})),q=j.slice(0),k=new e.Timer(0),h=document.createElement("div");h.style.width=23*j.length-28+"px";h.style.height="22px";h.style.overflowX="hidden";
h.style.overflowY="hidden";h.style.border="1px #555 solid";h.style.fontFamily='Consolas, "Courier New"';for(var c=[],f=0;f<j.length;f++)c[f]=document.createElement("div"),c[f].style.width="20px",c[f].style.height="20px",c[f].style.display="inline-block",c[f].style.position="relative",c[f].style.left=f+1===j.length?"-22px":"0px",c[f].style.top=f+1===j.length?"-22px":"0px",c[f].style.border="1px #AAA solid",c[f].style.textAlign="center",c[f].innerHTML=j[f],h.appendChild(c[f]);var g=0,d=1,n,p,E=0,F=
0,y=0;m.velocity=1E3*Math.random()+500;document.getElementsByTagName("body")[0].appendChild(h);k.addToQueue(function(a){if(5>m.velocity)if(0===g){for(a=0;a<c.length;a++)if((m.displace+22+22*a)%(22*j.length)-22<11*c.length&&(m.displace+22+22*a)%(22*j.length)>11*c.length){n=c[a];E=parseFloat(n.style.left);break}for(a=0;a<c.length;a++)if((m.displace+22+22*a)%(22*j.length)<11*c.length&&(m.displace+22+22*a)%(22*j.length)+22>11*c.length){p=c[a];F=parseFloat(p.style.left);break}y=p.offsetLeft-n.offsetLeft;
g=1}else if(1===g)n.style.backgroundColor="rgba(255,255,0,"+Math.round(1-d)+")",p.style.backgroundColor="rgba(255,255,0,"+Math.round(1-d)+")",d-=10*a.delta,0>d&&(g=2);else if(2==g)n.style.backgroundColor="rgba(255,255,0,"+Math.round(1-d)+")",p.style.backgroundColor="rgba(255,255,0,"+Math.round(1-d)+")",d+=10*a.delta,1<d&&(g=3,n.style.backgroundColor="rgba(255,255,255,0)",p.style.backgroundColor="rgba(255,255,255,0)",d=0);else if(3==g)n.style.left=E+d*y+"px",p.style.left=F-d*y+"px",d+=2*a.delta,1<
d&&(g=4);else if(4==g){if(d-=a.delta,0.5>d){a=c.indexOf(n);var b=c.indexOf(p),e;e=n.innerHTML;c[a].innerHTML=p.innerHTML;c[b].innerHTML=e;e=q[a];q.splice(a,1,q[b]);q.splice(b,1,e);b=-1/0;for(a=0;a<q.length;a++){if(q[a]<b){g=5;break}b=q[a]}g=5===g?5:6}}else if(5===g)d=1,m.velocity=1E3*Math.random()+500,g=0;else{if(6===g)return d=1,g=0,document.getElementsByTagName("body")[0].innerHTML+=q,!1}else{m.update(a);for(a=0;a<c.length;a++)b=(m.displace+22+22*a)%(22*j.length),a+1===j.length&&(b+=22*(j.length-
1)),c[a].style.left=b-22*a-22+"px"}return!0})})();

```

However, I used a bit of Google Closure Compiler to, er... I don't know. But it looks uglier, right?

It's like one of those lottory wheels, and each time it stops it swaps to numbers in the middle. You can have a play here: http://jsfiddle.net/VkJUE/5/ (to understand what I mean)

It does work, a bit, except that it may take hours for 6 numbers. However, I tested it on 3 numbers and it works fine!
> 11 votes

# Answer
## **Ruby Metasort**

```
#I know Ruby has a built-in method to order an array,
#but I can't remember what it is.  Oh well, metaprogramming to the rescue!
#I'll just try all of the available methods, and see which one works.

#check whether an array is ordered
def is_in_order? arr
  arr.is_a?(Array) && (0...(arr.size-1)).all? {|i| arr[i]<arr[i+1]}
end

Array.instance_methods.each do |meth|
  begin
    possibly_ordered_array = ARGV.map(&:to_i).send(meth)
    #have to check both that the new array is ordered, and that it's still the same size,
    #so that methods that change the array's elements don't create false positives.
    if is_in_order?(possibly_ordered_array) && possibly_ordered_array.size == ARGV.size
      puts possibly_ordered_array.join(", ")
      exit 0 #success!
    end
  rescue
    #method needed an argument or something
  end
end

exit 1 #could not order the array

```
> 9 votes

# Answer
Though I can't take credit for this **Java** code, Smoothsort is a good example of the tradeoff between readability and performance:

```
static final int LP[] = { 1, 1, 3, 5, 9, 15, 25, 41, 67, 109,
  177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529, 21891,
  35421, 57313, 92735, 150049, 242785, 392835, 635621, 1028457,
  1664079, 2692537, 4356617, 7049155, 11405773, 18454929, 29860703,
  48315633, 78176337, 126491971, 204668309, 331160281, 535828591,
  866988873 // the next number is > 31 bits.
};

public static <C extends Comparable<? super C>> void sort(C[] m,
    int lo, int hi) {
  int head = lo; // the offset of the first element of the prefix into m

  int p = 1; // the bitmap of the current standard concatenation >> pshift
  int pshift = 1;

  while (head < hi) {
    if ((p & 3) == 3) {
      sift(m, pshift, head);
      p >>>= 2;
      pshift += 2;
    } else {
      // adding a new block of length 1
      if (LP[pshift - 1] >= hi - head) {
        // this block is its final size.
        trinkle(m, p, pshift, head, false);
      } else {
        // this block will get merged. Just make it trusty.
        sift(m, pshift, head);
      }

      if (pshift == 1) {
        // LP[1] is being used, so we add use LP[0]
        p <<= 1;
        pshift--;
      } else {
        // shift out to position 1, add LP[1]
        p <<= (pshift - 1);
        pshift = 1;
      }
    }
    p |= 1;
    head++;
  }

  trinkle(m, p, pshift, head, false);

  while (pshift != 1 || p != 1) {
    if (pshift <= 1) {
      // block of length 1. No fiddling needed
      int trail = Integer.numberOfTrailingZeros(p & ~1);
      p >>>= trail;
      pshift += trail;
    } else {
      p <<= 2;
      p ^= 7;
      pshift -= 2;

      trinkle(m, p >>> 1, pshift + 1, head - LP[pshift] - 1, true);
      trinkle(m, p, pshift, head - 1, true);
    }

    head--;
  }
}

private static <C extends Comparable<? super C>> void sift(C[] m, int pshift,
    int head) {
  C val = m[head];

  while (pshift > 1) {
    int rt = head - 1;
    int lf = head - 1 - LP[pshift - 2];

    if (val.compareTo(m[lf]) >= 0 && val.compareTo(m[rt]) >= 0)
      break;
    if (m[lf].compareTo(m[rt]) >= 0) {
      m[head] = m[lf];
      head = lf;
      pshift -= 1;
    } else {
      m[head] = m[rt];
      head = rt;
      pshift -= 2;
    }
  }

  m[head] = val;
}

private static <C extends Comparable<? super C>> void trinkle(C[] m, int p,
    int pshift, int head, boolean isTrusty) {

  C val = m[head];

  while (p != 1) {
    int stepson = head - LP[pshift];

    if (m[stepson].compareTo(val) <= 0)
      break; // current node is greater than head. Sift.

    if (!isTrusty && pshift > 1) {
      int rt = head - 1;
      int lf = head - 1 - LP[pshift - 2];
      if (m[rt].compareTo(m[stepson]) >= 0
          || m[lf].compareTo(m[stepson]) >= 0)
        break;
    }

    m[head] = m[stepson];

    head = stepson;
    int trail = Integer.numberOfTrailingZeros(p & ~1);
    p >>>= trail;
    pshift += trail;
    isTrusty = false;
  }

  if (!isTrusty) {
    m[head] = val;
    sift(m, pshift, head);
  }
}

/* insert some basic static void main here...
   my Java's too rusty to do it from the top of my head
*/

```

(note: some comments removed for effect and to make it shorter; source taken from the wikipedia page linked above)
> 7 votes

# Answer
The **F#** "I hate functional programming" :

```
let numbers = System.Console.ReadLine().Split(',')
let mutable check = 0
let mutable sorted = ""

while not (sorted.Split(',').Length = numbers.Length) do
    for i in [check..check + 1000] do
        for number in numbers do
            if number = i.ToString() then
                if sorted.Length > 0 then
                    sorted <- sorted + ","
                sorted <- sorted + number
    check <- check + 1000

printfn "%s" sorted

```
> 7 votes

# Answer
A Cobol subprogram to sort a table of integers, guaranteed to have a higher WTF/minute than any other language. For performance purposes, the QuickSort algorithm is used:

```
Identification Division.
Program-ID. QwikSort is recursive.
Environment Division.
Data Division.
Working-Storage Section.
01 QwikSort-Working-Storage.
 05 Swap-Space           Pic X(80) Value spaces.
 05 Pivot         Binary Pic S9(8).
 05 I             Binary Pic S9(8).

Local-Storage Section.
01 QwikSort-Local-Storage.
 05 Lo            Binary Pic S9(8) Value 0.
 05 Hi            Binary Pic S9(8) Value 0.

Linkage Section.

01 The-Table-Area.
 05 The-Table     occurs 0 to 200000 depending on High-Element.
  10 The-Key     Binary Pic S9(8).

01 Low-Element     Binary Pic S9(8).
01 High-Element    Binary Pic S9(8).

Procedure Division using The-Table-Area
                         Low-Element
                         High-Element.

  Compute Lo  = Low-Element
  Compute Hi  = High-Element

  If ( High-Element > Low-Element )
     Perform Select-Pivot

* ----- Loop through table until indices cross
       Perform until Hi < Lo

* -------- Locate an item that should not be in less partition
          Perform varying Lo from Lo by 1
            until (( Lo >= High-Element )
               or  ( The-Key of The-Table ( Lo ) >= Pivot ))
          End-Perform

* -------- Locate an item that should not be in greater partition
          Perform varying Hi from Hi by -1
            until (( Hi <= Low-Element )
               or  ( The-Key of The-Table ( Hi ) <= Pivot ))
          End-Perform

* -------- Exchange the two and keep looking
          If ( Lo <= Hi )
             Perform Swap-Elements
             Compute Lo = Lo + 1
             Compute Hi = Hi - 1
          End-If

    End-Perform

    Perform Qsort-Less-Partition

    Perform Qsort-Greater-Partition

 End-If

 Goback.

*--------------------------------------------------------------*
* Select the pivot using median of three rule.
*--------------------------------------------------------------*
 Select-Pivot.

    Compute Pivot = ( Lo + Hi ) / 2
    Compute Pivot = Function Median (
            The-Key of The-Table ( Lo )
            The-Key of The-Table ( Pivot )
            The-Key of The-Table ( Hi )
         )
    End-Compute

    Exit.

*--------------------------------------------------------------*
* Exchange elements in the wrong partition
*--------------------------------------------------------------*
 Swap-Elements.
    Move The-Table ( Lo ) to Swap-Space
    Move The-Table ( Hi ) to The-Table ( Lo )
    Move Swap-Space       to The-Table ( Hi )
    Exit.

*--------------------------------------------------------------*
* Sort the less sub-partition
*  -- Optimization opportunity for the user: if the partition
*    size is sufficiently small you might want to apply a simple
*    sort like insertion or bubble, or perhaps a bose-nelson
*    network to order the last few and save the overhead of
*    another recursive call.
*--------------------------------------------------------------*
 Qsort-Less-Partition.
    If ( Low-Element < Hi )
       Call 'QwikSort' Using
          The-Table-Area
          Low-Element
          Hi
       End-Call
    End-If
    Exit.

*--------------------------------------------------------------*
* Sort the greater sub-partition
*  -- Optimization opportunity for the user: same as left part.
*--------------------------------------------------------------*
 Qsort-Greater-Partition.
    If ( Lo < High-Element )
       Call 'QwikSort' Using
          The-Table-Area
          Lo
          High-Element
       End-Call
    End-If
    Exit.

 End Program QwikSort.

```
> 6 votes

# Answer
```
var inp = [1, 4, 7, 2, 5],
    loops = 0,
    trysort;

while(++loops) {
    trysort = new Array(inp.length);

    for(var i = 0, len = inp.length; i < len; i++) {
        trysort[i] = inp[~~(Math.random()*inp.length)];
    }

    if( trysort.join(',') === '1,2,4,5,7' )
        break;
}
alert('done! Only ' + loops + ' iterations! ' + trysort);

```

http://www.jsfiddle.net/sAFMC/
> 4 votes

# Answer
## Python quicksort using lambda

Something I wrote on my blog:

```
qsort = lambda seq: [] if not seq else qsort(filter(lambda n: n<=seq[0], seq[1:]))+[seq[0]]+qsort(filter(lambda n: n>seq[0], seq[1:]))

```

Here's the actual blog post
> 4 votes

# Answer
# Ruby

```
#get user input from standard input and store it in a variable
var = gets
#make user input into a ruby array in a string
array_string = '[' + var + ']'
#evaluate this ruby array and store the array in a variable
array = eval(array_string)
#convert from strings to integers
#initialize loop variable as 0
i = 0
#loop until the loop variable is no longer small enough
#to be a valid index of the array
until !(i < array.length)
    #convert to a number then ensure it is an integer
    array[i] = array[i].to_f.floor
    #increment i
    i = i + 1
end

sorted = false

#infinite loop
while true
    #if it hasn't been sorted
    if ((!sorted) == true)
        #try to sort it
        #initialize loop variable as 0
        j = 0
        #loop while i is less than or equal to the length of the array
        while (i <= array.length)
            random = rand # get a random number
            #this gets a zero or one
            random = (random + random.round).floor
            #turn random into a boolean
            if random == 0
                random = true
            end
            if random == 1
                random = false
            end
            #don't do anything if this is the last one
            if j == (array.length - 1)
                #do nothing
            else
                if random == true
                    #true means keep these 2 elements in the same order
                end
                if random == false
                    #false means swap with next element
                    #initialize a variable to store the current element
                    swapvar = array[j]
                    #initialize a variable to store the next element
                    swapvar2 = array[j+1]
                    #set the current element to what was the next element
                    array[j] = swapvar2
                    #set the next element to what was in this one
                    array[j+1] = swapvar
                end
            end
            #increment j
            j = j + 1
            #loop kept looping, fixed now
            if j >= array.length
                break
            end
        end
        #now test if it is sorted
        #lets say it is
        sorted = true
        #now see if we are wrong
        #initialise a loop variable to zero
        k = 0
        while (array.length > k)
            #get current value from array and store it in a variable
            current = array[k]
            #get current value from array and store it in a variable
            next_ = array[k + 1]
            if !(array[k +1].nil? == true)#stop errors
                #if sorted correctly
                if next_ < current || next_ == current
                    #sorted stil== true
                else
                    sorted = false #not sorted, try again
                end
            end
            #increment loop variable
            k = k + 1
        end
            #DEBUG
        #p array
    else
        break #break out of infinite loop
    end
end

#it is now sorted in descending order
#we want ascending so lets flip it

#initialise a loop variable to zero
l = 0

final_array = Array.new([])

while (l <= (array.length - 1))
    final_array[array.length - l - 1] = array[l]
    #increment loop variable
    l += 1
end

#now we need to make it into a string
str = ''

#first map each element to a string
#to do this lets extend Array, then use this for our array
class Array
    def map #map each element to a string
        #initialise a loop variable to zero
        @m = 0
        arr = []
        while @m < self.length
            arr += [self[@m].to_s]
            #increment loop variable
            @m = @m + 1
        end
        return arr
    end
end

final_array = Array.new(final_array).map()
#DEBUG
#p final_array

#now add the elements to a string, separated by commas and spaces
#initialise a loop variable to zero
n = 0

while n < array.length
    #increment loop variable
    #add item to string
    str = str + final_array[n]
    #if not last item
    if !((array.length - 1 )== n)
        #add comma
        str += ','
    end
    #if not last item
    if !((array.length - 1 )== n)
        #add space
        str += ' '
    end
    n = n + 1
end

#now print the string
puts str

```
> 4 votes

# Answer
## C++ (4409)

```
#include <iostream>
#include <cstdlib>
#include <cctype>
#include <string>
#include <sstream>

std::string itostr(int number)
{
   std::stringstream ss;
   ss << number;
   return(ss.str());
}

class CStackLIFO
{
private:
    int* stack;
    size_t len;
public:
    CStackLIFO();
    CStackLIFO(int);
    ~CStackLIFO();
    void init();
    void init(int);
    void push(int);
    int pop();
    int pop(int&);
    void destroy(size_t);
    int get(size_t);
    size_t get_len();
};

void CStackLIFO::init()
{
    len = 0;
    stack = NULL;
}

void CStackLIFO::init(int val)
{
    len = 1;
    stack = new int[len];
    stack[0] = val;
}

CStackLIFO::CStackLIFO()
{
    init();
}

CStackLIFO::CStackLIFO(int val)
{
    init(val);
}

CStackLIFO::~CStackLIFO()
{
    len = 0;
    delete[] stack;
    stack = NULL;
}

void CStackLIFO::push(int val = NULL)
{
    if((stack == NULL) || (len == 0))
    {
        this->init(val);
    }
    else
    {
        int* buf = stack;
        len++;
        stack = new int [len];

        for(size_t i = 0; i < (len - 1); i++)
        {
            stack[i] = buf[i];
        }

        stack[len - 1] = val;
        delete[] buf;
    }
}

int CStackLIFO::pop()
{
    int val;
    int* buf = stack;
    len--;
    stack = new int [len];

    for(size_t i = 0; i < len; i++)
    {
        stack[i] = buf[i];
    }

    val = buf[len];
    delete[] buf;

    return(val);
}

int CStackLIFO::pop(int &out)
{
    if(len <= 0)
        return(false);

    int* buf = stack;
    len--;
    stack = new int [len];

    for(size_t i = 0; i < len; i++)
    {
        stack[i] = buf[i];
    }

    out = buf[len];
    delete[] buf;

    return(true);
}

void CStackLIFO::destroy(size_t idx)
{
    int* buf = stack;
    len--;
    stack = new int [len];
    for(size_t i = 0; i < idx; i++)
    {
        stack[i] = buf[i];
    }
    for(size_t i = idx; i < len; i++)
    {
        stack[i] = buf[i + 1];
    }
    delete[] buf;
}

int CStackLIFO::get(size_t idx)
{
    return(stack[idx]);
}

size_t CStackLIFO::get_len()
{
    return(len);
}

class CSort
{
private:
    void removeWhitespace();
public:
    std::string in;
    void sort();
    void display();
};

void CSort::display()
{
    std::cout << in << std::endl;
    return;
}

void CSort::removeWhitespace()
{
    for(size_t i = 0; i < in.size(); i++)
    {
        if(in[i] == ' ')
        {
            in = in.substr(0, i) + in.substr(i+1);
        }
    }
}

void CSort::sort()
{
    removeWhitespace();

    CStackLIFO nums;
    CStackLIFO s;

    // build stack
    for(size_t i = 0, offset = 0; i < in.size(); i++)
    {
        for(offset = 0; (i + offset) < in.size(); offset++)
        {
            if(!(isdigit(in[i + offset]) ||
                 (in[i + offset] == '-')))
                break;
        }

        if(offset > 0)
        {
            nums.push(atoi(in.substr(i, offset).c_str()));
        }

        i += offset;
    }

    // sort
    for(size_t lowest = 0; 0 < nums.get_len(); lowest = 0)
    {
        for(size_t i = 0; i < nums.get_len(); i++)
        {
            if(nums.get(i) < nums.get(lowest))
                lowest = i;
        }

        s.push(nums.get(lowest));
        nums.destroy(lowest);
    }

    // convert to string
    in = "";
    for(size_t i = 0; i < s.get_len(); i++)
    {
        // Convert num to string
        in += itostr(s.get(i));
        in += ", ";
    }
    if(in.size() > 2)
        in = in.substr(0, in.size() - 2);
}

int main(int argc, char* argv[])
{
    while(1)
    {
        CSort unsorted;
        unsorted.in = "";

        while(1)
        {
            std::string userin = "";
            std::cin >> userin;

            if(userin.compare("end") == 0)
                break;

            unsorted.in += userin + ", ";
        }

        unsorted.in = unsorted.in.substr(0, unsorted.in.size() - 2);

        CSort sorted;
        sorted.in = unsorted.in;
        sorted.sort();

        std::cout << "Input:" << std::endl;
        unsorted.display();
        std::cout << "Output:" << std::endl;
        sorted.display();
    }

    return(0);
}

```

Some things "bad" about this program:

* Really stringy. :) I could have simply inputted the numbers directly, instead of parsing the string for numbers.
* Uses excessive classes. I could have used the built-in ones, too, but a bad coder would simply reinvent the wheel.
* The loop for the sort is terribly inefficient. I think it's the slowest way possible, without making it look like I actually tried to make it slow. Actually, the actual "sort" part of the code is only like 11 lines, including the curly braces and line breaks.
> 3 votes

# Answer
This one is O(n\*n!)

```
from itertools import permutations, izip, islice
L=[10,9,8,7,6,5,4,3,2,1]
for l in permutations(L):
    if all([i<j for i,j in izip(L, islice(L,1,None))]):
        break
print l

```

It iterates all the permutations of the list and tests whether they are sorted. It is *so awful* that sorting just 10 items takes 17 seconds

```
$ time python badsort.py
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

real    0m17.563s
user    0m17.537s
sys     0m0.020s

```
> 3 votes

# Answer
## T-SQL

(SQL Server 2008 R2)

Naturally, with T-SQL, you use "ORDER BY" to sort. Duhhh.

```
DECLARE @LISTIN NVARCHAR(MAX);
SELECT @LISTIN = N'1, 4, 7, 2, 5'; --Input list goes here.
DECLARE @LISTINDEX BIGINT;
SELECT @LISTINDEX = 0;
DECLARE @CHARS NVARCHAR(MAX);
SELECT @CHARS = N'';
DECLARE @LISTOUT NVARCHAR(MAX);
SELECT @LISTOUT = N'';
DECLARE @ORDERBY TABLE (NUMBER NVARCHAR(MAX));
WHILE @LISTINDEX < LEN(@LISTIN) BEGIN;
SELECT @LISTINDEX = @LISTINDEX + 1;
SELECT @CHARS = @CHARS + SUBSTRING(@LISTIN, @LISTINDEX, 1);
IF PATINDEX(N'%, ', @CHARS) > 0 BEGIN;
INSERT INTO @ORDERBY (NUMBER) VALUES (REPLACE(@CHARS, N', ', N''));
SELECT @CHARS = N'';
END;
IF @LISTINDEX = LEN(@LISTIN) BEGIN;
INSERT INTO @ORDERBY (NUMBER) VALUES (@CHARS);
END;
END;
DECLARE ORDERBY CURSOR FOR SELECT NUMBER FROM @ORDERBY ORDER BY CONVERT(DECIMAL, NUMBER);
OPEN ORDERBY;
FETCH NEXT FROM ORDERBY INTO @CHARS;
WHILE @@FETCH_STATUS = 0 BEGIN;
SELECT @LISTOUT = @LISTOUT + @CHARS + N', ';
FETCH NEXT FROM ORDERBY INTO @CHARS;
END;
CLOSE ORDERBY;
DEALLOCATE ORDERBY;
IF @LISTOUT = N'' SELECT @LISTOUT;
ELSE SELECT SUBSTRING(@LISTOUT, 1, LEN(@LISTOUT) - 1);

```

See the "ORDER BY"? It's right there in the cursor declaration.
> 3 votes

# Answer
**Python** implementation of Funnel Sort. This algorithm can actually have good cache performance when implemented properly, which in this case it is most certainly not (it does, however, sort correctly).

```
class Funnel(object):
  """ In place funnel sorting algorithm. """
  def __init__(self, left_child, right_child):
    self.left_child = left_child
    self.right_child = right_child
    self.lookahead = (False, -1)

  def get_next(self):
    if self.left_child.has_next() and self.right_child.has_next():
      l, r = self.left_child.get_next(), self.right_child.get_next()
      if l < r:
        self.right_child.put_back(r)
        return l
      else:
        self.left_child.put_back(l)
        return r
    elif self.left_child.has_next():
      return self.left_child.get_next()
    elif self.right_child.has_next():
      return self.right_child.get_next()
    else:
      raise Exception("Out of elements.")

  def has_next():
    if self.lookahead[0]:
      self.lookahead = (False, self.lookahead[1])
      return self.lookahead[1]
    return self.left_child.has_next() or self.right_child.has_next()

  def put_back(self, item):
    self.lookahead = (True, item)

class Funnel_Base(Funnel):
  def __init__(self, buffer):
    self.buf = buffer
    self.lookahead = (False, -1)

  def get_next(self):
    if self.lookahead[0]:
      self.lookahead = (False, self.lookahead[1])
      return self.lookahead[1]
    return self.buf.pop(0)

  def has_next():
    return len(self.buf) > 0

def make_funnel(funnels):
  while len(funnels) > 1: funnels.append(Funnel(funnels.pop(0), funnels.pop(0)))
  return funnels[0]

def insertion_sort(array):
  def swap(i, j):
    t = array[i]
    array[i] = array[j]
    array[j] = t
  for i in xrange(1,len(array)):
    while i > 0 and  array[i] < array[i-1]:
      swap(i, i-1)
      i -= 1

def funnel_sort_internal(array):
  if len(array) < 100:
    # sort subsections with insertion sort and make base funnels
    insertion_sort(array)
    return Funnel_Base(array)
  else:
    K = int(len(array)**(1.0/3))
    new_funnels = [funnel_sort_internal(array[base:min(base+K, len(array))])
                   for base in xrange(0, len(array), K)]
    return make_funnel(funnels)

def funnel_sort(array):
  cp = array[:]
  srtd = funnel_sort_internal(cp)
  for i in xrange(len(array)): array[i] = cp[i]

```
> 2 votes

# Answer
Sorts a list of 32-bit integers. It is actually quite efficient for most ordinary cases:

```
#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

static unsigned char *bmp[131072];
static size_t total, printed;

static void set(int n);
static void print_page(unsigned char *page, int offset);
static void print_number(int n);

int main(void)
{
    int i, n;

    assert(INT_MIN == -2147483647 - 1 && INT_MAX == 2147483647);

    while (scanf("%d,*", &n) > 0) {
        set(n);
        total++;
    }

    for (i = 0; i < 131072; i++)
        if (bmp[i] != NULL)
            print_page(bmp[i], INT_MIN + i * 32768);
    putchar('\n');

    return 0;
}

static void set(int n)
{
    unsigned int i = n - INT_MIN;

    if (bmp[i >> 15] == NULL)
        bmp[i >> 15] = calloc(4096, sizeof(unsigned char));

    bmp[i >> 15][(i >> 3) & 4095] |= (unsigned int)1 << (i & 7);
}

static void print_page(unsigned char *page, int offset)
{
    int i, j;

    for (i = 0; i < 4096; i++, offset += 8)
        if (page[i])
            for (j = 0; j < 8; j++)
                if (page[i] & (1 << j))
                    print_number(offset + j);
}

static void print_number(int n)
{
    printf("%d%s", n, ++printed < total ? ", " : "");
}

```

Example:

```
$ echo '1, 4, -3, 7, -2147483648, 2147483647, 2, 5' | ./bitmap-sort
-2147483648, -3, 1, 2, 4, 5, 7, 2147483647

```
> 2 votes

# Answer
```
<?php
    /*  THIS SOFTWARE IS PROVIDED "AS IS" AND ANY
        EXPRESSED OR IMPLIED WARRANTIES, INCLUDING,
        BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
        OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
        PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
        REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
        INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
        CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
        TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
        LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
        INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
        LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
        OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
        IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
        ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.          */

    // Make the function
    function sort_numbers($nums) {
        // Remove duplicates from array
        array_unique($nums);
        // Filter out everything that's not a number or a numeric string
        foreach ($nums as $val) {
            if (!is_numeric($val)) {
                unset($array[$val]);
            }
        }
        // Do some random computations
        class SorterFunction {
            public $timestamp = 0;
            public $rand_num = 0;
            public function sort_a_numeric_array($num_arr) {
                // Sort the array
                sort($num_arr, SORT_NUMERIC);
                return $num_arr;
            }
            public function __construct() {
            $this->timestamp = time();
            $this->rand_num = rand() % 100000;
        }
    }
    // Create a new SorterFunction class
    $MySorterFunction = new SorterFunction();
    // Print out the sorted array's elements using var_dump
        $MySorterFunction->sort_a_numeric_array($nums);
        var_dump($nums);
    }
    $my_nums = array(1, 4, 7, 2, 5);
    sort_numbers($my_nums);
?>

```
> 2 votes

# Answer
**C++**, not sure if there is name for this sort, but here goes `<ducks for cover/>`

```
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

int main(void)
{
  std::istream_iterator<int> in(std::cin), end;
  std::vector<int> input(in, end);

  std::cout << "sorting.." << std::endl;
  std::copy(input.begin(), input.end(), std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;

  // this is the smart bit.. ;)
  while (std::next_permutation (input.begin(), input.end()));

  std::cout << "sorted.." << std::endl;
  std::copy(input.begin(), input.end(), std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;

  return 0;
}

```
> 2 votes

# Answer
An enterprisey solution (in pseudocode):

```
create sql connection
create temporary table: one autoincrementing ID field and one value field
convert array into xml
post xml to sql database
use stored procedure to create records from xml
run sql command "select * from temptable sort by value"
iterate records, adding to array
drop temporary table
close connection

```
> 2 votes

# Answer
In Ruby, a visual representation of a "Spaghetti Sort", designed to be run in an 80 column terminal:

```
$CONSOLE_WIDTH = 78
def sort a
  factor = $CONSOLE_WIDTH.to_f/a.max
  puts "Strands:"
  puts (strands=a.map{|v|['-'*(v*factor).to_i,v*factor]}).map{|s|s.first}
  results=[];
  len=0
  n = 1
  until strands.empty? do
   #puts "\nITERATION #{n}\n\n"
    n+=1
    $CONSOLE_WIDTH.downto(0) do |i|
      len = i
      contacts = strands.find_all{|s|s.first[i]!=nil}
      break unless contacts.empty?
    end
    puts "\nResults:"
    puts results.map{|s|s.first}
    puts "\nStrands:"
    puts strands.map{|s|s.first.ljust(len+1)+"|"}
    longest = strands.sort_by{|s|s.last}.max
    strands.delete_at strands.index(longest)
    results << longest
  end
  puts "\nResults:"
  puts results.map{|s|s.first}
  return results.map{|s|s.last/factor}

end

```

Usage: `p sort (1..10).map{rand(100)}`
> 2 votes

# Answer
## PL\SQL - 109 lines

This is a response to @eBusiness's comment in @steenslag's answer. It serves no useful purpose.

It has 4 stages:

1. Take a comma separated list of numbers and work out how many commas are in it.
2. Use the number of commas to split the string positionally based on the commas.
3. Loop through the known number of values and find the minimum value each time - deleting the previous minimum as we go.
4. Output them.

---

```
 create or replace procedure sort ( Plist_of_numbers varchar2 ) is

   type t_num_array is table of number index by binary_integer;

   t_sorted t_num_array;
   t_unsorted t_num_array;

   i binary_integer := 0;
   -- Can you tell this one was an afterthought?
   x binary_integer := 0;

   no_of_commas integer := 0;

   v_list_of_numbers varchar2(32000);
   v_min_value number;
   v_min_index binary_integer;

begin

   -- Best to be overly careful about these things.
   if trim(Plist_of_numbers) is null then
      raise_application_error(-20000,'You need to give me something to work with.');
   end if;

   -- Firstly we have to make sure that there is a trailing comma
   -- in Plist_of_numbers for this to work.
   if substr(Plist_of_numbers,-1) = ',' then
      v_list_of_numbers := Plist_of_numbers;
   else
      v_list_of_numbers := Plist_of_numbers || ',';
   end if;

   /* SQL ( being SQL ) we had to pass in a string of numbers
      because we'd need to create a type outside the function which
      wouldn-t really be in the spirit of things so, let's unpack
      our string. In order to do this ( bowling ) we need to know how
      many commas are in our sting.
   */

   for j in 1 .. length(v_list_of_numbers) loop

      if substr(v_list_of_numbers,j,1) = ',' then
         no_of_commas := no_of_commas + 1;
      end if;

   end loop;

   -- Next we unpack our list into t_unsorted;
   for j in 1 .. ( no_of_commas - 1 ) loop

      i := i + 1;
      t_unsorted(i) := to_number( substr( v_list_of_numbers
                                        , instr(v_list_of_numbers, ',', 1, j)
                                        , instr(v_list_of_numbers, ',', 1, j + 1)
                                           )
                                  );

   end loop;

   -- Next the actual sorting.
   -- Loop through the known number of elements in the array.
   for j in 1 .. i loop

      -- Then the array each time to find the minimum.
      -- As we-re deleting stuff in the middle here we have to be careful;
      k := t_unsorted.first;
      v_min_value := null;

      while k < t_unsorted.last loop

         if v_min_value is null then
            v_min_value := t_unsorted(k);
            v_min_index := k;
         elsif t_unsorted(k) < v_min_value then
            v_min_value := t_unsorted(k);
            v_min_index := k;
         end if;

         k := t_unsorted.next;

      end loop;

      -- Now we-ve found the next minimum value put it into the
      -- t_sorted array
      x := x + 1;
      t_sorted(x) := v_min_value;
      -- and delete our min value from the unsorted array.
      t_unsorted.delete(v_min_index);

   end loop;

   -- Lastly show that everything worked.
   for j in 1 .. x loop

      dbms_output.put_line( t_sorted(j) );

      -- it-s also nice to show the wider world what-s happening
      -- but let-s not do it too often, server load etc.
      if mod(j,10) = 0 then
          dbms_application_info.set_module('finding min', 'total: ' || j );
      end if;

   end loop;

end sort;

```

As you can see it's ridiculous... Bad things include:

* Doing this in SQL

That's pretty much it actually, it should be extremely quick.
> 2 votes

# Answer
Both the choice of language and algorithm need to be explained.

This algorithm is called slow sort. I intend to beat the crap out of bogosort (test random permutations until it's sorted) because, while algorithmically terribly inefficient, it's implementation is too simple and you cannot garantee its slowness.

I code slow sort in Scheme because Scheme's main goal is to be simple, which makes this a greater challenge. An interesting feature of Scheme is its unbeatable extensibility; in fact, implementations of the language are commonly (often completely) implemented in Scheme itself. Even better: all you need is abstractions (lambdas) and applications. Applications are evaluated in prefix notation:

```
(function arg1 arg2 ...)

```

... is just syntactic sugar for:

```
(apply function (list arg1 arg2 ...))

```

... which applies a function to lists of arguments.

In order to make a strike out of this code bowling, I have to redefine the max function to recursively split the list until it can compare itself. The min function is also redefined recursively using max by removing out all the maximums until one number remains. Finally, the sort is redefined by successively appending the minimums.

Slow sort is based on "multiply and surrender", as opposed to "divide and conquer". It works by recursively pulling out the maximums until you are left with the minimum, appending the resulting minimum each time to the solution and restarting over until all minimums have been appended in turn. While totally inefficient, my implementation reuses computations as much as possible because: 1) It is needed for the algorithm 2) You might want this sort to end some day...

```
(define sort
  (lambda ns
    (define max
      (lambda (ns)
        (let ([len (length ns)])
          (case len
            [(2) (receive (a b) (car+cdr ns)
                   (if (> a b) a b))]
            [(1) (car ns)]
            [else (receive (a b)
                    (split-at ns
                      (floor (/ len 2)))
                    (let ([ma (max a)]
                          [mb (max b)])
                      (if (> ma mb) ma mb)))]))))
    (define min
      (lambda (ns)
        (if (null? (cdr ns)) (car ns)
            (min (remove ns (max ns))))))
    (if (every number? ns)
        (let sort ([ns ns] [sorted (list)])
          (if (null? ns) sorted
              (let ([m (min ns)])
                (sort (remove ns m)
                  (append ns m)))))
    (error "These are not all numbers: " ns))))

```
> 2 votes

# Answer
## Java exaggerated mess/heaviness

That was fun! Feels weird to post something like this.

```
import java.util.LinkedList;

public class WTF {

    // XXX We all know linkedlists are awesome for random access!
    public static LinkedList<Integer> sort(LinkedList<Integer> array) {
        // XXX Instead of sorting in place, we create another array entirely!
        LinkedList<Integer> result = new LinkedList<Integer>();

        // while array is not all null
        // XXX No comments!
        boolean arrayAllNull = true;
        for (int a = 0; a < array.size(); a = a + 1) {
            if (array.get(a) != null) {
                arrayAllNull = false;
            }
        }

        while (arrayAllNull != true) {

            // XXX We could use Integer.MAX_VALUE, but lets assumes something instead
            Integer i = 999999999;
            // find lowest
            for (int a = 0; a < array.size(); a = a + 1) {
                if (array.get(a) != null) {
                    if (array.get(a) < i) {
                        i = array.get(a);
                    }
                }
            }

            // replace lowest by null
            // XXX Yup, another loop! :)
            // XXX We're breaking the original array, but don't tell anyone.
            for (int a = 0; a < array.size(); a = a + 1) {
                if (array.get(a) != null) {
                    if (array.get(a) == i) {
                        array.set(a, null);
                    }
                }
            }

            result.add(i);

            // XXX Lets repeat that test once again, functions are bad.
            arrayAllNull = true;
            for (int a = 0; a < array.size(); a = a + 1) {
                if (array.get(a) != null) {
                    arrayAllNull = false;
                }
            }

        }

        return result;
    }

    public static void main(String[] args) {
        int[] numbers = new int[]{1, 4, 7, 2, 5};
        LinkedList<Integer> nums = new LinkedList<Integer>();
        for (int i : numbers)
            nums.add(i);
        System.out.println(sort(nums));
    }

}

```
> 1 votes

# Answer
## Python

Only works if all the items are less than 9e99 :)

```
>>> L=[10,9,8,7,6,5,4,3,2,1]
>>>
>>> print [[min(L),L.__setitem__(L.index(min(L)),9e99)][0] for i in L]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

```

Each time through the loop, extract the smallest element and replace it with 9e99
> 1 votes

# Answer
## Python (634)

If the list is sorted, print it. Otherwise, swap two elements that are in the wrong order, then generate a python script that handles the new order. After running that, delete the created script.

```
list_to_sort = input()
n = 0
n += 1
import sys, os
for i in range(len(list_to_sort)-1):
    if list_to_sort[i]>list_to_sort[i+1]:
        (list_to_sort[i],list_to_sort[i+1]) = (list_to_sort[i+1],list_to_sort[i])
        source_file = open(sys.argv[0],'r')
        temp_filename = 'temp'+repr(n)+'.py'
        temp_file = open(temp_filename,'w')
        temp_file.write('list_to_sort = ' + repr(list_to_sort) + '\n')
        temp_file.write('n = ' + repr(n) + '\n')
        for line in source_file.readlines()[2:]:
            temp_file.write(line)
        source_file.close()
        temp_file.close()
        os.system('python ' + temp_filename)
        os.remove(temp_filename)
        sys.exit(0)
print list_to_sort

```
> 1 votes

# Answer
## Bogobogosort in Python

```
import random
import copy

def isSorted(list):
    newlist = copy.deepcopy(list)
    while True:
        newlist[:len(newlist)-1] = bogobogosort(newlist[:len(newlist)-1])
        if newlist[len(newlist)-2] < newlist[len(newlist)-1]:
            break
        random.shuffle(newlist)
    return newlist == list

def bogobogosort(list):
    ret = copy.deepcopy(list)
    if (len(ret) > 1):
        while not isSorted(ret):
            random.shuffle(ret)
    return ret

```

Algorithm invented by David Morgan-Mar.

Warning: don't try this with any list larger than 5 elements. Even 5 is very slow.
> 1 votes

# Answer
# Python

My solution. Includes error handling, and a feature that preserves whitespace when sorting numbers, i.e., whitespace stays in place; numbers move.

e.g.,

```
Please tell me your favorite list of numbers.
I'll sort them for you.
7, 8, 6, 7, 1, 3, 5
1, 3, 5, 6, 7, 7, 8

9,  6  ,8, 43, 90, 13   , 54, 3223, 4
4,  6  ,8, 9, 13, 43   , 54, 90, 3223

```

Code:

```
#!/usr/bin/env python
import sys
import re

class SillyUserException(ValueError):
    def __init__(self, reason, input):
        self.reason = reason
        self.input = input

    def __str__(self):
        return '''
"No man is exempt from saying silly things; the mischief is to say them deliberately."
 - Michel de Montaigne, The Complete Essays
 Your offense was {}.  You should know that it's {}.
         '''.format(self.input, self.reason)

class Item(object):
    def __init__(self, number, prespace, postspace):
        self.number = number
        self.prespace = prespace
        self.postspace = postspace

    def __str__(self):
        return self.prespace + str(self.number) + self.postspace

class ListOfNumbers(object):
    def __init__(self, string):
        self.array = self.parse(string)

    def __str__(self):
        outs = ''
        for i in self.array:
            outs += '{}{}{},'.format(i.prespace, i.number, i.postspace)
        return outs[:-1]

    def parse(self, string):
        array = []

        for item in string.split(','):
            try:
                x = int(item)
            except ValueError:
                raise SillyUserException("not a number", item)

            whitespace = re.findall("\s+", item)
            pre = ''
            post = ''
            if len(whitespace) > 0:
                pre = whitespace[0]
            if len(whitespace) > 1:
                post = whitespace[-1]

            array.append(Item(x, pre, post))

        def swap(i, j):
            tmp = array[i].number
            array[i].number = array[j].number
            array[j].number = tmp

        def min(arr, offset):
            m = arr[0]
            index = 0
            for i, e in enumerate(arr):
                if e.number < m.number:
                    m = e
                    index = i
            return index + offset

        for i, x in enumerate(array):
            m = min(array[i:], i)
            if m != i:
                swap(m, i)

        return array

if __name__ == "__main__":
    sys.stdout.writelines('\n'.join([
        "Please tell me your favorite list of numbers.",
        "I'll sort them for you.  ",
        ""
    ]))

    sys.stdout.flush()

    def read_lines():
        while True:
            line = raw_input()
            yield line

    try:
        for line in read_lines():
            if not line:
                raise SillyUserException('polite to speak when asked a question.', "<nothing>")
            if line.strip() == '42':
                raise SillyUserException('the answer to life, the universe, and everything',
                    'using and overly powerful value')
            if ',' not in line:
                raise SillyUserException("not a list", line)

            print ListOfNumbers(line)

    except SillyUserException as sillyness:
        print sillyness

```
> 1 votes

# Answer
# Python 3

This program accepts a space separated list of numbers on standard input. It will then print the on standard output in the proper order. Eventually.

```
import base64, pickle
pickle.loads(base64.b64decode(b'gAIoY2J1aWx0aW5zCmxpc3QKcQBjYnVpbHRpbnMKbWFwCnEBY2J1aWx0aW5zCmludApjYnVpbHRpbnMKZ2V0YXR0cgpxAmNidWlsdGlucwppbnB1dAopUlgFAAAAc3BsaXSGUilShlKFUnEDaABoAWNmdW5jdG9vbHMKcGFydGlhbApxBGNvcGVyYXRvcgphZGQKY19vcGVyYXRvcgpuZWcKY2J1aWx0aW5zCm1pbgpoA4VShVKGUmgDhlKFUnEFaABoAWgCY2FzeW5jaW8KZ2V0X2V2ZW50X2xvb3AKcQYpUlgKAAAAY2FsbF9sYXRlcoZSaAVoAWgEaARjYnVpbHRpbnMKcHJpbnQKhlJoA4ZSh1KFUjFoAmgGKVJYEgAAAHJ1bl91bnRpbF9jb21wbGV0ZYZSY2FzeW5jaW8Kc2xlZXAKY19vcGVyYXRvcgphZGQKY2J1aWx0aW5zCm1heApoBYVSSwGGUoVShVIu'))

```

Explanation: the pickle protocol actually provides a lot of freedom, most notable the freedom to import and call arbitrary objects with arguments. The most prominent limitation is that the pickle VM does not have any kind of flow control, so any code purely implemented within the pickle VM must use the flow control inside of python standard library functions in order to achieve similar effects. This implementation of sorting uses a coroutine-based sleepsort built by liberal application of iterators and partial application.

The equivalent python code would be something like this:

```
from asyncio import get_event_loop, sleep
from operator import add
from functools import partial
values = list(map(int, input().split()))
times = list(map(partial(add, -min(values)), values))
list(map(get_event_loop().call_later, times, map(partial(partial, print), values)))
get_event_loop().run_until_complete(sleep(max(times)+1))

```
> 1 votes

# Answer
# Perl

not so long but self-explained:
```
if (my @list = (2,5,4,1)) {
    do { @list = sort @list and print @list} if("you want to sort it")
}

```
> 0 votes

# Answer
# Radix Sort in Haskell

I have tried to do some optimization using Data.Sequence but it probably needs some more around assingBuckets method.

```
import qualified Data.Sequence as Seq
import qualified Data.Foldable as Fold
import System.Environment

digit :: Int -> Int -> Int
digit x pos = if pos >= 0 && pos < xlength
                then read [xstr !! (xlength - 1 - pos)]
                else 0
    where xlength = length xstr
          xstr = show x

assignBuckets :: [Int] -> Int -> [[Int]]
assignBuckets xs dig = map Fold.toList . Fold.toList $
                            assign xs dig
                              (Seq.fromList $ take 10 $ repeat (Seq.empty :: Seq.Seq Int))
    where assign :: [Int] -> Int -> Seq.Seq (Seq.Seq Int) -> Seq.Seq (Seq.Seq Int)
          assign []     _   seq = seq
          assign (x:xs) dig seq = assign xs dig $
                                    Seq.update idx
                                      ((Seq.index seq idx) Seq.|> x) seq
           where idx = digit x dig

radixSort     :: [Int] -> [Int]
radixSort []   = []
radixSort xs   = sort xs 0 (length . show . maximum $ xs)
    where sort xs n m = if n >= m
                         then xs
                         else sort buckets (n+1) m
           where buckets = (concat $ assignBuckets xs n)

main = do
  args <- getArgs
  print . radixSort . map (read :: String -> Int) $ args

```

This sort (if done properly I haven't checked the asymptotic runtime 100%) should run i O(kN) where k is the number of digits in the largest number which is good if k is constant.
> 0 votes

# Answer
oh lawd

```
<?php

    $input = "1, 4, 7, 2, 5";

    $array = explode(', ', $input);

    $max = '';

    $min = '';

    foreach ($array as $value) {

        if (is_numeric($value) === true) {

            $max = ($max < $value ? $value : $max);

            $min = ($min > $value ? $value : $min);
        }
    }

    $output = '';

    for ($i == $min; $i <= $max; $i++) {

        if (in_array($i, $array) === true) {

            $output .= $i . ', ';
        }
    }

    echo trim($output, ', ');

?>

```

http://codepad.org/GioGvxzl
> 0 votes

---
Tags: sorting, code-bowling
---


title: Sorted Lexical Partition of a Number

text:
# Question
Title: Sorted Lexical Partition of a Number
The challenge is really simple: given a number, you split its digits into an array of smaller numbers such that the resulting numbers are non-decreasing. The catch is that you have to split it such that the array length is maximal.

**Confused?**

* You are given a positive integer via STDIN (or closest alternative), command-line argument or function argument in any convenient, unambiguous input format.
* You have to partition the number's decimal digits into contiguous, disjoint groups.
* The array of numbers represented by these digit groups should be sorted (in the usual, non-decreasing order) **without rearranging the groups**.
* In cases where more than one such partition exists, you have to partition the input into as many numbers as possible. In the case of ties, return one such result.
* You can output the array to STDOUT (or closest alternative) or as a function return value. In case of STDOUT (or closest alternative), the array should be printed in any convenient, unambiguous list format.
* The split numbers should not have leading zeroes. So for instance `1002003` cannot be printed as either `[1, 002, 003]` or `[1, 2, 3]` and the only valid answer for it is `[100, 2003]`.

**Test cases:**

```
123456 -> [1, 2, 3, 4, 5, 6]
345823 -> [3, 4, 5, 8, 23]
12345678901234567890 -> [1, 2, 3, 4, 5, 6, 7, 8, 90, 123, 456, 7890]
102 -> [102]
302 -> [302]
324142 -> [3, 24, 142] OR [32, 41, 42]
324142434445 -> [32, 41, 42, 43, 44, 45]
1356531 -> [1, 3, 5, 6, 531]
11121111111 -> [1, 1, 1, 2, 11, 11, 111]
100202003 -> [100, 202003]

```

**Scoring**

This is code-golf so shortest code in bytes wins.

# Answer
> 10 votes
# Pyth, 34

```
FNyUz#aYmv:zhdedC,+0N+NlzB)efqSTTY

```

Try it online here. Notice, this has a time (and space) complexity of O(n). Therefore the test case `12345678901234567890` takes too long in the online compiler. Use the offline one instead (1 minute on my laptop).

This is only my first attempt. There might be some room for improvements.

First some ideas how my algorithm works.

* I interpret the input as string and not as a number.
* Then I create all possible subsets of `[0, 1, 2, ..., len(n-1)]`
* For each of these subsets (lets take `[1, 4, 5]`), I split the input string into part using these numbers. `[input[0:1], input[1, 4], input[4,5], input[5,len(input)]]`.
* Afterwards I try to convert these numbers into strings. There can be two problems. Pyth (or Python) throws an exception for an empty string, and for a string of numbers starting with `0`. Therefore I use a `try - catch` block (actually infinity loop with an immediate break). If converting was successfully, I add the result to a list `Y`.
* After I handled all subsets, I filter the list `Y` for results, that are already sorted and print the last one (the last one has the most groups).

Now the detailed explanation:

```
                            Implicit: z = input() (z is a String!)
                                      Y = empty list
FNyUz                       for each subset N of [0, 1, 2, ..., len(z)-1]:

     #                         start try-catch block (actually an infinite loop,
                               but the Python implementation uses a try catch.

      aY                          append to Y:
                C,+0N+Nlz            zip([0] + N, N + [len(z)])
        m                            map each element d to
          :zhded                     z[d[0]:d[-1]]
         v                           evaluated
                         B        if this didn't throw an exception already, end the infinite loop
                          ) end for loop

 f    Y      filter Y for elements T, for which
  qSTT           sorted(T) == T
e            and print the last one (the subsets generated with yUz are sorted
             by length, so the last one has the most groups)

```

# Answer
> 6 votes
# Mathematica, ~~134~~ 127 bytes

This is pretty inefficient since it generates a *lot* more partitions than the valid ones. The `324142434445` test case runs within a few seconds, but I wouldn't try `12345678901234567890`.

```
f/@Last@Select[Needs@"Combinatorica`";f=FromDigits;SetPartitions[d=IntegerDigits@#],0<=##&@@f/@#&&Join@@#==d&&#~FreeQ~{0,__}&]&

```

This defines an unnamed function which takes an integer and returns a list of integers.

## Explanation

The reading order of this code is a bit all over the place, so I'll break down in the order it's intended to be read (and evaluated for the most part):

* `d=IntegerDigits@#` get the decimal digits of the input and assign this list to `d`.
* `SetPartitions` (which requires `Needs@"Combinatorica`";`) gives me all partitions of this. However, it returns a lot more than I actually want since it treats the input as a *set*. This is what makes it inefficient, but I'm using this because the shortest way I know to get all list partitions is much longer. As an example, if the list was `{1, 2, 3}` the function would return:

```
{{{1, 2, 3}}, {{1}, {2, 3}}, {{1, 2}, {3}}, {{1, 3}, {2}}, {{1}, {2}, {3}}}

```

Note that a) the consecutive partitions are all in the right order and b) the partitions are sorted from coarsest to finest.
* `Select[...,...&]` then filters this list by the anonymous function passed in as the second argument.
    + `Join @@ # == d` checks that we've actually got a list partition instead of a general set partition.
    + `#~FreeQ~{0, __}` checks that no partition starts with a leading zero.
    + `0 <= ## & @@ f /@ #` is a bit more obscure. First we map `FromDigits` onto each list in the partition to recover the numbers represented by the digits. Then we apply `0 <= ##` to those numbers, where `##` refers to all the numbers. If the partition is `{1, 23, 45}` then this expands to `0 <= 1 <= 23 <= 45`, so it checks that the array is sorted.
* `Last@` then gives me the last partition left after filtering - this works because `SetPartitions` already sorted the partitions, such that the finest ones are at the end.
* Finally, `f/@` recovers the numbers from the digit lists.

# Answer
> 5 votes
# Python 3, 134 bytes

```
def f(s,n=0,L=[],R=[],i=0):
 while s[i:]:i+=1;m=int(s[:i]);R=max([f(s[i:],m,L+[m]),R][m<n or"1">s[i:]>"":],key=len)
 return[L,R][s>""]

```

It's a little messy, but oh well. The program just generates all valid partitions recursively. The interesting part is that to disallow leading zeroes, all that was necessary was an additional `or "1">s[i:]>""` condition.

Takes input like `f("12345678901234567890")` and returns a list of ints.

# Answer
> 4 votes
# Pyth, ~~62~~ ~~61~~ 60

```
JlzKkef&qJsml`dTqTSTolNmmibTcjKsC,z+m>Ndt>+*J]0jk2_JKNU^2-J1

```

## Explanation

The algorithm works by generating all binary numbers between `0` (inclusive) and `2^(n-1)` (exclusive), where `n` is the length of the input.

The binary digits of each are then mapped to a separator (`N`) for 1 and nothing for 0.

These characters are then inserted between each input character, and the result is split by `N`, yielding a list.

The values in the lists are then parsed to integers, and the lists are sorted by length. Then all that is left is to filter out non-sorted ones and ones that have been split at leading zeroes, after which the longest list is picked.

```
Jlz                                                   set J to len(input)
Kk                                                    set K to ""
e                                                     take the last of:
 f&                                                    only take lists where:
   qJsml`dT                                             sum of string lengths of items
                                                        is equal to length of input and
           qTST                                         list is in order
               olN                                       sort by length
                  m                                       map k over...
                   mibT                                    convert items to int (base-10)
                       c                        N           split by N
                        jK                                   join by ""
                          s                                   sum to combine tuples
                           C,z                                 zip input with
                              +                K                append [""] for equal lengths
                               m>Nd                              replace 1 with N, 0 with ""
                                   t                              take all but first
                                    >        _J                    take len(input) last values
                                     +                              pad front of binary with
                                      *J]0                           [0] times input's length
                                          jk2                        current k in binary
                                                 U^2-J1  range 0..2^(len(input)-1)-1

```

# Answer
> 1 votes
# Pyth, 25 bytes

```
ef&&Fmnhd\0T.A<V=NsMTtN./

```

Try it online!

How it works:

```
ef&&Fmnhd\0T.A<V=NsMTtN./  Q = eval(input())
                         ./  all partitions of Q
 f                       ./  filter all partitions of Q where:
  &                            both:
   &Fmnhd\0T                     neither substring starts with "0"
                               and:
            .A<V=NsMTtN          all entries are less than their proceeding ones
e                            returns the last amongst the filtered partitions

```

# Answer
> 0 votes
# J, 109 bytes

Very long but at least takes up O(n * (2n)!) memory and O(n * log(n) * (2n)!) time where n is the length of the input. (So don't try to run it with more than 5 digits.)

```
f=.3 :0
>({~(i.>./)@:(((-:/:~)@(#$])*#)@>))<@".(' 0';' _1')rplc"1~(#~y-:"1' '-."#:~])(i.!2*#y)A.y,' '#~#y
)

```

The function takes the input as a string.

Examples:

```
   f every '5423';'103';'1023'
  5 423
103   0
 10  23

```

Method:

* Add the same number of spaces to the input as it's length.
* Permute it in every possible way.
* Check if the spaceless string is the same as the input (i.e. it's a partition of it).
* Replace ' 0's to ' \_1's to invalidate leading zero solutions.
* Evaluate each string.
* Find the longest list which is also sorted. This is the return value.

# Answer
> 0 votes
# Haskell, 161 bytes

```
(#)=map
f[x]=[[[x]]]
f(h:t)=([h]:)#f t++(\(a:b)->(h:a):b)#f t
g l=snd$maximum[(length x,x::[Int])|x<-[read#y|y<-f l,all((/='0').head)y],and$zipWith(>=)=<<tail$x]

```

Test run:

```
*Main> mapM_ (print . g) ["123456","345823","12345678901234567890","102","302","324142","324142434445","1356531","11121111111","100202003"]
[1,2,3,4,5,6]
[3,4,5,8,23]
[1,2,3,4,5,6,7,8,90,123,456,7890]
[102]
[302]
[32,41,42]
[32,41,42,43,44,45]
[1,3,5,6,531]
[1,1,1,2,11,11,111]
[100,202003]

```

How it works: the helper function `f` splits the input list into every possible list of sublists. `g` first discards those with a sublist beginning with `0` and then those without the proper order. Pair every remaining list with it's length, take the maximum and discard the length part again.

---
Tags: code-golf, number, combinatorics, set-partitions
---


title: Reverse Engineer Bracket Rectangles

text:
# Question
Title: Reverse Engineer Bracket Rectangles
Every programmer knows that rectangles  are really fun. To exacerbate this fun, these cute and fuzzy diagrams can be transformed into groups of interwoven brackets.

This challenge is the inverse of my previous.

Let's say you have a group of interlocking rectangles like so:

```
   +------------+
   |            |
+--+-+     +----+-+
|  | |     |    | |
|  | | +---+--+ | |
|  | | |   |  | | |
+--+-+ | +-+--+-+-+-+
   |   | | |  | | | |
   |   | | |  | | | |
   |   | | |  | | | |    +-+
   |   +-+-+--+ | | |    | |
   |     | |    | | |  +-+-+-+
   +-----+-+----+ | |  | | | |
         | |      | |  | +-+ |
         | +------+ |  |     |
         |          |  |     |
         +----------+  +-----+

```

Additional Notes:

* No two `+`s will ever be adjacent
* No two rectangles will ever share an edge or corner
* **There will only ever be at most one vertical edge in each column**

The first step is to look at the left-most edge of any rectangle. Assign it one of four bracket types `({[<`. I choose `[`.

```
   +------------+
   |            |
[--+-]     +----+-+
[  | ]     |    | |
[  | ] +---+--+ | |
[  | ] |   |  | | |
[--+-] | +-+--+-+-+-+
   |   | | |  | | | |
   |   | | |  | | | |
   |   | | |  | | | |    +-+
   |   +-+-+--+ | | |    | |
   |     | |    | | |  +-+-+-+
   +-----+-+----+ | |  | | | |
         | |      | |  | +-+ |
         | +------+ |  |     |
         |          |  |     |
         +----------+  +-----+

```

Now look at the second left-most rectangle. Since it overlaps a `[` rectangle, it must be of a different type. I choose `(`.

```
   (------------)
   (            )
[--(-]     +----)-+
[  ( ]     |    ) |
[  ( ] +---+--+ ) |
[  ( ] |   |  | ) |
[--(-] | +-+--+-)-+-+
   (   | | |  | ) | |
   (   | | |  | ) | |
   (   | | |  | ) | |    +-+
   (   +-+-+--+ ) | |    | |
   (     | |    ) | |  +-+-+-+
   (-----+-+----) | |  | | | |
         | |      | |  | +-+ |
         | +------+ |  |     |
         |          |  |     |
         +----------+  +-----+

```

The next left-most rectangle does not intersect with any previous rectangle, but does nest within the previous. I choose to assign it `(` again. It is normally a good guess to assign a rectangle the same type as what it is nesting inside if possible, but sometimes backtracking is needed.

```
   (------------)
   (            )
[--(-]     +----)-+
[  ( ]     |    ) |
[  ( ] (---+--) ) |
[  ( ] (   |  ) ) |
[--(-] ( +-+--)-)-+-+
   (   ( | |  ) ) | |
   (   ( | |  ) ) | |
   (   ( | |  ) ) | |    +-+
   (   (-+-+--) ) | |    | |
   (     | |    ) | |  +-+-+-+
   (-----+-+----) | |  | | | |
         | |      | |  | +-+ |
         | +------+ |  |     |
         |          |  |     |
         +----------+  +-----+

```

This next rectangle can be assigned `[` again.

```
   (------------)
   (            )
[--(-]     +----)-+
[  ( ]     |    ) |
[  ( ] (---+--) ) |
[  ( ] (   |  ) ) |
[--(-] ( [-+--)-)-+-]
   (   ( [ |  ) ) | ]
   (   ( [ |  ) ) | ]
   (   ( [ |  ) ) | ]    +-+
   (   (-[-+--) ) | ]    | |
   (     [ |    ) | ]  +-+-+-+
   (-----[-+----) | ]  | | | |
         [ |      | ]  | +-+ |
         [ +------+ ]  |     |
         [          ]  |     |
         [----------]  +-----+

```

This next rectangle is kinda fun. It intersects both a `(` and a `[` rectangle, so I could call it a `{` rectangle (or `<` but nobody likes those).

```
   (------------)
   (            )
[--(-]     {----)-}
[  ( ]     {    ) }
[  ( ] (---{--) ) }
[  ( ] (   {  ) ) }
[--(-] ( [-{--)-)-}-]
   (   ( [ {  ) ) } ]
   (   ( [ {  ) ) } ]
   (   ( [ {  ) ) } ]    +-+
   (   (-[-{--) ) } ]    | |
   (     [ {    ) } ]  +-+-+-+
   (-----[-{----) } ]  | | | |
         [ {      } ]  | +-+ |
         [ {------} ]  |     |
         [          ]  |     |
         [----------]  +-----+

```

The last two rectangles aren't that bad. They can be of any two different types.

```
   (------------)
   (            )
[--(-]     {----)-}
[  ( ]     {    ) }
[  ( ] (---{--) ) }
[  ( ] (   {  ) ) }
[--(-] ( [-{--)-)-}-]
   (   ( [ {  ) ) } ]
   (   ( [ {  ) ) } ]
   (   ( [ {  ) ) } ]    {-}
   (   (-[-{--) ) } ]    { }
   (     [ {    ) } ]  <-{-}->
   (-----[-{----) } ]  < { } >
         [ {      } ]  < {-} >
         [ {------} ]  <     >
         [          ]  <     >
         [----------]  <----->

```

**Reading off the rectangles, I get `[(]([{))}]<{}>`.** This would be one possible output for the above input. Here's a list of many possible options, not exhaustive:

```
[(]([{))}]<{}>
<(>(<{))}>{()}
{<}[{(]>)}[<>]
any of the 4! permutations of ([{<, you get the idea...

```

## Input

ASCII-art rectangles, on the assumptions that they are unambiguous (see notes above) and can be properly converted into a string of brackets. You may assume either no trailing spaces or padded to a rectangle, with optional trailing newline. There will be no leading whitespace.

## Output

Any one of the valid bracket strings that obeys the intersection restrictions of the rectangles. Other than an optional trailing newline, there should be no other characters than brackets. The main rule is, if two squares intersect, then they should be assigned different bracket types.

## Goal

This is code-golf, (lack of) quantity over quality.

# Answer
> 2 votes
# Python 3, 519 bytes

```
def c(i):
 a,b,c,d={},0,[],{}
 for e in map("".join,zip(*i.split("\n"))):
  if"+"in e:
   f=e.index("+"),e.rindex("+")
   if f in a:j=a.pop(f);d[j]=f+(d[j],len(c));c.append(j)
   else:a[f]=b;d[b]=len(c);c.append(b);b+=1
 g,h={},0
 while d:
  i={list(d)[0]};
  for j,(k,l,m,n)in d.items():
   for(o,p,q,r)in(d[v]for v in i):
    if not(m>r or n<q or k>p or l<o or(q<m<n<r and o<k>l<p)):break
   else:i.add(j)
  for j in i:del d[j];g[j]=h
  h+=1
 s,u=set(),""
 for t in c:u+="[{(<]})>"[g[t]+4*(t in s)];s.add(t)
 return u

```

Here's a first attempt at a solution. The algorithm used purely looks at the corners in the diagram, abusing the fact only one vertical line can occur in a column, and therefore the first and last + in a column must be the corners of a rectangle. It then collects all rectangles and performs a naive (and somewhat nondeterministic) search for collisionless groups. I am not sure if this will always find the most optimal solution, but it worked for all examples I tried so far. Alternatively it could be replaced by a brute-force search for the least amount of groups.

Input: a string containing the ascii art. No trailing newline, and all lines must be padded to the same length using spaces. It is also completely fine with you not putting any of the |'s or -'s in there as it just looks at the corners.

As the golfing is quite simple (just whitespace minimalization and variable renaming mostly) it could probably be shorter, but as there are no other answers on this yet I'll leave it like this for now.

---
Tags: code-golf, string, ascii-art, balanced-string
---


title: Choose The Powerball Numbers!

text:
# Question
Title: Choose The Powerball Numbers!
Powerball is an American lottery that has recently gained attention because the current jackpot (as of January 11, 2016) is the largest lotto prize in history, at about $1.5 billion (USD).

Powerball players choose 5 distinct numbers from 69 numbered white balls, and 1 one "Powerball" number from 26 numbered red balls. They win the jackpot if their five white ball choices match what was drawn in any order, *and* if they chose the correct "Powerball" number.

So the chances of winning the jackpot are 1 in `(69 choose 5)*(26 choose 1)` or `((69*68*67*66*65)/(5*4*3*2*1))*26`, which is **1 in 292,201,338**

No one won the jackpot in the most recent drawing on January 9, 2016, but perhaps someone will win the next drawing on January 13, 2016, 10:59 pm ET.

# Challenge

Write a program or function that simulates a Powerball drawing, taking no input but outputting 5 *distinct* random numbers from 1 to 69 inclusive, and then one random "Powerball" number from 1 to 26 inclusive (which could be a repeat of one of the 5 initial numbers).

The "Powerball" number should always be the last number in the output, but otherwise the order of the first 5 numbers does not matter.

The 6 numbers should be output **in decimal**, either space separated or newline separated, with an optional single trailing newline. Commas, brackets, and other characters are not allowed in the output.

So these would be valid outputs (using the numbers from the last drawing):

```
32 16 19 57 34 13
```

```
32
16
19
57
34
13
```

**All 292201338 possible outcomes should be possible with uniform probability.** You may use built-in pseudo-random number generators and assume they meet this standard.

Here is an ungolfed reference implementation that works in Python 2 or 3:

```
import random
print(' '.join(map(str, random.sample(range(1,70), 5) + [random.randint(1, 26)])))

```

**The shortest code in bytes wins.**

---

Note that I have no affiliation with Powerball and don't really suggest that you play. But if you win anything from numbers generated by one of the programs here, I'm sure we'd love to hear about it. :D

# Answer
> 28 votes
## Dyalog APL, 10 bytes

```
(5?69),?26

```

Dyadic `?` is ⍺ distinct random numbers in \[1,⍵\], and monadic `?` is a single random number.

Try it here.

# Answer
> 13 votes
## CJam, 16 bytes

```
69,mr5<26mr+:)S*

```

```
69,   range(69)
mr    shuffle the generated array
5<    first 5 elements
26mr  random number 0..25
+     concat to array
:)    increment each array element
S*    join with spaces

```

Try it online.

# Answer
> 8 votes
# MATL, 10 bytes

```
69 5Zr26Yr

```

Uses current version (9.2.0) of the language/compiler.

### Example

With compiler run on Matlab:

```
>> matl
 > 69 5Zr26Yr
 >
66
59
64
56
29
12

```

With compiler run on Octave:

```
>> matl
 > 69 5Zr26Yr
 >
2 69 41 44 23
22

```

The first five numbers are separated by space, not by newline. This is due to Octave's underlying `randsample` function behaving differently from Matlab's (and has been corrected in a new version of the compiler). Anyway, newline and space are both allowed by the challenge.

*Edit (April 4, 2016)*: **Try it online!**

### Explanation

```
69 5Zr    % randsample(69,5), without replacement by default. Gives a 5x1 column vector
26Yr      % randi(26). Gives single number
          % implicit display

```

See relevant Matlab functions: `randsample` and `randi`.

# Answer
> 7 votes
# Ruby, ~~33~~ 32

```
p *[*1..69].sample(5),rand(26)+1

```

Ruby happens to have a built-in method, sample, that selects random values from an array without replacement. Thanks to QPaysTaxes for pointing out that I don't need the parens.

# Answer
> 6 votes
# R, ~~30~~ 29 bytes

```
cat((s=sample)(69,5),s(26,1))

```

The `sample` function performs simple random sampling from the input. If a single integer is given as the first argument, sampling is done from 1 to the argument. The sample size is the second argument. We're employing the default option of sampling without replacement.

Try it online

# Answer
> 6 votes
## Python 3.5, 63 bytes

```
from random import*
print(*sample(range(1,70),5),randint(1,26))

```

It's basically the reference implementation golfed. Note that 3.5 is necessary to splat in a non-last argument.

# Answer
> 6 votes
## PowerShell v2+, ~~31~~ 27 bytes

```
1..69|Random -c 5;Random 27

```

Requires version 2 or newer, as `Get-Random` wasn't present in v1 (the `Get-` is implied, and `-Maximum` is positional). Output is newline separated.

### Ungolfed:

```
Get-Random -InputObject (1..69) -Count 5
Get-Random -Maximum 27

```

# Answer
> 6 votes
# Octave, ~~35~~ 32 bytes

Calvin's Hobbies confirmed that `ans =` was OK when using a function, so:

```
@()[randperm(69)(1:5),randi(26)]

```

It has similarities to Memming's answer, but it uses direct indexing that's only possible in Octave, and it's ~~5~~ 7 bytes shorter, so I figured it was worth posting anyway.

`randperm(69)` creates a list with a random permutation of the numbers 1-69. It's possible to directly index the list (not possible in MATLAB) to only get the first 5 numbers like this `(1;5)`. The list is followed by `randi(26)` which returns a single number between 1 and 26.

**Old:**

```
disp([randperm(69)(1:5),randi(26)])

```

The resulting list is displayed using `disp`.

# Answer
> 5 votes
# Shell + coreutils, 31

```
shuf -i1-69 -n5
shuf -i1-26 -n1

```

# Answer
> 4 votes
# Pyth - ~~13~~ ~~14~~ 13 bytes

Major golfing possible, this was just a FGITW.

```
jb>5.SS69hO26

```

Try it online here.

# Answer
> 4 votes
## C#, ~~153 bytes~~ 140 bytes

Thanks to "McKay":

```
string.Join(" ",Enumerable.Range(1,69).OrderBy(e=>Guid.NewGuid()).Take(5).Concat(Enumerable.Range(1,26).OrderBy(e=>Guid.NewGuid()).Take(1)))

```

153 bytes solution:

```
string.Join(" ",Enumerable.Range(1,69).OrderBy(e=>Guid.NewGuid()).Take(5))+" "+string.Join(" ",Enumerable.Range(1,26).OrderBy(e=>Guid.NewGuid()).Take(1))

```

Simple solution using Linq and shuffling using GUID.

# Answer
> 4 votes
## MATLAB, 40

```
x=randperm(69);disp([x(1:5) randi(26)])

```

I know. It's the boring solution.

# Answer
> 4 votes
## PHP, 69 bytes

```
<?foreach(array_rand(range(1,69),5)as$k)echo$k+1," ";echo rand(1,26);

```

Pretty straight forward answer. Generate a 1-69 `range`, then use `array_rand` to grab 5 random keys from the array, and echo out the `$k+1` value (0-indexed), then echo a random int from 1-26.

# Answer
> 2 votes
# Mathematica, 64 bytes

```
StringRiffle@Append[Range@69~RandomSample~5,RandomInteger@25+1]&

```

Quite simple.

# Answer
> 2 votes
# Brachylog, 40 bytes

```
1:5e,68{I`random(I)+1=Z`Z=w,"
"w}\;25:1&

```

### Explanation

Brachylog doesn't have a built-in for random numbers (yet...) so we have to use an SWI-Prolog predicate for that: `random/1`. We can input SWI-Prolog code in Brachylog using backquotes.

```
1:5e,                             \  § Enumerate from 1 to 5 using \ (backtrack), which
                                     § evaluates to false and thus constructs a loop

     68{                         }   § Declare sub-predicate 1 and call it with 68 as input

        I`random(I)+1=Z`             § Z is the arithmetic expression 'random(I) + 1' where
                                     § I is the input of the sub-predicate

                        Z=w,         § Evaluate Z and write it
                            "\n"w    § Write a new line

;                                    § Else (we will reach this after the 5th iteration of
                                     § the enumeration, since \ is always false)

25:1&                                § Call the sub-predicate 1 with 25 as input

```

# Answer
> 2 votes
# JavaScript (ES6), ~~106~~ ~~86~~ 84 bytes

```
F=(s=new Set,r=Math.random)=>s.size<5?F(s.add(r()*69+1|0)):[...s,r()*26|0+1].join` `

```

Since we can't uniquely sample randoms in JavaScript, this works by creating a Set (which only holds unique values), recursively adding randoms (1-69) until there are 5 unique ones, appending a random number (1-26), then joining and returning it all out.

# Answer
> 2 votes
### Ruby, ~~47~~ ~~43~~ 39 bytes

```
puts *(1..69).to_a.sample(5),rand(26)+1

```

I think it can be golfed more, but I'll work on that once I'm done admiring how pretty this code looks, considering.

It works pretty much the same way as everything else: Take an array of the numbers 1 to 69, shuffle them, get the first five, output those, then output a random number between 1 and 26.

I went through a few iterations before posting this:

```
puts (1..69).to_a.shuffle.first(5).join(' ')+" #{rand(26)+1}"  #61
puts (1..69).to_a.shuffle[0..5].join(' ')+" #{rand(26)+1}"     #58
puts (1..69).to_a.shuffle[0..5].join('<newline>'),rand(26)+1   #52
puts *('1'..'69').to_a.shuffle[0..5],rand(26)+1                #47
puts *('1'..'69').to_a.sample(5),rand(26)+1                    #43

```

(where `<newline>` is replaced with an actual newline)

EDIT: Whoops, didn't see the preexisting Ruby answer. I stumbled on `sample` and was scrolling down to edit my answer, but then I saw it... Oh well. My final score is 43 bytes, but I'll keep golfing a little to see how well I can do.

# Answer
> 2 votes
# Elixir, 83 Bytes

```
Enum.reduce Enum.take_random(1..69,5)++[Enum.random(1..26)],fn(x,a)->"#{a} #{x}"end

```

When just `IO.puts`ing an array of integers, Elixir will interpret the integers as characters and therefore output some string instead of the desired powerball numbers. So, we have to reduce the integer array down to a string.

# Answer
> 1 votes
## PARI/GP, ~~71~~ 70 bytes

```
apply(n->print(n),numtoperm(69,random(69!))[1..5]);print(random(26)+1)

```

It generates a random permutation of \[1..69\], then takes the first 5.

Unfortunately this is an inefficient user of randomness, consuming an average of 87 bytes of entropy compared to the information-theoretic ideal of 3.5. This is mainly because the entire permutation is generated instead of just the first 5 members, and also because the perms are ordered (losing lg 5! =~ 7 bits). Further, `random` uses a rejection strategy rather than using arithmetic coding. (This is because PARI uses Brent's xorgen, which is fast enough that the overhead from more complicated strategies is rarely worthwhile.)

There are three 'obvious' changes which do not work under the current (2.8.0) version of gp. `random` and `print` could be stored in variables, and `print` could be called directly rather than via the anonymous `->` function:

```
r=random;apply(p=print,numtoperm(69,r(69!))[1..5]);p(r(26)+1)

```

Together these would save 9 bytes. Unfortunately both functions are valid without arguments, and hence are evaluated immediately rather than stored, so these do not compute the desired output.

# Answer
> 1 votes
# Perl 5, 59 bytes

```
{say for(sort{-1+2*int rand 2}1..69)[0..5];say$==1+rand 25}

```

It's a subroutine; use it as:

```
perl -M5.010 -e'sub f{...}f'

```

# Answer
> 1 votes
## PHP, 65 bytes

```
<?=join(' ',array_rand(array_flip(range(1,69)),5))." ".rand()%26;

```

Thanks to the other PHP answer on this page. I wrote up a program on my own, and it turned out to be the exact same answer as the one written by Samsquanch, which drove me to take it a step further to save a few bytes.

If anyone can figure out a way to append one array to another in here that's less than the 5 bytes it takes me to join the powerball number on after, I would greatly appreciate it, cause it's driving me nuts! The best I could come up with would be after `array_rand` and before `join`, having a statement something like `+[5=>rand()%25]`, but that's an extra byte over just concatenating it on after.

```
<?=                                                              // This represents an inline 'echo' statement
                                  range(1,69)                    // Get an array of all numbers from 1 to 69 inclusive
                       array_flip(           )                   // Swap the keys and values.
            array_rand(                       ,5)                // Get a random subset of five keys.
   join(' ',                                     ).rand()%26     // Concatenate the array with spaces, along with the powerball number

```

Run it through the command line. Sample:

```
C:\(filepath)>php powerball.php

```

Output:

```
 12 24 33 67 69 4

```

# Answer
> 0 votes
## Intel x86 Machine code, 85 bytes

```
¿I ±‰ø1Ò»E ÷óB‰Ðè+ ‰þÑç÷ƒÇþÉ„Éuâ‰ø1Ò» ÷óB‰Ðè
 0äÍ¸ Í±ëÆÔ
00†Äˆã´ÍˆØÍ° ÍÃ

```

Well it does sometimes print the same numbers if so, just try again by pressing a key.

Compile with:

```
nasm file.asm -o file.bin

```

Make sure to align it to a floppy size (add zeros at the end) in order to mount it to a vm (it does not need any operating system).

Disassembly:

```
BITS 16
ORG 0x7c00

mov di,73 ;starting seed
mov cl,5 ;we need five numbers

loop:

mov ax,di

xor dx,dx
mov bx,69
div bx
inc dx
mov ax,dx

call print_rnd_number

mov si,di
shl di,1
add di,si
add di,7

dec cl

test cl,cl
jne loop

mov ax,di

xor dx,dx
mov bx,26
div bx
inc dx
mov ax,dx

call print_rnd_number

xor ah,ah
int 0x16
mov ax,0x0002
int 0x10
mov cl,5
jmp loop

print_rnd_number:
aam
add ax,0x3030
xchg al,ah
mov bl,ah
mov ah,0x0E
int 0x10
mov al,bl
int 0x10
mov al,' '
int 0x10
ret

```

# Answer
> 0 votes
# C, 142 bytes

```
i,x[6],n;main(j){for(srand(time(0));i<6;n-i?0:printf("%d ",x[i]),i++)for(x[n=j=i]=(69-i/5*43)*(rand()/2147483647.)+1;i<6&&j--;)i-=x[i]==x[j];}

```

Not terribly happy with this solution as it feels like there should be more golfing opportunity. I'll look at it again tomorrow with fresh eyes. Try it here.

# Answer
> 0 votes
# Swift, 165 bytes

```
import UIKit;var a=[Int]();for i in 0...5{func z()->Int{return Int(arc4random_uniform(i<5 ?68:25)+1)};var n=z();while i<5&&a.contains(n){n=z()};a.append(n);print(n)}

```

Can quickly be run in an Xcode Playground.

**EDIT:** Current problem here is that it's theoretically possible for this to run forever in the while loop if arc4random\_uniform somehow keeps pulling the same number. The odds of that happening, for any significant length of time, are probably better than the odds of winning the Powerball.

# Answer
> 0 votes
# Perl 6,  ~~32~~  31 bytes

```
# space is necessary so that the parens denote a list
# rather than being part of the call to `put`
put (pick(5,1..69),(1..26).pick) # 32 bytes
# 25 35 57 67 62 24␤

```

---

Turning it into a function that returns a string, I can remove 4 bytes (`put␠`) while only adding 3 (`{~` `}`)

```
{~(pick(5,1..69),(1..26).pick)} # 31 bytes

```

Usage:

```
say {...}().perl; # use .perl to prove it returns a string
# "25 35 57 67 62 24"

```

---

### If a function were allowed to return a list of the values, the following would also work.

( Otherwise it would be the same as above but within `{ }` )

* function that returns a single flat list

```
{|pick(5,1..69),(1..26).pick} # 29 bytes
# (25,35,57,67,62,24)

```
* function that returns a list with the first 5 numbers in a sub list

```
{pick(5,1..69),(1..26).pick} # 28 bytes
# ((25,35,57,67,62),24)

```
* function that returns a list with the first 5 in a sub list, and the Powerball in another sub list

```
{pick(5,1..69),pick 1,1..26} # 28 bytes
# ((25,35,57,67,62),(24,))

```

# Answer
> 0 votes
# Seriously, 35 bytes

My first attempt at an answer in a golfing language.

Feels longer than it should have to be.
The repetition could likely be removed with **W**, but it seems to be broken in the online interpreter and I don't want to post untested code.

Too bad **{** doesn't work on lists.

**Code:**

```
:70:1xi J{. J{. J{. J{. J{.:26:Ju.

```

**Hex dump:**

```
3a37303a317869204a7b2e204a7b2e204a7b2e204a7b2e204a7b2e3a32363a4a752e7f

```

**Explanation:**

```
:70:1x                       # Push a list of the numbers 1-69
i                            # Explode list
 J{.                         # rotate stack random(len(stack)) times and pop/print
 J{. J{. J{. J{.             # same thing 4 more times
:26:Ju.                      # print random number in 1-26
                             # (7F) unprintable, terminate without explicit printing

```

Online interpreter

# Answer
> 0 votes
# Lua, 96 Bytes

A simple solution, using a table as a set by putting the value inside it as `table[value]=truthy/falsy`to be able to check if they are inside it or not.

I lose 5 bytes because I have to set the first value of my table, else I won't go inside the `while(o[n])`loop and will simply output `n` before using the random function. As Lua uses 1-based tables, I also have to force it to put its first value to the cell `[0]`, otherwise I couldn't output a `1`.

```
m,n,o=math.random,0,{[0]=0}for i=1,5 do while(o[n])do n=m(69)end o[n]=0 print(n)end print(m(26))

```

### Ungolfed:

```
m,n,o=math.random,0,{[0]=0}
for i=1,5
do
  while(o[n])
  do
    n=m(69)
  end
  o[n]=0
  print(n)
end
print(m(26))

```

# Answer
> 0 votes
## C++, 252 bytes

### Golfed:

```
#include<iostream>
#include <random>

int main(){std::random_device rd;std::mt19937 gen(rd());std::uniform_int_distribution<> dis(1,69);for(int c=0;c<=5;c++){std::cout<<dis(gen)<<" ";}int x=dis(gen);while(x>26||x<1){x=dis(gen);}std::cout<<x;return 0;}

```

### Ungolfed:

```
#include<iostream>
#include <random>

int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(1, 69);
    for(int c = 0; c <= 5; c++){
        std::cout<<dis(gen)<<" ";
    }
    int x = dis(gen);
    while (x > 26 || x < 1){
        x = dis(gen);
    }
    std::cout<<x;
    return 0;
}

```

---
Tags: code-golf, number, game, random, probability-theory
---