Write a short program for 196-algorithm. The algorithm starts from an integer, then adds its reverse to it until a palindrome is reached.

e.g.

input = 5280
5280 + 0825 = 6105
6105 + 5016 = 11121
11121 + 12111 = 23232
output = 23232

Input

an integer, which is not a lyrchrel number (that is, it does eventually yield a palindrome under this algorithm, rather than continuing infinitely)

Output

the palindrome reached.

  • 5
    Because your question is probably the only one involving the 196 algorithm. Making single-use tags is not useful. – Chris Jester-Young Jan 29 '11 at 8:48
  • 2
    What I meant was, your question is likely to be the only one ever to involve this topic, even in 2 years' time. :-) – Chris Jester-Young Jan 29 '11 at 9:12
  • 1
    @Chris: Well, 196-algorithm is a pretty popular one, going by many different names. Just to be sure, though, I'll post another question about it before the 2-year-time lapses ;) – Eelvex Jan 29 '11 at 9:49
  • 1
    @GigaWatt also, I had missread your fist question :) Just don't bother with A023108s' case. – Eelvex Mar 9 '12 at 16:03
  • 1
    @Joel, as with A023108, just ignore them (act like you don't know about them); we don't know if any exists anyway. – Eelvex May 27 '12 at 15:02

43 Answers 43

up vote 10 down vote accepted

APL (22 characters)

{a≡⌽a←⍕(⍎⍵)+⍎⌽⍵:a⋄∇a}⍞

This works in Dyalog APL. Here's an explanation, from right to left:

  • { ... }⍞: Get input from the user as characters () and feed it to our function ({ ... }).
  • Within the direct function ( separates statements, so we look at them from left to right):
    • a≡⌽a←⍕(⍎⍵)+⍎⌽⍵ : a: Evaluate () the right argument's () reverse (), and add that to the evaluated version of the right argument itself. Then, format the result (; i.e., give its character representation), assign () that to the variable a, and finally test if a's reverse is equivalent to a (i.e., is a a palindrome?). If true, return a; otherwise...
    • ∇a: Feed a back into our function ( is implicit self-reference).

Example:

      {a≡⌽a←⍕(⍎⍵)+⍎⌽⍵:a⋄∇a}⍞
412371
585585
  • 2
    It saves a few characters to use numeric input. {⍵=A←⍎⌽⍕⍵:⍵⋄∇A+⍵}⎕. You save the braces, a reverse and an eval. – marinus May 27 '12 at 7:38

GolfScript, 29 chars

~]{{.`.-1%.@={;0}{~+1}if}do}%

Selected commentary

The meat of the program is the do loop, of course. So I'll just cover that.

  1. .` copies the number and stringifies it.
  2. .-1% copies that string version and reverses it.
  3. .@ copies the reversed version, and brings the original non-reversed version to the front.

So, say, the number is 5280. At this stage, the stack is: 5280 "0825" "0825" "5280". The stage is set for the comparison. (After the comparison, the stack will be left at 5280 "0825" no matter what---the items to compare have been popped off.)

  1. If the string and the reverse are the same, we don't care about the reversed string, so just pop it off (;) and return 0 (to end the do loop).
  2. If they don't match, then evaluate (~) the reversed string (to make it a number), add (+) that to the original number, and return 1 (to continue the do loop).
  • 4
    Are you sure you didn't press random keys on your keyboard? It looks like that... – user11 Jan 29 '11 at 3:03
  • 1
    @M28: GolfScript looks even more like line noise than Perl, doesn't it? ;-) – Chris Jester-Young Jan 29 '11 at 3:10
  • I feel sorry for you, it must be painful to code that – user11 Jan 29 '11 at 3:51
  • @M28: That wasn't nearly as painful as the solution I wrote for Luhn algorithm. Just think about that. :-P – Chris Jester-Young Jan 29 '11 at 4:33
  • Your family is worried about you – user11 Jan 29 '11 at 4:36

Python 2, 55 bytes

Following JPvdMerwe suggestion:

n=input()
while`n`!=`n`[::-1]:n+=int(`n`[::-1])
print n

Python 2, 62:

n=raw_input()
while n!=n[::-1]:n=`int(n)+int(n[::-1])`
print n
  • Hehe ..)))))))) – Nakilon Jan 28 '11 at 21:53
  • 2
    By looking at n as an int you can shorten by 6 characters, check for the code: meta.codegolf.stackexchange.com/q/75/62 – JPvdMerwe Jan 28 '11 at 22:39
  • Seems I accidentally included the new line vim sneakily added to the end of my file to my count. The real count is 55. – JPvdMerwe Jan 29 '11 at 18:56

Ruby — 56 chars

x,r=gets
x="#{x.to_i+r.to_i}"until x==r=x.reverse
puts x

Just exercising my Pyth skills, not a serious contender.

Pyth, 16 bytes

L?bqb_by`+vbi_bTyz

Equivalent to Python 3:

y=lambda b:b if b==b[::-1] else y(str(eval(b)+int(b[::-1],10)))
print y(input())
  • Just trying some old challenges, already answered, so not serious contender. – swstephe Dec 23 '14 at 19:28
  • 1
    Some challenge authors will update the accepted answer if a shorter solutions comes in, so I think it's fair to inform the OP, that this is not technically a valid submission. (Don't get me wrong, I like to answer old challenges with CJam for fun, too - and I just did a few minutes ago. I'm just saying, if you do, leave a note, that the language is newer than the challenge.) – Martin Ender Dec 23 '14 at 19:30

J 25 27 31

f=:(+g)^:(~:g=.|.&.":)^:_
e.g.
f 5280
23232

CJam, 22 21 bytes

CJam was created after this question was asked, so technically its an invalid submission. But I found the question interesting, so here goes:

r{__W%:X=0{~X~+s1}?}g

Explanation:

r{                 }g    "Read the input number as string and enter a while-do loop";
  __                     "Make 2 copies of the string number";
    W%:X                 "Reverse the second and store it in X";
        =                "Check if the number is already palindrome";
         0{      }?      "Put 0 on stack if it is palindrome, else, run the code block";
           ~             "Convert the string to int";
            X~           "Put the reverse string on stack and convert it to int too";
              +s         "Add the two numbers and covert back the result to string";

The core logic is that in each while-do iteration, you first check if palindrome is achieved or not. If not, add the reverse to the number. Pretty much what the algorithm is!

Try it online here

This is an actual contender, since J has been around for decades.

J (16 bytes)

(+^:~:|.&.":)^:_

This is a verb, so it can be assigned to a variable in a J session and used like so:

   f =. (+^:~:|.&.":)^:_
   f 5280
23232

How it works:

(+^:~:|.&.":)^:_
 +^:~:           add if unequal
      |.&.":     reverse under string format
 +^:~:|.&.":     add reverse unless a palindrome
(           )^:_ repeat until unchanged

Python: 66

n=input()
while 1:
 r=int(`n`[::-1])
 if n==r:break
 n+=r
print n

Perl, 40 chars

$_=<>;$_+=$r while$_!=($r=reverse);print

Scala 82

def p(n:Int):Int={val s=n.toString.reverse.toInt
if(n==s)n else p(n+s)}
p(readInt)

JAGL Alpha 1.2 - 19, 21 with stdin

Not contending, just getting some experience with my language
Expects a number from stdin

T~d{DddgCi+dgdC=n}uSP

Explanation

T~                       Get a line of input, and eval to an integer
  d                      Duplicate (for first round)
   {Ddd                  Drop last and duplicate twice
       gCi               Convert to string, reverse, and convert back to integer
          +d             Add to original and duplicate
            gdC          Convert to string, duplicate, reverse
               =n}       If it isn't a palindrome, keep going
                  uSP    Run until palindrome reached, then print output number
  • Edited. @Optimizer – globby Dec 24 '14 at 6:47
  • Please don't edit all your submissions at once for minor edits (like a version number), as this unnecessarily clutters the front page. It's fine if you do 2 or maybe 3 at a time, but please wait a few hours before doing more systematic edits. – Martin Ender Dec 30 '14 at 0:51
  • Forgot that it would push to front page, my bad. @MartinBüttner – globby Dec 30 '14 at 0:52

PHP - 54 48 characters

<?for($s=`cat`;$s!=$r=strrev($s);$s+=$r);echo$s;

Test:

$ php 196.php <<< 5280
23232
  • I'm going to have to remember the $str = cat`` thing for future golfing. Heck of a lot better than using STDIN and still better than $argv[0]. – Mr. Llama Mar 8 '12 at 23:01
  • @GigaWatt: $s='m4' should also work. – ninjalj Nov 23 '12 at 20:49

Bash (64)

X=`rev<<<$1|sed s/^0*//`;[ $1 = $X ]&&echo $1||. $0 $(($1+$X))

Call with: bash <filename> <number>

  • What is the <filename> for? – Eelvex Mar 9 '12 at 5:50
  • 2
    @Eelvex the script needs to call itself so you need to store it in a file. – marinus Mar 12 '12 at 14:52

C# - 103 99 chars

public int P(int i)
{
    var r = int.Parse(new string(i.ToString().Reverse().ToArray())));
    return r == i ? i : P(i + r);        
}

C# never does very well in golf. Elegant, but verbose.

  • 1
    You can easily golf it more. Use ""+ rather than .ToString and get rid of some spaces. – Jacob Dec 30 '14 at 4:46

In Q (39 characters)

f:{while[x<>g:"I"$reverse -3!x;x+:g];x}

Sample Usage:

q)f 5280
23232

Edit:

Down to 34 now, same usage:

{while[x<>g:"I"$(|) -3!x;x+:g];x} 5280
r=input()
while 1:
    r=`r`
    if r==r[::-1]:
      break
    else:
      r=int(r)+int(r[::-1])

print r

05AB1E, 7 bytes (non-competing)

Non-competing, since the language postdates the challenge.

Code:

[DÂQ#Â+

Explanation:

[        # Infinite loop.
 DÂ      # Duplicate and bifurcate (which duplicates it and reverses the duplicate).
   Q#    # If the number and the number reversed are equal, break.
     Â+  # Add the reversed number to the initial number.

Uses the CP-1252 encoding. Try it online!.

  • Could you explain a little more on the process of bifurcation? – Conor O'Brien Jul 28 '16 at 18:41
  • 1
    @CᴏɴᴏʀO'Bʀɪᴇɴ For example, on the stack is the string hello. The bifurcation will keep the original string, and pushes the string reversed. It's short for duplicate and reverse. – Adnan Jul 28 '16 at 18:43
  • Oh, I see. Cool! Thanks – Conor O'Brien Jul 28 '16 at 18:51

Jelly, 9 bytes (non competing)

A very simple answer, just for the challenge of coding in and esoteric language.

ṚḌ+µŒḂ¬$¿

ṚḌ        : take the argument, reverse (and vectorize) it
  +µ      : add both
    ŒḂ¬$¿ : while the result isn't a palindrome

Try it online!

Should this answer be unclear or wrong on any level, feel free to point it out.

Thanks to Dennis for helping me out with this first small piece of code.

  • Wow, not everyone uses Jelly in their first post. – Stephen Leppik Apr 25 at 14:36
  • It was on my to-do list to post an answer on PPCG using an esoteric language. Jelly happened to be the first one I thought of :) – z3r0 Apr 25 at 14:40

Brachylog, 8 bytes

↔?|↔;?+↰

Try it online!

Somewhat similar to one of the first Brachylog programs I saw and was intrigued by, from the Brachylog introduction video.

?↔?.|↔;?+↰.  (initial ? and the .s are implicit)

?↔?          % If the input and its reverse are the same,
   .         %   then the input is the output
    |↔;?+↰   % Or, add the input and its reverse, and call this predicate recursively
          .  % The result of that is the output

Python. 85 characters:

s,i=str,int;rs=lambda q:s(q)[::-1];n=i(input());
while rs(n)!=s(n):n+=i(rs(n));print n

If you don't want output on each iteration:

s,i=str,int;rs=lambda q:s(q)[::-1];n=i(input());
while rs(n)!=s(n):n+=i(rs(n))
print n

(one less character)

  • The task description states that only the final palindrome should be printed. – Joey Jan 29 '11 at 12:00

Windows PowerShell (63)

for($a=+"$input";-join"$a"[99..0]-ne$a){$a+=-join"$a"[99..0]}$a

I still hate it that there is no easy way to reverse a string.

  • Can be shortened by two characters if there only ever are ten digits of input. This way it's safe for long as well which is the largest integral type PowerShell supports anyway but still, I waste two chars. – Joey Jan 29 '11 at 11:56

Haskell 89 87 chars

r=read.reverse.show
main=getLine>>=print.head.filter(\x->x==r x).iterate(\x->x+r x).read

Somewhat readable version:

myFind p = head . filter p
rev = read . reverse . show
isPalindrome x = x == rev x
next x = x + rev x
sequence196 = iterate next
palindrome196 = myFind isPalindrome . sequence196

main = getLine >>= print . palindrome196 . read

The golfed version was created by manual inlining and renaming the remaining functions to single character names.

  • 1
    You can shorten this quite a bit by taking advantage of the underused function until from the Prelude, as well as extracting the pattern of applying a binary operator to x and r x. Also, use readLn instead of getLine and read. The result saves 20 characters: f%x=f x$read.reverse.show$x;main=readLn>>=print.until((==)%)((+)%) – hammar Nov 8 '11 at 21:47
  • @hammar: You could use the function monad and save even more: Define r=(=<<read.reverse.show) and just use r(==)`until`r(+). Apart from that saving, it doesn't need to be a full program, a valid submission could just be the unnamed function from before. This brings you down to 41 bytes: Try it online! – BMO Aug 2 at 18:31

befunge, 57 bytes

"KCTS"4(&:0\v
\T\a*+\:0`jv>:a%\a/
0:+_v#-TD2$<^\
  @.<

though the code is places in a 4x19 grid, so might call it 76.

  • first line is initializeing, and reading input number
  • second line reverse first number in stack and put it in the second stack position.
  • and the third line checks if a number is palindrome.

C++ TMP (256 characters)

#include<cstdio>
#define Y(A,B,C,D)template<int N>struct A<C,D>{enum{v=B};};
#define Z(A)template<int N,int M>struct A{enum{v=
#define n 5194
Z(R)R<N/10,M*10+N%10>::v};};Y(R,N,0,N)Z(S)S<N+M,R<N+M,0>::v>::v};};Y(S,N,N,N)main(){printf("%d",S<n+R<n,0>::v,0>::v);}

This version could be shortened a bit, but a 256-character answer is hard to pass up. Here's an un-golfed version:

#include <iostream>

template<size_t N>
class Reverse
{
    template<size_t M, size_t R>
    struct Inner
    {
        enum { value = Inner<M/10, R*10 + M%10>::value };
    };

    template<size_t R>
    struct Inner<0, R>
    {
        enum { value = R };
    };

public:
    enum { value = Inner<N, 0>::value };
};

template<size_t N>
class OneNineSix
{
    template<size_t M, size_t R=Reverse<M>::value>
    struct Inner
    {
        enum { value = OneNineSix<M + R>::value };
    };

    template<size_t M>
    struct Inner<M, M>
    {
        enum { value = M };
    };

public:
    enum { value = Inner<N + Reverse<N>::value>::value };
};

int main()
{
    const size_t N = 4123;

    std::cout << OneNineSix<N>::value << std::endl;
}

Pyke, 13 bytes (noncompeting)

D`_b]D$XIsr)h

Try it here!

 `_b          -     int(reversed(str(num))
D   ]         -    [num, ^]
     D        -   _ = ^
      $       -  delta(^)
       XI     - if ^:
         s    -  num = sum(_)
          r   -  goto_start()
            h - _[0]

Add++, 57 bytes

L,BDbRBv
D,f,@,1]A+
D,g,@,1]A=
D,h,@,{f}A{g}Q{h}
L,{h}2/i

Try it online!

How it works

L,	; Create a function 'lambda 1'
	; Example argument:   [5280]
    BD	; Digits;     STACK = [[5 2 8 0]]
    bR	; Reverse;    STACK = [[0 8 2 5]]
    Bv	; Undigits;   STACK = [825]

D,f,@,	; Define a monadic function 'f'
	; Example argument:         [5280]
    1]	; Call 'lambda 1';  STACK = [825]
    A+	; Add the argument; STACK = [6105]

D,g,@,	; Define a monadic function 'g'
	; Example argument:          [5280]
    1]	; Call 'lambda 1';   STACK = [825]
    A=	; Equal to argument; STACK = [0]

D,h,@,	; Define a monadic function 'h'
	; Example argument:  [5280]
   {f}	; Call 'f';  STACK = [6105]
   A{g}	; If 'g'...
   Q	;   Return
   {h}	; Else call 'h'

L,	; Define a function, 'lambda 2'
	; Example argument: [5280]
   {h}	; Call 'h'; STACK = [46464]
   2/i	; Halve;    STACK = [23232]

Powershell, 63 62 bytes

-1 byte thanks to @AdmBorkBork

param($m)for(;$m-$s;$m=-join"$s"[-1..-"$s".Length]){$s+=$m};$s

Test script:

$f = {
param($m)for(;$m-$s;$m=-join"$s"[-1..-"$s".Length]){$s+=$m};$s
}

&$f 5280
  • 1
    You don't need the ; between param($m) and for. – AdmBorkBork Aug 3 at 14:01
  • exactly! thanks – mazzy Aug 3 at 15:27

GNU dc, 46 bytes

Requires GNU dc, min version 1.4 (for R command).

[O~3RO*+rd0<R]sR[+lfx]sg[ddO~rd0<R+d3R!=g]dsfx

Input and output are top-of-stack, as usual. It takes a surprising amount of code to reverse digits in dc (unless I'm missing something, which is far from impossible). It does have the numeric range to behave nicely with inputs such as these (which will overflow 32-bit unsigned arithmetic, for example):

  • 89 ⇒ 8,813,200,023,188
  • 8997 ⇒ 16,668,488,486,661
  • 10677 ⇒ 4,668,731,596,684,224,866,951,378,664

Explanation

# Reverse digits, starting after first digit extracted
[O~3RO*+r d0<R]sR

# Recursion helper - add and recurse
[+ lfx]sg

# Main recursive function
[dd O~r d0<R+ d3R !=g]dsfx
  • Try it online! (Javascript) – Toby Speight Aug 2 at 14:11
  • Might want to specify that this works only on GNU dc 1.4 and later, since it uses the new R command. Good solution, though! – Sophia Lechner Aug 3 at 18:29
  • I'm working on a totally different approach but not sure it will wind up smaller. – Sophia Lechner Aug 3 at 18:31
  • Thanks Sophia - I hadn't realised that R was new. Looking forward to seeing your method! – Toby Speight Aug 6 at 7:15
  • Ah, nope...I tried a different approach to arranging the outside loop but it ended up about five bytes larger and no prettier. You win. =) – Sophia Lechner Aug 6 at 16:27

R, 193 109 105 bytes

-84 bytes thanks to Giuseppe! -4 byes thanks to JayCe!

function(x){"-"=utf8ToInt
S=strtoi
"!"=rev
while({z=paste(S(x)+S(intToUtf8(!-x),10));any(-z!=!-z)})x=z
z}

Try it online!

  • 1
    You can (and should) choose a different way of doing this than string manipulation, but here are some golfing tips for the method you've chosen: strsplit(x,"") is shorter than strsplit(x,NULL), and el(L) is shorter than L[[1]]. as.double is shorter than as.numeric and strtoi is shorter than both; instead of setting t just use it directly in your if statement. also this is a recursive function if I'm not mistaken, so you need to put f= as part of your submission. – Giuseppe Aug 2 at 15:51
  • @Giuseppe Got it. Thanks for the tips. I'll keep working on this. It's easier for me to just get something that works then go back and optimize. – Robert S. Aug 2 at 16:01
  • 1
    Hehehe, no worries. If you're hell-bent on using strings (or forced to by the problem), consider utf8ToInt to convert to digits and intToUtf8 to convert back. That'll be a big byte saving! – Giuseppe Aug 2 at 16:07
  • 1
  • 1
    Save 4 more bytes by using - in place of U. I also replaced rev with ! but it does not save any byte... – JayCe Aug 6 at 17:02

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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