Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Re: Challenge: Nearest Palindromic Number

by Corion (Patriarch)
on Feb 02, 2005 at 20:24 UTC ( [id://427423]=note: print w/replies, xml ) Need Help??


in reply to Challenge: Nearest Palindromic Number

My hypothesis is the following:

For a number of even length ABCDEF there are three "close" palindromes:
AB(C-1)(C-1)BA
# ABCCBA
AB(C+1)(C+1)BA
For a number of odd length ABCDEFG there are also three "close" palindromes:
AB(C-1)D(C-1)BA
ABCDCBA
AB(C+1)D(C+1)BA
I brute force the closest palindrome of the three:

use strict; for my $n (1..1000000) { #for my $n (1000..1090) { my $candidate = palindrome($n); print "$n: $candidate\n"; }; use strict; sub palindrome { my ($n) = @_; my $l = int ((length $n) / 2); $n =~ /^(\d{$l})(.?)(\d{$l})$/ or return $n; my ($left,$middle,$right) = ($1,$2,$3); my @parts = map { ($left ? $left + $_ : "") . $middle . ($left ? rev +erse $left + $_ : "") } (-1, 0, 1); for (@parts) { die "$n: $_ is no palindrome" if $_ ne reverse $_; }; my $result = $parts[0]; for (@parts) { $result = $_ if abs($n - $_) < abs($n - $result); }; die "$n: $result is no palindrome" if $result ne reverse $result; return $result };

Update: On thinking a bit longer about this, I think my hypothesis above is wrong, but my code is still right, as there is the case of C == 0, which I neglected to mention. My handling of the code below, still generates the good results though.

Feh. On further testing, my code already fails for 107, where the closest palindrome is 111 and not 101 as my code finds. Oh well :-(

Replies are listed 'Best First'.
Re^2: Challenge: Nearest Palindromic Number
by johnnywang (Priest) on Feb 02, 2005 at 20:59 UTC
    The odd case is not quite right, ABCDEFG can also have: ABC(D-1)CBA, or ABC(D+1)CBA

      I thought so too, but there are close palindromic numbers that do not even have any digits in common, for example 197 has 191 (6) according to my hypothesis, but 202 is closer (5). I think I'll be cutting my losses and exhaustively search the space above the number, up to the distance to the (easily found) next smaller palindromic number. Not elegant.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://427423]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others exploiting the Monastery: (7)
As of 2024-03-28 22:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found