3 of 6 added 343 characters in body

GolfScript, 30 chars (35 as named function, 31 as full program)


This code takes an array on the stack and sorts its unique elements in descending order by number of occurrences. For example, if the input array is:

["John" "Doe" "Dick" "Harry" "Harry" "Doe" "Doe" "Harry" "Doe" "John"]

then the output array will be

["Doe" "Harry" "John" "Dick"]

Note: The code above is a bare sequence of statements. To turn it into a named function, wrap it in braces and assign it to a name, as in:


Alternatively, to turn the code into a full program that reads a list from standard input (using the list notation shown above) and prints it to standard output, prepend ~ and append ` to the code. The initial [ can be omitted in this case (since we know there will be nothing else on the stack), so that the resulting 31-character program will be:


How does it work?

  • The initial $ sorts the input array, yielding:

    ["Dick" "Doe" "Doe" "Doe" "Doe" "Harry" "Harry" "Harry" "John" "John"]
  • The code (0@{.3$=.{;;)}*}/ removes and counts consecutive duplicates while dumping the elements of the array onto the stack. This is the tricky part of the code, so it probably deserves a closer look:

    • ( shifts the first element off the array, 0 just pushes a literal zero onto the stack, and @ pulls the original array on top of the stack. Thus, after (0@, the stack looks like this:

      "Dick" 0 ["Doe" "Doe" "Doe" "Doe" "Harry" "Harry" "Harry" "John" "John"]
    • The { }/ construct is basically a for-each loop: it takes the array off the top of the stack, pushes each name in it onto the stack one at a time, and runs the code between the braces after each name is push onto the stack. Thus, at the beginning of the first iteration, the stack looks like this:

      "Dick" 0 "Doe"
    • Within the loop body, .3$= compares the topmost and third-topmost elements on the stack (i.e. the current and previous names), pushing 1 onto the stack if they're equal and 0 otherwise, giving:

      "Dick" 0 "Doe" 0
    • The following . duplicates the 0, and the { }* pops the copy off the stack and uses it as the number of times to run the code in the braces. Thus, if the result of the comparison is 0, this part of the loop is a no-op.

      However, if the result is 1 (i.e. if the last two names are equal), then the inner loop body ;;) will run once: it simply pops the topmost two elements (the 1 and the duplicate name) off the top of the stack, and then increments the now-topmost value on the stack. This leaves the stack looking exactly as it was before this iteration of the outer loop, except that the topmost value has been incremented once.

    At the end, the stack will thus look like this:

    "Dick" 0 "Doe" 3 "Harry" 2 "John" 1

    (The counts are offset by one, but that's OK, since we only care about the relative values.)

  • The ] gathers everything put on the stack since the previous [ into an array, and the -2/ reverses the array and splits it into chunks of two elements, giving:

    [[1 "John"] [2 "Harry"] [3 "Doe"] [0 "Dick"]]
  • The $ sorts this array, giving:

    [[0 "Dick"] [1 "John"] [2 "Harry"] [3 "Doe"]]

    the 0,* flattens it to:

    [0 "Dick" 1 "John" 2 "Harry" 3 "Doe"]

    and -2% extracts every second element starting from the end, yielding the desired output:

    ["Doe" "Harry" "John" "Dick"]