# Sort numbers represented in an unknown base

Given a list of strings, sort the list as numbers without knowing what base is used. The values of the digits are also unknown (it is possible that `'1'` > `'2'`).

Since the values of digits are unknown, use Benford's Law (or First Digit's Law) to determine the relative value of the digits. For distributions that follow Benford's Law, lower valued digits appear as a leading digit more frequently than higher valued digits.

Rules

• This is
• The list of strings can come from a source of your choosing (stdin, variable, file, user, etc.)
• Strings are limited to ASCII characters.
• Characters that do not appear as a leading character have the highest values. (assume there are no zeros, and sort strictly by leading frequency.)
• Characters that appear as leading digits the same number of times as other characters are weighted equally.

Example

Unsorted

``````['c','ca','ac','cc','a','ccc','cx','cz','cy']
``````

Sorted

``````['c','a','cc','ca','cz','cy','cx','ac','ccc']
``````

Note: In the example, `'cz'`,`'cy'` and `'cx'` can appear as the 5th, 6th and 7th elements in any order since the digits `'x'`,`'y'` and `'z'` are equally weighted.

-
"Strings are limited to ASCII characters." Your example only shows alphanumerics (actually only alphabetic characters). Do you mean all ASCII characters, or just [0-9a-zA-Z], and do lower case letters count the same or differently from upper case characters? – Joshua Taylor Jun 13 '14 at 19:33
All ASCII characters should be supported, and uppercase and lowercase are different. – Rynant Jun 13 '14 at 21:02

# Python, 59 108112

``````sorted(a,None,lambda x:(-len(x),map(zip(*a)[0].count,x)),1)
``````

Input is provided as the list `a`, and this expression produces the sorted list (+2 characters to assign to a variable). This sorts the list in reverse by negated length and then by frequency.

-
+1 Nicely done. Didn't think it could be done space efficiently in single expression. – Seeq Jun 12 '14 at 18:24
Nice! I didn't know about `zip` with `None`. Though it doesn't work in Python 3 which would use `itertools.zip_longest`. – Rynant Jun 12 '14 at 18:54
`None` can't compare to integers in Python 3, so it would fail anyway. – nneonneo Jun 12 '14 at 18:55
@nneonneo Right, `fillvalue` would have to be set to something less than the smallest value. – Rynant Jun 12 '14 at 19:17
And I thought I knew something about python - nope. Could you explain your code somewhat more detailed? I'd be very happy - python newbie here. – flawr Jun 13 '14 at 9:02

# Ruby, 65

``````f=->a{a.sort_by{|s|[s.size,s.chars.map{|c|a.count{|t|t[0]!=c}}]}}
``````

Sorts lexicographically on the string's size, then each character's frequency as not the leading digit.

-

## Java (261)

``````void s(String[]s){int[]a=new int[128];for(String t:s)a[t.charAt(0)]++;java.util.Arrays.sort(s,(o,p)->{int j=o.length()-p.length();if(j!=0)return j;for(int i=0;i<Math.min(o.length(),p.length());i++){j=a[p.charAt(i)]-a[o.charAt(i)];if(j!=0)return j;}return 0;});}

void s(String[] s) {
int[] a = new int[128];
for (String t : s) {
a[t.charAt(0)]++;
}
java.util.Arrays.sort(s, (o, p) -> {
int j = o.length() - p.length();
if (j != 0) {
return j;
}
for (int i = 0; i < Math.min(o.length(), p.length()); i++) {
j = a[p.charAt(i)] - a[o.charAt(i)];
if (j != 0) {
return j;
}
}
return 0;
});
}
``````

The methods takes an array of strings, and sorts the array in place. Nothing fancy about the implementation, but it does make use of the lambda expressions added to Java 8.

-

# Javascript (E6) 147

``````F=i=>(f={},i.map(x=>(f[x[0]]=-~f[x[0]])),i.map(x=>[x,[...x].map(y=>1e9-~f[y]+'')]).sort((a,b,d=a[0].length-b[0].length)=>d||a[1]<b[1]).map(x=>x[0]))
``````

Limit

Frequency values up to 1000000000: for sorting, the frequency values are merged in a big padded string

Ungolfed

``````F=i=>(
f={}, //init frequency map
i.map(x => (f[x[0]]=-~f[x[0]])), // build frequency map
i.map(x => [x, [...x].map(y=>1e9-~f[y]+'')]) // add frequency info to each element of input list
.sort((a,b,d=a[0].length-b[0].length)=>d || a[1]<b[1]) // then sort by lenght and frequency
.map( x => x[0]) // throw away frequency info
)
``````

Sidenote `X-~` increment by 1 even if the original number X is undefined or NaN

Usage

``````F(['c','ca','ac','cc','a','ccc','cx','cz','cy'])
``````

Output: `["c", "a", "cc", "ca", "cx", "cz", "cy", "ac", "ccc"]`

-