18
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ There are exactly 100 integers input, and there are no duplicate values (see under "Input") \$\endgroup\$ – lochok Oct 24 '12 at 8:54
  • \$\begingroup\$ Right you are, didn't spot that. \$\endgroup\$ – Strigoides Oct 24 '12 at 9:01
  • 2
    \$\begingroup\$ It's not a duplicate as such, but it's not very different to codegolf.stackexchange.com/questions/6487/… \$\endgroup\$ – Peter Taylor Oct 24 '12 at 11:10
  • \$\begingroup\$ So many clever responses! I'll select shortest answer on Oct 31 at 8:10-Zulu \$\endgroup\$ – lochok Oct 28 '12 at 11:55

14 Answers 14

9
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Credit for such a concise answer, but (forgive me, as I don't speak or understand GolfScript) - wouldn't the ^ disqualify it from the -100 bonus? \$\endgroup\$ – lochok Oct 24 '12 at 12:50
  • 1
    \$\begingroup\$ @lochok, the built-in sort function is $ - that's why I mentioned that the $ in the program aren't sorts (it's context-dependent). The majority of the program (28 of the 42 characters) defines the function ^; the first version, using the built-in sort, was only 14 characters. \$\endgroup\$ – Peter Taylor Oct 24 '12 at 12:55
  • \$\begingroup\$ Ahh - right. Thanks for the clarification! \$\endgroup\$ – lochok Oct 24 '12 at 13:02
  • 1
    \$\begingroup\$ You can save two chars with the following output loop: 2/{~p}%n*. \$\endgroup\$ – Howard Oct 26 '12 at 14:43
  • 1
    \$\begingroup\$ 2/zip~+n* and .);\+2%n* also do the trick for the same number of chars as @Howard's version. Alas, I haven't managed to find anything shorter yet. \$\endgroup\$ – Ilmari Karonen Oct 26 '12 at 20:07
6
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ t=l=[] and exec't+=[input()];'*100 would save you a few chars \$\endgroup\$ – quasimodo Oct 26 '12 at 16:48
  • \$\begingroup\$ also, you can use one exec statement for more than one loop. \$\endgroup\$ – quasimodo Oct 26 '12 at 17:33
  • \$\begingroup\$ @quasimodo I tried something like that, but with t=l=[] t and l point to the same object and it doesn't work. Skipping parentheses on exec is nice though. \$\endgroup\$ – daniero Oct 26 '12 at 19:31
  • \$\begingroup\$ You could use t=t+[input()];, this creates a new object each time. And you can even do the print loop in the exec statement: ';i+=1;print l[i*3%100]'*100. \$\endgroup\$ – quasimodo Oct 27 '12 at 10:53
  • \$\begingroup\$ You're right again. Thanks! Also added some other golfing like removing the %3 and avoiding repeation of 100. \$\endgroup\$ – daniero Oct 28 '12 at 13:30
4
\$\begingroup\$

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

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]]
\$\endgroup\$
  • \$\begingroup\$ Is Sort not a built-in sort function? \$\endgroup\$ – Peter Taylor Oct 24 '12 at 22:56
  • \$\begingroup\$ You are correct! I missed the constraint about sort. \$\endgroup\$ – DavidC Oct 24 '12 at 23:20
  • \$\begingroup\$ I made a hand-rolled Sort. \$\endgroup\$ – DavidC Oct 25 '12 at 19:04
3
\$\begingroup\$

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.

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

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Your -72 solution assumes the list starts out sorted, which is not the case. \$\endgroup\$ – histocrat Dec 5 '13 at 19:14
  • \$\begingroup\$ Oops. Seems I didn't re-read the question thoroughly when I revisited this one. Will try to come up with something else. \$\endgroup\$ – daniero Dec 6 '13 at 8:28
  • \$\begingroup\$ @histocrat that should do it. \$\endgroup\$ – daniero Dec 11 '13 at 16:14
1
\$\begingroup\$

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

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

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ x=map(input,['']*100) \$\endgroup\$ – ugoren Oct 26 '12 at 5:32
  • \$\begingroup\$ And I don't think you even need the extra []s, just any single character string. \$\endgroup\$ – job Nov 1 '12 at 17:24
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ With R=range you could save 5 characters. \$\endgroup\$ – scleaver Oct 24 '12 at 19:18
  • \$\begingroup\$ a=map(input,['']*100) \$\endgroup\$ – ugoren Oct 26 '12 at 5:33
1
\$\begingroup\$

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

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

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

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

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.
\$\endgroup\$
  • \$\begingroup\$ Although this isn't exactly a practical answer, it could be of use for validating the output from other programs, since most of it is just describing the constraint placed on the output. \$\endgroup\$ – Unrelated String Apr 5 at 20:36
0
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.