Inversement-ajout de palindrome

Le processus d'inversion-addition est où un nombre est ajouté à son inverse jusqu'à ce que le nombre créé soit un palindrome. Par exemple, si nous commençons par 68, le processus serait:

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

Comme vous pouvez le voir, cela a pris 3 ajouts pour obtenir un nombre palindromique. Si nous devions commencer 89, nous aurions besoin de 24 étapes (dont vous pouvez voir la répartition ici ).

Le record du monde pour le plus grand nombre de mesures prises avant qu'un palindrome soit atteint est 261, ce qui se produit pour le nombre 1186060307891929990, produisant un nombre supérieur à 10 ¹¹⁸ . Cependant, il y a eu pas mal de chiffres que nous n'avons pas pu obtenir de palindrome. Ce sont les nombres de Lychrel .

Puisque nous travaillons en base 10, nous ne pouvons vraiment les appeler que des candidats, car il n'existe aucune preuve que ces chiffres n'atteignent jamais un palindrome. Par exemple, le plus petit candidat Lychrel en base 10 est 196, et a traversé bien plus d'un milliard d'itérations. Si le palindrome existe, il est beaucoup plus grand que 10 ^{10 8,77} . À titre de comparaison, si ce nombre de 1 était inscrit sur des atomes, il nous faudrait 2,26772 × 10 ^588843575 univers d'atomes pour l'écrire, en supposant qu'il existe.

Ta tâche

Créez un programme ou une fonction qui prend une entrée entière et renvoie ou imprime le nombre d'étapes nécessaires pour atteindre un palindrome. Vous ne serez pas obligé de traiter avec des candidats Lychrel (c.-à-d. Que votre programme, lorsqu'il reçoit un candidat Lychrel, est autorisé à lancer une erreur ou à courir indéfiniment).

Cas de test:

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

Règles

1. Pas de failles standard.

Bonus

1. Si vous imprimez chaque étape d'ajout, formatée n + rev(n) = m, vous pouvez multiplier votre score par 0,75 . Les sommes doivent être imprimées avant le nombre d'étapes.
2. Si votre code peut détecter si un nombre est un candidat Lychrel, vous pouvez multiplier votre score par 0,85 . Dans ce cas, il suffit de supposer que tout ce qui prend plus de 261 itérations est un candidat Lychrel. Soit ne renvoyez rien, ou tout ce qui n'est pas un nombre qui peut être confondu avec une réponse correcte (etc: n'importe quelle chaîne ou un nombre non compris dans la plage 0-261). Toute erreur ne compte pas comme sortie valide (ex. Profondeur de récursivité maximale dépassée) et ne peut pas être utilisée dans la détection.
3. Si vous terminez les deux bonus, multipliez par 0,6 .

Il s'agit de code-golf , donc le moins d'octets gagne.

Cet extrait de code montre un exemple de solution en Python 3 avec les deux bonus.

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 octets

f_I`~+Qs_`Q0

Essayez-le en ligne: démonstration ou test de harnais

Cela utilise une toute nouvelle fonctionnalité (seulement 17 heures).

Explication

               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

Éditer:

Un peu changé le code. L'ancienne version était

fqKs_`Q~+QK0

Même nombre d'octets, mais le nouveau est beaucoup plus cool.

Python, 51

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

Pour Python 2, les backticks ne peuvent pas remplacer en str()raison de l' Lattachement aux longlittéraux.

Voici une autre version avec un score de 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)

Et une version alternative pour Python 3 avec un score de 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 octets

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

Le code fait 24 octets et affiche -1 pour les candidats Lychrel.

Essayez-le en ligne.

Comment ça fonctionne

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 elle {}#réussit, l'index correspond également au nombre d'étapes. Si, en revanche, le tableau ne contient pas de palindrome, {}#il poussera -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;}

Il s'agit d'une simple boucle qui fait exactement ce qu'elle dit sur la boîte, mais avec du golf ajouté. Retourne 1000pour les candidats Lychrel pour obtenir le bonus de détection. Il s'avère que j'ai pu imprimer pour pas trop de caractères (pour Java au moins) et accrocher ce bonus également. Le mieux que je pouvais faire sans code bonus était 156, donc ça valait le coup.

Avec quelques sauts de ligne:

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

Ancienne réponse: 171 * 0,85 = 145,35 octets

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

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

Avec des drapeaux -nl, courez

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

La sortie ressemble à

 $ 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 donné 196, il imprime les 261 premières étapes d'addition puis nil.

Rien de trop compliqué ici. Nous vérifions si $_(qui est initialisé à l'entrée) contient son revers, ce qui n'est possible que s'ils sont égaux car ils sont de la même taille. Si c'est le cas, nous imprimons le numéro d'étape et quittons, sinon, nous affichons et exécutons l'étape d'addition, stockant la nouvelle valeur dans $_(je ne peux malheureusement pas simplement evalla chaîne que j'affiche car elle interprète un nombre inversé avec un 0 à la fin) comme un octal littéral). putsrenvoie une valeur de falsey pour que la boucle continue.

Pyth - 19 octets

Utilise une boucle et un compteur. Il existe probablement un algorithme plus petit que celui-ci, mais il est assez court.

Wnz_z=z`+szs_z=hZ;Z

Essayez-le en ligne ici .

K, 25 octets

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

Pas très élégant. La forme globale ( {monad 1}{monad 2}\x) est l'équivalent de K d'une boucle "while" générale, où la première monade est la condition d'arrêt et la seconde est une fonction appliquée de manière itérative à l'argument x. La première monade ( {~x~|x}) est la négation de la phrase classique "is xa palindrome". La deuxième monade concatène ensemble une chaîne représentant x plus l'inverse de x, l'évalue puis recompose le résultat dans une chaîne avec $.

Un échantillon montrant des résultats intermédiaires:

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

Faire une sortie formatée comme demandé pour le bonus serait très maladroit et ajouterait une quantité importante de code.

CJam, 23 octets

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

Encore quelques jours dans CJam, je suis donc assez heureux d'être au moins dans la même gamme que certains des pros. :) J'ai utilisé l'astuce de comparaison de cordes de Martin qu'il a également publiée dans les conseils CJam. J'ai également jeté un œil à la solution de Dennis pour comprendre comment inverser une chaîne.

Explication:

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.

Testez-le en ligne

Julia, 129120 octets * 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)

Cela crée une fonction sans nom qui prend un entier en entrée et renvoie un entier, en attendant l'impression de chaque étape. Les candidats Lychrel ont une valeur de retour de 262. Pour l'appeler, donnez-lui un nom, par exemple f=i->....

Notez qu'en omettant le code relatif uniquement aux bonus, cette solution serait de 84 octets.

Non golfé + explication:

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

Exemples:

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

Sauvegardé 2 octets grâce aux Geobits!

CJam, 24 octets

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

Testez-le ici.

Explication

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.

Pour plus d'informations sur la raison pour laquelle vous #pouvez utiliser pour vérifier l'inégalité des chaînes, consultez cette astuce .

Haskell, 66 53 octets

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

Exemple d'utilisation:

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

Clojure, 94 octets

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

C'est ma première tentative de coder le golf, alors dites-moi si je fais quelque chose de mal.

Avec quelques espaces:

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

Récursivité simple de la fonction interne. Il prend deux arguments, l'entier %1et un index %2. S'il %1s'agit d'un palindrome, l'index est renvoyé. Sinon, la fonction s'appelle avec la somme et l'index incrémenté. La fonction externe initialise l'index avec zéro.

Un échantillon:

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 octets

Pas vraiment une langue. Toujours cool.

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

Assez simple, à part le hack basé sur les regex élaborés que j'ai utilisé pour inverser la chaîne.

Rubis, 44

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

Nécessite Ruby 1.9 ou supérieur pour la ->syntaxe lambda.