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\$
4
  • \$\begingroup\$ There are exactly 100 integers input, and there are no duplicate values (see under "Input") \$\endgroup\$
    – lochok
    Oct 24, 2012 at 8:54
  • \$\begingroup\$ Right you are, didn't spot that. \$\endgroup\$
    – Strigoides
    Oct 24, 2012 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\$ Oct 24, 2012 at 11:10
  • \$\begingroup\$ So many clever responses! I'll select shortest answer on Oct 31 at 8:10-Zulu \$\endgroup\$
    – lochok
    Oct 28, 2012 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\$
5
  • \$\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, 2012 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\$ Oct 24, 2012 at 12:55
  • \$\begingroup\$ Ahh - right. Thanks for the clarification! \$\endgroup\$
    – lochok
    Oct 24, 2012 at 13:02
  • 1
    \$\begingroup\$ You can save two chars with the following output loop: 2/{~p}%n*. \$\endgroup\$
    – Howard
    Oct 26, 2012 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\$ Oct 26, 2012 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\$
7
  • \$\begingroup\$ t=l=[] and exec't+=[input()];'*100 would save you a few chars \$\endgroup\$
    – quasimodo
    Oct 26, 2012 at 16:48
  • \$\begingroup\$ also, you can use one exec statement for more than one loop. \$\endgroup\$
    – quasimodo
    Oct 26, 2012 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, 2012 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, 2012 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, 2012 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\$
3
  • \$\begingroup\$ Is Sort not a built-in sort function? \$\endgroup\$ Oct 24, 2012 at 22:56
  • \$\begingroup\$ You are correct! I missed the constraint about sort. \$\endgroup\$
    – DavidC
    Oct 24, 2012 at 23:20
  • \$\begingroup\$ I made a hand-rolled Sort. \$\endgroup\$
    – DavidC
    Oct 25, 2012 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\$
3
  • 1
    \$\begingroup\$ Your -72 solution assumes the list starts out sorted, which is not the case. \$\endgroup\$
    – histocrat
    Dec 5, 2013 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, 2013 at 8:28
  • \$\begingroup\$ @histocrat that should do it. \$\endgroup\$
    – daniero
    Dec 11, 2013 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\$
2
  • 1
    \$\begingroup\$ x=map(input,['']*100) \$\endgroup\$
    – ugoren
    Oct 26, 2012 at 5:32
  • \$\begingroup\$ And I don't think you even need the extra []s, just any single character string. \$\endgroup\$
    – job
    Nov 1, 2012 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\$
2
  • \$\begingroup\$ With R=range you could save 5 characters. \$\endgroup\$
    – scleaver
    Oct 24, 2012 at 19:18
  • \$\begingroup\$ a=map(input,['']*100) \$\endgroup\$
    – ugoren
    Oct 26, 2012 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\$
1
  • \$\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\$ Apr 5, 2019 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 and acknowledge you have read our privacy policy.

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