Każda dodatnia liczba całkowita może być wyrażona jako suma co najwyżej trzech palindromicznych dodatnich liczb całkowitych w dowolnej zasadzie b ≥5.   Cilleruelo i in., 2017

Dodatnia liczba całkowita jest palindromiczna w danej bazie, jeśli jej reprezentacja w tej bazie bez zer wiodących odczytuje to samo wstecz. Poniżej rozważana będzie tylko podstawa b = 10.

Rozkład jako suma liczb palindromicznych nie jest unikalny . Na przykład 5można wyrazić bezpośrednio jako 5lub jako sumę 2, 3. Podobnie 132może być rozkładany jako 44, 44, 44lub jako 121, 11.

Wyzwanie

Biorąc pod uwagę dodatnią liczbę całkowitą, uzyskaj jej sumaryczny rozkład na trzy lub mniej dodatnich liczb całkowitych, które są palindromiczne w podstawie 10.

Dodatkowe zasady

• Zastosowany algorytm powinien działać dla dowolnie dużych danych wejściowych. Jest jednak dopuszczalne, jeśli program jest ograniczony ograniczeniami pamięci, czasu lub typu danych.

• Dane wejściowe i wyjściowe można przyjmować dowolnymi rozsądnymi środkami . Format wejściowy i wyjściowy jest elastyczny jak zwykle.

• Możesz wybrać tworzenie jednego lub więcej prawidłowych rozkładów dla każdego wejścia, o ile format wyjściowy jest jednoznaczny.

• Programy lub funkcje są dozwolone w dowolnym języku programowania . Standardowe luki są zabronione.

• Najkrótszy kod w bajtach wygrywa.

Przykłady

Ponieważ dane wejściowe mogą mieć wiele rozkładów, są to raczej przykłady niż przypadki testowe. Każdy rozkład jest pokazany w innym wierszu.

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

~+ℕᵐ.↔ᵐ

Wypróbuj online!

Zaskakująco nie tak wolno.

Wyjaśnienie

(?)~+  .          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 bajtów

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

Wypróbuj online!

Galaretka , 12 10 9 8 bajtów

ŒṗDfU$ṪḌ

Wypróbuj online!

Jak to działa

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

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]

Wypróbuj online!

Drukuje listę list, z których każda jest rozwiązaniem. Rod zaoszczędził 9 bajtów.

JavaScript (ES6), 115 ... 84 83 bajtów

Zawsze zwraca tablicę trzyelementową, w której nieużywane wpisy są uzupełniane zerami.

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

Przypadki testowe

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

Dzięki Giuseppe za grę w golfa z 19 bajtów

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

Wypróbuj online!

Wyjaśnienie

R nie ma natywnego sposobu odwracania łańcuchów i wiele domyślnych operacji na łańcuchach nie działa na liczbach. Najpierw konwertujemy ciąg dodatnich liczb całkowitych (plus 0) na znaki.

Następnie tworzymy wektor 0 i wszystkie palindromy. Odwrócenie ciągu wymaga podzielenia każdej liczby na znaki, odwrócenia kolejności wektora i wklejenia ich z powrotem bez odstępu.

Następnie chcę sprawdzić wszystkie trzy grupy (tutaj ważne są zera), na szczęście R ma wbudowaną funkcję kombinacji, która zwraca macierz, każda kolumna w kombinacji.

Stosuję tę colSumsfunkcję do macierzy i zachowuję tylko te elementy, które są równe podanemu celowi.

Wreszcie, ponieważ istnieją dwa zera, każdy zestaw dwóch dodatnich liczb całkowitych zostanie zduplikowany, więc używam unikalnej funkcji w kolumnach.

Dane wyjściowe to macierz, w której każda kolumna jest zbiorem dodatnich liczb całkowitych pallindromicznych, które sumują się do wartości docelowej. Jest leniwy i zwraca 0, gdy używanych jest mniej niż 3 elementy.

Galaretka , 14 bajtów

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

Wypróbuj online!

Bardzo, bardzo nieefektywny.

Galaretka , 17 bajtów

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

Wypróbuj online!

-6 bajtów dzięki HyperNeutrino.

Wysyła wszystkie sposoby. Jednak wynik składa się z niektórych duplikatów.

Ohm v2 , 13 12 10 bajtów

#Dð*3ç⁇Σ³E

Wypróbuj online!

Mathematica, 49 bajtów

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

Wypróbuj online!

zwraca wszystkie rozwiązania

-2 ~ MartinEnder ~ bajtów

Haskell , 90 86 79 bajtów

-7 bajtów dzięki Laikoni!

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

Wypróbuj online!

Zwraca listę wszystkich rozwiązań z pewną duplikacją.

Java (OpenJDK 8) , 185 bajtów

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

Wypróbuj online!

Usuń 1 bajt z TIO, aby uzyskać prawidłową kwotę, ponieważ przesłanie nie zawiera ;po lambda.

Proton , 117 bajtów

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]

Wypróbuj online!

Wyprowadza rozwiązanie

Pyt ,  16 12  10 bajtów

ef_I#`MT./

Wypróbuj tutaj!

Jak to działa

ef_I # `MT. / ~ Pełny program.

        ./ ~ Partycje całkowite.
 f ~ Filtruj ze zmienną T.
     `MT ~ Odwzoruj każdy element T na ciąg znaków.
    # ~ Filtruj.
  _I ~ Czy palindrom? (tzn. niezmiennik w stosunku do rewersu?)
e ~ Zdobądź ostatni element.

05AB1E , 17 bajtów

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

Wypróbuj online!

Powoduje wyświetlenie wyniku w trzech listach w następujący sposób:

• Listy palindromiczne o długości 1 (oryginalny numer IFF to palindromiczny).

• Listy palindromiczne o długości 2.

• Listy palindromiczne o długości 3.

Aksjomat, 900 bajtów

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);[])

kod testowy

--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]

Jeśli ten kod musi rozkładać liczbę X na 1,2,3 palindromie, co robi ten kod, próbuje spróbować w pobliżu palindromu N <X i rozkłada XN na 2 palindromie; jeśli ten rozkład XN zakończy się sukcesem, zwróć 3 palindrom; jeśli się nie powiedzie, wypróbuj poprzedni palindrom G <N <X i spróbuj rozłożyć XG na 2 palindrom itp. Kod Ungolfa (ale możliwe, że jest jakiś błąd)

 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
   []

wyniki:

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

Drukuje kopie, ale nie są zbanowani 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]);}}}

Wypróbuj online!

APL (Dyalog) , 51 bajtów

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

Wypróbuj online!

05AB1E , 8 bajtów

ÅœR.ΔDíQ

Wypróbuj online!

Wyjaśnienie:

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

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

Wypróbuj online!

• grep { $_ eq .flip }, 1 .. $_ tworzy listę wszystkich liczb palindromowych od 1 do liczby wejściowej.
• 3 Rxx replikuje tę listę trzy razy.
• [X]zmniejsza tę listę list za pomocą operatora krzyżowego produktu X, w wyniku czego powstaje lista wszystkich 3-krotek liczb palindrominc od 1 do liczby wejściowej.
• first *.sum == $_ znajduje pierwszą taką trójkę, która sumuje się do liczby wejściowej.

Python 3 , 106 bajtów

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]

Wypróbuj online!

W linku TIO użyłem szybszej (ale o 1 bajt dłuższej wersji), która bierze pierwszy poprawny wynik jako generator, zamiast budować całą listę możliwych kombinacji i brać pierwszą.

Rubinowy , 84 bajtów

Tworzy listę wszystkich możliwych kombinacji 3 palindromów od 0 do n, znajduje pierwszą, której suma pasuje, a następnie przycina zera.

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

Wypróbuj online!

Dodaj ++ , 62 bajty

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

Wypróbuj online!

~ 50 bajtów gry w golfa podczas pisania wyjaśnienia. Definiuje funkcję lambda, która zwraca listę list zawierających rozwiązania.

Jak to działa

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

$1, 2, ..., n$gRÞgg$A$ na później.

Kolejną sekcję można podzielić na trzy dalsze części:

BcB]
Gd‽k
dG‽k€bF

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

D,k,@@*,

Ta funkcja w zasadzie nic nie robi. Otrzymuje dwa argumenty i zawija je w tablicę. Jednak szybki stół ‽to magiczna sztuczka. Pobiera dwie listy i generuje każdą parę elementów między tymi dwiema listami. Tak [1 2 3]i [4 5 6]generuje [[1 4] [1 5] [1 6] [2 4] [2 5] [2 6] [3 4] [3 5] [3 6]]. Następnie przyjmuje argument funkcjonalny (w tym przypadkuk ) i uruchamia tę funkcję nad każdą parą, która w tym przypadku po prostu zwraca pary w niezmienionej postaci.

$A$€bF

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