Originally this came up when I was trying to figure out a useful generic sort order for the keys of a hash. I wanted it so that if the keys were numeric they would get sorted numerically, and if the keys were alphanumeric they would get lexicographical ordering. Then the thought came up what happens if there are both? Answer: Put the numbers at the top and the words at the bottom. But what happens if we have keys like 1 1a 2 2a 2b? Well they should be sorted into the numeric portion....


So here is the specification for the golf:

Write a subroutine that takes a list of keyvalues, sorts them according to the below specification and returns the sorted list.

  • Any key that is also an integer (ignoring leading spaces) should be placed in numeric order at the begining of the list. This means that the values must match  /^\s*(?0|-?[1-9]\d{0,8})$/. Note that this includes negative numbers.
  • Any key that begins with an integer as defined by the previous rule should be sorted into the correct numerical order, then by the alphanumeric portion.
  • Any key that does not satisfy the above rules should be placed into lexicographical order at the end of the list.
  • The solution must run under warnings and strictures without generating any messages or errors.
  • UPDATE: japhy raised an interesting question, concerning whether he can put a newline where perl syntax says whitespace is mandatory and thus not have the space count. After clarification from Masem (see below) it seems this is illegal. As he points out it should possible to execute the code after doing an s/\n//g.

An example input (in csv) is

1a, 2a, a10, 1, 0, 0alpha, 2, AbBa, 10, -13bravo, 42, 13, adam1, 20b, abc, a-BC, 18, 92, A-b-c, Arthur, Bravo, 25, 11a, 12a, ab-ba

Which should produce the output list

-13bravo, 0, 0alpha, 1, 1a, 2, 2a, 10, 11a, 12a, 13, 18, 20b, 25, 42, 92, A-b-c, AbBa, Arthur, Bravo, a-BC, a10, ab-ba, abc, adam1

There is no requirement to print out the output, only to return it in the correct order.

A slight twist on this problem is to do the same thing above, but substituting a dictionary sort order for the lexicographical sortorder. (Dictionary sort order is where non alphabetic chars are removed and case is irrelevant.) In this case the output for the above input would be

-13bravo, 0, 0alpha, 1, 1a, 2, 2a, 10, 11a, 12a, 13, 18, 20b, 25, 42, 92, a10, AbBa, ab-ba, abc, a-BC, A-b-c, adam1, Arthur, Bravo

As I'm interested in effiency as well as code size I will rate the entries in both ways, although you can submit different subroutines for both. Of course if the smallest is also the fastest then it wins overall...

Anyway, I hope this is interesting to you all, it certainly was fun working on it for me.

Oh, and heres my attempts, but I'm sure they won't be winners.

sub demerphq_lexi { # 1 1 2 3 4 5 6 +7 8 8 #123456789012345678901234567890123456789012345678901234567890123456789 +01234567890123456 map{$$_[2]}sort{defined$$a[0]&&defined$$b[0]?$$a[0]-$$b[0]||$$a[1]cmp +$$b[1]:!$$a[0]&&! $$b[0]?$$a[1]cmp$$b[1]:!$$a[0]&&$$b[0]?1:-1}map{/^\s*(0|-?[1-9]\d{0,8 +})?(\D.*)?/s;[$1, $2||"",$_]}@_ # 86*2+13=185 } sub demerphq_dict { # 1 2 3 44 5 6 +7 7 #123456789012345678901234567890123456789012345678901234567890123456789 +01234567 map{$$_[2]}sort{defined$$a[0]&&defined$$b[0]?$$a[0]-$$b[0]||$$a[1]cmp +$$b[1]:! $$a[0]&&!$$b[0]?$$a[1]cmp$$b[1]:!$$a[0]&&$$b[0]?1:-1}map{($b=lc)=~s/[ +^a-z]//g ;[/^\s*(0|-?[1-9]\d{0,8})?/,$b||"",$_]}@_ # 77*2+41=195 }
So my lexicographical solution is 185 chars, and my dictionary solution is 195...

Now lets see how many chars I wasted... ;-)

PS Im really interested to see if someone can come up with a GRT version of the sort, so bonus points if you can do it with a GRT instead of an ST, and even more bonus points for doing it without either...

Yves / DeMerphq
When to use Prototypes?