Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Given a number N, output/return X so that N+X is a palindrome, where |X| has to be as small as possible.

Palindrome: A number is a palindrome, if its sequence of digits is the same when reading them from left to right as when reading from right to left.
95359 and 6548456 are symmetric, 123 and 2424 are not. Numbers with leading zeros such as 020 are not a palindrome.

Input is a positive integer smaller than 1015. Read it from stdin, as a method-parameter, whatever.

Output has to be an integer (positive or negative) and ought to be 0 if the input is already a palindrom. You may write your output to stdout, return it from a function or whatever you like. If there are 2 numbers (e.g. 2 and -2) that satisfy the requirements, output only one of them.

Examples:

Input             Output
3                 0
234               -2
1299931           -10
126               5 or -5 (only one of them)
share|improve this question
1  
The common term is palindrome, not symmetrical number. –  isaacg Aug 27 at 13:34
    
Presumably if a number is halfway between the two nearest palindromes, either is an acceptable output? E.g. for N=10 the output can be X=-1 or X=1? –  Peter Taylor Aug 27 at 13:45
6  
For what it's worth, the hasty editing which has left two answers which don't comply with the edited spec could have been avoided by using the Sandbox for Proposed Challenges. –  Peter Taylor Aug 27 at 13:49
1  
@Moop You can find a palindrome pretty quickly, since at worst you can change half the digits to match. That doesn't always give the smallest change, but it's an easy upper bound. –  Geobits Aug 27 at 18:35
1  
Since output says it "may be 0" if the number is already a palindrome, that means that X may be > 0 even if it would otherwise equal 0? Or should that be "ought to be 0"? –  guifa Aug 28 at 3:50

16 Answers 16

up vote 8 down vote accepted

Pyth, 26 20

Lnb_bWP`+QZ=Z-g0ZZ)Z

Updated to meet the new rules.

The program runs in an infinite loop which tests every possible increment, in the order 0, -1, 1, -2, -2 ...

Explanation:

Q=eval(input())     implicit
Z=0                 implicit
Lnb_b               def P(b): return b != rev(b)
WP`+QZ              while P(repr(Q+Z)):
=Z-g0ZZ             Z=(0>=Z)-Z
)                   <end while>
Z                   print(Z)

Example run:

python3 pyth.py programs/palin.pyth <<< 965376457643450
-2969881

This took 23 seconds.


Bonus solution, same character count:

Wn`+QZ_`+QZ=Z-g0ZZ)Z
share|improve this answer
    
Just to let you know, the rules changed to finding the nearest palindrome (in either direction). But I guess since you posted before that rule change there's no obligation for you to fix it. –  Martin Büttner Aug 27 at 14:12
    
Might it save chars to loop Z through [0, 1, -1, 2, -2, ...] by an update Z=-Z+(Z<0)? –  xnor Aug 27 at 20:37
    
Yep - I thought of that independently. –  isaacg Aug 27 at 23:31
    
@xnor Added. Filler. –  isaacg Aug 27 at 23:36
    
Ok, cool. Have you also looked into putting the negation of the condition into the while? And maybe saving a repr by applying it to the input to P? –  xnor Aug 27 at 23:40

Ruby, 111 84 bytes

i=$*[j=-1].to_i
r=->j{s=(i+j).to_s
abort(j.to_s)if s==s.reverse}
loop{r[j+=1]
r[-j]}

Takes the number as its only command-line argument.

share|improve this answer
    
How about this website? –  Manu Aug 27 at 13:59
    
@Manu Thanks didn't know that one! My submission works as far as I can tell. –  Martin Büttner Aug 27 at 14:01

CJam, 34 29 25 bytes

q~:I!{:R1<R-RI+`_W%=!}g;R

Try it online.

Examples

$ cjam palfind.cjam <<< 120; echo
1
$ cjam palfind.cjam <<< 121; echo
0
$ cjam palfind.cjam <<< 122; echo
-1

How it works

q~:I    " Read from STDIN, evaluate and save the result in “I”.                           ";
!       " Compute the logical NOT (0 since the integer is positive).                      ";
{       "                                                                                 ";
  :R    " Save the topmost integer in “R”.                                                ";
  1<R-  " Compute (R < 1) - R. This produces the sequence 0 → 1 → -1 → 2 → -2 → … .       ";
  RI+   " Push I + R.                                                                     ";
  `_    " Cast to string and push a copy.                                                 ";
  W%=!  " Check if the reversed copy matches the original.                                ";
}g      " If it doesn't, repeat the loop.                                                 ";
;R      " Discard the integer on the stack and push “R”.                                  ";
share|improve this answer

Haskell - 62

f n=[x-n|x<-[0..]>>= \v->[n+v,n-v],show x==(reverse.show)x]!!0

Save it to a file named golf.hs and then test it with ghci:

*Main> :l golf
[1 of 1] Compiling Main             ( golf.hs, interpreted )
Ok, modules loaded: Main.
*Main> map f [1000..1050]
[-1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10,-11,-12,-13,-14,-15,-16,-17,-18,-19,-20,-21,-22,-23,-24,-25,-26,-27,-28,-29,-30,-31,-32,-33,-34,-35,-36,-37,-38,-39,-40,-41,-42,-43,-44,-45,-46,-47,-48,-49]
*Main> 
share|improve this answer
    
how about writing x<-[0..]>>=(\v->[n+v,n-v]) ? It is shorter and it makes it a one-liner –  proud haskeller Aug 28 at 7:43
    
@proudhaskeller Thanks! Very elegant trick with the list monad. –  Ray Aug 28 at 7:50

Python 2.7, 98, 81

Creates a palindrome from the input number, then subtracts that from the input to find the delta.

def f(n):
    m=map(int,str(n));l=len(m)/2;m[-l:]=m[l-1::-1];return int(`m`[1::3])-n

usage:

print f(3)          # 0
print f(234)        # -2
print f(2342)       # -10
print f(129931)     # -10
print f(100000)     # 1

ungolfed and annotated:

def f(n):                      # take a integer n
    m=map(int,str(n));         # convert n into array of ints
    l=len(m)/2;                # get half the length of the array of ints
    m[-l:]=m[l-1::-1];         # replace the last elements with the first elements reversed
    return int(`m`[1::3])-n    # convert array of ints backinto single int and subtract the original number to find the delta
share|improve this answer
    
This doesn't give the smallest delta. f(19) = -8 (palindrome 11), where it should be +3 to make 22. –  Geobits Aug 27 at 18:31
    
@Geobits Yes, the 10-100 values will give me a problem with this approach –  Moop Aug 27 at 18:47
    
It's not just those. Similarly, 199999 gives -8 instead of 3, 9911 gives 88 instead of -22. Just reversing the first digits doesn't work to get the smallest delta in a lot of cases. –  Geobits Aug 27 at 18:52
    
well i wouldn't say a lot of cases, i bet 99.9% of cases it works for. But yes, it needs to work for 100% of cases –  Moop Aug 27 at 18:55
    
@Geobits. Sure, so 27% error rate there. But when you get to the 100000000s the error rate drops considerably. It would be interesting to calculate the actual error rate. –  Moop Aug 27 at 19:08

Java : 127 109

Basic iteration, checking both negative and positive before moving to the next candidate.

int p(long n){int i=0;for(;!(n+i+"").equals(new StringBuilder(n+i+"").reverse()+"");i=i<1?-i+1:-i);return i;}

For input 123456789012345, it returns -1358024, to equal palindrome 123456787654321.

Line breaks:

int p(long n){
    int i=0;
    for(;!(n+i+"").equals(new StringBuilder(n+i+"").reverse()+"");i=i<1?-i+1:-i);
    return i;
}   
share|improve this answer
    
Does n+i+"" work and save the brackets? I think that the precedence should be correct. –  Peter Taylor Aug 27 at 14:45
    
@PeterTaylor Yep, and got another few from toString(). Thanks :) –  Geobits Aug 27 at 14:53
1  
Can I steal that sweet i=i<1?-i+1:-i? I shall call it "indecrement". –  Jacob Aug 28 at 9:19
    
@Jacob Go for it ;) –  Geobits Aug 28 at 12:32

Clojure, 92

Takes the first from a lazy for-sequence that works from 0 out and only includes values that make palindromes:

(defn p[x](first(for[i(range)j[1 -1]k[(* i j)]s[(str(+ x k))]:when(=(seq s)(reverse s))]k)))

REPL-LPER session:

golf-flog> (p 3)
0
golf-flog> (p 10)
1
golf-flog> (p 234)
-2
golf-flog> (p 1299931)
-10
golf-flog> (p (bigint 1e15))
1
share|improve this answer

JavaScript, 175 136 117

Straightforward. p returns true if a given number is palindrome, f searches the nearest.

EDIT: I also golfed it a little bit more thanks to the sweet "indecrement" trick by Geobits in the Java answer here.

p=function(n){return (s=''+n).split('').reverse().join('')==s}
f=function(n){for(i=0;!p(n+i);i=i<1?-i+1:-i);return i}

Usage:

f(3)
f(234)
f(1299931)
share|improve this answer
    
104 in ES6: p=n=>[...s=''+n].reverse().join('')==s f=n=>{r=t=0;while(!(p(n+r++)||p(n+t--)));return p(n+r-1)?r-1:t+1} :) –  William Barbosa Aug 27 at 19:09
1  
I bet it is. function and return are terribly long reserved-words... –  Jacob Aug 27 at 19:12

Perl 5, 93 89 88 87 75 63 44

$/=($/<1)-$/while$_+$/-reverse$_+$/;$_=$/+0

Ungolfed:

while($input + $adjustment - reverse($input + $adjustment)) {
    $adjustment = ($adjustment < 1) - $adjustment;   
}
$input = $adjustment + 0;  ## gives 0 if $adj is undefined (when $input is a palindrome)
print $input;  ## implicit

Thanks to Dennis's suggestions, got it down to 43 + -p = 44

share|improve this answer
1  
1. -$a is shorter than $a*-1. 2. If you use ($a<1), there's no need for ? :$a++. 3. If you use the -p switch, $_=<> and print$_ is implicit, so you can drop the first statement and change the last to $_=$a+0. –  Dennis Aug 28 at 21:55
    
@Dennis Nice finds. This is only my second attempt at code golf, so appreciate the advice! –  guifa Aug 28 at 22:02
    
It's customary to count the -p switch as one extra byte, but you can get it back by using ($a<1)-$a instead of -$a+($a<1). –  Dennis Aug 28 at 22:52
    
@Dennis I though about using that method based on your answer above, but the gain gets lost because it requires a space before while –  guifa Aug 28 at 22:56
    
If you use $/ instead of $a, it will work. –  Dennis Aug 28 at 23:01

Groovy - 131 111 107 chars

Golfed:

n=args[0] as long;a=n;b=n;f={if("$it"=="$it".reverse()){println it-n;System.exit 0}};while(1){f a++;f b--}

sample runs:

bash-2.02$ groovy P.groovy  0
0
bash-2.02$ groovy P.groovy  234
-2
bash-2.02$ groovy P.groovy  1299931
-10
bash-2.02$ groovy P.groovy  123456789012345
-1358024

Ungolfed:

n=args[0] as long
a=n
b=n
f={ if("$it"=="$it".reverse()) {
       println it-n
       System.exit 0
    }
}

while(1) {
    f a++
    f b--
}
share|improve this answer

Python 2 - 76

i=input()
print sorted([r-i for r in range(2*i)if`r`==`r`[::-1]],key=abs)[0]

Gets the input number and generates a list of the differences between the input and every number between 0 and 2*i only if the number is palindromic.

It then sorts the list by absolute value and prints the first element.

share|improve this answer
    
I don't think range(2*i) will work for large inputs. –  Moop Aug 27 at 20:13
    
You can use min with a keyword argument rather than sorting. –  xnor Aug 27 at 21:00
    
To use ranges that long, you need to switch to xrange, which is a generator, and min, which short-circuits, to avoid overrunning your memory. –  isaacg Aug 28 at 1:56

C++ 289

Function P checks for palindromes using <algorithm> method.

Ungolfed:

bool P(int32_t i)
{
string a,b;
stringstream ss;
ss<<i;
ss>>a;
b=a;
reverse_copy(b.begin(),b.end(),b.begin());
int k=a.compare(b);
return (k==0);
}
int main()
{
int32_t n; cin>>n;
int32_t x=0,y=n,z=n,ans=x;
while(1)
{
if(P(y)){ans=x; break;}
if(P(z)){ans=-1*x; break;}
x++;
y+=x;
z-=x;
}
cout<<ans<<endl;
return 0;
}
share|improve this answer

Mathematica 75

Probably can be golfed more..

p = (j=0; b=#; While[a=IntegerDigits[b]; b += ++j(-1)^j; a!=Reverse[a]]; #-b+(-1)^j) &

Spaces not counted and not needed.

share|improve this answer

J - 49 char

A function mapping integers to integers.

((0{g#f)>:@]^:(+:/@g=.(-:|.)@":@+f=._1 1*])^:_&0)

Here's how you might build to this result, in three parts. This is the display of the J REPL: indented lines are user input and outdented ones are REPL output. And yes, J spells the negative sign with an underscore _.

   236 (_1 1*]) 4                          NB. -ve and +ve of right arg
_4 4
   236 (f=._1 1*]) 4                       NB. name it f
_4 4
   236 (+f=._1 1*]) 4                      NB. add left to each
232 240
   236 (":@+f=._1 1*]) 4                   NB. conv each to string
232
240
   236 ((-:|.)@":@+f=._1 1*]) 4            NB. palindrome? on each
1 0
   236 (g=.(-:|.)@":@+f=._1 1*]) 4         NB. name it g
1 0
   236 (+:/@g=.(-:|.)@":@+f=._1 1*]) 4     NB. logical NOR (result 1 if both=0)
0
   palin =: (+:/@g=.(-:|.)@":@+f=._1 1*])


   236 (>:@]) 0                            NB. increment right
1
   236 (>:@]^:2) 0                         NB. functional power
2
   236 (>:@]^:(236 palin 3)) 3             NB. power 1 if no palindromes
4
   236 (>:@]^:(236 palin 4)) 4             NB. power 0 if has palindrome
4
   236 (>:@]^:palin) 4                     NB. syntactic sugar
4
   236 (>:@]^:palin^:_) 0                  NB. increment until palindrome, start with 0
4
   (>:@]^:(+:/@g=.(-:|.)@":@+f=._1 1*])^:_&0) 236    NB. bind 0
4
   delta =: >:@]^:(+:/@g=.(-:|.)@":@+f=._1 1*])^:_&0


   ((f) delta) 236       NB. f=: -ve and +ve
_4 4
   ((g) delta) 236       NB. g=: which are palindromes
1 0
   ((g#f) delta) 236     NB. select the palindromes
_4
   ((g#f) delta) 126     NB. what if both are equal?
_5 5
   ((0{g#f) delta) 126   NB. take the first element
_5
   ((0{g#f)>:@]^:(+:/@g=.(-:|.)@":@+f=._1 1*])^:_&0) 236   NB. it works!
_4

Examples:

   pal =: ((0{g#f)>:@]^:(+:/@g=.(-:|.)@":@+f=._1 1*])^:_&0)
   pal 3
0
   pal every 234 1299931 126
_2 _10 _5
   pal 2424
18
   2424 + pal 2424
2442

You can also make the golf prefer the positive solution over the negative when they're equal, by changing _1 1 to 1 _1.

share|improve this answer

CoffeeScript: 73

(x)->(x+="")[0...(y=x.length/2)]+x[0...-y].split("").reverse().join("")-x

Explanation: This takes advantage of the fact that if we have a number of odd length (say 1234567), x.slice(0, y) won't include the middle digit but x.slice(0, -y) will. JavaScript's slice probably shouldn't work this way, but it does.

I was expecting CoffeeScript/JavaScript to have a better way to reverse a string, but the split/reverse/join method seems to be all there is.

share|improve this answer

PYTHON: 109

def q(x,z):
 r=lambda s:int(str(s)[::-1])
 if x+z==r(x+z):return z
 if x-z==r(x-z):return -z
 return q(x,z+1)
share|improve this answer
    
this throws an error when running (maximum recursion depth exceeded) –  Moop Aug 27 at 17:47
    
That's not an error in my code. It will exceed maximum recursion depth on a massive number, but it works on decently sized numbers. As there was no maximum test case in the specs, this should still be considered a valid solution. –  Batman Aug 27 at 18:10
1  
The number 123456789 causes it to fail, well below the 10^15 limit posted in the question. –  Moop Aug 27 at 18:13
1  
You could easily turn the recursion into a loop and avoid this issue altogether –  Moop Aug 27 at 18:15
1  
Running this in the Stackless Python implementation should avoid the recursion depth issue. –  xnor Aug 27 at 19:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.