Palindrome Reversal-Addition

Proses Reversal-Addition adalah di mana angka ditambahkan ke terbalik sampai angka yang dibuat adalah palindrome. Misalnya, jika kita mulai dengan 68, prosesnya adalah:

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

Seperti yang Anda lihat, ini membutuhkan 3 tambahan untuk mendapatkan nomor palindromic. Jika kita memulainya 89, kita akan membutuhkan 24 langkah (yang dapat Anda lihat rinciannya di sini ).

Rekor dunia untuk langkah terbanyak yang diambil sebelum palindrome tercapai adalah 261, yang terjadi untuk angka tersebut 1186060307891929990, menghasilkan angka yang lebih besar dari 10 ¹¹⁸ . Namun, ada beberapa angka yang belum bisa kita dapatkan palindrom. Ini disebut nomor Lychrel .

Karena kami bekerja di basis 10, kami benar-benar hanya dapat memanggil mereka kandidat, karena tidak ada bukti bahwa angka-angka ini tidak pernah mencapai palindrom. Sebagai contoh, kandidat Lychrel basis-10 terkecil adalah 196, dan telah melewati lebih dari satu miliar iterasi. Jika palindrom memang ada, itu jauh lebih besar dari 10 ^{10 8,77} . Sebagai perbandingan, jika banyak 1s itu ditorehkan pada atom, kita akan membutuhkan 2.26772 × 10 ^588843575 nilai alam semesta atom untuk menuliskannya, dengan asumsi itu ada.

Tugas Anda

Buat program atau fungsi yang mengambil input integer dan mengembalikan atau mencetak jumlah langkah yang diperlukan untuk mencapai palindrome. Anda tidak akan diharuskan untuk berurusan dengan kandidat Lychrel (yaitu program Anda, ketika diberi kandidat Lychrel, diizinkan untuk melakukan kesalahan atau menjalankan selamanya).

Kasus uji:

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

Aturan

1. Tidak ada celah standar.

Bonus

1. Jika Anda mencetak setiap langkah penambahan, diformat n + rev(n) = m, Anda dapat mengalikan skor Anda dengan 0,75 . Jumlahnya harus dicetak sebelum jumlah langkah.
2. Jika kode Anda dapat mendeteksi jika suatu angka adalah kandidat Lychrel, Anda dapat mengalikan skor Anda dengan 0,85 . Dalam hal ini cukup untuk mengasumsikan apa pun yang membutuhkan lebih dari 261 iterasi adalah kandidat Lychrel. Entah tidak mengembalikan apa pun, atau apa pun yang bukan angka yang dapat salah untuk jawaban yang benar (dll: string apa pun atau angka yang tidak berada dalam kisaran 0-261). Kesalahan apa pun tidak dihitung sebagai output yang valid (mis. Kedalaman rekursi maksimum terlampaui) dan tidak dapat digunakan dalam deteksi.
3. Jika Anda menyelesaikan kedua bonus, kalikan dengan 0,6 .

Ini adalah kode-golf , jadi paling sedikit jumlah byte yang menang.

Cuplikan kode ini menunjukkan contoh solusi dalam Python 3 dengan kedua 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 byte

f_I`~+Qs_`Q0

Cobalah secara online: Demonstrasi atau Uji harness

Ini menggunakan fitur yang cukup baru (hanya 17 jam).

Penjelasan

               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

edit:

Mengubah kode sedikit. Versi lama adalah

fqKs_`Q~+QK0

Jumlah byte yang sama, tetapi yang baru lebih keren.

Python, 51

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

Untuk Python 2, backticks tidak dapat menggantikan str()karena Lmelekat pada longliteral.

Ini versi alternatif dengan skor 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)

Dan versi alternatif untuk Python 3 dengan skor 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 byte

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

Kode panjangnya 24 byte dan mencetak -1 untuk kandidat Lychrel.

Cobalah online.

Bagaimana itu bekerja

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.

Jika {}#berhasil, indeks juga merupakan jumlah langkah. Jika, di sisi lain, array tidak mengandung palindrome, {}#akan mendorong -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;}

Ini adalah loop sederhana yang tidak hanya apa yang tertulis di kotak, tetapi dengan beberapa golf ditambahkan. Pengembalian 1000untuk kandidat Lychrel untuk mendapatkan bonus deteksi. Ternyata saya bisa mencetak untuk karakter yang tidak terlalu banyak (setidaknya untuk Java) dan mendapatkan bonus itu juga. Yang terbaik yang bisa saya lakukan tanpa kode bonus adalah 156, jadi itu sangat berharga.

Dengan beberapa jeda baris:

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

Jawaban Lama: 171 * 0,85 = 145,35 byte

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

Dengan bendera -nl, jalankan

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

Outputnya seperti

 $ 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

Jika diberikan 196, ia mencetak 261 langkah penambahan pertama dan kemudian nil.

Tidak ada yang terlalu rumit di sini. Kami memeriksa apakah $_(yang diinisialisasi ke input) berisi kebalikannya, yang hanya mungkin jika mereka sama karena ukurannya sama. Jika ya, kami mencetak nomor langkah dan keluar, jika tidak, kami menampilkan dan mengeksekusi langkah tambahan, menyimpan nilai baru di $_(sayangnya saya tidak bisa hanya evalstring yang saya tampilkan karena menafsirkan angka yang dibalik dengan trailing 0 sebagai oktal literal). putsmengembalikan nilai falsey sehingga loop berlanjut.

Pyth - 19 byte

Menggunakan while dan counter. Mungkin ada algoritma yang lebih kecil dari ini, tetapi ini cukup singkat.

Wnz_z=z`+szs_z=hZ;Z

Cobalah online di sini .

K, 25 byte

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

Tidak terlalu elegan. Bentuk keseluruhan ( {monad 1}{monad 2}\x) adalah ekuivalen K dari loop umum "sementara", di mana monad pertama adalah kondisi penghentian dan yang kedua adalah fungsi yang diterapkan secara iteratif pada argumen x. Monad pertama ( {~x~|x}) adalah negasi dari frasa klasik "is xa palindrome". Monad kedua menyatukan string yang mewakili x ditambah kebalikan dari x, mengevaluasinya dan kemudian melemparkan hasilnya kembali ke string dengan $.

Contoh dijalankan menunjukkan hasil antara:

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

Melakukan output yang diformat seperti yang diminta untuk bonus akan sangat canggung dan menambahkan sejumlah kode.

CJam, 23 byte

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

Masih hanya beberapa hari ke CJam, jadi saya cukup senang berada di kisaran yang sama dengan beberapa pro. :) Saya memang menggunakan trik perbandingan string Martin yang juga diposting di petunjuk CJam. Saya juga mengintip solusi Dennis untuk mengetahui cara membalikkan string.

Penjelasan:

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.

Uji secara online

Julia, 129 120 byte * 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)

Ini menciptakan fungsi tanpa nama yang mengambil integer sebagai input dan mengembalikan integer, sementara itu mencetak setiap langkah. Kandidat Lychrel memiliki nilai kembali 262. Untuk memanggil ini, beri nama, misalnya f=i->....

Perhatikan bahwa menghilangkan kode yang hanya berkaitan dengan bonus, solusi ini akan menjadi 84 byte.

Penjelasan + tidak dikumpulkan:

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

Contoh:

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

Disimpan 2 byte berkat Geobits!

CJam, 24 byte

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

Uji di sini.

Penjelasan

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.

Untuk informasi lebih lanjut tentang mengapa #dapat digunakan untuk memeriksa ketimpangan string, lihat tip ini .

Haskell, 66 53 byte

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

Contoh penggunaan:

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

Clojure, 94 byte

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

Ini adalah upaya pertama saya untuk kode golf, jadi tolong beri tahu saya jika saya melakukan sesuatu yang salah.

Dengan beberapa ruang:

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

Rekursi sederhana dari fungsi bagian dalam. Dibutuhkan dua argumen, bilangan bulat %1dan indeks %2. Jika%1 palindrom, indeks akan dikembalikan. Jika tidak, fungsi memanggil dirinya sendiri dengan jumlah dan indeks yang ditambahkan. Fungsi luar menginisialisasi indeks dengan nol.

Sebuah sampel:

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 byte

Bukan bahasa. Masih asik.

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

Cukup mudah, selain hack berbasis regex yang rumit saya gunakan untuk membalikkan string.

Ruby, 44

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

Membutuhkan Ruby 1.9 atau lebih tinggi untuk ->sintaks lambda.