The Strange Unsorting Machine for Nefarious Purposes

Question

Good Evening Golfers!

Your challenge is to completely unsort a series of numbers.

Input

Exactly 100 integers will be fed to your program. Your program may accept the input either as a file, or via stdin. Each integer will be separated by a newline character.

Those 100 integers will range from the minimal to the maximal values of a signed integer in your chosen language.

There will be no duplicate values. The values may be ordered, unordered or partially ordered - your program should be able to handle each case.

Output

The output must be each of the 100 integers, completely unsorted, each separated by a newline character. The output may be via stdout, or to a file.

Completely Unsorted means that no value is adjacent to any value which it would be adjacent to if the list were completely sorted in an ordered sequence.

Score

1 point per character, and lowest score wins. There is a bonus of -100 for any solution using no built in or library sorting functions. There is a bonus of -20 for any solutions using no built in random number functions.

I have tried to define this question as completely as possible. If you have any questions, please ask. If you have any comments on how I could do better next time, please let me know.

Fore!

Answer 1

GolfScript (score 27 - 120 = -93)

~].,{{.2$<{\}*}*]}*.(;+2%n*

Note: that $ is referencing an element on the stack. There is sorting, but it's done with an manually coded bubble sort.

Thanks to Howard, for -90 => -92; and Ilmari, who inspired -92 => -93.

Answer 2

Python -26

(94-120): New, crude approach. Keep popping lowest elements into new list to get the elements sorted, then iterate:

t=l=[]
i=N=100
exec't=t+[input()];'*N+'l+=[t.pop(t.index(min(t)))];'*N+'print l[i%N];i+=3;'*N

Python -13

(107-120): First approach: Removes four lowest elements at a time, then print these four in another order:

exec'l=[]'+'+[input()]'*100
while l:
 a,b,c,d=eval('l.pop(l.index(min(l))),'*4)
 for e in[b,d,a,c]:print e

Answer 3

C: 11 (131 - 120)

The programm reads from stdin and does a simple insert sort, after that it prints the nth together with th n+50th number, like many of the other solutions.

main(){int*i,a[101],*j=a;while(scanf("%d",a)>0)for(i=++j;i-->a;)i[1]=*i>=*a?*i:*(i=a);while(a<(i=j-50))printf("%d\n%d\n",*i,*j--);}

Answer 4

Ruby 1.9, -59

(61-120)

Recursion! This one does in fact, unlike my previous Ruby attempts, unsort the list regardless of their original order.

p *(f=->l{l[1]&&f[l-m=l.minmax]+m||[]})[$<.map &:to_i].rotate

Previous attempts

Cute one-liner, now using builtin sort to work properly:

$<.map(&:to_i).sort.each_slice(4){|a,b,c,d|p b,d,a,c}

First one -- Didn't necessarily unsort the last 4 values:

l=$<.map &:to_i
48.times{l-=p *l.minmax}
a,b,c,d=l
p b,d,a,c

Answer 5

J, -63 (57-120) characters

Since everyone else is going down the self-written sort route...

,50(}.,.{.)($:@([-.m),~m=.]#~]=<./)^:(0<#),".[;._2[1!:1[3

Doesn't use any random number function, nor any built-in sort.

Uses a simple recursive selection sort to sort the input.

Answer 6

Mathematica -56 44 4 (95-120) = -25

Edit:

This version relies on neither built-in functions for sorting lists, nor randomization functions.

Riffle[RotateLeft[#[[All, 2]], 2], #[[All, 1]]] &
[Partition[l //. {x___, a_, b_, y___} /; b < a :> {x, b, a, y}, 2]]

Answer 7

Perl 5: 95 - 120 = -25 chars

Counting the following command line:

perl -ne '$n=$_;splice@n,(grep{$n[$_]>$n}0..@n),0,$n}{print for map{@n[$_,$#n/2+$_+1]}0..$#n/2'

Answer 8

Ruby: -50 (70 chars - 120)

I did the same as many other answers: iteratively remove the max and min from the input list and append them to the output. However, I realized that if the 2 numbers on either side of the median are themselves consecutive, the output will be incorrect (because those 2 consecutive numbers will appear together at the end of the output). To fix this, I rotate the "unsorted" list right by 1 element:

n=$*.map &:to_i;u=[];50.times{u+=n.minmax;n-=u.last 2};p *u.rotate(-1)

Or, to work with arbitrarily many inputs (using only 4 more characters):

n=$*.map &:to_i;u=[];(u+=n.minmax;n-=u.last 2)while n.any?;p *u.rotate(-1)

Note: Some fewer-char Ruby answers have already been posted, but those solutions did not address the median issue (and/or assumed a sorted input list).

Answer 9

J 37 - 100 = -63

({~?~@#)^:(+./@(1=|)@(2&(-/\))@/:)^:_

Uses no sort (though does use rank up) Uses random numbers.

Explanation:

({~?~@#)             NB. Randomizes the array
^: foobar ^:_        NB. as long as
foo =: +./@(1 = |)   NB. as any 1 == absolute value of
bar =: (2&(-/\))@/:  NB. differences between adjacent ranks
foobar =: foo@bar

Answer 10

Brachylog, 22 bytes - 120 = -98

ṇịᵐpX¬{p≤₁s₂.&s₂p}∧Xẉᵐ

Try it online!

The TIO link only has an input of eight integers, rather than one hundred, because this is so dreadfully slow that it can't handle any more in 60 seconds. The reason for this is that, among other things, rather than implement some simple but normal sorting algorithm for the mandatory bonus, I for the sake of brevity used what amounts to a deterministic bogosort: p≤₁ backtracks through every permutation of the input until it finds one which is non-decreasing. Although a larger reason would probably be that it employs a similar degree of brute force to find the output, and that it recomputes the sorted version every time... I attempted to test it on an actual input of size 100, but I'm not sure just how many days it will take.

An overall better version:

Brachylog, 14 bytes - 20 = -6

p.¬{os₂.&s₂p}∧

Try it online!

This ignores the antiquated I/O requirements for brevity, and neglects to take the -100 bonus so it can possibly be tested without a supercomputer (although as of writing this, I've had it running on only 20 items for several minutes and it still hasn't given me anything).

 .                The output is
p                 a permutation of
                  the input
  ¬{        }∧    such that it cannot be proven that
         s₂       a pair of adjacent values in
        &         the output
       .   p      is a permutation of
     s₂           a pair of adjacent values in
    o             the output sorted.

Answer 11

Python 2: 90 char

n=100
s=sorted(int(raw_input())for i in range(n))
for i in range(n):print s[(4*i+4*i/n)%n]

lazy attempt but just for starters

Answer 12

Python 27 (147 - 100 - 20)

R=range
def S(L):
 for i in R(len(L)-1):
    if L[i]>L[i+1]:L[i:i+2]=[L[i+1],L[i]];S(L)
a=map(input,['']*100);S(a)
for i in R(100):print a[i/2+i%2*50]

Note: the spaces before if L[i]>... should be a tab but apparently show up as spaces in a code block.

Answer 13

Python 48 = (148 - 100)

from random import*
x=[input()for i in range(100)]
while any(abs(x[i]-x[i+1])>1 for i in range(99)):n=randint(1,99);x=x[n:]+x[:n]
for j in x:print j

Haven't tested this because it isn't guaranteed (or likely) to run in any reasonable amount of time, but should work in theory given infinite time.

Answer 14

Forth (gforth), 79 - 120 = -21 bytes

: f 100 0 do dup i 2 mod 4 * 2 - i + i 99 = i 0 = - 3 * + cells + @ . cr loop ;

Try it online!

Ignore antiquated input requirements and takes input as an address in memory where the numbers are stored.

Explanation

Loops through all numbers from 0 to 99. For each number (n):

• If n is 0:
  • output the value at array address + 1
• Else If n is 99:
  • output the value at array address + 98
• Else If n is odd:
  • output the value at array address + (n + 2)

• Else (n is even):

  • output the value at array address + (n - 2)

• Output a newline

Code Explanation

: f               \ start new word definition
  100 0 do        \ loop from 0 to 99
    dup           \ duplicate the array address
    i             \ place the loop index on the stack
    2 mod 4 * 2 - \ convert to 2 if it's odd and -2 if it's even
    i +           \ add the result to the the loop index
    i 99 =        \ if i = 99 place -1 on top of the stack, else place a 0
    i 0 =         \ i i = 0 place -1 on top of the stack, else place 0
    - 3 *         \ subtract previous two results from each other and multiply by 3
\ the above line is used to avoid writing if/then by instead using math to get 98 and 1
    +             \ add result to existing result from above
    cells         \ multiply by the size of a single integer in memory
    +             \ add to the array's starting address
    @ . cr        \ get the value at the calculated address, print it, then print a newline
  loop            \ end the loop
;                 \ end the word definition