|
Re^2: Challenge: Nearest Palindromic Number
by dragonchild (Archbishop) on Feb 02, 2005 at 21:00 UTC
|
sub build {
my ($f, $l) = @_;
my $b = reverse $f;
substr($b, 0, 1, '') if $l;
return $f . $b;
}
sub palindrate {
my $num = shift;
my $is_odd = length($num) % 2;
my $first = substr( $num, 0, int(length($num)/2 + .5 ) );
my $one = build( $first, $is_odd );
$first += $one < $num ? 1 : -1;
my $two = build( $first, $is_odd );
return ((abs($one-$num) < abs($two-$num)) ? $one : $two);
}
Being right, does not endow the right to be rude; politeness costs nothing.
Being unknowing, is not the same as being stupid.
Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.
| [reply]
[d/l] |
|
|
This works perfectly. :-)
For those who don't understand it, here's an explanation. Take the first half of the digits and build a palindrome. (Be careful, you need to keep it even/odd in size.) That palindrome is going to be larger or smaller than the original number. Adjust the first half up/down one then build a palindrome on the other side of the original number. One of those two is closest, so take the closer one.
To truly verify that it works (I'm just giving the handwaving explanation) you'll find that you actually are taking the nearest palindromes to either side in every case except where adding/subtracting from $first changes the number of digits that you have. But the only case where that happens is in 1 and numbers matching the pattern /^1(0*)(0|1)$/. In those cases $one winds up being 100...0001 and $two is wildly off. But in those cases, $one is one of the (possibly 2) acceptable answers, so the algorithm is right again.
| [reply] |
Re^2: Challenge: Nearest Palindromic Number
by tilly (Archbishop) on Feb 03, 2005 at 06:53 UTC
|
Try it with $num = 199. The answer should be 202. The answer that you give is 191. | [reply] |
|
|
tilly,
For the record, Roy Johnson was the first to produce working code. Unfortunately it was broken during some refactoring. The code that I validated originally was:
sub nearest {
my $num = shift;
my $firstlen = int(length($num)/2 + .5);
my $first = substr($num, 0, $firstlen);
my $back = reverse($first);
substr($back, 0, 1, '') if $firstlen > length($num)/2;
# Update (again): if higher, check lower and vice-versa:
my $one = $first . $back;
$first += $one < $num ? 1 : -1;
$back = reverse($first);
substr($back, 0, 1, '') if $firstlen > length($num)/2;
my $two = $first . $back;
return abs( $one - $num ) < abs( $two - $num) ? $one : $two;
}
| [reply]
[d/l] |
|
|
| [reply] |
Re^2: Challenge: Nearest Palindromic Number
by Limbic~Region (Chancellor) on Feb 02, 2005 at 19:33 UTC
|
Roy Johnson,
This fails on the same test that halley's does:
N = 1085, X = 1111
I see you updated the code, I will test it more rigorously and let you know.
| [reply] |
|
|
| [reply] |
|
|
Roy Johnson,
I tested it from N = 1 to N = 332_288 1_500_000 as well as 11_441 random numbers between 1 and 999_999_999. It provided acceptable solutions for all of them. Good job.
| [reply] |
Re^2: Challenge: Nearest Palindromic Number
by dragonchild (Archbishop) on Feb 02, 2005 at 20:03 UTC
|
| [reply] |
