Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Inspired by the ill-fated sorting-a-numbers-digits-without-using-an-array, but I thought it made a better code golf than SO question.

Given a positive integer, sort the digits in that integer.

Lowest score wins!

  1. Start with 0 points.
  2. Add one point per character.
  3. Add 20 points for each array you use.
  4. Add 10 points for each multi-character string in your code. (Except the initial input as long as it is converted to an integer without any other operations done on it.)
  5. Add 32 points if the maximum number of digits your program can handle is limited by your program (as opposed to the machine).
  6. Subtract 10 points if your code can change the direction of the sort given another argument (whatever you want, but for example 0 for descending sort and 1 for ascending.)

Every language is different, but the idea is to avoid any kind of iterable-of-digits hackery.

Example:

Input: 52146729

Output: 97654221 or 12245679

Notes:

  1. Use any built-in sorting capabilities your programming language provides, but if that sort feature involves strings or arrays, take the penalty!
  2. You can write the solution as a function that takes an integer directly, or as a program that takes an argument from argv, a file or stream and converts it to an integer. As long as you convert it to an integer immediately and discard the original char* input without doing any further operations on it, no penalty applies.
  3. The penalties apply not only to string literals in your program text, but any part of your program feature that arguably inputs or outputs a string or iterable. For example, JavaScript String.prototype.split has at least one string as input (this) and an Array as output, so +30 for using that.
  4. I've tried to make these rules guide the principle of the algorithm design, not the initial/final I/O (hence note #2). I don't think the penalty ought to apply to int(input()) even if input's signature says it returns a string, as long as that expression is the initial entry point of the program. Likewise, if the final output of the program is print(x) and x must be a string, the penalty doesn't apply to the last-ditch string casting operation. All that said, I explicitly never said that this had to be a program or where the I/O had to come from or go. A function that takes an int and returns an int would serve, and wouldn't suffer from these ambiguities.
share|improve this question
1  
Does " " count as a multi character string? A single character would not be considered as "multi"... –  WallyWest Mar 28 at 23:50
4  
Seems to me like an easy implementation of sleepsort. –  ace Mar 29 at 4:13
1  
You don't forbid the language's sorting funtions. –  user80551 Mar 29 at 5:18
1  
I'd write better the rules about built-in functions, also penalities are too low: this incentivate the use of an array instead of an alternative (probably longer) method. –  Antonio Ragagnin Mar 29 at 15:51
1  
@AntonioRagagnin I didn't want to change the penalties ex post facto, but I clarified the rules around built-in functions. –  kojiro Mar 29 at 19:34

29 Answers 29

GolfScript, 11 4

(4 + 10 (string) - 10 (reverse option))

Input on STDIN.

~`$%

Input format is this:

(1 or -1) (the number)

1 to sort normally, -1 to reverse. 4 characters - 10 for reverse option = score of -6.

The input is technically a string, so I'm not sure whether that counts for +10. I'm interpreting the rule as "a string declared in your program" (since it says "in your code").


Old answer (score of 11):

$
share|improve this answer
2  
Strings are technically arrays in GS, just to really complicate the scoring debate. –  Peter Taylor Mar 29 at 9:53
    
Yes, input of a string (that is not immediately converted into an integer) is +10. –  kojiro Mar 29 at 20:05
    
@kojiro ~ immediately converts to integer. But then it's converted back to a string with `. Does converting into a string count? Because sometimes the string might not be multicharacter (1 digit input) –  Doorknob Mar 29 at 20:18
    
Yes, converting into a string counts unless the function (or whatever) can only output a one-character string. This should be assessed based on the function signature or documentation. If it's designed to output one character (like chr), it's fine. –  kojiro Mar 29 at 20:23

Haskell 106

t=10;d=divMod;s z|z<w z=s$w z|t>0=z
w x|x<t=x|y>z=(q*t+y)*t+z|t>0=y+t*(w v)where{(v,y)=d x t;(q,z)=d v t}

example:

ghci> s 502010406072952146729521467295214672952146729
999997777766666555554444422222222221111100000

An answer that doesn't dodge the question.

An explanation was requested, here it is ungolfed. It's a very inefficient bubble sort.

-- t=10 - alias for 10. d=divMod - alias for divMod.
-- The alias for '10' turns out to be unnecessary; inlining it
-- and using '1>0' for True has the same character count. It's
-- a relic of earlier versions of the code.

-- 's': if no digits need swapped, return the number,
-- otherwise return 's' applied to the number with
-- that pair of digits swapped.
sort z=
  let temp=sort_pair z
  -- because we are sorting in descending order,
  -- sorting a pair of digits always increases the number.
  -- testing > costs one less char than ==.
  if z<temp then
    -- golfed version uses guards instead of if/else to save space.
    -- t>0 is '10 > 0', which is 'True', in fewer chars.
    sort temp
  else
    z
-- 'w': recursively swap one pair of out of order digits, or
-- return the original number if no pairs needed swapped.
sort_pair x=
  -- haskell does the assignments below lazily, they aren't
  -- calculated unless I use them. 'divMod' lets me do this
  -- with fewer chars.
  let y = x `mod` 10 -- last digit
      v = x `div` 10 -- all but last digit
      z = v `mod` 10 -- second last digit
      q = v `div` 10 -- all but last 2 digits
  in
  if x < 10 then
    x
  else if y > z then
    -- last 2 digits are out of order. swap them & return
    -- This is rearranged using Horner's method to save space
    -- http://en.wikipedia.org/wiki/Horner%27s_method
    -- ... although it turns out not to save anything, it's a relic.
    (q * 10 + y)*10 + z
  else
    -- last digit is ok, so try sort_pair on remaining digits
    let temp = sort_pair v in
    -- put last digit back on the end and return
    -- having the bracketed expression last here
    -- let me remove a space before 'where'
    y+(10*temp)

Shorter answers exist in Haskell, equivalent to some of the others posted, eg:

import Data.List;s=read.sort.show::Integer->Integer

... scores 52+20=72, or this, scoring 45+20=65:

import Data.List;main=interact(reverse.sort)

... but the spirit of the question - no arrays, strings, or characters - is more interesting.

share|improve this answer
2  
Could you add an explanation? –  user80551 Mar 29 at 6:17
    
You should get a bonus point reduction for having the integer input size not even being limited by the machine due to Haskell's implicit arbitrary precision integers. –  awashburn Mar 29 at 17:29
    
@awashburn Well, he got it (i.e. he didn't add 32 points!) And supposedly, so did I (here) –  ambigram_maker Mar 30 at 5:38
    
@ambigram_maker I think he means that yours, for example, can't take input larger than Integer.MAX_VALUE-it takes an int. Mine, and some of the others, accept any size input-the input type of s is Integer, equivalent in BigDecimal in java. That isn't what I took the question to mean though, I thought it was penalizing answers that 'sort' only one digit numbers. –  bazzargh Mar 30 at 6:03
1  
It's easily changed. I don't think its a big deal. –  bazzargh Mar 30 at 6:12

C + x86 assembly, 636

I know this isn't gonna win but it felt so much unnatural and twisted that I had to share it. No arrays or strings (as long as you don't count the input arguments). The number of digits its limited by the 32 bit range.

So here's a little explanation on what I did:

I thought I'd do this without using any arrays or strings, and then recursion came into mind, but of course, with recursion I wouldn't be able to swap values from other recursive calls... and then was when I realized that there was a way. Linking my C program with an assembly function I could jump up in the stack and return a pointer to the base pointer of the desired call, that's what "recursionStackAt" function does. Of course recursionStackAt is a very ugly function, its result doesn't only depend on the input or program's state but on the caller itself. Note that that's what made me change the indexes from 0 based to 1 based.

Without further ado, here's the code:

#include <stdio.h>
#include <stdlib.h>

int numberToSort;
int totalLength = 0;
int decreasing;

int* recursionStackAt(int pos); //Here's the magic

void swapAtStack(int pos1, int pos2) {
    int a = *(recursionStackAt(pos1)+3);
    *(recursionStackAt(pos1)+3) = *(recursionStackAt(pos2)+3);
    *(recursionStackAt(pos2)+3) = a;
}

int getAt(i) {
    return *(recursionStackAt(i)+3);
}

void printNumber(int len) {
    int i = 0;
    for(i = 1; i <= len; ++i) {
        printf("%d",*(recursionStackAt(i)+3));
    }
    printf("\n");
}

void computeNextDigit(int remainingNumber, int nextDigit) {

    if(remainingNumber == 0) {
        //Bubble sort cause I was lazy and it's quite compact
        ++totalLength;

        int i, j;

        for(i = 1; i <= totalLength; ++i)
            for(j = 1; j <= totalLength-1; ++j) {
                if(decreasing) {
                    if(getAt(j) > getAt(j+1)) 
                        swapAtStack(j,j+1);
                }
                else { 
                    if(getAt(j) < getAt(j+1))
                        swapAtStack(j,j+1);
                }
            }

        printNumber(totalLength);   
    }
    else {
        ++totalLength;
        computeNextDigit(remainingNumber/10, remainingNumber%10);
    }
}

int main(int argc, char* argv[]) {
    if(argc == 3) {
        numberToSort = atoi(argv[1]);
        decreasing = atoi(argv[2]);
    }
    else exit(1);
    computeNextDigit(numberToSort/10, numberToSort%10);
} 

And of course the x86 (AT&T sintax, btw) assembly code for the recursionStackAt function:

.text
    .align 4
    .globl  recursionStackAt
    .type   recursionStackAt, @function
recursionStackAt:
        pushl %ebp
        movl %esp,%ebp
        pushl %esi
        movl $0, %esi #i = 0
        movl (%ebp), %eax #pointer
while:  
        cmp %esi, 8(%ebp)
        je endwhile
        movl (%eax),%eax
        incl %esi
        jmp while
endwhile:
        popl %esi
        movl %ebp, %esp
        popl %ebp
        ret

Some examples on the output: (1 means increasing and 0 decreasing)

$ ./sortasort 6543210 1
0123456
$ ./sortasort 32507345 1
02334557
$ ./sortasort 32507345 0
75543320

Here's the obfuscated version (which is unreadable but works fine):

http://pastebin.com/XkYt9DLy (C code) http://pastebin.com/h0S0dfeU (x86 code)

So if LibreOffice isn't lying my obfuscated code consists of 646 characters (without spaces, should I count them?) and with all the other conditions met I get a -10 for the incresing/decreasing choice.

Oh, and to compile this you should do (On Unix-like systems)

gcc -c [-m32] recursionStackAt.s 
gcc -o sortasort [-m32] sortasort.c recursionStackAt.o

Note that the -m32 flag is only if you're on a 64 bit machine. You also need the 32 bit libraries to compile it.

share|improve this answer
    
I think necessary whitespace is normally counted. At least thats what I do, after stripping out unnecessary whitespace. Anyone who has the balls to mess with the stack like this gets my upvote! +1 –  DigitalTrauma Mar 30 at 19:35

Bash (echo) (0+7+0+0+32-10) = 29

Sorta:

echo $*

Usage:

sorta 5
5

Use "-e" to sort in reverse:

sorta -e 3
3
  • produces the correct result for positive integers 1-9, plus 0
  • avoids any kind of iterable-of-digits hackery.
  • 7 characters (+7)
  • no arrays
  • no multi-character strings
  • maximum number of digits it can handle: 1 (+32)
  • can optionally reverse the sort (-10)

EDIT: changed "cat" to "echo" so it would actually work. EDIT 2: Added " $*" and put it into "sorta" script

share|improve this answer
    
Haha; nice trick, but it's still the losing answer out of all the (also rule-bending) answers so far ;) –  Doorknob Mar 29 at 1:11
4  
The whole thing is undeserved; why pick on the sorting? –  Glenn Randers-Pehrson Mar 29 at 1:17
2  
Legendary abuse of rules. +1 –  DigitalTrauma Mar 29 at 1:32
2  
@kojiro: For example, -e could be used as argument for the reverse output. –  Heiko Oberdiek Mar 29 at 2:14
3  
Never mind, you are right, "-e" would work as well as "". I'd have to rewrite the user manual though, and for backward compabibility I'd have to continue to accept "". –  Glenn Randers-Pehrson Mar 29 at 3:15

Bash+coreutils, 14 (24 chars - 10 for reverse)

I think this might be bending the rules a bit, but here goes, its Friday...

I assume use of standard libraries is allowed. My interpretation of standard library for bash is coreutils:

fold -1|sort $1|tr -d\\n
  • No arrays - streams are used instead
  • No quotes == no multi-character strings
  • No limit to input/output length
  • optional arg "-r" reverses the output.

Input from stdin. In use:

$ declare -i i=52146729
$ ./ksort.sh <<< $i
12245679 $ 
$ ./ksort.sh -r <<< $i
97654221 $ 
$ 
share|improve this answer
    
I really wish I'd included a rule against the program working with anything that isn't an integer. I guess it's too late now. –  kojiro Mar 28 at 23:49
1  
Don't count the newline after the "\\n" so you score 20 not 21. –  Glenn Randers-Pehrson Mar 29 at 1:48
    
I'm not counting the newline, but as a script saved in a file it has a \0 at the EOF as saved by my editor. I usually count these anyway. But I can strip that \0 off, and the script still works, so I'll take it! –  DigitalTrauma Mar 29 at 1:53
    
@kojiro It works with bash's idea of integers too (declare -i). Edited. –  DigitalTrauma Mar 29 at 2:18
    
(BSD/OSX tr doesn't like your syntax, which would cost you one character on those systems.) Anyway, I'd argue that these are still all string operations at heart. declare -i doesn't make a name an integer, it just makes the shell use arithmetic context on it on the RHS of assignment expressions. –  kojiro Mar 29 at 20:01

Python3

My script features:

No arrays

No strings

Complexity is O(n): I used countingsort (modified by me to not use arrays, but prime numbers to count occourences)

No limitations in size

Characters: 260 234

n=int(input())
def C(n,k):
    return (n//(10**(k-1)))%10
P=lambda l:((((29-6*l%2,19-2*l%2)[l<9],13-2*l%2)[l<7],2*l-1)[l<5],2)[l==1]

p=1
while n>=1:
    c =C(n,1)
    p*=P(c+1)
    n=n//10
f=1
k=r=0
while p>2:
    if(p%P(f)==0):
        r+=(f-1)*10**k
        p=p//P(f)
        k+=1
    else: f+=1
print(r)
share|improve this answer
1  
I could be wrong, but I think you can lose the parens around some of that arithmetic to shave some characters off. –  kojiro Mar 29 at 19:16
    
I really like the use of primes here. It's so very weird. Also, I think P can be written lambda l:((((29-6*l%2,19-2*l%2)[l<9],13-2*l%2)[l<7],2*l-1)[l<5],2)[l==1], shaving off quite a few characters. I may have messed it up a little, but the idea is to use a nested version of the old-school Python ternary (before Python had a ternary) (false_result, true_result)[boolean]. –  kojiro Mar 30 at 18:41
    
Thanks random guy from the internet! BTW I'm having fun with this now, try to see if you like: codegolf.stackexchange.com/a/25086/16992 –  Antonio Ragagnin Mar 30 at 20:08

C - 64 characters, 64 points

main(int a,char**b){b++;qsort(*b,strlen(*b),1,strcmp);puts(*b);}

You might wonder how I get this to work without any headers. Simple, compile with:

gcc -include stdio.h stdlib.h string.h test.c -o test --std=gnu11 -Wall -g -O3

Un-golfed:

#include <stdio.h> 
#include <stdlib.h>
#include <string.h>

main(int a, char **b)
{
    b++;
    qsort(*b, strlen(*b), sizeof(char), strcmp);  // sizeof(char) is guaranteed to be 1 by standards
    puts(*b);
}

I also decided to include sorting of characters, just because I could.

Test runs:

$ ./test 132815
112358
$ ./test 423791
123479
$ ./test 1234767189728975213132471243985123957120837412
0111111112222222233333344445556777777788889999
$ ./test 4789359uihjasvb8ygohq9poi3n4jiouy58g
3344557888999abgghhiiijjnooopqsuuvyy
share|improve this answer
1  
Nicely done bit of "golfing" :D –  ProgrammerDan Mar 30 at 21:10
    
I can't compile this on Ubuntu 14.04 but I can compile main(int a,char**b){b++;qsort(*b,strlen(*b),1,strcmp);puts(*b);} which is shorter anyway. –  gmatht Apr 1 at 9:13
    
@gmatht I'm not sure why it wouldn't compile, it was able to on my system just fine. Thanks for the hint BTW! –  syb0rg Apr 1 at 12:41
    
It didn't like c(*a, my version of gcc insisted that we needed to do c(char*a instead. –  gmatht Apr 1 at 23:10

c function (little-endian arch), 131 108 chars

No sorting challenge is complete without a sleepsort answer. This one will take up to 10 seconds to return, but it does work, and I think it is fully within spec. This function takes a single int param and returns an int with the decimal digits sorted:

c=0,d;
k(i){
    for(;i;i/=10,fork()?c++:(sleep(d),exit(d)))
        d=i%10;
    for(;c--;i=i*10+(d>>8&255))
        wait(&d);
    return i;
}

newlines and indentation added for readability

Call as follows:

int main (int argc, char **argv) {
    int i = 52146729;

    printf("%d\n", k(i));
    return (0);
}
share|improve this answer
2  
Nice. But I think you can use global variables to save some chars. Also, you can use ?: instead of if-else. fork()?c++:(sleep(d),exit(d)); –  ace Mar 30 at 19:44
    
@ace Thanks for the tips! I tried the ternary operator earlier but slipped up on the (,). –  DigitalTrauma Mar 30 at 23:00

TeX/LaTeX (332)

If the actual code is put in a package s, then the main LaTeX file looks nice and easy. The number is just given as math. If the number is negative, the sorting order is reversed. The code of package s can also used with plain TeX, example further below.

\documentclass{book}
\usepackage{s}
\begin{document}
  $52146729$

  $-52146729$ % reversed ordering

  $277981468517523153773703292073191466142223027369188752287219582183$
\end{document}

The package s (one line, line ends are not needed):

\TeXXeTstate1\everymath{\aftergroup\B\def~#1{\gdef#1{}\aftergroup#1}
~\a~\b~\c~\d~\e~\f~\g~\h~\i~\j\aftergroup\E\xdef\B{}\xdef\E{}}
\def~#1#2{\mathcode`#1"8000\lccode`~`#1\lowercase{\def~{\xdef#2{#2#1}}}}
~0\a~1\b~2\c~3\d~4\e~5\f~6\g~7\h~8\i~9\j\mathcode`-"8000\lccode`~`-
\lowercase{\def~{\xdef\B{\beginR}\xdef\E{\endR}}}

Result:

Result

Score: hopeless

  • Using plain TeX with etex or pdftex, the file can be reduced to:

    <contents of s.sty>\rm\shipout\hbox{$<number>$}\bye

    Bytes: 318 bytes (s.sty) + 24 bytes for the rest without the number

  • Arrays are not used: 0

  • I do not see multi-character strings: 0

  • The number is not limited by the algorithm. The largest TeX number is 231 - 1 = 2147483647. The example uses a 66-digit number, way larger: 0

  • If a minus is given, then the sorting order is reverted to descending: −10

0 + 318 + 24 + 0 + 0 − 10 = 332

Algorithm:

The digits are made active characters in math mode. Each digit remembers and collects each usages in a macro. After the math mode the macros are output with the digits in ascending order.

The direction change is done by right-to-left text, an e-TeX feature.

Degolfed version of the code in s.sty

\TeXXeTstate = 1 % enable mixed direction typesetting
\everymath{%
  % \B and \E surround the number, they will be redefined
  % with right-to-left primitives to output the reverted number
  \xdef\B{}
  \xdef\E{}
  \aftergroup\B
  % the active character ~ is defined as help macro;
  % the argument is the collector macro
  \def~#1{%
    \gdef#1{}% initially the macro is empty
    \aftergroup#1%
  }%
  % the ten macros \a to \j form the result number
  ~\a~\b~\c~\d~\e~\f~\g~\h~\i~\j
  \aftergroup\E
}
% the active ~ is used as helper macro;
% first argument is the digit, the second argument is the collector macro
\def~#1#2{%
  \mathcode `#1  = "8000 % make digit active in math mode
  \lccode `~ = `#1 % trick for defining the active digit 
  \lowercase{%
    \def~{%
      \xdef#2{#2#1}% the digit adds itself to its collector macro
    }%
  }%
}
~0\a~1\b~2\c~3\d~4\e~5\f~6\g~7\h~8\i~9\j
% Defining the minus character as switch for descending digits:
\mathcode `- = "8000 % minus sign active in math mode
\lccode `~ = `- % trick for defining the active minus
\lowercase{%
  % the minus sign redefines the wrapper macros \B and \E that
  % surround the result number. These macros now uses
  % primitives for right-to-left typesetting.
  \def~{%
    \xdef\B{\beginR}%
    \xdef\E{\endR}%
  }%
}

Reproducing

There are some online LaTeX compilers, a list can be found here. I tried the first item on the list, LaTeX servlet on sciencesoft.at. It can be used without signing and it can also create permanent URLs: source and result as image.

share|improve this answer
    
I do not have the LaTeX chops to assess this myself. I'll have to take your word for it. :) –  kojiro Mar 29 at 19:55
    
@kojiro: There are some online compilers for LaTeX, see the updated answer for an example. –  Heiko Oberdiek Mar 29 at 20:10
    
This is horrifying, Heiko. +1! XD –  Sean Allred Mar 31 at 17:40

Java : 262 points

Yeah, yeah I know, it's hopeless, but still..

class G{Object m(StringBuffer s,int o){for(int i=1;i<s.length();i++){int j=i-1,t=s.charAt(i),u=s.charAt(j);boolean c=o==0?t>u:t<u;for(;j>-1&c;){s.setCharAt(j+1,s.charAt(j));c=--j>-1;c=c?(o==0?t>s.charAt(j):t<s.charAt(j)):c;}s.setCharAt(++j,(char)t);}return s;}}

Analysis (marking):

  1. Starting with 0. (score = 0)
  2. 262 characters total. (score = 0 + 262 = 262)
  3. +10 - for using StringBuffer (I used it because it's shorter than StringBuilder) (score = 262 + 10 = 272)
  4. -10 - for making the output flexible. I've considered 0 = descending, 1 = ascending, so back to 262!

Usage:

When you try and compile the G.java file in command prompt, it generates a hell lot of problems (errors). So, the solution?

Compile the G.java class in an IDE like NetBeans or Eclipse or even BlueJ. It should compile without any trouble (ignore any warnings).

Then, this class should be called by a main() method from any other class (or even that class itself). I'm putting it another class, so I'm not adding it to my character count. Compile the other class in a similar manner (without using cmd). Now the main() method in the other class should be something like:

public static void main(String[]a){
    System.out.println(new G().m(new StringBuffer(a[0]),1));
    //for descending, put '0' instead of '1'
}

Excluding unnecessary spaces, comments and line breaks, it's another 93 characters. I'm not adding it to my character because this is just for demonstration through console.

Output:

ZERO i.e. 0 is considered. Supposing the external class is Helper.java, and it has been successfully compiled, a few examples through console are:

INPUT : C:...>java Helper 008321
OUTPUT:001238

INPUT : C:...>java Helper 79359105
OUTPUT:01355799

When changed to 0 i.e. descending...

INPUT : C:...>java Helper 008321
OUTPUT:832100

INPUT : C:...>java Helper 79359105
OUTPUT:99755310

NOTES:

  1. I didn't explicitly declare any array in G.java. That is the core class.
  2. I'm using insertion sort to sort the number digit-wise.
  3. The number can be of of the maximum length - Integer.MAX_VALUE because that is the maximum size any array can hold (in Java).
  4. This answer can be shortened (I believe) so please help me (improve my first answer).
  5. Darn those great Gods who accidentally created such a lengthy yet great language like Java (and also who came up with code conventions)!
share|improve this answer

Haskell - 96

96 characters, no arrays, no strings, no integer limit, can't reverse

d=(`divMod`10)
a&(0,0)=a
a&(y,z)=(z%d a)&d y
a%(y,z)|z>a=10*(a%d y)+z|1<3=100*y+10*z+a
s=(0&).d

Examples:

λ: s 52146729
12245679
λ: s 502010406072952146729521467295214672952146729
1111122222222224444455555666667777799999
λ: s 100
1

This one is insertion sort, performed directly on the integers themselves. This is similar to the other Haskell entry which is bubble sort, though I swear I was working on it before I saw that one.

Brief guide:

  • d divides a number into units and tens, i.e.: d 135 is the pair (13,5)
  • a%x is sorted insertion of digit a into the number x
  • a&x sorts x by inserting the units digit into a and recursing on the result and remainder
  • s x sorts x by kicking off the & recursion on 0 and x

The trick is that the second argument of % and & isn't x directly, but x divMod'd using d

share|improve this answer
    
Nice. I'd forgotten about using infix. I can maybe shave a couple of chars that way, but you have me beat. +1 –  bazzargh Mar 30 at 13:26

Python3.3 61 points

print(''.join(sorted(input())))

This program takes in the input as a string, which counts as a string because it is not changed to an integer immediately. +10

The string is sorted into an array +10

This array is joined together into a string +10

Note: The '' used to join the array's contents is not a multi character string, so +10 is not added to the score.

The program consists of 31 characters. +31

31+10+10+10 = 61 points

share|improve this answer
    
+1 although the data you process is never a number. (It's not the only answer like that, I know.) –  kojiro Mar 31 at 0:46
    
It's not explicitly stated, although it is said that. My original code was print(int(''.join(sorted(input())))), but the cast to integer only added points and did not make the code follow the rules any closer. I didn't really stay true to the challenge I suppose. But he does state that the input can be a string, and the output can be a string (for print statements), and says nothing about in between :] –  erdekhayser Mar 31 at 0:51

J, 10 characters (+ 1 string) score = 20

s=./:~&.":

Usage:

   s 52146729
12245679

Works for all 32 bit numbers.

Explanation:

/:~ sort up &. under ": format. My previous version used an array as well, but they're costly so now I need to just use a string and sort the characters alphabetically. ": converts the number that is input into a string and /:~ sorts the digits into ascending order. Because the sort is done 'under' format, when the sort is finished, the string is converted back into a number. Adding the ability to reverse would probably cost more than it saves, so I didn't bother.

The argument could be made that since J, like APL and K, is an array-based language, the single input is an array of 1 item, but I chose not to take such a harsh view when calculating my score.

The 32-bit limit is imposed by J, rather than my program. Any higher and J switches the numbers to scientific notation. It's not clear from the question whether the 32 point penalty applies in this case, but even if both of the previous penalties apply (I don't think they should) the score goes up to 72 and still comfortably beats the vast majority of the other answers.

share|improve this answer
    
Can you provide an explanation? This looks like it's formatting the number as a string, splitting into an array, sorting the array, then reforming it as a string...aren't there penalties for the array & string? –  bazzargh Mar 29 at 15:23
    
@bazzargh I deliberately didn't declare a score when I submitted my answer for two reasons: 1) it's tagged [code-golf] so bonuses don't really make sense, and 2) it wasn't clear to me which would apply. I'll add an explanation. –  Gareth Mar 29 at 16:27
    
What tag should I have used? It's code golf with penalties… –  kojiro Mar 29 at 19:36
    
@kojiro - mouse over the code-golf tag it tells you - code-challenge. –  bazzargh Mar 29 at 20:37

Python 2.7: 174

import math
i=input()
d={n:0for n in xrange(10)}
for n in(i/10**c%10for c in xrange(1+math.log10(i))):d[n]+=1
print"".join(str(n)for n in xrange(10)for c in xrange(d[n]))
  • No arrays (iterators and a dictionary are used instead)
  • No multi-character strings (except output)
  • No artificial maximum number of digits
  • No reversing

It works by creating a dictionary mapping all 10 digits to 0. Then it iterates over the length of the number (log10(i)), extracting each digit ((i / (10 ** c)) % 10), and incrementing the counter for that digit in the dictionary. Finally it creates a string made by iterating over all 10 digits, and for each digit yielding one instance of the digit as a string.

I could change the last line to print"".join(d[n]*str(n)for n in xrange(10)) which would be 16 characters less, but would use multi-character strings.

share|improve this answer
    
i=int(input()) can be just i=input() as input() automatically evals the number. –  user80551 Mar 31 at 15:21
    
@user80551: Yes, of course! Good call. –  Gabe Mar 31 at 15:41

C# - 179

using System.Linq;class S{void Main(string[] a){Console.Write(string.Concat(string.Concat(a).Replace("-","").OrderBy(o=>a[0].Contains('-')?-o:o)));}}

Un-golfed

using System.Linq;

class S
{
    void Main(string[] a)
    {
        Console.Write(string.Concat( 
            string.Concat(a)
                .Replace("-", "")
                .OrderBy(o => a[0].Contains('-') ? -o : o )));
    }
}

Test

Normal:

app.exe 52313698

Reversed:

app.exe 52313698-

Points: (I hope I understood the point system properly - feel free to correct)

  • Chars: 149
  • Strings: 10+10
  • Arrays: +20
  • Order: -10
  • Total: 149+10+20-10 = 179

C# with LINQPAD - 123

void Main(string[] a){Console.Write(string.Concat(string.Concat(a).Replace("-","").OrderBy(o=>a[0].Contains('-')?-o:o)));}

Test

Normal:

lprun.exe sorta.linq 52313698

Reversed:

lprun.exe sorta.linq 52313698-

Points:

  • Chars: 122
  • Strings: 10+10
  • Arrays: +20
  • Order: -10
  • Total: 122+10+20-10 = 152
share|improve this answer

AWK - 101

The 'x' file:

BEGIN{n=ARGV[1]
r=ARGV[2]
for(d=r;d<10;d++)for(p=1;p<=length(n);p++){D=r?d:9-d
if(D==substr(n,p,1))printf D}print}

The run:

$ awk -f x 52146729
97654221
$ awk -f x 52146729 0
97654221
$ awk -f x 52146729 1
12245679
$ awk -f x 1234567890123456789012345678901234567890
9999888877776666555544443333222211110000
$ awk -f x 1234567890123456789012345678901234567890 1
111122223333444455556666777788889999

The only array used is ARGV and this is no help in sorting, it only is access to the commandline parameters and these values are in non-array variables where actually needed for calculations. I think this won't count against this solution. The following calculation does not take the ARGV-array into account:

111 (chars) - 10 (can do reverse)

share|improve this answer
    
Sometimes the only sane answer to an insane world is insanity. – Fox Mulder –  kojiro Mar 29 at 23:59
    
:-D Indeed! :-D –  yeti Mar 30 at 0:03

I don't see anything about sorting functions in the question, so... (I'm gonna remove the answer if it bends or breaks the rules, let me know)

JavaScript 56 96

function s(){alert(+prompt().split('').sort().join(''))}

JavaScript 69 109 (reversable)

function s(r){x=prompt().split('').sort();x=r?x.reverse():x;alert(+x.join(''))}

Can be golfed down a bit using EcmaScript 6 arrow functions:

ES6 50 90

s=()=>{alert(+prompt().split('').sort().join(''))}

ES6 63 103 (reversable) (73-10)

s=(r)=>{x=prompt().split('').sort();x=r?x.reverse():x;alert(+x.join(''))}
share|improve this answer
    
prompt returns a string (that you don't immediately convert into an integer): +10; split returns an array: +20; sort does an in-place sort (so it's still the same array); join returns a new string, +10. Total: 96. –  kojiro Mar 29 at 19:27
    
How the rules are written made me understand that only literals were counted. Updating the score, anyway. –  LightStyle Mar 30 at 8:34

SED 67 Chars (score either 67 or 107)

s/$/;0123456789/;:a;s/\(.\)\(.\)\(.*;.*\2.*\1\)/\2\1\3/;ta;s/;.*//;

This uses a bubble sort for brevity. Score would be 107 if each regular expression pattern and replacement count as a string (i.e. 67 + (10 * 4))

Number of digits handled limited by memory (and probably patience)

share|improve this answer

Python lambda function (reversible), 69

lambda n,d:''.join(sorted(n,reverse=d))
  • 39 chars (+39)
  • Two multi-char strings: n(input) and ''.join(...) (+20)
  • One list: sorted(...) (+20)
  • Can reverse direction depending on the parameter d (-10)

Python lambda function (non-reversible), 67

lambda n:''.join(sorted(n))

EDIT: Input should be a string. I am considering the penalty of using that string directly.

share|improve this answer
    
I clarified the game a little above, particularly about using built-in sorts. A generator might be OK, but the Python help (for 2 and 3 both) clearly states raw_input([prompt]) -> string, so sorted(raw_input()) is +10. Also sorted -> new sorted list, so +20. Then, S.join -> string, so +10 again. Slice notation also implies strings, so +10 (anything else supporting slice notation would arguably be +20). So I calculate 73 and 108, respectively. –  kojiro Mar 29 at 19:53
    
@kojiro Please clarify: Can I use a function that takes the string of the number as an argument(I accept the penalty). Can I use a function that prints instead of returning? –  user80551 Mar 30 at 7:19
    
Please see note 4. (Although on a specific note, I'm curious why you didn't use a lambda here.) –  kojiro Mar 30 at 14:47
1  
@kojiro My main issue about print/return is that print is shorter and doesn't require wrappers. I didn't know that you would allow lambda functions. Kind of facepalmed when I read that. Is it correct now? –  user80551 Mar 30 at 15:59
    
''.join(sorted(str(n))) .could you please tell me why this won't be considered as an answer?I'm kinda new –  shaktimaan Mar 31 at 9:43

C - 65

r,t,i;s(n){for(;++i;)for(t=n;t;t/=10)r=t%10-i?r:10*r+i;return r;}

The astute observer will note that this sorting algorithm runs in O(n) time on the number of digits in n.

The pragmatic observer will note that this sorting algorithm runs in time proportional to the range of signed integers on the platform, that it mutates global state which must be re-initialized between runs, and that many other sacrifices have been made in favor of brevity.

The ungolfed version is not exactly equivalent, but it better conveys the actual algorithm involved.

int s(int n)
{
    int r = 0;
    int t;
    int i;
    for(i = 0; i < 10; i++)
    {
        for(t = n; t != 0; t /= 10)
        {
            if(t % 10 == i)
            {
                r = 10 * r + i;
            }
        }
    }
    return r;
}

Here's a test harness for the function:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    if(argc != 2) return 1;
    printf("%d\n", s(atoi(argv[1])));
    return 0;
}
share|improve this answer

Java 1469

A string and array free solution in Java. 1437 characters + 32 because it only takes up to Long.MAX_VALUE as input. By using Double I could go to over 300 digits instead but that would be too tedious to implement. Anything bigger than that would need BigInteger and AFAIK that uses arrays internally. If you use less than 19 digits for the input the output will have leading zeroes. Negative input will give all zeroes and anything not a number will cause an exception.

For the sort I used the easiest I could think of so it's pretty inefficient. (should be O(n*n))

input:  9212458743185751943
output: 1112233444555778899

I know this doesn't really compare to the solutions in other languages but I feel this at least is the shortest I can get it in Java. (if anyone knows how to get this even shorter feel free to edit/comment)

class D
{
    long c,d,e,f,g,h,k,l,m,n,o,p,q,r,s,t,u,v,w;
    long x;

    public D(Long a)
    {
        x = a;
        c = g();
        d = g();
        e = g();
        f = g();
        g = g();
        h = g();
        k = g();
        l = g();
        m = g();
        n = g();
        o = g();
        p = g();
        q = g();
        r = g();
        s = g();
        t = g();
        u = g();
        v = g();
        w = g();
        int i=0;
        while(i++ < 19) s();
        System.out.printf("%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d",c,d,e,f,g,h,k,l,m,n,o,p,q,r,s,t,u,v,w);
    }

    long g()
    {
        if( x <= 0 ) return 0;
        long b = x % 10;
        x = x / 10; 
        return b;
    }

    void s()
    {
        if(c > d) {c += d; d = c - d; c -= d;}
        if(d > e) {d += e; e = d - e; d -= e;}
        if(e > f) {e += f; f = e - f; e -= f;}
        if(f > g) {f += g; g = f - g; f -= g;}
        if(g > h) {g += h; h = g - h; g -= h;}
        if(h > k) {h += k; k = h - k; h -= k;}
        if(k > l) {k += l; l = k - l; k -= l;}
        if(l > m) {l += m; m = l - m; l -= m;}
        if(m > n) {m += n; n = m - n; m -= n;}
        if(n > o) {n += o; o = n - o; n -= o;}
        if(o > p) {o += p; p = o - p; o -= p;}
        if(p > q) {p += q; q = p - q; p -= q;}
        if(q > r) {q += r; r = q - r; q -= r;}
        if(r > s) {r += s; s = r - s; r -= s;}
        if(s > t) {s += t; t = s - t; s -= t;}
        if(t > u) {t += u; u = t - u; t -= u;}
        if(u > v) {u += v; v = u - v; u -= v;}
        if(v > w) {v += w; w = v - w; v -= w;}
    }

    public static void main(String[] y)
    {
        D d = new D(Long.parseLong(y[0]));
    }
}
share|improve this answer

C (222)

static int a[10],r=1;o(n,c){while(n--)printf("%""i",c);}p(){int n;for(n=r<0?9:0;n>=0&&n<10;n+=r)o(a[n],n);}main(int _,char**v){char*s=v[1];if(*s=='-'){r=-1;++s;}do++a[*s-'0'];while(*++s);p();}

Points:

  • 192 (192 Chars)
  • 40 (2 Arrays: argv(v) and a)
  • 0 (no multi char strings)
  • 0 (it's not limited to n digits)
  • -10 (sorts reverse if the number (argv[1]) is negative)

    = 222 Points

Flags needed to get rid of the 1000 compiler warnings: gcc -Wno-implicit-function-declaration -Wno-return-type -Wno-implicit-int -Wno-char-subscripts -o count2 counta2.c

"Better" readable:

static int a[10],r=1;
o(n,c){while(n--)printf("%""i",c);}
p(){int n;for(n=r<0?9:0;n>=0&&n<10;n+=r)o(a[n],n);}
main(int _,char**v){char*s=v[1];if(*s=='-'){r=-1;++s;}do++a[*s-'0'];while(*++s);p();}

Somewhat ungolfed:

static int a[10],r=1;
o(n,c){
    while(n--) printf("%""i",c);
}
p(){
    int n;
    for(n=r<0?9:0;n>=0&&n<10;n+=r) o(a[n],n);
}
main(int _,char**v){
    char*s=v[1];
    if(*s=='-'){
        r=-1;
        ++s;
    }
    do ++a[*s-'0']; while(*++s);
    p();
}
share|improve this answer
    
Why use "%""i" instead of "%i"? They compile to the same thing, so you're just wasting two chars. –  Gabe Mar 31 at 15:44
    
@Gabe Yes I'm wasting 2 Chars but "%i" is a "multi char string" (10 Points) where "%""i" is not ... at least that's what people argumented here... –  max.haredoom Mar 31 at 21:41

Common Lisp - 126

(defun s(n p)(labels((a(n)(if(= 0 n)()(cons(mod n 10)(a (floor n 10)))))(b(a)(if(null a)0(+(car a)(* 10(b(cdr a)))))))(b(sort(a n) p))))

The ungolfified (stylistically as well as lexically, but functionally identical) version:

(defun sorta (n p)
  (labels ((digits (n)
             (unless (zerop n)
               (multiple-value-bind (quotient remainder)
                   (truncate n 10)
                 (cons remainder (digits quotient)))))
           (digit-cat (digits)
             (if (null digits)
                 0
               (+ (car digits)
                  (* 10 (digit-cat (cdr digits)))))))
    (digit-cat (sort (digits n) p))))

The digits of a negative number are treated as having negative value, and digits are sorted least-significant-first (i.e., little-endian). Examples:

CL-USER> (sorta 1234 #'<)
=> 4321
CL-USER> (sorta 12344321 #'<)
=> 44332211
CL-USER> (sorta 12344321 #'>)
=> 11223344
CL-USER> (sorta -12344321 #'>)
=> -44332211
CL-USER> (sorta 0 #'>)
=> 0
CL-USER> (sorta 8675309 #'<)
=> 9876530

There are 136 characters in the golfed version, including whitespace. It uses no strings and no arrays, and handles arbitrary-precision integers, including negative integers. The sorting is parameterized on a binary predicate which defines a total ordering on the integers in [-9, 9], including but not limited to < and >:

CL-USER> (sorta 3546219870 (lambda (a b)
                             (cond ((and (evenp a)
                                         (oddp b))
                                    t)
                                   ((and (evenp b)
                                         (oddp a))
                                    nil)
                                   (t
                                    (< a b)))))
=> 9753186420

This gives a score of 126.

share|improve this answer

Is there a reason I dont see this solution already?

Ruby

pry(main)> 52146729.to_s.split("").sort.join.to_i
=> 12245679

Am not sure how to score this. The split would generate an array, but beyond that not sure.. 38 chars + 2x20 for arrays? Or should it include all arrays that sort might create internally?

share|improve this answer

VBScript - 76 (96?)

x = "7892347684578892348025023389054859034234"

for i=0 to 9:n=n&string(len(x)-len(replace(x,i,"")),""&i):next:x=n

' x -> 00002222233333344444455556777888888889999

66 character + 10 for the use of string n
(Don't know if the use of the replace function and string function that returns n amount of character x is counted as an extra string).

It counts the amount of a certain digit by comparing the length of the original string with the same string with the certain digit replaced. Then it attaches that amount of digits to n.

share|improve this answer

C (up to C90) or C++, 78 66 points

The function so sort an integer is called s.

s(i){t=10,a=i?s(i/t):0,b=i%t,c=a%t;return c>b?t*s(a-c+b)+c:t*a+b;}

Scoring:

  • 66 Characters (+66)
  • 0 arrays (+0)
  • 0 strings (+0)
  • Range defined by machine (size of int) (+0)
  • Only one sorting direction (-0)

Old version (78 points, works also with C++ and more modern C versions)

int s(int i){int t=10,a=i?s(i/t):0,b=i%t,c=a%t;return c>b?t*s(a-c+b)+c:t*a+b;}
share|improve this answer

Python 3 sleepsort (168)

With absolutely no list or loop, only generators.

import math, threading
n=input()
if any(threading.Timer(x,lambda x:print(x,end='',flush=1),(x,)).start()for x in(n//10**i%10for i in range(math.log10(n)//1+1))):pass

could probably be improved.

share|improve this answer

JavaScript 416 / 185

No Arrays, no Strings, no arbitrary length constraint...

But sorting up/down would have used up more than 10 characters ^^ But I found the idea of counting digits and printing them interesting - maybe someone can use this idea in GolfScript and win the prize ;-)

var x=window.prompt(),y=0,z=0,a=0,b=0,c=0,d=0,e=0,f=0,g=0,h=0,i=0,j=0;
do
{
    z=x%10;
    x=(x-z)/10;
    if(!z)a++;
    if(z==1)b++;
    if(z==2)c++;
    if(z==3)d++;
    if(z==4)e++;
    if(z==5)f++;
    if(z==6)g++;
    if(z==7)h++;
    if(z==8)i++;
    if(z==9)j++;
}while(x);

while(a--)y=y*10;
while(b--)y=y*10+1;
while(c--)y=y*10+2;
while(d--)y=y*10+3;
while(e--)y=y*10+4;
while(f--)y=y*10+5;
while(g--)y=y*10+6;
while(h--)y=y*10+7;
while(i--)y=y*10+8;
while(j--)y=y*10+9;

alert(y);

The same code shorter, using eval: (but that would likely be considered using strings...)

var i = window.prompt(),o=0,i0=0,i1=0,i2=0,i3=0,i4=0,i5=0,i6=0,i7=0,i8=0,i9=0;
do
{
    eval("i"+i%10+"++");
    i = ~~(i/10);
} while (i > 0)

for(var j=0;j<10;j++) while (eval("i"+j+"--")>0) o = o*10+j;

alert(o);
share|improve this answer
    
You can shorten the longer version by 30 bytes by using 1-character names instead of iN. –  Glenn Randers-Pehrson Mar 31 at 16:35
    
@GlennRanders-Pehrson Thank you :-) –  Falco Apr 1 at 8:04

Racket 97

97 points (87 +20 for two strings, -10 for sorting, no arrays)

(define(s n <)(string->number(list->string(sort(string->list(number->string n))<))))

This uses lists of chars so you need to give it a char comparison function like char<? or char>?. I feel this also passes as ungolfed since it's not much to do than add spaces and increase variable names. My old version is perhaps more honorable :)

Old version without strings:

110 points (120 bytes (utf-8) - 10 for allowing for changing sort order. It uses no strings and no arrays)

(define(S d <)(foldl(λ(x a)(+(* a 10)x))0(sort(let L((l'())(
d d))(if(= d 0)l(L(cons(modulo d 10)l)(quotient d 10))))<)))

Ungolfed:

(define (number-digit-sort number <)
  (foldl (λ (x a) (+ (* a 10) x))
         0
         (sort (let loop ((acc '()) (number number))
                 (if (= number 0)
                     acc
                     (loop (cons (modulo number 10) acc)
                           (quotient number 10))))
               <)))

I tested it with the 100,000th fibonacci number:

(number-digit-sort (fibonacci 100000) <)
;==> 1111... basically it's the digits:
; 1 2135 times
; 2 2149 times
; 3 2096 times
; 4 2023 times
; 5 2053 times
; 6 2051 times
; 7 2034 times
; 8 2131 times
; 9 2118 times

And the same in opposite order:

(number-digit-sort (fibonacci 100000) >)
; ==> 999... and the digest is
; 9 2118 times
; 8 2131 times
; 7 2034 times
; 6 2051 times
; 5 2053 times
; 4 2023 times
; 3 2096 times
; 2 2149 times
; 1 2135 times
; 0 2109 times
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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