Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Challenge: Nearest Palindromic Number

by Limbic~Region (Chancellor)
on Feb 02, 2005 at 19:11 UTC ( #427378=perlquestion: print w/ replies, xml ) Need Help??
Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:

All,
I like palindromic* numbers. Today I thought of a problem that seems easy, but has me stumped for anything other than a brute force method.

Problem:
Given a base 10 number N, find the nearest palindromic base 10 number X to N. If N is already palindromic do nothing. If two palindromic numbers are equidistant to N, (10 - 1 = 9, 10 + 1 = 11) returning either is acceptable.

Here is my brute force implementation:

#!/usr/bin/perl use strict; use warnings; my $N = $ARGV[0] || 0; print nearest( $N ); sub nearest { my $N = shift; return $N if scalar(reverse $N) eq $N; my $pos = $N; ++$pos while scalar(reverse $pos) ne $pos; $pos = $pos - $N; my $neg = $N; --$neg while scalar(reverse $neg) ne $neg; $neg = $N - $neg; return $pos > $neg ? $N - $neg : $N + $pos; }

Challenge:
The primary goal is to solve the problem, as stated, using a technique other than the straight forward brute force method I presented. I am not personally interested in golfed solutions unless they satiate the primary goal, but feel free to add them either way to show off your talents. Additionally, having the ability to solve the problem in any base would get you bonus points.

* A palindromic number is one that is the same forwards and backwards such as 10701

Cheers - L~R

Comment on Challenge: Nearest Palindromic Number
Download Code
Re: Challenge: Nearest Palindromic Number
by halley (Prior) on Feb 02, 2005 at 19:21 UTC
    Is there something I'm missing here? Just yank the first half of the number in question, reverse THAT, and replace the last half of the number with that. Then incrementation or decrementation is easy, to find the alternative choice.

    While not the whole answer, solutions (such as the quick Roy Johnson's) would use code similar to this:

    sub palindrate { my $number = shift . ''; my $front = substr($number, 0, (length($number)+1)/2); my $back = reverse($front); chop($front) if not (length($front) % 2); return $front . $back; }

    Edge cases I can think of:

    • input is already palindromic (input is answer),
    • higher alternative needs more digits (use all-nines),
    • lower alternative needs fewer digits (use all-nines, minus a digit)
    • is '-12321-' a valid palindromic answer?

    --
    [ e d @ h a l l e y . c c ]

      halley,
      Is there something I'm missing here?

      N = 1000, X = 999
      N = 1085, X = 1111

      Cheers - L~R

        Howdy!

        ...yeah, but 1001 is equally valid as an answer...

        yours,
        Michael
        Hrm. That's just an edge case, and will only happen when you find that the palindrate($N) is greater than $N. In those cases, '9'x(length($N)-1) would exceed the decrimented '0990' value.

        I'm still thinking out loud at this stage, but it doesn't seem like you'd have to iterate at all, to find provably close palindromic numbers.

        --
        [ e d @ h a l l e y . c c ]

Re: Challenge: Nearest Palindromic Number
by Roy Johnson (Monsignor) on Feb 02, 2005 at 19:29 UTC
    I think this covers all the cases:
    my $num = shift; my $firstlen = int(length($num)/2 + .5); my $backlen = length($num) - $firstlen; my $first = substr($num, 0, $firstlen); my $closest = 0; for (1..2) { my $new = $first . substr(reverse($first), -$backlen); $closest = $new if abs($new - $num) < abs($closest - $num); $first += $num <=> $closest; } print "Closest palindrome to $num is $closest\n";

    Caution: Contents may have been coded under pressure.
      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.

      Cheers - L~R

        I hadn't seen that at the time I posted. And I had modified it by the time your response showed up. Now I've modified it again, and I think it's airtight. :-)

        Caution: Contents may have been coded under pressure.
      1048 results in 0 as the closest palindrome.

      It would help if I learned to cut'n'paste.

      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.

      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.

        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.

      Try it with $num = 199. The answer should be 202. The answer that you give is 191.
        I've been refactoring and got my <=> line reversed. Thanks. It's fixed now.

        Caution: Contents may have been coded under pressure.
        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; }

        Cheers - L~R

Re: Challenge: Nearest Palindromic Number
by dragonchild (Archbishop) on Feb 02, 2005 at 19:49 UTC
    I don't think this yields an elegant solution. At least, not one that is anywhere faster than the brute force one.

    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.

      Howdy!

      The problem is to find which of the two nearest palindromic numbers is closest. If missing one of the pair when both are equally distant is acceptable (as in the problem as laid out here), then slinging strings is both fast and elegant, given that palindromicity is a string property, not a numeric property.

      The solution Roy_Johnson got into print before I could (and which is a refinement of halley's, attacks the given problem about as elegantly as you can.

      yours,
      Michael
Re: Challenge: Nearest Palindromic Number
by Corion (Pope) on Feb 02, 2005 at 20:24 UTC

    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 :-(

      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.

Re: Challenge: Nearest Palindromic Number
by murugu (Curate) on Feb 03, 2005 at 07:38 UTC

    Hi guys this is my try.

    use strict; use warnings; sub palindrome{ my ($n)=shift; my ($a,$b); $b=$a=$n; return $a if ($a eq reverse $a); 1 while (++$a != (reverse $a)); 1 while (--$b != (reverse $b)); (abs($n-$a)>abs($n-$b))?$b:$a; }

    Please give your kind suggestions.

    Murugesan.

Re: Challenge: Nearest Palindromic Number
by BrowserUk (Pope) on Feb 03, 2005 at 09:10 UTC

    You said you'd consider an obfu if it worked? It takes a somewhat different approach too.

    local$/;use Compress::Zlib;use List::Util qw[ reduce ];;;;;; $_=reduce{ref$a?$a:$a+$b<=$ARGV[0]?($a+=$b):[$a,$a+$b];;;;;; }unpack'U0xU*',Compress::Zlib::memGunzip(unpack'u*',<DATA>); print $ARGV[0]-$_->[0]<=$_->[1]-$ARGV[0]?$_->[0]:$_->[1];;;; __DATA__ M'XL(```````""^W8P:V"4!`%T#!+IDW7KQ(6%F`!)C9`%X86J$06O@V1W=/X MPD$6Q/F)W,--F/QAJ$?D^XBQ'MGX*DH]LO%57.I1OG:5?L-O^(W#JUBF_:?T M\U6Z>W?O[MV]NS_%W<?SOO\L4W_?%3'$$$,,,<0X7XST-,000PPQQ!##6]S3 M$$,,,<000PQO<:420PPQQ!!##&]Q,<000PPQQ/`6]S3$$$,,,<00PUO<TQ!# M##'$$$,,;W&E$D,,,<00PUO<TQ!###'$$$.,+F/$^IB/SF4RG`L#0(```0($ M"!`@0)_.9*!!@``!`@0($"!`@&S2&@0($"!`@``!`@3()JU!@``!,@0$"!`@ M0#9I#0($"!`@0(```0)DD]8@0(```0($"!`@0(8V:0T"!`@0($"```$"9)/6 M($"```$"!`@0($`V:0T"!`@0($"```$"]-?#6&_7PW/["]-Z;HPP4*%"A0H5 M*E2H4/UR6E@H%2I4J%"A0H4*%2K+NE*A0H4*%2I4J%"9HK*L*Q4J5*A0P4"% M"A4JR[I2H4*%"A4J5*A,4:&RK"L5*E2H8*!"A0H5*LLZ*:5"A0H5*E2FJ%"A MLJPK%2I4,%"A0H4*%2I4EG6E0H4*%2I4J%"A0F595RI4,%"A0H4*%2I4J%I, MDX52H4*%"A4J5*A0H?*?=:5"A0H5*E2H4*$R16595RI4J%"A@H$*%2I4EG6E M0H4*%2I4J%"9HD)E65<J5*A0P4"%"A4J5)9U4DJ%"A4J5*A,4:%"95E7*E2H 38*!"A0H5JF;3\06.=,S9-'L!````

    Examine what is said, not who speaks.
    Silence betokens consent.
    Love the truth but pardon error.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://427378]
Approved by herveus
Front-paged by grinder
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (6)
As of 2014-09-17 10:26 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (72 votes), past polls