Setiap bilangan bulat positif dapat dinyatakan sebagai jumlah dari paling banyak tiga bilangan bulat palindromik positif di setiap basis b ≥5.   Cilleruelo et al., 2017

Bilangan bulat positif adalah palindromik pada basis yang diberikan jika representasinya pada basis itu, tanpa nol di depan, membaca yang sama ke belakang. Berikut ini, hanya basis b = 10 yang akan dipertimbangkan.

Dekomposisi sebagai jumlah bilangan palindrom tidak unik . Misalnya, 5dapat dinyatakan secara langsung sebagai 5, atau sebagai jumlah 2, 3. Demikian pula, 132dapat diuraikan sebagai 44, 44, 44atau sebagai 121, 11.

Tantangan

Dengan bilangan bulat positif, hasilkan jumlah dekomposisi menjadi tiga atau lebih sedikit bilangan bulat positif yang palindromik pada basis 10.

Aturan tambahan

• Algoritma yang digunakan harus bekerja untuk input besar yang sewenang-wenang. Namun, dapat diterima jika program dibatasi oleh memori, waktu atau batasan tipe data.

• Input dan output dapat diambil dengan cara apa pun yang wajar . Format input dan output fleksibel seperti biasa.

• Anda dapat memilih untuk menghasilkan satu atau beberapa dekomposisi yang valid untuk setiap input, selama format output tidak ambigu.

• Program atau fungsi diizinkan, dalam bahasa pemrograman apa pun . Celah standar dilarang.

• Kode terpendek dalam byte menang.

Contohnya

Karena input dapat memiliki banyak dekomposisi, ini adalah contoh daripada kasus uji. Setiap dekomposisi ditampilkan pada garis yang berbeda.

Input  ->  Output

5     ->   5
           2, 3

15    ->   1, 3, 11
           9, 6

21    ->   11, 9, 1
           7, 7, 7

42    ->   22, 11, 9
           2, 7, 33

132   ->   44, 44, 44
           121, 11

345   ->   202, 44, 99
           2, 343

1022  ->   989, 33
           999, 22, 1

9265  ->   9229, 33, 3
           8338, 828, 99

Brachylog , 7 byte

~+ℕᵐ.↔ᵐ

Cobalah online!

Anehnya tidak begitu lambat.

Penjelasan

(?)~+  .          Output is equal to the Input when summed
     ℕᵐ.          Each element of the Output is a positive integer
       .↔ᵐ(.)     When reversing each element of the Output, we get the Output

Python 2 , 82 79 byte

f=lambda n:min([f(n-k)+[k]for k in range(1,n+1)if`k`==`k`[::-1]]or[[]],key=len)

Cobalah online!

Jelly , 12 10 9 8 byte

ŒṗDfU$ṪḌ

Cobalah online!

Bagaimana itu bekerja

ŒṗDfU$ṪḌ  Main link. Argument: n (integer)

Œṗ        Find all integer partitions of n.
  D       Convert each integer in each partition to base 10.
     $    Combine the two links to the left into a chain.
    U     Upend; reverse all arrays of decimal digits.
   f      Filter the original array by the upended one.
      Ṫ   Take the last element of the filtered array.
          This selects  the lexicographically smallest decomposition of those with
          the minimal amount of palindromes.
       Ḍ  Undecimal; convert all arrays of decimal digits to integers.

Python 2 , 117 byte

def f(n):p=[x for x in range(n+1)if`x`==`x`[::-1]];print[filter(None,[a,b,n-a-b])for a in p for b in p if n-a-b in p]

Cobalah online!

Mencetak daftar daftar, yang masing-masing merupakan solusi. Batang disimpan 9 byte.

JavaScript (ES6), 115 ... 84 83 byte

Selalu mengembalikan array tiga elemen, di mana entri yang tidak digunakan diisi dengan nol.

f=(n,b=a=0)=>(r=[b,a%=n,n-a-b]).some(a=>a-[...a+''].reverse().join``)?f(n,b+!a++):r

Uji kasus

f=(n,b=a=0)=>(r=[b,a%=n,n-a-b]).some(a=>a-[...a+''].reverse().join``)?f(n,b+!a++):r

console.log(JSON.stringify(f(5)))
console.log(JSON.stringify(f(15)))
console.log(JSON.stringify(f(21)))
console.log(JSON.stringify(f(42)))
console.log(JSON.stringify(f(132)))
console.log(JSON.stringify(f(345)))
console.log(JSON.stringify(f(1022)))
console.log(JSON.stringify(f(9265)))

R, 126 byte 145 byte

Terima kasih kepada Giuseppe untuk bermain golf 19 byte

function(n){a=paste(y<-0:n)
x=combn(c(0,y[a==Map(paste,Map(rev,strsplit(a,"")),collapse="")]),3)
unique(x[,colSums(x)==n],,2)}

Cobalah online!

Penjelasan

R tidak memiliki cara asli untuk membalikkan string dan banyak operasi string default tidak berfungsi pada angka. Jadi pertama-tama kita mengonversi rangkaian bilangan bulat positif (ditambah 0) ke karakter.

Selanjutnya kita menghasilkan vektor 0 dan semua palindrom. Pembalikan string membutuhkan pemisahan setiap angka dengan karakter, membalik urutan vektor dan menempelkannya kembali bersama tanpa celah.

Selanjutnya saya ingin memeriksa semua kelompok tiga (di sinilah 0s penting), untungnya R memiliki fungsi kombinasi built in yang mengembalikan matriks, setiap kolom dalam kombinasi.

Saya menerapkan colSumsfungsi ke matriks dan hanya menyimpan elemen yang sama dengan target yang disediakan.

Akhirnya, karena ada dua 0s, setiap himpunan dua bilangan bulat positif akan digandakan jadi saya menggunakan fungsi unik pada kolom.

Outputnya adalah matriks di mana setiap kolom adalah himpunan bilangan bulat pallindromic positif yang dijumlahkan ke nilai target. Itu malas dan mengembalikan 0 ketika kurang dari 3 elemen digunakan.

Jelly , 14 byte

L<4aŒḂ€Ạ
ŒṗÇÐf

Cobalah online!

Sangat, sangat tidak efisien.

Jelly , 17 byte

RŒḂÐfṗ3R¤YS⁼³$$Ðf

Cobalah online!

-6 byte berkat HyperNeutrino.

Keluaran semua cara. Namun output terdiri dari beberapa duplikat.

Ohm v2 , 13 12 10 byte

#Dð*3ç⁇Σ³E

Cobalah online!

Mathematica, 49 byte

#~IntegerPartitions~3~Select~AllTrue@PalindromeQ&

Cobalah online!

mengembalikan semua solusi

-2 ~ MartinEnder ~ byte

Haskell , 90 86 79 byte

-7 byte terima kasih kepada Laikoni!

f=filter
h n=[f(>0)t|t<-mapM(\_->f(((==)<*>reverse).show)[0..n])"123",sum t==n]

Cobalah online!

Mengembalikan daftar semua solusi dengan duplikasi.

Java (OpenJDK 8) , 185 byte

n->{for(int i=0,j=n,k;++i<=--j;)if(p(i))for(k=0;k<=j-k;k++)if(p(k)&p(j-k))return new int[]{j-k,k,i};return n;}
boolean p(int n){return(""+n).equals(""+new StringBuffer(""+n).reverse());}

Cobalah online!

Hapus 1 byte dari TIO untuk mendapatkan jumlah yang benar karena pengiriman tidak mengandung ;after lambda.

Proton , 117 byte

a=>filter(l=>all(p==p[by-1]for p:map(str,l)),(k=[[i,a-i]for i:1..a-1])+sum([[[i,q,j-q]for q:1..j-1]for i,j:k],[]))[0]

Cobalah online!

Menghasilkan solusi

Pyth ,  16 12  10 byte

ef_I#`MT./

Coba di sini!

Bagaimana itu bekerja

ef_I # `MT. / ~ Program lengkap.

        ./ ~ Partisi Integer.
 f ~ Filter dengan variabel T.
     `MT ~ Petakan setiap elemen T ke representasi string.
    # ~ Filter.
  _I ~ Apakah palindrome? (Yaitu Invariant dari terbalik?)
e ~ Dapatkan elemen terakhir.

05AB1E , 17 byte

LʒÂQ}U4GXNãDO¹QÏ=

Cobalah online!

Keluarkan hasilnya dalam tiga daftar sebagai berikut:

• Daftar palindromik dengan panjang 1 (angka asli IFF adalah palindromik).

• Daftar panjang palindrom 2.

• Daftar panjang palindrom 3.

Aksioma, 900 byte

R(x)==>return x;p(r,a)==(n:=#(a::String);if r<0 then(a=0=>R a;n=1 or a=10^(n-1)=>R(a-1);a=10^(n-1)+1=>R(a-2));if r>0 then(n=1 and a<9=>R(a+1);a=10^n-1=>R(a+2));r=0 and n=1=>1;v:=a quo 10^(n quo 2);repeat(c:=v;w:=(n rem 2>0=>v quo 10;v);repeat(c:=10*c+w rem 10;w:=w quo 10;w=0=>break);r<0=>(c<a=>R c;v:=v-1);r>0=>(c>a=>R c;v:=v+1);R(c=a=>1;0));c)
b:List INT:=[];o:INT:=0
f(a:NNI):List INT==(free b,o;o:=p(-1,o);w:=0;c:=#b;if c>0 then w:=b.1;e:=a-o;e>10000000=>R[];if w<e then repeat(w:=p(1,w);w>e=>break;b:=cons(w,b));g:List INT:=[];for i in #b..1 by-1 repeat(b.i>e=>break;g:=cons(b.i,g));if o>e then g:=cons(o,g);n:=#g;for i in 1..n repeat(x:=g.i;x=a=>R[x];3*x<a=>break;for j in i..n repeat(y:=g.j;t:=x+y;t>a=>iterate;t=a=>R[x,y];t+y<a=>break;for k in j..n repeat(z:=t+g.k;z=a=>R[x,y,g.k];z<a=>break)));[])
D(a:NNI):List INT==(free o;p(0,a)=1=>[a];o:=a;for j in 1..10 repeat(t:=f(a);#t>0=>R t);[])

kode uji

--Lista random di n elmenti, casuali compresi tra "a" e "b"
randList(n:PI,a:INT,b:INT):List INT==
    r:List INT:=[]
    a>b =>r
    d:=1+b-a
    for i in 1..n repeat
          r:=concat(r,a+random(d)$INT)
    r

test()==
   a:=randList(20,1,12345678901234)
   [[i,D(i)] for i in a]

Jika kode ini harus mendekomposisi angka X dalam 1,2,3 palindrome, apa yang dilakukan kode ini, ia coba di dekat palindrom N <X dan mendekomposisi XN dalam 2 palindrom; jika dekomposisi XN ini berhasil mengembalikan 3 palindrome yang ditemukan; jika gagal, cobalah palindrome G <N <X sebelumnya dan coba dekomposisi XG dalam 2 palindrom dll. Hapus kode kode (tetapi ada kemungkinan bug)

 R(x)==>return x

-- se 'r'=0 ritorna 1 se 'a' e' palindrome altrimenti ritorna 0
-- se 'r'>0 ritorna la prossima palindrome >'a'
-- se 'r'<0 ritorna la prossima palindrome <'a'
p(r,a)==(n:=#(a::String);if r<0 then(a=0=>R a;n=1 or a=10^(n-1)=>R(a-1);a=10^(n-1)+1=>R(a-2));if r>0 then(n=1 and a<9=>R(a+1);a=10^n-1=>R(a+2));r=0 and n=1=>1;v:=a quo 10^(n quo 2);repeat(c:=v;w:=(n rem 2>0=>v quo 10;v);repeat(c:=10*c+w rem 10;w:=w quo 10;w=0=>break);r<0=>(c<a=>R c;v:=v-1);r>0=>(c>a=>R c;v:=v+1);R(c=a=>1;0));c)

b:List INT:=[]   -- the list of palindrome
o:INT:=0         -- the start value for search the first is a

--Decompose 'a' in 1 or 2 or 3 palindrome beginning with prev palindrome of o
--if error or fail return []
f(a:NNI):List INT==
    free b,o
    -- aggiustamento di o, come palindrome piu' piccola di o
    o:=p(-1,o)
    -- aggiustamento di b come l'insieme delle palindromi tra 1..a-o compresa
    w:=0;c:=#b
    if c>0 then w:=b.1 --in w la massima palindrome presente in b
    e:=a-o
    output["e=",e,"w=",w,"o=",o,"#b=",#b]
    e>10000000=>R[]   --impongo che la palindrome massima e' 10000000-1
    if w<e then       --se w<a-o aggiungere a b tutte le palindromi tra w+1..a-o
          repeat(w:=p(1,w);w>e=>break;b:=cons(w,b))
                      -- g e' l'insieme dei b palindromi tra 1..a-o,o
    g:List INT:=[];for i in #b..1 by-1 repeat(b.i>e=>break;g:=cons(b.i,g))
    if o>e then g:=cons(o,g)
    --output["g=",g,b]
    n:=#g
    for i in 1..n repeat
        x:=g.i
        x=a  =>R[x]
        3*x<a=>break
        for j in i..n repeat
           y:=g.j;t:=x+y
           t>a   =>iterate
           t=a   =>R[x,y]
           t+y<a =>break
           for k in j..n repeat
                z:=t+g.k
                z=a =>R[x,y,g.k]
                z<a =>break
    []

--Decompose 'a' in 1 or 2 or 3 palindrome
--if error or fail return []
dPal(a:NNI):List INT==
   free o
   p(0,a)=1=>[a]
   o:=a                  -- at start it is o=a
   for j in 1..10 repeat -- try 10 start values only
        t:=f(a)
        #t>0=>R t
   []

hasil:

(7) -> [[i,D(i)] for i in [5,15,21,42,132,345,1022,9265] ]
   (7)
   [[5,[5]], [15,[11,4]], [21,[11,9,1]], [42,[33,9]], [132,[131,1]],
    [345,[343,2]], [1022,[999,22,1]], [9265,[9229,33,3]]]
                                                      Type: List List Any
                                   Time: 0.02 (IN) + 0.02 (OT) = 0.03 sec
(8) -> test()
   (8)
   [[7497277417019,[7497276727947,624426,64646]],
    [11535896626131,[11535888853511,7738377,34243]],
    [2001104243257,[2001104011002,184481,47774]],
    [3218562606454,[3218561658123,927729,20602]],
    [6849377785598,[6849377739486,45254,858]],
    [375391595873,[375391193573,324423,77877]],
    [5358975936064,[5358975798535,136631,898]],
    [7167932760123,[7167932397617,324423,38083]],
    [11779002607051,[11779000097711,2420242,89098]],
    [320101573620,[320101101023,472274,323]],
    [5022244189542,[5022242422205,1766671,666]],
    [5182865851215,[5182864682815,1158511,9889]],
    [346627181013,[346626626643,485584,68786]],
    [9697093443342,[9697092907969,443344,92029]],
    [1885502599457,[1885502055881,542245,1331]], [10995589034484,[]],
    [1089930852241,[1089930399801,375573,76867]],
    [7614518487477,[7614518154167,246642,86668]],
    [11859876865045,[11859866895811,9968699,535]],
    [2309879870924,[2309879789032,81418,474]]]
                                                      Type: List List Any
      Time: 0.25 (IN) + 115.17 (EV) + 0.13 (OT) + 28.83 (GC) = 144.38 sec

Java (OpenJDK 8) , 605 byte

Mencetak dupes tetapi tidak diblokir afaik

a->{int i=0,j,k,r[]=new int[a-1];for(;i<a-1;r[i]=++i);for(i=0;i<a-1;i++){if(r[i]==a&(""+r[i]).equals(""+new StringBuffer(""+r[i]).reverse()))System.out.println(r[i]);for(j=0;j<a-1;j++){if(r[i]+r[j]==a&(""+r[i]).equals(""+new StringBuffer(""+r[i]).reverse())&(""+r[j]).equals(""+new StringBuffer(""+r[j]).reverse()))System.out.println(r[i]+" "+r[j]);for(k=0;k<a-1;k++)if(r[i]+r[j]+r[k]==a&(""+r[i]).equals(""+new StringBuffer(""+r[i]).reverse())&(""+r[j]).equals(""+new StringBuffer(""+r[j]).reverse())&(""+r[k]).equals(""+new StringBuffer(""+r[k]).reverse()))System.out.println(r[i]+" "+r[j]+" "+r[k]);}}}

Cobalah online!

APL (Dyalog) , 51 byte

{w/⍨⍵=+/¨w←(,y∘.,z),,(z←,∘.,⍨y),y←,x/⍨(⌽≡⊢)¨⍕¨x←⍳⍵}

Cobalah online!

05AB1E , 8 byte

ÅœR.ΔDíQ

Cobalah online!

Penjelasan:

Ŝ          # integer partitions of the input
  R         # reversed (puts the shortest ones first)
   .Δ       # find the first one that...
     D Q    # is equal to...
      í     # itself with each element reversed

Perl 6 , 51 byte

{first *.sum==$_,[X] 3 Rxx grep {$_ eq.flip},1..$_}

Cobalah online!

• grep { $_ eq .flip }, 1 .. $_ menghasilkan daftar semua nomor palindromic dari 1 ke nomor input.
• 3 Rxx mengulangi daftar itu tiga kali.
• [X]mengurangi daftar-daftar-itu dengan operator produk-silang X, menghasilkan daftar semua 3-tupel nomor palindrominc dari 1 hingga nomor input.
• first *.sum == $_ menemukan 3-tuple pertama yang jumlah ke nomor input.

Python 3 , 106 byte

lambda n:[(a,b,n-a-b)for a in range(n)for b in range(n)if all(f'{x}'==f'{x}'[::-1]for x in(a,b,n-a-b))][0]

Cobalah online!

Dalam tautan TIO saya menggunakan versi yang lebih cepat (tetapi versi 1 byte lebih lama) yang mengambil hasil valid pertama sebagai generator, daripada membangun seluruh daftar kombinasi yang mungkin dan mengambil yang pertama.

Ruby , 84 byte

Buat daftar semua kemungkinan kombinasi 3 palindrom dari 0 hingga n, temukan yang pertama yang jumlahnya cocok, lalu pangkas nol.

->n{a=(0..n).select{|x|x.to_s==x.to_s.reverse};a.product(a,a).find{|x|x.sum==n}-[0]}

Cobalah online!

Tambahkan ++ , 62 byte

D,g,@,BDdbR=
D,l,@@,$b+=
D,k,@@*,
L,RÞgdVBcB]Gd‽kdG‽k€bF++A$Þl

Cobalah online!

~ 50 byte golf saat menulis penjelasan. Menentukan fungsi lambda yang mengembalikan daftar daftar yang berisi solusi.

Bagaimana itu bekerja

$1, 2$$3$$1$$n$$n$

$1, 2, ..., n$gRÞgg$A$

Bagian selanjutnya dapat dibagi menjadi tiga bagian lebih lanjut:

BcB]
Gd‽k
dG‽k€bF

$A$[1 2 3 4 ...][[1] [2] [3] [4] ... ]$A$k

D,k,@@*,

Fungsi ini pada dasarnya tidak melakukan apa pun. Ia menerima dua argumen dan membungkusnya dalam sebuah array. Namun, tabel cepat, ‽adalah trik sulap di sini. Dibutuhkan dua daftar dan menghasilkan setiap pasangan elemen di antara kedua daftar itu. Jadi [1 2 3]dan [4 5 6]hasilkan [[1 4] [1 5] [1 6] [2 4] [2 5] [2 6] [3 4] [3 5] [3 6]]. Kemudian mengambil argumen fungsionalnya (dalam hal ini k) dan menjalankan fungsi tersebut di atas setiap pasangan, yang, dalam hal ini, hanya mengembalikan pasangan apa adanya.

$A$€bF

$1, 2$$3$$n$l$n$