5
\$\begingroup\$

I wrote some perl to sort by debian package version number (specification here). Whilst readable, it was disappointingly long (114 lines, 2042 characters) - shocking. So this challenge is to produce the shortest program (in perl or otherwise) which takes debian package version numbers on STDIN separated by \n, sorts them, and puts the output on STDOUT separated by \n.

You can produce an dataset of debian versions numbers on a debian/ubuntu box by:

apt-cache madison . | perl -n -e 'print "$1\n" if /^\S+\s+\|\s+(\S+)\s+/;'

For those not on Debian / Ubuntu I've put a random selection of 1000 here. The sorted version of this sample is here. The md5sum of the unsorted and sorted versions (check they each end with a \n) are:

5ffd12d3f59b06619a712e92791c0dfd  input.sample
e6b2d03ddfd9491c5bdf2594a5aa82e5  output.sample

(note as Ventero points out in the comments, there are certain equivalent version numbers, e.g. lines 135-138 out of the output, where 08 and 8 are equivalent and thus the sort order is arbitrary)

For the purposes of verifying your input, you can install Debian::Dpkg::Version from CPAN and use the following to test:

#!/usr/bin/perl

use strict;
use warnings;
use Debian::Dpkg::Version;

my @input;

while (<>)
{
    chomp;
    push @input, $_;
}

my @output = sort version_compare (@input);
print join("\n", @output)."\n";

The following test data is thus sorted in the correct order, and (I believe) only contains lines complying with the Debian spec above, with each version being distinct:

0~~-~~
0~~-~
0~-~~
0~-~
0~-0
0-0
0-1
0-02
3-0
04-0
04a-0
5-0
04:3-0
5:3-0
06:3-0
06:3a-0
06:3a-01
06:3a-3~
06:3a-3
6:3a-04
06:3a-05
06:3.-0
06:3:a
06:3:a-01
06:3:a-05

The rules are:

  • Package name sorting must be exactly per the Debian spec
  • No inclusion of external modules written to perform Debian packages sorting, as that would make it rather easy. Therefore golfing the above test program will not produce a legal answer, as it includes Debian::Dpkg::Version. You may of course look to the source of that module for inspiration if you lack imagination, but I believe there are shorter ways to do this.
  • You may assume that any input line whose format is invalid (i.e. does not constitute a version number conforming to the debian spec) must be retained, but may be sorted arbitrarily.
  • Equivalent version numbers may be sorted arbitrarily, e.g. 0.08-1 is equivalent to 0.8-1 as the numeric components 08 and 8 are compared as integers.
  • Save in respect of the arbitrary sort order of any lines not constituting version numbers conforming to the debian spec, and equivalent version numbers, your output should be identical to the test program above.
\$\endgroup\$
  • \$\begingroup\$ Could you please also provide the sorted version of your input? And do we have to reject invalid version numbers? \$\endgroup\$ – Ventero Jul 5 '14 at 20:45
  • \$\begingroup\$ @Ventero I've added a test program and md5sum of the input and output sample data. Invalid version numbers should be retained but may be sorted arbitrarily. \$\endgroup\$ – abligh Jul 5 '14 at 21:13
  • \$\begingroup\$ @Ventero oh, and a link to the sorted data which is what you actually asked for :-) \$\endgroup\$ – abligh Jul 5 '14 at 21:33
  • \$\begingroup\$ Nice, thanks a lot. Looks like I've still got a bug or two to iron out ... \$\endgroup\$ – Ventero Jul 5 '14 at 21:50
  • \$\begingroup\$ Regarding lines 135-138 in your reference output: Those lines can appear in any order, as the integer value of 08 and 8 are compared for sorting, correct? (Also, a warning to others: files downloaded from pastebin have their lines terminated with \r\n) \$\endgroup\$ – Ventero Jul 5 '14 at 22:06
3
\$\begingroup\$

Ruby 2.0, 145 179 characters

puts$<.sort_by{|a|(1..3).map{|i|"#{a[/^(\d+:)?(.+?)(-[^-]+)?
/,i]}".scan(/(\D*)(\d*)/).map{|w,n|w.bytes.map{|c|c<126?c>58?c:c+99:-1}+[0,n.hex]}}}

Correctly sorts both the linked reference input (though it generates a slightly different output order due to different sorting of equivalent version numbers, e.g. 1.06-2 vs 1.6-2) and the included test data.

\$\endgroup\$
  • 1
    \$\begingroup\$ I've verified this works (158 characters when I verified). \$\endgroup\$ – abligh Jul 6 '14 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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