Палиндром Реверс-сложение

Процесс Reversal-Addition заключается в том, что число добавляется к обратному, пока созданное число не станет палиндромом. Например, если мы начнем с 68, процесс будет:

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

Как видите, для получения палиндромного числа потребовалось 3 дополнения. Если бы мы начали с того 89, что нам понадобилось бы 24 шага (вы можете увидеть разбивку здесь ).

Мировой рекорд по большинству шагов, предпринятых до достижения палиндрома, составляет 261, что соответствует числу 1186060307891929990, в результате чего число превышает 10 ¹¹⁸ . Тем не менее, было довольно много цифр, которые мы не смогли получить палиндром. Они называются числами Лихрела .

Поскольку мы работаем над базой 10, мы действительно можем назвать их только кандидатами, потому что нет никаких доказательств того, что эти числа никогда не достигают палиндрома. Например, самая маленькая база-10 Lychrel кандидат 196, и прошел более миллиарда итераций. Если палиндром существует, он намного больше 10 ^{10 8,77} . Для сравнения, если бы это число 1 было записано на атомах, нам потребовалось бы 2,26772 × 10 ^{588843575 единиц} вселенных, чтобы выписать его, предполагая, что оно существует.

Твое задание

Создайте программу или функцию, которая принимает целое данные и возвращает или печатает количество шагов, необходимых для достижения палиндром. От вас не потребуется иметь дело с кандидатами в Lychrel (т. Е. Вашей программе, если выдан кандидат в Lychrel, разрешается либо выдавать ошибку, либо выполняться вечно).

Тестовые случаи:

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

правила

1. Нет стандартных лазеек.

Бонусы

1. Если вы распечатаете каждый отформатированный шаг добавления, n + rev(n) = mвы можете умножить свой счет на 0,75 . Суммы должны быть распечатаны до количества шагов.
2. Если ваш код может определить, является ли число кандидатом в лихрель, вы можете умножить свой счет на 0,85 . В этом случае достаточно предположить, что все, что занимает более 261 итерации, является кандидатом в Лихрел. Либо ничего не вернуть, либо что-либо, что не является числом, которое может быть ошибочно принято за правильный ответ (и т. Д .: любая строка или число, не находящееся в диапазоне 0-261). Любая ошибка не считается действительным выходным сигналом (например, превышена максимальная глубина рекурсии) и не может использоваться при обнаружении.
3. Если вы завершите оба бонуса, умножить на 0,6 .

Это код-гольф , поэтому выигрывает наименьшее количество байтов.

Этот фрагмент кода показывает пример решения в Python 3 с обоими бонусами.

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 байт

f_I`~+Qs_`Q0

Попробуйте онлайн: демонстрация или тестовая привязь

Это использует совершенно новую функцию (всего 17 часов).

объяснение

               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

редактировать:

Немного изменил код. Старая версия была

fqKs_`Q~+QK0

Тот же счетчик байтов, но новый намного круче.

Python, 51

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

В Python 2 обратные ссылки не могут быть заменены str()из-за Lпривязки к longлитералам.

Вот альтернативная версия со счетом 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)

И альтернативная версия для Python 3 со счетом 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 байта

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

Код имеет длину 24 байта и печатает -1 для кандидатов в Lychrel.

Попробуйте онлайн.

Как это устроено

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.

Если {}#успешно, индекс также число шагов. Если, с другой стороны, массив не содержит палиндрома, {}#будет выдвигаться -1 .

Ява, 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;}

Это простая петля, которая выполняет только то, что написано на коробке, но с добавлением некоторого количества гольфа. Возвращает 1000кандидатов в Лихрел, чтобы получить бонус за обнаружение. Оказывается, я смог напечатать не слишком много символов (по крайней мере, для Java) и получить этот бонус. Лучшее, что я мог сделать без кода бонуса, было 156, так что оно того стоило.

С некоторыми переносами строк:

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

Старый ответ: 171 * 0,85 = 145,35 байт

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

Рубин, (80 + 2) * 0,6 = ~ 49,2

С флагами -nlбеги

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

Выход выглядит как

 $ 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

Если дано 196, он печатает первые 261 этапы сложения, а затем nil.

Здесь нет ничего сложного. Мы проверяем, $_содержит ли (который инициализируется для ввода) его реверс, что возможно только в том случае, если они равны, поскольку имеют одинаковый размер. Если это так, мы печатаем номер шага и выходим, в противном случае мы отображаем и выполняем шаг сложения, сохраняя новое значение в $_(я, к сожалению, не могу просто evalотобразить строку, потому что она интерпретирует перевернутое число с завершающим 0 как восьмеричное буквальное). putsвозвращает значение Falsey, поэтому цикл продолжается.

Pyth - 19 байт

Использует цикл while и счетчик. Вероятно, алгоритм меньше, чем этот, но он довольно короткий.

Wnz_z=z`+szs_z=hZ;Z

Попробуйте это онлайн здесь .

К, 25 байт

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

Не очень элегантно Общая форма ( {monad 1}{monad 2}\x) является эквивалентом K общего цикла while, где первая монада является условием остановки, а вторая - итеративно применяемой функцией аргумента x. Первая монада ( {~x~|x}) - это отрицание классической фразы «является палиндромом». Вторая монада объединяет строку, представляющую x плюс обратную x, вычисляет ее и затем возвращает результат обратно в строку с $.

Пробный прогон с промежуточными результатами:

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

Выполнение форматированного вывода в соответствии с запросом бонуса будет очень неуклюжим и добавит значительное количество кода.

CJam, 23 байта

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

До CJam осталось всего несколько дней, так что я очень рад оказаться в том же диапазоне, что и некоторые профессионалы. :) Я использовал трюк сравнения строк Мартина, который он также опубликовал в подсказках CJam. Я также заглянул в решение Денниса, чтобы выяснить, как перевернуть строку.

Объяснение:

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.

Протестируйте это онлайн

Юлия, 129 120 байтов * 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)

Это создает безымянную функцию, которая принимает целое число в качестве входных данных и возвращает целое число, в то же время печатая каждый шаг. Кандидаты в Lychrel имеют возвращаемое значение 262. Чтобы вызвать это, дайте ему имя, например f=i->....

Обратите внимание, что без учета кода, относящегося только к бонусам, это решение будет иметь размер 84 байта.

Ungolfed + объяснение:

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

Примеры:

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

Сохранено 2 байта благодаря Geobits!

CJam, 24 байта

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

Проверьте это здесь.

объяснение

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.

Дополнительную информацию о том, почему #можно использовать для проверки неравенства строк, смотрите в этом совете .

Haskell, 66 53 байта

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

Пример использования:

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

Clojure, 94 байта

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

Это моя первая попытка кодировать гольф, поэтому, пожалуйста, скажите мне, если я делаю что-то не так.

С некоторыми пробелами:

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

Простая рекурсия внутренней функции. Он принимает два аргумента, целое число %1и индекс%2 . Если %1это палиндром, индекс возвращается. В противном случае функция вызывает себя с суммой и увеличенным индексом. Внешняя функция инициализирует индекс с нуля.

Образец:

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 байта

Не совсем язык. Все еще круто.

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

Довольно просто, кроме сложного взлома на основе регулярных выражений, который я использовал, чтобы перевернуть строку.

Руби, 44

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

Требуется Ruby 1,9 или выше для ->лямбда-синтаксиса.