Inversión-adición de palíndromo

El proceso de adición de reversión es donde se agrega un número al reverso hasta que el número creado es un palíndromo. Por ejemplo, si comenzamos con 68, el proceso sería:

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

Como puede ver, esto tomó 3 adiciones para llegar a un número palindrómico. Si comenzáramos 89, necesitaríamos 24 pasos (que puede ver el desglose aquí ).

El récord mundial para la mayoría de los pasos dados antes de alcanzar un palíndromo es 261, lo que ocurre para el número 1186060307891929990, produciendo un número mayor que 10 ¹¹⁸ . Sin embargo, ha habido bastantes números que no hemos podido obtener un palíndromo. Estos se llaman números de Lychrel .

Como estamos trabajando en la base 10, realmente solo podemos llamarlos candidatos, porque no existe prueba de que estos números nunca lleguen a un palíndromo. Por ejemplo, el candidato más pequeño de base 10 Lychrel es 196, y ha pasado por más de mil millones de iteraciones. Si el palíndromo existe, es mucho más grande que 10 ^{10 8.77} . En comparación, si esa cantidad de 1s estuviera inscrita en átomos, necesitaríamos 2.26772 × 10 ^588843575 universos por valor de átomos para escribirla, suponiendo que exista.

Tu tarea

Cree un programa o función que tome una entrada entera y devuelva o imprima el número de pasos necesarios para alcanzar un palíndromo. No tendrá que tratar con candidatos de Lychrel (es decir, su programa, cuando recibe un candidato de Lychrel, puede lanzar un error o ejecutarse para siempre).

Casos de prueba:

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

Reglas

1. No hay lagunas estándar.

Bonos

1. Si imprime cada paso adicional, formateado n + rev(n) = m, puede multiplicar su puntaje por 0.75 . Las sumas deben imprimirse antes del número de pasos.
2. Si su código puede detectar si un número es un candidato de Lychrel, puede multiplicar su puntaje por 0.85 . En este caso, es suficiente suponer que cualquier cosa que requiera más de 261 iteraciones es un candidato de Lychrel. O no devuelve nada, o cualquier cosa que no sea un número que pueda confundirse con una respuesta correcta (etc.: cualquier cadena o un número que no esté en el rango 0-261). Cualquier error no cuenta como salida válida (p. Ej., Se excede la profundidad máxima de recursión) y no puede utilizarse en la detección.
3. Si completa ambas bonificaciones, multiplique por 0.6 .

Este es el código de golf , por lo que gana el menor número de bytes.

Este fragmento de código muestra una solución de ejemplo en Python 3 con ambos bonos.

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)

Pyth, 12 bytes

f_I`~+Qs_`Q0

Pruébelo en línea: demostración o prueba de arnés

Utiliza una función bastante nueva (solo 17 horas).

Explicación

               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:

Cambió el código un poco. La versión anterior era

fqKs_`Q~+QK0

El mismo recuento de bytes, pero el nuevo es mucho más genial.

Python, 51

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

Para Python 2, los backticks no pueden reemplazarse str()debido a los Ladjuntos a longliterales.

Aquí hay una versión alternativa con puntaje 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)

Y una versión alternativa para Python 3 con puntaje 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%=}#

El código tiene 24 bytes de longitud e imprime -1 para los candidatos de Lychrel.

Pruébalo en línea.

Cómo 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.

Si {}#tiene éxito, el índice también es el número de pasos. Si, por otro lado, la matriz no contiene un palíndromo, {}#empujará -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 es un bucle simple que hace exactamente lo que dice en la caja, pero con algo de golf agregado. Devoluciones 1000para los candidatos de Lychrel para obtener el bono de detección. Resulta que pude imprimir para no demasiados caracteres (al menos para Java) y enganchar ese bono también. Lo mejor que pude hacer sin el código de bono fue 156, por lo que valió la pena.

Con algunos saltos de línea:

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;
}

Respuesta anterior: 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;}

Rubí, (80 + 2) * 0.6 = ~ 49.2

Con banderas -nl, corre

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

La salida se ve como

 $ 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

Si se le da 196, imprime los primeros 261 pasos de suma y luego nil.

Nada demasiado complicado aquí. Verificamos si $_(que se inicializa en la entrada) contiene su reverso, que solo es posible si son iguales ya que son del mismo tamaño. Si es así, imprimimos el número de paso y salimos, de lo contrario, mostramos y ejecutamos el paso de suma, almacenando el nuevo valor en $_(desafortunadamente no puedo solo evalla cadena que estoy mostrando porque interpreta un número invertido con un 0 al final como un literal octal). putsdevuelve un valor falsey para que el ciclo continúe.

Pyth - 19 bytes

Utiliza while loop y un contador. Probablemente haya un algoritmo más pequeño que este, pero esto es bastante corto.

Wnz_z=z`+szs_z=hZ;Z

Pruébelo en línea aquí .

K, 25 bytes

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

No muy elegante La forma general ( {monad 1}{monad 2}\x) es el equivalente de K de un ciclo general "while", donde la primera mónada es la condición de detención y la segunda es una función aplicada iterativamente al argumento x. La primera mónada ( {~x~|x}) es la negación de la clásica frase "is xa palindrome". La segunda mónada concatena una cadena que representa x más el reverso de x, la evalúa y luego vuelve a arrojar el resultado en una cadena con $.

Una ejecución de muestra que muestra resultados intermedios:

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

Hacer una salida formateada según lo solicitado para la bonificación sería muy torpe y agregaría una cantidad significativa de código.

CJam, 23 bytes

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

Todavía solo unos pocos días en CJam, así que estoy bastante feliz de estar al menos en el mismo rango que algunos de los profesionales. :) Utilicé el truco de comparación de cadenas de Martin que también publicó en las sugerencias de CJam. También eché un vistazo a la solución de Dennis para descubrir cómo invertir una cadena.

Explicación:

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.

Pruébelo en línea

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)

Esto crea una función sin nombre que toma un entero como entrada y devuelve un entero, mientras imprime cada paso. Los candidatos de Lychrel tienen un valor de retorno de 262. Para llamar a esto, asígnele un nombre, p. Ej.f=i->... .

Tenga en cuenta que omitiendo el código relacionado solo con los bonos, esta solución sería de 84 bytes.

Ungolfed + explicación:

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

Ejemplos:

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

¡Ahorró 2 bytes gracias a Geobits!

CJam, 24 bytes

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

Pruébalo aquí.

Explicación

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 obtener más información sobre por qué #se puede usar para verificar la desigualdad de cadenas, consulte este consejo .

Haskell, 66 53 bytes

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

Ejemplo 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))

Este es mi primer intento de codificar golf, así que dígame si estoy haciendo algo mal.

Con algunos espacios:

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

Recurrencia simple de la función interna. Se necesitan dos argumentos, el entero %1y un índice.%2 . Si %1es un palíndromo, se devuelve el índice. De lo contrario, la función se llama a sí misma con la suma y el índice incrementado. La función externa inicializa el índice con cero.

Una muestra:

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

No es realmente un idioma. Aún genial

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) ;
}

Bastante sencillo, aparte del elaborado truco basado en expresiones regulares que usé para invertir la cadena.

Rubí, 44

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

Necesita Ruby 1.9 o superior para la ->sintaxis lambda.