Perl Golf My solutions

| 4 Comments
sub i{($i,$j)=@_;$e=$i[$j];$i[$j]=$i[$i];$i[$i]=$e}$w=$i=0;@i=@ARGV;while($w<@i){$w++;$i=0if($i+2)>@i;if($i[$i]>$i[$i+1]){i($i,$i+1);$w=0}$i++}print@i
sub i{
  ($i,$j)=@_;
  $e=$i[$j];
  $i[$j]=$i[$i];
  $i[$i]=$e
}
$w=$i=0;
@i=@ARGV;
while($w<@i){
  $w++;
  $i=0if($i+2)>@i;
  if($i[$i]>$i[$i+1]){
    i($i,$i+1);
    $w=0
  }
  $i++
}
print@i;

(150 chars)
Looping through the array and swapping elements until the lowest is in the first position. Then move to the second element and loop again. O(n^2), it works, but is confusing to look at.

Next:
sub i{($i,$j)=@_;$t=$i[$j];$i[$j]=$i[$i];$i[$i]=$t}@i=@ARGV;for($i=0;$i<@i;$i++){for($j=$i;$j<@i;$j++){i($i,$j)if($i[$i]>$i[$j])>0}}print@i
sub i{
  ($i,$j)=@_;
  $t=$i[$j];
  $i[$j]=$i[$i];
  $i[$i]=$t
}
@i=@ARGV;
for($i=0;$i<@i;$i++){
  for($j=$i;$j<@i;$j++){
    i($i,$j)if($i[$i]>$i[$j])>0
  }
}
print@i

(139 chars)
I used two nested loops that Ran in O(n^2) time to swap items around as necessary. fairly straight forward

next:
sub A{$R=shift;@A=@_;return$R if!@A;my$A=shift@A;return($R,$A,@A)if$R<$A;return($A,A($R,@A))}foreach$A(@ARGV){@A=A($A,@A)}print@A
sub A{
  $R=shift;
  @A=@_;
  return$R if!@A;
  my$A=shift@A;
  return($R,$A,@A)if$R<$A;
  return($A,A($R,@A))
}
foreach$A(@ARGV){
  @A=A($A,@A)
}
print@A

(129 chars)
Here I used an insertion sort idea with recursion. This one was probably the most fun to write, and runs in O(n^2) time. It could be modified to run in O(n log(n)) time without too much hassle

next:
#slow but works:
foreach$A(@ARGV){$R{$A}++;$V=$A if$A<$V}while($G<@ARGV){for($A=0;$A<$R{$V};$A++){print$V;$G++}$V++}
__END__
#slow but works
foreach$A(@ARGV){
  $R{$A}++;
  $V=$A if$A<$V
}
while($G<@ARGV){
  for($A=0;$A<$R{$V};$A++){
    print$V;
    $G++
  }
  $V++
}
(99 chars)
This is limited to integers, and will only work when the numbers are within a 10^10 range from min to max.
I loop through the array looking for the smallest integer, and increment a hash element for each item.
Then I start at my minimum and loop through each index, if the hash >0 I print the number that many times, and then I add one to my minimum.

I not sure what to say for O notation here. The runtime of this algorithm depends more on the range of your numbers than the number of numbers. In fact. for the *right datasets* this would run in O(n), but for others, it would do much worse than O(n^2).

Example of the first: a million numbers, all between 1 and 100, would sort in the lenght of time it took to loop through the numbers twice.
Example of the second: a hundred numbers, ranging from -100 trillion to 100 trillion. It would be faster to sort these numbers by hand.
__END__

next:
@V=@ARGV;foreach$A(@V){$G=0;foreach$R(@V){$G++if$R<$A}$f[$G]=$A}foreach(@f){$V=$_||$V;print$V}
#######

@V=@ARGV;
foreach$A(@V){
  $G=0;
  foreach$R(@V){
    $G++if$R<$A
  }
  $f[$G]=$A
}
foreach(@f){
  $V=$_||$V;
  print$V
}


(94 characters) My shortest so far.O(n^2)for each number, compare it to each number and count the number that are smaller than it. After each number, you add the position to the result array.
This runs in O(n^2) time but is clever in that you build the result array as you do your double loop the first time around. This makes for less typing.

The only problem with this approach is that you need to consider duplicates in your dataset when printing. If your dataset is entirely unique, you could get away with 71 characters here:
@V=@ARGV;foreach$A(@V){$G=0;foreach$R(@V){$G++if$R<$A}$f[$G]=$A}print@f

4 Comments

With a little pushing you can get it down to 74 characters:
for$A(@V=@ARGV){$G=0;$A>$_&&$G++for@V;$f[$G]=$A}$V=$_||$V,print$V,$/for@f

Hmm, your version seems to drop 0s and my version of your code drops them altogether.

It is even worse than I thought, given -1 0 1, it replies -1 -1 1.

This internet web site is my breathing in, really great pattern and perfect content .

About this Entry

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

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

Vacation is the next entry in this blog.

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