Odwrócenie-dodawanie palindromu

Proces dodawania przez odwrócenie ma miejsce, gdy liczba jest dodawana do jej odwrotności, dopóki utworzona liczba nie będzie palindromem. Na przykład, jeśli zaczniemy od 68, proces wyglądałby następująco:

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

Jak widać, zajęło to 3 uzupełnienia, aby uzyskać liczbę palindromową. Gdybyśmy mieli zacząć 89, potrzebowalibyśmy 24 kroków (które można zobaczyć tutaj podział ).

Rekord świata w największej liczbie kroków wykonanych przed osiągnięciem palindromu wynosi 261, co występuje dla liczby 1186060307891929990, dając liczbę większą niż 10 ¹¹⁸ . Było jednak sporo liczb, których nie udało nam się uzyskać palindromu. Są to tak zwane liczby Lychrel .

Ponieważ pracujemy w bazie 10, naprawdę możemy nazywać ich kandydatami, ponieważ nie ma dowodów, że liczby te nigdy nie osiągają palindromu. Na przykład najmniejszy kandydat na Lychrela z grupy podstawowej 10 ma 196 lat i przeszedł ponad miliard iteracji. Jeśli palindrom istnieje, jest znacznie większy niż 10 ^{10 8,77} . Dla porównania, jeśli tyle atomów 1 zostało zapisanych na atomach, potrzebowalibyśmy atomów o wartości 2,26772 × 10 ^588843575 wszechświatów, aby je zapisać, zakładając, że istnieje.

Twoje zadanie

Utwórz program lub funkcję, która przyjmuje liczbę całkowitą i zwraca lub drukuje liczbę kroków wymaganych do osiągnięcia palindromu. Nie będziesz musiał radzić sobie z kandydatami Lychrel (tzn. Twój program, gdy otrzyma kandydata Lychrel, może albo rzucić błąd, albo działać wiecznie).

Przypadki testowe:

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

Zasady

1. Brak standardowych luk.

Bonusy

1. Jeśli wydrukujesz każdy krok dodawania, sformatowany n + rev(n) = m, możesz pomnożyć swój wynik przez 0,75 . Sumy powinny zostać wydrukowane przed liczbą kroków.
2. Jeśli Twój kod może wykryć, czy liczba jest kandydatem Lychrel, możesz pomnożyć swój wynik przez 0,85 . W tym przypadku wystarczy założyć, że wszystko, co wymaga więcej niż 261 iteracji, jest kandydatem Lychrela. Albo nie zwracaj niczego, ani niczego, co nie jest liczbą, którą można pomylić z poprawną odpowiedzią (itp .: dowolny ciąg znaków lub liczba spoza zakresu 0–261). Każdy błąd nie jest liczony jako prawidłowy wynik (np. Przekroczona maksymalna głębokość rekurencji) i nie może być użyty do wykrywania.
3. Jeśli ukończysz oba bonusy, pomnóż je przez 0,6 .

To jest golf golfowy , więc wygrywa najmniejsza liczba bajtów.

Ten fragment kodu pokazuje przykładowe rozwiązanie w Pythonie 3 z obydwoma bonusami.

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 bajtów

f_I`~+Qs_`Q0

Wypróbuj online: Demonstracja lub Uprząż testowa

Wykorzystuje to całkiem nową funkcję (tylko 17 godzin).

Wyjaśnienie

               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

edytować:

Trochę zmieniłem kod. Stara wersja była

fqKs_`Q~+QK0

Ta sama liczba bajtów, ale nowy jest znacznie fajniejszy.

Python, 51

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

W Pythonie 2 backticks nie mogą zastąpić str()ze względu na Ldołączone do longliterałów.

Oto alternatywna wersja z wynikiem 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)

I alternatywna wersja dla Pythona 3 z wynikiem 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 bajtów

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

Kod ma 24 bajty i drukuje -1 dla kandydatów Lychrel.

Wypróbuj online.

Jak to działa

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.

Jeśli {}#się powiedzie, indeks jest również liczbą kroków. Z drugiej strony, jeśli tablica nie zawiera palindromu, {}#popchnie -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;}

Jest to prosta pętla, która robi dokładnie to, co jest napisane na pudełku, ale z dodatkiem golfa. Zwraca 1000kandydatów Lychrel, aby uzyskać premię za wykrywanie. Okazuje się, udało mi się wydrukować na nie zbyt wielu znaków (dla Java co najmniej) i szkopuł, że premia za dobrze. Najlepsze, co mogłem zrobić bez kodu bonusowego, to 156, więc było warto.

Z pewnymi podziałami linii:

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

Stara odpowiedź: 171 * 0,85 = 145,35 bajtów

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

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

Z flagami -nlbiegnij

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

Wygląda jak

 $ 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

Jeśli podano 196, drukuje pierwsze 261 kroków dodawania, a następnie nil.

Nie ma tu nic trudnego. Sprawdzamy, czy $_(który jest inicjowany na wejściu) zawiera jego odwrotność, co jest możliwe tylko wtedy, gdy są równe, ponieważ mają ten sam rozmiar. Jeśli tak, drukujemy numer kroku i kończymy, w przeciwnym razie wyświetlamy i wykonujemy krok dodawania, przechowując nową wartość w $_(niestety nie mogę po prostu evalwyświetlać ciągu, ponieważ interpretuje on liczbę odwróconą z końcową wartością 0 jako literał ósemkowy). putszwraca wartość falsey, więc pętla trwa.

Pyth - 19 bajtów

Używa pętli while i licznika. Prawdopodobnie istnieje mniejszy algorytm niż ten, ale jest on dość krótki.

Wnz_z=z`+szs_z=hZ;Z

Wypróbuj online tutaj .

K, 25 bajtów

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

Niezbyt elegancki. Ogólna forma ( {monad 1}{monad 2}\x) jest odpowiednikiem K ogólnej pętli „while”, gdzie pierwsza monada jest warunkiem zatrzymania, a druga iteracyjnie zastosowana funkcja do argumentu x. Pierwsza monada ( {~x~|x}) jest zaprzeczeniem klasycznej frazy „is xa palindrome”. Druga monada łączy ze sobą ciąg reprezentujący x plus odwrotność x, ocenia go, a następnie rzutuje wynik z powrotem na ciąg z $.

Przykładowy przebieg pokazujący wyniki pośrednie:

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

Wykonanie sformatowanych danych wyjściowych zgodnie z żądaniem premii byłoby bardzo nieporadne i wymagałoby znacznej ilości kodu.

CJam, 23 bajty

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

Jeszcze tylko kilka dni do CJam, więc jestem całkiem szczęśliwy, że jestem w tym samym zakresie, co niektórzy profesjonaliści. :) Użyłem sztuczki porównywania napisów Martina, którą opublikował również w poradach CJam. Zajrzałem również do rozwiązania Dennisa, aby dowiedzieć się, jak odwrócić ciąg.

Wyjaśnienie:

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.

Przetestuj online

Julia, 129 120 bajtów * 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)

Tworzy to nienazwaną funkcję, która przyjmuje na wejściu liczbę całkowitą i zwraca liczbę całkowitą, jednocześnie drukując każdy krok. Kandydaci Lychrel mają wartość zwracaną 262. Aby to nazwać, nadaj mu nazwę, np f=i->....

Zauważ, że pomijając kod odnoszący się tylko do bonusów, to rozwiązanie miałoby 84 bajty.

Niegolfowane + wyjaśnienie:

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

Przykłady:

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

Zaoszczędzono 2 bajty dzięki Geobits!

CJam, 24 bajty

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

Sprawdź to tutaj.

Wyjaśnienie

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.

Aby uzyskać więcej informacji o tym, dlaczego #można użyć do sprawdzenia nierówności łańcucha, zobacz tę wskazówkę .

Haskell, 66 53 bajtów

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

Przykład użycia:

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

Clojure, 94 bajty

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

To moja pierwsza próba kodowania golfa, więc powiedz mi, czy robię coś źle.

Z pewnymi spacjami:

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

Prosta rekurencja funkcji wewnętrznej. Wymaga dwóch argumentów, liczby całkowitej %1i indeksu %2. Jeśli %1jest palindromem, indeks jest zwracany. W przeciwnym razie funkcja wywołuje się z sumą i indeksem przyrostowym. Funkcja zewnętrzna inicjuje indeks zerem.

Próbka:

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 bajty

Niezupełnie język. Nadal fajne.

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

Całkiem proste, inne niż skomplikowany hack oparty na wyrażeniach regularnych, którego użyłem do odwrócenia łańcucha.

Ruby, 44

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

Wymaga Ruby 1.9 lub nowszego dla ->składni lambda.