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.

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.

share|improve this question
    
"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 at 19:33
    
All ASCII characters should be supported, and uppercase and lowercase are different. –  Rynant Jun 13 at 21:02

4 Answers 4

up vote 7 down vote accepted

Python, 59 108 112

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.

share|improve this answer
    
+1 Nicely done. Didn't think it could be done space efficiently in single expression. –  Sieg Jun 12 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 at 18:54
    
None can't compare to integers in Python 3, so it would fail anyway. –  nneonneo Jun 12 at 18:55
    
@nneonneo Right, fillvalue would have to be set to something less than the smallest value. –  Rynant Jun 12 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 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.

share|improve this answer

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.

share|improve this answer

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"]

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.