Adição de Reversão Palíndromo

O processo de adição de reversão é onde um número é adicionado ao seu reverso até que o número criado seja um palíndromo. Por exemplo, se começarmos com 68, o processo seria:

68 + 86 => 154 + 451 => 605 + 506 => 1111

Como você pode ver, foram necessárias três adições para chegar a um número palindrômico. Se fôssemos começar 89, precisaríamos de 24 etapas (que você pode ver aqui ).

O recorde mundial de todas as medidas tomadas antes que um palíndromo seja alcançado é 261, o que ocorre para o número 1186060307891929990, produzindo um número maior que 10 ¹¹⁸ . No entanto, houve alguns números que não conseguimos obter um palíndromo. Estes são chamados números de Lychrel .

Como estamos trabalhando na base 10, podemos realmente chamá-los apenas de candidatos, porque não existe prova de que esses números nunca cheguem a um palíndromo. Por exemplo, o menor candidato Lychrel da base 10 é 196 e já passou por mais de um bilhão de iterações. Se o palíndromo existe, é muito maior que 10 ^{10 8,77} . Como comparação, se esses 1s fossem inscritos em átomos, precisaríamos de 2.26772 × 10 ^588843575 universos no valor de átomos para escrevê-lo, assumindo que ele exista.

Sua tarefa

Crie um programa ou função que receba uma entrada inteira e retorne ou imprima o número de etapas necessárias para alcançar um palíndromo. Você não será obrigado a lidar com os candidatos à Lychrel (ou seja, seu programa, quando recebe um candidato à Lychrel, poderá gerar um erro ou executar para sempre).

Casos de teste:

                  f(0) => 0
                 f(11) => 0
                 f(89) => 24
                f(286) => 23
          f(196196871) => 45
         f(1005499526) => 109
f(1186060307891929990) => 261

Regras

1. Sem brechas padrão.

Bônus

1. Se você imprimir cada etapa de adição formatada n + rev(n) = m, poderá multiplicar sua pontuação por 0,75 . As somas devem ser impressas antes do número de etapas.
2. Se seu código puder detectar se um número é um candidato à Lychrel, você poderá multiplicar sua pontuação por 0,85 . Nesse caso, é suficiente assumir que qualquer coisa que exija mais de 261 iterações é um candidato à Lychrel. Não retorne nada, ou qualquer coisa que não seja um número que possa ser confundido com uma resposta correta (etc: qualquer sequência ou número que não esteja no intervalo de 0 a 261). Qualquer erro não conta como saída válida (por exemplo, profundidade máxima de recursão excedida) e não pode ser usado na detecção.
3. Se você completar os dois bônus, multiplique por 0,6 .

Isso é código-golfe , portanto, o menor número de bytes vence.

Este trecho de código mostra uma solução de exemplo no Python 3 com os dois bônus.

def do(n,c=0,s=''):
  m = str(n)
  o = m[::-1]
  if c > 261:
    return "Lychrel candidate"
  if m == o:
    print(s)
    return c
  else:
    d = int(m)+int(o)
    s+="%s + %s = %s"%(m,o,str(d))
    return do(d,c+1,s)

Pitão, 12 bytes

f_I`~+Qs_`Q0

Experimente on-line: demonstração ou equipamento de teste

Isso usa um recurso bastante novo (apenas 17 horas).

Explicação

               implicit: Q = input number
f          0   repeat the following expression until it 
               evaluates to true and return the number of steps
         `Q       convert Q to string
        _         reverse the digits
       s          convert to int
     +Q           add Q
    ~             assign the result to Q
                  (this returns the old value of Q)
   `              convert the old value of Q to a string
 _I               and check if it's invariant under the operation reverse

editar:

Alterou o código um pouco. A versão antiga era

fqKs_`Q~+QK0

Contagem de bytes iguais, mas a nova é bem mais legal.

Python, 51

def f(n):r=int(str(n)[::-1]);return n-r and-~f(n+r)

Para o Python 2, os backticks não podem ser substituídos str()por causa dos Lanexos aos longliterais.

Aqui está uma versão alternativa com pontuação 64 * 0.85 = 54.4 :

def f(n,c=262):r=int(str(n)[::-1]);return c*(n-r)and-~f(n+r,c-1)

E uma versão alternativa para Python 3 com pontuação 88 * 0.6 = 52.8 :

def f(n,c=262):r=int(str(n)[::-1]);return c*(n-r)and-~f(n+r,print(n,'+',r,'=',n+r)or~-c)

CJam, 23 22 20,4 bytes

ri{__sW%i+}261*]{s_W%=}#

O código tem 24 bytes e imprime -1 para os candidatos a Lychrel.

Experimente online.

Como funciona

ri                       e# Read an integer from STDIN.
  {       }261*          e# Do the following 261 times:
   __                    e#   Push two copies of the integer on the stack.
     sW%i                e#   Cast to string, reverse and cast back to integer.
         +               e#   Add the copy and the reversed copy of the integer.
               ]         e# Wrap all 262 results in an array.
                {     }# e# Push the index of the first element such that:
                 s       e#   The string representation equals...
                  _W%=   e#   the reversed string representation.

Se {}#for bem-sucedido, o índice também é o número de etapas. Se, por outro lado, a matriz não contém um palíndromo, {}#pressionará -1 .

Java, 200 * 0,6 = 120

import java.math.*;int f(BigInteger a){int s=-1;for(String b,c;(b=a+"").equals(c=new StringBuffer(b).reverse()+"")!=s++<999;)System.out.println(b+" + "+c+" = "+(a=a.add(new BigInteger(c))));return s;}

Este é um loop simples que faz exatamente o que diz na caixa, mas com um pouco de golfe adicionado. Retorna 1000para os candidatos Lychrel para obter o bônus de detecção. Acontece que eu era capaz de imprimir para não demasiado muitos caracteres (para Java pelo menos) e snag esse bônus também. O melhor que pude fazer sem o código de bônus foi 156, por isso valeu a pena.

Com algumas quebras de linha:

import java.math.*;
int f(BigInteger a){
    int s=-1;
    for(String b,c;(b=a+"").equals(c=new StringBuffer(b).reverse()+"")!=s++<999;)
        System.out.println(b+" + "+c+" = "+(a=a.add(new BigInteger(c))));
    return s;
}

Resposta antiga: 171 * 0.85 = 145.35 bytes

import java.math.*;int f(BigInteger a){int s=-1;for(String b,c;(b=a+"").equals(c=new StringBuffer(b).reverse()+"")!=s++<262;)a=a.add(new BigInteger(c));return s>261?-1:s;}

Ruby, (80 + 2) * 0,6 = ~ 49,2

Com bandeiras -nl, corra

p (0..261).find{$_[b=$_.reverse]||puts($_+' + '+b+' = '+$_="#{$_.to_i+b.to_i}")}

Saída parece

 $ ruby -nl lychrel.rb 
89
89 + 98 = 187
187 + 781 = 968
968 + 869 = 1837
1837 + 7381 = 9218
9218 + 8129 = 17347
17347 + 74371 = 91718
91718 + 81719 = 173437
173437 + 734371 = 907808
907808 + 808709 = 1716517
1716517 + 7156171 = 8872688
8872688 + 8862788 = 17735476
17735476 + 67453771 = 85189247
85189247 + 74298158 = 159487405
159487405 + 504784951 = 664272356
664272356 + 653272466 = 1317544822
1317544822 + 2284457131 = 3602001953
3602001953 + 3591002063 = 7193004016
7193004016 + 6104003917 = 13297007933
13297007933 + 33970079231 = 47267087164
47267087164 + 46178076274 = 93445163438
93445163438 + 83436154439 = 176881317877
176881317877 + 778713188671 = 955594506548
955594506548 + 845605495559 = 1801200002107
1801200002107 + 7012000021081 = 8813200023188
24

Se fornecido, ele imprime as 261 primeiras etapas de adição e depois nil.

Nada muito complicado aqui. Verificamos se $_(que é inicializado na entrada) contém seu reverso, o que só é possível se forem iguais, pois são do mesmo tamanho. Se for, imprimimos o número da etapa e saímos; caso contrário, exibimos e executamos a etapa de adição, armazenando o novo valor $_(infelizmente não consigo apenas evala string que estou exibindo porque interpreta um número invertido com um 0). como um literal octal). putsretorna um valor falsey para que o loop continue.

Pitão - 19 bytes

Usa o loop while e um contador. Provavelmente existe um algoritmo menor que esse, mas isso é bastante curto.

Wnz_z=z`+szs_z=hZ;Z

Experimente online aqui .

K, 25 bytes

#1_{~x~|x}{$. x,"+",|x}\$

Não é muito elegante. A forma geral ( {monad 1}{monad 2}\x) é o equivalente de K a um loop geral "while", em que a primeira mônada é a condição de parada e a segunda é uma função aplicada iterativamente ao argumentox . A primeira mônada ( {~x~|x}) é a negação da frase clássica "is xa palindrome". A segunda mônada concatena uma string representando x mais o reverso de x, avalia-a e depois converte o resultado em uma string com $.

Uma amostra de execução mostrando resultados intermediários:

  {~x~|x}{$. x,"+",|x}\$68
("68"
 "154"
 "605"
 "1111")

Fazer a saída formatada conforme solicitado para o bônus seria muito desajeitado e adicionaria uma quantidade significativa de código.

CJam, 23 bytes

Wl{\)\__W%_@#\i@i+s\}g;

Ainda faltam apenas alguns dias para o CJam, então estou bastante feliz por estar pelo menos na mesma faixa de alguns profissionais. :) Eu usei o truque de comparação de cordas de Martin, que ele também postou nas dicas do CJam. Também espiei a solução de Dennis para descobrir como reverter uma string.

Explicação:

W    Initialize counter, will keep this at bottom of stack.
     Start counting at -1 because the counter will be incremented in the
     last pass through the loop, when the palindrome is detected.
l    Get input.
{    Start block of while loop.
\)\  Increment counter. Need to swap before/after because it's one below top of stack.
__   Copy current value twice. Need 3 copies in total:
       * one for reversal
       * one for comparison
       * one for addition with reverse
W%   Reverse value.
_    Copy the reverse value once because we need 2 copies:
       * one for comparison
       * one for addition with original value
@    Rotate one copy of original value to top.
#    Test for non-equality with reverse, using Martin's trick.
\i   Swap reverse value to top, and convert it to int.
@i   Rotate remaining copy of original value to top, and convert it to int.
+s   Add the values, and convert result to string.
\    Swap, so that comparison result is at top of stack for while loop test.
}g   End of while loop.
;    Current value sits at top of stack. Pop it, leaving only counter.

Teste on-line

Julia, 129 120 bytes * 0,6 = 72

i->(i=big(i);n=0;d=digits;while d(i)!=reverse(d(i))&&n<262 t=BigInt(join(d(i)));println(i," + ",t," = ",i+=t);n+=1end;n)

Isso cria uma função sem nome que recebe um número inteiro como entrada e retorna um número inteiro, enquanto isso imprime cada etapa. Os candidatos a Lychrel têm um valor de retorno de 262. Para chamar isso, dê um nome, por exemplof=i->... .

Observe que, omitindo código relacionado apenas aos bônus, essa solução seria de 84 bytes.

Ungolfed + explicação:

function f(i)
    # Convert the input to a big integer
    i = big(i)

    # Initialize a step counter to 0
    n = 0

    # While the number is not a palindrome and we haven't exceeded 261 steps...
    while digits(i) != reverse(digits(i)) && n < 262

        # Get the reverse of the integer
        # Note that we aren't using reverse(); this is because digits()
        # returns an array of the digits in reverse order.
        t = BigInt(join(digits(i)))

        # Print the step and increment i
        println(i, " + ", t, " = ", i += t)

        # Count the step
        n += 1
    end

    # Return the number of steps or 262 for Lychrel candidates
    n
end

Exemplos:

julia> f(286)
286 + 682 = 968
968 + 869 = 1837
1837 + 7381 = 9218
9218 + 8129 = 17347
17347 + 74371 = 91718
91718 + 81719 = 173437
173437 + 734371 = 907808
907808 + 808709 = 1716517
1716517 + 7156171 = 8872688
8872688 + 8862788 = 17735476
17735476 + 67453771 = 85189247
85189247 + 74298158 = 159487405
159487405 + 504784951 = 664272356
664272356 + 653272466 = 1317544822
1317544822 + 2284457131 = 3602001953
3602001953 + 3591002063 = 7193004016
7193004016 + 6104003917 = 13297007933
13297007933 + 33970079231 = 47267087164
47267087164 + 46178076274 = 93445163438
93445163438 + 83436154439 = 176881317877
176881317877 + 778713188671 = 955594506548
955594506548 + 845605495559 = 1801200002107
1801200002107 + 7012000021081 = 8813200023188
23

julia> f(1186060307891929990)
(steps omitted)
261

julia> f(196)
(steps omitted)
262

julia> f(11)
0

Economizou 2 bytes graças ao Geobits!

CJam, 24 bytes

0q{__W%#}{_W%~\~+s\)\}w;

Teste aqui.

Explicação

0q     e# Push a zero (the counter) and read input.
{      e# While this block leaves something truthy on the stack...
  __   e#   Make two copies of the current number (as a string).
  W%   e#   Reverse the second copy.
  #    e#   Check that they are not equal.
}{     e# ... run this block.
  _W%  e#   Make a copy of the current number and reverse it.
  ~\~  e#   Evaluate both N and its reverse.
  +s   e#   Add them and turn the sum into a string.
  \)\  e#   Pull up the counter, increment it, and push it back down again.
}w
;      e# Discard the palindrome to leave the counter on the stack.

Para obter mais informações sobre por que #pode ser usado para verificar a desigualdade de string, consulte esta dica .

Haskell, 66 53 bytes

r=reverse.show
f x|show x==r x=0|1<2=1+f(x+read(r x))

Exemplo de uso:

*Main> map f [0,11,89,286,196196871,1005499526,1186060307891929990]
[0,0,24,23,45,109,261]

Clojure, 94 bytes

(fn[x](#(let[r(bigint(apply str(reverse(str %1))))] (if(= %1 r)%2(recur(+ %1 r)(inc %2))))x 0))

Esta é a minha primeira tentativa de codificar golfe, por isso me diga se estou fazendo algo errado.

Com alguns espaços:

(fn [x]
(#(let [r (bigint (apply str (reverse (str %1))))]
  (if (= %1 r) %2 (recur (+ %1 r) (inc %2)))) x 0))

Recursão simples da função interna. São necessários dois argumentos, o número inteiro %1e um índice %2. E se%1 for um palíndromo, o índice será retornado. Caso contrário, a função se chamará com a soma e o índice incrementado. A função externa inicializa o índice com zero.

Uma amostra:

repl=> ((fn[x](#(let[r(bigint(apply str(reverse(str %1))))](if(= %1 r)%2(recur(+ %1 r)(inc %2))))x 0)) 1186060307891929990)
261

Boost.Build, 304 bytes

Não é realmente uma língua. Ainda legal.

import sequence ;
import regex ;
rule r ( n ) {
m = "([0-9]?)" ;
return [ sequence.join [ sequence.reverse [ regex.match "$(m)$(m)$(m)$(m)$(m)$(m)$(m)$(m)$(m)" : $(n) ] ] : "" ] ;
}
rule x ( n ) {
i = 0 ;
while $(n) != [ r $(n) ] {
n = [ CALC $(n) + [ r $(n) ] ] ;
i = [ CALC $(i) + 1 ] ;
}
echo $(i) ;
}

Bem simples, além do hack elaborado baseado em regex que eu usei para reverter a string.

Ruby, 44

f=->n{n==(r=n.to_s.reverse.to_i)?0:f[n+r]+1}

Precisa do Ruby 1.9 ou superior para a ->sintaxe lambda.