Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Your task is to generate the nth term of the RATS sequence, where n is the input. The RATS sequence is also known as the Reverse Add Then Sort sequence. This sequence can also be found here: http://oeis.org/A004000.

test cases:

0 > 1
1 > 2
2 > 4
3 > 8
4 > 16
5 > 77
6 > 145
7 > 668

For example, the output for 5 is 77 because 16 + 61 = 77. After this the 77 is sorted.

Shortest submission wins. This is my first challenge so i hope this is not a duplicate or something.

share|improve this question
    
Does the input have to be an Integer or could it also be a string? – DenkerAffe Jan 31 at 15:36
    
@DenkerAffe do you mean a number in the form of a string? – justaprogrammer Jan 31 at 15:37
    
@justaprogrammer Yea, so I can get "123" instead of 123 as Integer. Would mayve save some bytes. – DenkerAffe Jan 31 at 15:40
1  
isn't 77+77=154? Or have I missed something? EDIT: Oh, yes, I forgot to sort. – Denham Coote Feb 1 at 10:48
3  
@DenhamCoote I think you meant "oh rats, I forgot to sort!" – Martin Ender Feb 2 at 10:49

18 Answers 18

MATL, 11 12 bytes

1i"tVPU+VSU

Input is a string (with single quotes) representing an integer in unary. String input is allowed by the challenge, and unary is a valid format.

Try it online!

Explanation

1      % push number 1 to the stack
i      % input. Will be a string of "n" ones 
"      % for loop: repeat n times (consumes string)
  t    %   duplicate
  V    %   convert to string
  P    %   reverse
  U    %   convert to number
  +    %   add
  V    %   convert to string
  S    %   sort
  U    %   convert to number
       % loop is implicitly ended
       % stack content is implicitly displayed    
share|improve this answer
4  
I don't know which scares/perplexes me more, MATL or Jelly... +1 – Downgoat Jan 31 at 19:00

CJam, 15 bytes

1ri{_sW%i+s$i}*

Test it here.

Explanation

1     e# Push 1 as the start of the sequence.
ri    e# Read input and convert to integer N.
{     e# Run this block N times...
  _s  e#   Duplicate and convert to string.
  W%  e#   Reverse string.
  i+  e#   Convert back to integer and add to previous value.
  s$  e#   Convert to string and sort.
  i   e#   Convert back to integer for the next iteration.
}*
share|improve this answer
3  
how can all these languages be so short – justaprogrammer Jan 31 at 15:52
2  
@justaprogrammer Single-character names for built-in functions help. ;) CJam, Pyth and Brachylog are all golfing languages, specifically designed with code golf in mind. (See en.wikipedia.org/wiki/Code_golf#Dedicated_golfing_languages.) Then there's also languages like APL and J that aren't golfing languages at all but are similarly terse, because the designers thought it would be a good idea. – Martin Ender Jan 31 at 15:54
    
Which one do you recommend the most for winning challenges like these? – justaprogrammer Jan 31 at 16:03
3  
@justaprogrammer I wouldn't pick one based on which one is winning these challenges (that would likely be Pyth or Jelly). It can be just as fun to golf in a "normal" language (especially because there might be more competition within that language). For a golfing language, it's probably more important that you enjoy using it. CJam is quite fun - it's a stack-based which makes you bend your mind a bit more than other languages, and at the same time it's quite a powerful language, that I've started to use for simple throwaway scripts outside of golf, which is a good boost to my productivity. – Martin Ender Jan 31 at 16:07
    
These languages look very interesting and I can't wait to learn one myself. I don't know what jelly is? Is that some kind of gelatine or something? – justaprogrammer Jan 31 at 16:23

Pyth, 17 13 12 bytes

uS`+vGv_GQ\1
u        Q\1    reduce range(input()) on base case of "1" (string)
   +vG          eval the string (to get a number), and add...
      v_G       the same number, reversed first and then eval'd
 S`             convert back to string and sort

Try it on the online interpreter.

share|improve this answer
4  
What is this magic? How does this work? – justaprogrammer Jan 31 at 15:42
1  
@justaprogrammer I've added an explanation. :) – Doorknob Jan 31 at 16:00
    
Huh, but how. How do you test this code? – justaprogrammer Jan 31 at 16:02
1  
@justaprogrammer I've added a link to an online interpreter that you can run the code on. – Doorknob Jan 31 at 16:06
    
This is awesome, it is so short, yet so beautiful – justaprogrammer Jan 31 at 16:11

05AB1E, 6 bytes

Code:

$FDR+{

Explanation:

$       # Push 1 and input
 F      # For N in range(0, input)
  D     # Duplicate top of the stack
   R    # Reverse top of the stack
    +   # Add top two items
     {  # Sort top of the stack
        # Implicitly print top of the stack

This also works with a 0 byte program.

share|improve this answer
    
@Adnan Three days ago, actually. Still, well played... – Doorknob Jan 31 at 19:23
    
@Doorknob Just in time haha – Adnan Jan 31 at 19:28
10  
You can save 6 bytes by eliminating your source code. – Dennis Jan 31 at 21:00
2  
You can also shorten 05AB1E by first eliminating the leading zero, and then omitting the 1, as 1E==E. Then you get just 5ABE, -2 bytes. – flawr Jan 31 at 23:49
1  
@Dennis great observation – Adnan Feb 1 at 20:48

Python 2, 72

f=lambda x,n=1:x and f(x-1,int(''.join(sorted(`n+int(`n`[::-1])`))))or n

Recursive function, makes use of the Python 2 shorthand for __repr__, which will break once the function reaches very large values (an L will be appended to the number's string), I'm not certain from the spec if there is a place where we can stop, but if not changing to str() only adds 6 bytes, but then it becomes slightly shorter to output as a string, at 75 bytes:

f=lambda x,n='1':x and f(x-1,''.join(sorted(str(int(n)+int(n[::-1])))))or n

1 byte saved thanks to trichoplax on this version

share|improve this answer
    
Is that a surplus space before the or in the second code block? – trichoplax Feb 1 at 2:09
1  
@trichoplax thanks for the catch :) – FryAmTheEggman Feb 1 at 2:21

JavaScript ES6, 70 bytes

Saved 1 byte thanks to @user81655

f=n=>n?+[...+[...''+(b=f(n-1))].reverse().join``+b+''].sort().join``:1

sigh JavaScript is really verbose. A lot (> 50%) of the code is just case to string + array function + join + cast to int. I've tried reduce, eval, and all sorts of stuff but this seems to be the shortest.

Try it online (All browsers work)

share|improve this answer
2  
Just like mine, but better (and posted earlier). Bah! – edc65 Jan 31 at 16:04
    
String Manipulation is JS is so long, you have my condolences – MayorMonty Jan 31 at 18:24
    
@user81655 cool, thanks! I would of never thought to re-order that way – Downgoat Feb 1 at 3:17

Brachylog, 19 bytes

0,1 .|-1=:0&Rr+R=o.

Explanation

0,1 .               § If Input is 0, unify the Output with 1
     |              § Else
      -1=:0&R       § unify R with the output of this main predicate, with input = Input - 1
             r+R=o. § Reverse R, add it to itself and order it, then unify with the Output.
share|improve this answer

Haskell, 67 bytes

import Data.List
g i=i:g(sort$show$read i+read(reverse i))
(g"1"!!)

Usage example: (g"1"!!) 7-> "668".

It's a direct implementation of the definition: starting with "1", repeatedly append the reverse-add-sort result of the current element. The main function (g"1"!!) picks the ith element.

share|improve this answer
    
This is the most readable program under 70 bytes! – Gaurav Agarwal Feb 1 at 23:54

Julia, 77 bytes

n->(x=1;for _=1:n x=(p=parse)(join(sort(["$(x+p(reverse("$x")))"...])))end;x)

This is a lambda function that accepts an integer and returns an integer. To call it, assign it to a variable.

Ungolfed:

function f(n::Int)
    # Begin x at 1
    x = 1

    # Repeat this process n times
    for _ = 1:n
        # Add x to itself with reversed digits
        s = x + parse(reverse("$x"))

        # Refine x as this number with the digits sorted
        x = parse(join(sort(["$s"...])))
    end

    # Return x after the process (will be 1 if n was 0)
    return x
end
share|improve this answer

Jelly, 13 12 bytes

I'm sure this can probably be golfed, as this is my first answer in Jelly/in a tacit language.

DUḌ+ðDṢḌ Performs RATS
1Ç¡      Loops

D        Converts integer to decimal
 U       Reverses
  Ḍ      Converts back to integer
   +     Adds original and reversed
    ð    Starts new chain
     D   Converts back to decimal
      Ṣ  Sorts
       Ḍ Back to integer again

1        Uses 1 instead of input
 Ḍ       Uses line above
  ¡      For loop

EDIT: Saved 1 byte, thanks to Dennis

share|improve this answer

Lua, 179 Bytes

I can't see how I could golf it more, but I'm sure there's a way.

tonumber is used again and again because I have to convert a to a string to reverse it, do the addition, and go back to a string to sort it.

a,z=0,table for i=0,tonumber(io.read())do t={}(""..a+tonumber((""..a):reverse())):gsub(".",function(d)z.insert(t,d)end)z.sort(t)a=a<1 and 1 or tonumber(z.concat(t,""))end print(a)

Ungolfed and explanations

a=0                                  
z=table                              -- z is a pointer on the table named table
                                     -- it allows me to use its functions
                                     -- while saving 4 bytes/use

for i=0,tonumber(io.read())          -- Iterate n times for the nth element
do
  t={}
  (""..a+tonumber((""..a):reverse()))-- we add a with its "reversed" value
                                     -- and convert the whole thing to a string
    :gsub(".",function(d)            -- for each character in it, use an anonymous fucntion
       z.insert(t,d)end)             -- which insert them in the array t
  z.sort(t)                          
  a=a<1 and 1 or                     -- if i==0, a=1
     tonumber(z.concat(t,""))        -- else we concat t in a string and convert it to number
end
print(a)
share|improve this answer

Java 1.8, 251 bytes

interface R{static void main(String[]a){int i,r,n=1,c=0,t=Byte.valueOf(a[0]);while(++c<=t){i=n;for(r=0;i!=0;i/=10){r=r*10+i%10;}n+=r;a[0]=n+"";char[]f=a[0].toCharArray();java.util.Arrays.sort(f);n=Integer.valueOf(new String(f));}System.out.print(n);}}

Expanded

interface R{
static void main(String[]args){
    int input,reversed,nextValue=1,count=0,target=Byte.valueOf(args[0]);
    while(++count<=target){
        input=nextValue;
        for(reversed=0;input!=0;input/=10){reversed=reversed*10+input%10;}
        nextValue+=reversed;
        args[0]=nextValue+"";
        char[]sortMe=args[0].toCharArray();
        java.util.Arrays.sort(sortMe);
        nextValue=Integer.valueOf(new String(sortMe));
    }
    System.out.print(nextValue);
}
}
share|improve this answer
    
Why do you use interface R instead of class R which is 4 bytes shorter? – Will Sherwood Feb 2 at 5:04
    
@WillSherwood because you can then omit the public modifier on main(), making it shorter overall :) – Denham Coote Feb 2 at 8:08

ES6, 79 bytes

n=>eval("r=1;while(n--)r=+[...+[...r+''].reverse().join``+r+''].sort().join``")

82 bytes without eval:

n=>[...Array(n)].reduce(r=>+[...+[...r+''].reverse().join``+r+''].sort().join``,1)

All those conversions are painful.

@edc65 I actually saved 4 bytes by switching from map to reduce this time... no doubt you'll prove me wrong again though.

share|improve this answer
    
for is shorter: n=>eval("for(r=1;n--)r=+[...+[...r+''].reverse().join``+r+''].sort().join``‌​") – Downgoat Jan 31 at 16:01
    
@Doᴡɴɢᴏᴀᴛ Doesn't work for n=0, even after I've fixed the syntax errors. – Neil Jan 31 at 16:03

Python 2, 91 Bytes

Input as Integer, result is printed to the screen.

def f(n):
 t=1
 for i in range(n):t=int("".join(sorted(str(int(str(t)[::-1])+t))))
 print t

This could be a lot shorter with some recursion magic I guess, but I cant wrap my head around it yet. Gonna have a fresh look later and hopefully improve this one.

share|improve this answer

Python 2, 83 bytes

def f(n):
 v='1'
 for _ in v*n:v=''.join(sorted(str(int(v)+int(v[::-1]))))
 print v
share|improve this answer

Perl 6, 40 bytes

{(1,{[~] ($_+.flip).comb.sort}...*)[$_]} # 40

( If you want it to return an Int put a + right before [~] )

Usage:

# give it a lexical name
my &RATS = {…}

say RATS 5; # 77

# This implementation also accepts a list of indexes

# the first 10 of the sequence
say RATS ^10; # (1 2 4 8 16 77 145 668 1345 6677)
share|improve this answer

Mathematica 10.3, 66 61 bytes

Nest[FromDigits@Sort@IntegerDigits[#+IntegerReverse@#]&,1,#]&

Quite simple.

share|improve this answer

Seriously, 17 bytes

1,`;$R≈+$S≈`n

Try it online!

Explanation:

1,`;$R≈+$S≈`n
1              push 1
 ,`       `n   do the following n times:
   ;$R≈        reverse
       +       add
        $S≈    sort
share|improve this answer

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.