Perl Golf Part 2.1

| 22 Comments
It seems that I missed a crucial part to the rules for my first round of Perl golf:

The challenge is to sort inputs in @ARGV without using Perl's "sort", in as few characters as possible.

To those who put brain cycles into this, I am sorry, but really the shortest solution without this rule is probably just:

print sort@ARGV

So here's to another try at this.

Additionally, to anyone who wants to say this is produces bad code: I KNOW! The point is to exercise the noggin, and think of new ways to solve problems using our favorite language.


22 Comments

I am violating a bunch of rules, and this can be shorter, but I really like it:

#!perl
$f=a;($f)++for-1..344569;$"=",";exec"$^X -le'print for+$f {\$a-\$b}@ARGV'"

Here is a real answer using a minimal quicksort implementation in 122 characters:

#!/usr/bin/perl -l
sub f{my$p=pop;return$p
if!@_;@_=&f;@a=@b=%c;$p>$_?push@a,$_:push@b,$_
for@_;@a,$p,@b}print for f@ARGV

Not quite done with it (there has to be a better way to deal with the pushes)/

Shaved off two more characters:

#!/usr/bin/perl -l
sub f{my$p=pop;return$p
if!@_;@_=&f;@a=@b=%c;push@{$p>$_?\@a:\@b},$_
for@_;@a,$p,@b}print for f@ARGV

What is the target length?

Selection sort is a winner in terms of characters (108), but I worry about its performance:


#!/usr/bin/perl -l
f:for$n(@ARGV){for$i(0..$#s){splice(@s,$i,0,$n)^next
f if$s[$i]>$n}push@s,$n}print for@s

Shaved off another two from selection sort:
#!/usr/bin/perl -l
f:for(@ARGV){for$i(0..$#s){splice(@s,$i,0,$_)^next
f if$s[$i]>$_}push@s,$_}print for@s

133 symbols:

sub p{my@a=([],[pop],[]);push@{$a[1-($a[1][0]$_)]},$_ for@_;@$_ and$_=[p(@$_)]for@a[0,2];return map{@$_}@a;}print join',',p @ARGV

or full variant

use 5.010;
use Data::Dump;
use strict;

sub mysort {
my @h = ([],[pop],[]);
push @{$h[1 - ($h[1][0] $_)]},$_ for @_;
@$_ and $_ = [mysort(@$_)] for @h[0,2];
dd @h;
return map { @$_ } @h;
}

dd mysort @ARGV;

blog parser ate some symbols...

full variant - http://nopaste.info/c12a00d93a.html
short - http://nopaste.info/a94d303d00.html

133 symbols

Extra-inefficient selection sort in 98:

@A=@ARGV;{$R|=$A=@A>1&&$A[0]>$A[1];push@G,splice@A,$A,1;@A&&redo;(@A,@G,$R)=@G,redo if$R}print"@G"

If Chas. Owens' output format is desired, change the ending to: print for@G at a cost of two points.

Note: word-wrapping on the blog makes it impossible to see some of the code without copy-pasting. Non-scoring, manually line-wrapped version:

@A=@ARGV;{
$R|=$A=@A>1&&$A[0]>$A[1];push@G,splice@A,$A,1;
@A&&redo;(@A,@G,$R)=@G,redo if$R}print"@G"

Shaved off a bit more.

83 characters using space separated list and no #! line
f:for$A(@ARGV){$R[$_]>$A&&splice(@R,$_,0,$A)^next
f for 0..$#R;push@R,$A}print"@R"

104 characters using newline separated list and a #! line
#!/usr/bin/perl -l
f:for$A(@ARGV){$R[$_]>$A&&splice(@R,$_,0,$A)^next
f for 0..$#R;push@R,$A}print for@R

It costs more than two points, you need the -l from the shebang line for it to work properly.

I replaced ^ with > to bring down the unique character count.

new line separated without shebang (newline after next is a space)
f:for$n(@ARGV){$s[$_]>$n&&splice(@s,$_,0,$n)>next
f for 0..$#s;push@s,$n}$\=$/;print for@s

new line separated with shebang (newline after next is a space)
#!/usr/bin/perl -wf:for$n(@ARGV){$s[$_]>$n&&splice(@s,$_,0,$n)>next
f for 0..$#s;push@s,$n};print for@s

space separated (newline after next is a space)
f:for$n(@ARGV){$s[$_]>$n&&splice(@s,$_,0,$n)>next
f for 0..$#s;push@s,$n};print"@s"

Saw this while searching for the term "perl golf"
Rather late, but a nice 58:
s//@ARGV
/;$&>$'&&s/(\S+) \G(\S+)/$2 $1/while/\S+ /g;print

Mmm, that can be improved to 56 by combining the search regex with the substirute regex:

s//@ARGV
/;$2>$'&&s//$2 $1/while/(\S+)?\G ?(\S+)/g;print

or by making the original code tighter:

s//@ARGV
/;$&>$'&&s/($&)\G (\S+)/$2 $1/while/\S+/g;print

Changing the sort algorithm a bit and dropping the final newline leads to a 50:
s//@ARGV/;$'

Ah, this blog has problems with < in posts. The code for the 50 is:
s//@ARGV/;$'<$1and$_="$`$' $1"while/(\S+) /g;print

I was too focused on string processing here. Insertion sort based on an array actually works better and is less insanely inefficient (O(n**2) instead of O(n**4)). It gives this 48:

//,splice@r,(grep$_<$',@r),0,$' for@ARGV;print@r

And adding spaces inbetween and a newline at the end only costs 3 extra chars. Dropping the newline gives 50 so it's at least as good as my previous attempt

Counting positions is actually very usefull. Doing a complete reorder based on that is even shorter. 44:
@r[map//*grep($_<$',@r),@r]=@r=@ARGV;print@r

It is however sensitive to rounding errors in the string conversion. It fails to properly sort
3.99999999999999999999999999999999 and 4

Previous solutions didn't have this problem because they worked completely on the stringified (rounded) numbers. So for general use the 44 version is wrong.

Oh, and better use of parenthesis gives 43:
@r[map{//*grep$_<$',@r}@r]=@r=@ARGV;print@r

Cleaner and shorter (42):
$z[grep$_<$n,@r]=$n=$_ for@r=@ARGV;print@z

Back to the regex trick gives 41:

$z[grep$_<$',@r]=$'*//for@r=@ARGV;print@z

This however gives a warning on newer perls

Can you please explain what perl golf is? Thanks.

About this Entry

This page contains a single entry by leonard published on July 26, 2010 12:21 PM.

Perl Golf Part 2 was the previous entry in this blog.

Perl Golf My solutions is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.