Re (tilly) 1: (Golf) Nearest Neighbors
by tilly (Archbishop) on Apr 05, 2001 at 00:29 UTC
|
sub nn {
my@x=@_[0,1];@_=sort{abs$x[0]-$x[1]<abs$a-$b or@x=($a,$b);$a<=>$b}@_;@
+x
}
(75...)
UPDATE
MeowChow pointed out that the parens for the arguments
of abs were not needed. That cut out 3 characters.
Plus by reversing the order of the comparison I managed
to substitute or for and, saving another. That makes it
71...
UPDATE 2
This is sick and slick.
sub nn {
()=sort{abs$_[0]-$_[1]<abs$a-$b or@_=($a,$b);$a<=>$b}@_;@_
}
Enjoy verifying that I am perfectly safe in using @_ as my
temporary array. I think that 58 is the best I can do...
UPDATE 3</B
petral sent me a /msg explaining how to remove 3 chars
from that solution. I would like to see him post that
since it was his idea, but until he does I want to note
that that solution can be beaten. | [reply] [Watch: Dir/Any] [d/l] [select] |
|
OK, a couple of simple typographic manipulations to bring it to 55:
sub nn {
()=sort{abs$a-$b>abs$_[0]-$_[1]or@_=($a,$b);$a-$b}@_;@_
}
(There are advantages to being slow (or having no time!)).  I was still up over 80 strokes with my sort-based solution when I looked up and saw this guy casually strolling past Tiger Woods.
p | [reply] [Watch: Dir/Any] [d/l] |
|
Wow, that really is quite ingenious. At first I thought this might fail on some inputs, if sort doesn't compare two sequential numbers, but then I realized that sort requires that every two sequential elements are compared (in some order). Amazing...
MeowChow
s aamecha.s a..a\u$&owag.print | [reply] [Watch: Dir/Any] |
|
Excellent solution.
The interesting thing about Perl Golf is how different people tackle problems in terms of their favourite tools; map, sort, regex, grep, closures, slices or whatever.
Just for fun I ran your solutions through Perltidy as a test case. Here is the output:
sub nn {
my @x = @_[0, 1];
@_ = sort {
abs $x[0] - $x[1] < abs $a - $b or @x = ($a, $b);
$a <=> $b;
} @_;
@x
}
sub nn {
() = sort {
abs $_[0] - $_[1] < abs $a - $b or @_ = ($a, $b);
$a <=> $b;
} @_;
@_
}
John. --
| [reply] [Watch: Dir/Any] [d/l] |
|
Okay Monks,
I would like to make my contribution of this golf, but after tilly's one, I can't continue. Maybe I'll find a 120 characters so :) ... that over for me.
BoBiOne KenoBi ;)
| [reply] [Watch: Dir/Any] |
Re: (Golf) Nearest Neighbors
by danger (Priest) on Apr 04, 2001 at 14:42 UTC
|
As Tortue points out, all the ones using lexigraphic sorting fail on
some sets of numbers. Stripping leading spaces and newlines, my stab
weighs in at 87 characters:
sub nn {
@_=sort{$a<=>$b}@_;
$_[1]-$_[0]>$_[$_+1]-$_[$_]and@_[0,1]=@_[$_,$_+1]for 1..@_-2;
@_[0,1]
}
| [reply] [Watch: Dir/Any] [d/l] |
|
Very nice! Sniping one character gives:
sub nn {
@_=sort{$a<=>$b}@_;
$_[1]-$_[0]>$_[$_]-$_[$_-1]and@_[0,1]=@_[$_,$_-1]for 2..$#_;
@_[0,1]
}
The number to beat is 86...
MeowChow
s aamecha.s a..a\u$&owag.print | [reply] [Watch: Dir/Any] [d/l] |
|
This doesn't deal with duplicates. If you want to deal with duplicates, I think you change it to:
sub nn {
@_{@_}=0;@_=sort{$a<=>$b}keys%_;
$_[1]-$_[0]>$_[$_]-$_[$_-1]and@_[0,1]=@_[$_,$_-1]for 2..$#_;
@_[0,1]
}
That brings the total from 86 to 99. I'm not sure if the spec requires that duplicates be treated as one element or separate elements. | [reply] [Watch: Dir/Any] [d/l] |
Re: (Golf) Nearest Neighbors
by snowcrash (Friar) on Apr 04, 2001 at 13:27 UTC
|
# 79 chars
sub nn9 {
@_=sort@_;$_{$_[$_]-$_[$_-1]}=[@_[$_-1,$_]]for 1..$#_;@{$_{(sort key
+s%_)[0]}}
}
snowcrash ////// | [reply] [Watch: Dir/Any] [d/l] |
Re: sort problem? (Golf) Nearest Neighbors
by Tortue (Scribe) on Apr 04, 2001 at 14:15 UTC
|
Ummm.... no doubt I'm missing something here, but when I test these functions on certain sets of values, only the first works, because sort insists on doing a lexical rather than a numeric sort.
print join(",",nn1(1,5,34,43,123,444)), "\n";
print join(",",nn2(1,5,34,43,123,444)), "\n";
print join(",",nn3(1,5,34,43,123,444)), "\n";
1,5
34,43
1,123
| [reply] [Watch: Dir/Any] [d/l] |
|
| [reply] [Watch: Dir/Any] |
Re: (Golf) Nearest Neighbors
by MeowChow (Vicar) on Apr 05, 2001 at 00:39 UTC
|
A bit late, considering tilly's death-blow, er... swing, but here's one that merlyn might appreciate, weighing in at 84 chars:
sub nn {
my($p,@l)=sort{$a<=>$b}@_;@{(sort{$$a[0]<=>$$b[0]}map[$_-$p,$p+0,$p=
+$_],@l)[0]}[1,2]
}
MeowChow
s aamecha.s a..a\u$&owag.print | [reply] [Watch: Dir/Any] [d/l] |
|
| [reply] [Watch: Dir/Any] [d/l] |
|
Ah, I should think a bit more before submitting. Here is
a 44 (and I should also mention it only works for smallish natural numbers, all different and at least 2 arguments):
sub nn{$a|=2x$_.3for@_;$b.=2until$a=~/3$b(3)/;@a=@-}
The need for the assign is a perlbug, otherwise it would be 41
| [reply] [Watch: Dir/Any] [d/l] |
Re: (Golf) Nearest Neighbors
by jmcnamara (Monsignor) on Apr 04, 2001 at 13:36 UTC
|
Omitting leading whitespace this is 97 chars:
sub nn_single {
@_=sort{$a<=>$b}@_;
$_{abs$_[$_]-$_[$_-1]}=[$_-1,$_]for 1..$#_;
@_[@{$_{(sort{$a<=>$b}keys%_)[0]}}]
}
I worked on this without looking at your solutions but it is very similar to your nn3. Great minds?
If the list contains duplicates then the following will work.
Omitting leading whitespace this is 114 chars.
sub nn_dup {
my$s=sub{sort{$a<=>$b}keys%_};
@_{@_}=0;
@_=&$s;
%_=();
$_{abs$_[$_]-$_[$_-1]}=[$_-1,$_]for 1..$#_;
@_[@{$_{(&$s)[0]}}]
}
Update: I've updated this for a numerical sort and included snowcrash's %_ hack. danger, as usual, looks like the one to beat.
John.
--
| [reply] [Watch: Dir/Any] [d/l] [select] |
(tye)Re: (Golf) Nearest Neighbors
by tye (Sage) on Apr 04, 2001 at 22:32 UTC
|
sub nn{my$x=pop;(sort{$b<=>$a}map{abs($_-$x)}@_)[0,1]}
I guess that is 46 chars.
Update: Sorry (oops), make that:
sub nn{my$x=pop;
(map$_->[0],sort{$a->[1]<=>$b->[1]}map[$_,abs$_-$x],@_)[0,1]}
# or
sub nn2{my$x=pop;
my@d=map abs$_-$x,@_;@_[(sort{$d[$a]<=>$d[$b]}0..$#_)[0,1]]}
for 69 or 68 chars.
Update: Well, those last two are okay solutions for the wrong problem. *sigh* (:
-
tye
(but my friends call me "Tye") | [reply] [Watch: Dir/Any] [d/l] [select] |
|
print nn(1, 4, 7);
returns 2 elements that are not in the input list.
UPDATE
print nn(1, 5, 7);
print nn2(1, 5, 7);
# Hmmmm
print nn(1, 5, 11);
print nn2(1, 5, 11);
after your first update all result in 51. Care to try
again? :-) | [reply] [Watch: Dir/Any] [d/l] [select] |
|
Just following the (ambiguous) specification. Are you looking for numbers from (5,11) that are close to 1 or numbers from (1,5) that are close to 11? I didn't find an API spec and found others using pop so I went ahead with the 2-character savings.
Or am I only supposed to return one number if the "two closest" are both on "the same side" of the search-for number? That wasn't clear to me either so I just went with "return the two closest" without trying to assume a bunch of extra subtle meaning to that phrase. No, I'm not going to produce a version that sometimes returns only one number. (:
-
tye
(but my friends call me "Tye")
| [reply] [Watch: Dir/Any] |
|
|
|
|
Re: (Golf) Nearest Neighbors
by satchboost (Scribe) on Apr 04, 2001 at 19:14 UTC
|
While this may not have many new ideas, it does weigh in at 117 characters and deal with dups:
sub nn2 {
my$s=sub{sort{$a<=>$b}keys%_};
@_{@_}=0;@_=&$s;%_=();
$_{abs($_[$_]-$_[$_+1])}=[@_[$_,$_+1]]for 0..$#_;
@{$_{(&$s)[0]}}
}
Neat problem! | [reply] [Watch: Dir/Any] [d/l] |