Каждое положительное целое число может быть выражено как сумма не более трех палиндромных положительных чисел в любом основании b ≥5.   Cilleruelo и др., 2017

Положительное целое число является палиндромным в данной базе, если его представление в этой базе без ведущих нулей читает то же самое в обратном направлении. Далее будет рассматриваться только основание b = 10.

Разложение как сумма палиндромных чисел не является уникальным . Например, 5может быть выражен непосредственно как 5или как сумма 2, 3. Аналогично, 132может быть разложен как 44, 44, 44или как 121, 11.

Соревнование

Учитывая положительное целое число, произведите его разложение суммы на три или меньше положительных целых числа, которые являются палиндромными в основании 10.

Дополнительные правила

• Используемый алгоритм должен работать для произвольно больших входов. Однако это допустимо, если программа ограничена памятью, временем или типом данных.

• Ввод и вывод могут быть приняты любым разумным способом . Формат ввода и вывода, как обычно, гибкий.

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

• Программы или функции разрешены на любом языке программирования . Стандартные лазейки запрещены.

• Самый короткий код в байтах побеждает.

Примеры

Поскольку входные данные могут иметь много декомпозиций, это скорее примеры, чем тестовые случаи. Каждое разложение показано на отдельной строке.

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

Брахилог , 7 байт

~+ℕᵐ.↔ᵐ

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

Удивительно не так медленно.

объяснение

(?)~+  .          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 байт

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

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

Желе , 12 10 9 8 байт

ŒṗDfU$ṪḌ

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

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

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

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]

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

Распечатывает список списков, каждый из которых является решением. Род спас 9 байтов.

JavaScript (ES6), 115 ... 84 83 байта

Всегда возвращает массив из трех элементов, где неиспользуемые записи дополняются нулями.

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

Контрольные примеры

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 байтов, 145 байтов

Спасибо Джузеппе за игру в гольф с 19 байтами

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

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

объяснение

В R нет собственного способа обращения строк, и многие строковые операции по умолчанию не работают с числами. Итак, сначала мы преобразуем ряд положительных целых чисел (плюс 0) в символы.

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

Далее я хочу проверить все группы из трех (здесь, где 0 важны), к счастью, R имеет встроенную функцию комбинации, которая возвращает матрицу, каждый столбец в комбинации.

Я применяю colSumsфункцию к матрице и сохраняю только те элементы, которые соответствуют поставленной цели.

Наконец, поскольку есть два 0, любой набор из двух натуральных чисел будет продублирован, поэтому я использую уникальную функцию для столбцов.

Выходные данные представляют собой матрицу, в которой каждый столбец представляет собой набор положительных, паллиндромных целых чисел, которые суммируются с целевым значением. Это ленивый и возвращает 0, когда используется менее 3 элементов.

Желе , 14 байт

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

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

Очень, очень неэффективно.

Желе , 17 байт

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

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

-6 байт благодаря HyperNeutrino.

Выводит все пути. Однако вывод состоит из нескольких дубликатов.

Ом v2 , 13 12 10 байт

#Dð*3ç⁇Σ³E

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

Mathematica, 49 байтов

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

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

возвращает все решения

-2 ~ MartinEnder ~ байтов

Haskell , 90 86 79 байтов

-7 байт благодаря Лайкони!

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

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

Возвращает список всех решений с некоторым дублированием.

Java (OpenJDK 8) , 185 байт

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

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

Удалите 1 байт из TIO, чтобы получить правильную сумму, потому что представление не содержит ;после лямбды.

Протон , 117 байт

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]

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

Выводит решение

Pyth ,  16 12  10 байт

ef_I#`MT./

Попробуй это здесь!

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

ef_I # `MT. / ~ Полная программа.

        ./ ~ Целочисленные разделы.
 f ~ Фильтр с переменной T.
     `MT ~ Отобразить каждый элемент T в строковое представление.
    # ~ Фильтр.
  _I ~ Является ли палиндром? (т.е. инвариант по обратному?)
e ~ Получить последний элемент.

05AB1E , 17 байт

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

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

Выводит результат в три списка следующим образом:

• Палиндромные списки длиной 1 (исходное число IFF это палиндромные).

• Палиндромные списки длины 2.

• Палиндромные списки длины 3.

Аксиома, 900 байт

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

тестовый код

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

Если этот код должен разложить число X в 1,2,3-палиндроме, то, что делает этот код, он пытается около палиндрома N <X и разложить XN в 2-палиндроме; если это разложение XN имеет успех, верните 3 найденных палиндрома; если это не удается, попробуйте предыдущий палиндром G <N <X и попробуйте разложить XG на 2 палиндрома и т. д. Код Ungolf (но возможно некоторая ошибка)

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

Результаты:

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

Печатает парни, но они не забанены

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

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

APL (Дьялог) , 51 байт

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

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

05AB1E , 8 байтов

ÅœR.ΔDíQ

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

Объяснение:

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

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

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

• grep { $_ eq .flip }, 1 .. $_ создает список всех палиндромных чисел от 1 до введенного числа.
• 3 Rxx повторяет этот список три раза.
• [X]сокращает этот список списков с помощью оператора перекрестных произведений X, в результате чего получается список всех трех наборов чисел палиндроминов от 1 до входного числа.
• first *.sum == $_ находит первый такой 3-х кортеж, который суммирует с входным числом.

Python 3 , 106 байт

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]

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

В ссылке TIO я использовал более быструю (но на 1 байт более длинную версию), которая берет первый действительный результат в качестве генератора, а не собирала весь список возможных комбинаций и брала первую.

Рубин , 84 байта

Составляет список всех возможных комбинаций из 3 палиндромов от 0 до n, находит первую, чья сумма совпадает, затем обрезает нули.

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

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

Добавить ++ , 62 байта

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

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

~ 50 байтов в гольфе при написании объяснения. Определяет лямбда-функцию, которая возвращает список списков, содержащих решения.

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

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

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

Следующий раздел можно разделить на три части:

BcB]
Gd‽k
dG‽k€bF

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

D,k,@@*,

Эта функция в принципе ничего не делает. Он получает два аргумента и упаковывает их в массив. Тем не менее, стол быстро, ‽это магический трюк здесь. Он принимает два списка и генерирует каждую пару элементов между этими двумя списками. Так [1 2 3]и [4 5 6]получится [[1 4] [1 5] [1 6] [2 4] [2 5] [2 6] [3 4] [3 5] [3 6]]. Затем он принимает свой функциональный аргумент (в данном случае k) и запускает эту функцию для каждой пары, которая в этом случае просто возвращает пары как есть.

$A$€bF

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