Yo boy, faut-il résumer

67

Chaque entier positif peut être exprimé par la somme d'au plus trois entiers positifs palindromiques dans toute base b ≥5.   Cilleruelo et al., 2017

Un entier positif est palindrome dans une base donnée si sa représentation dans cette base, sans zéros non significatifs, lit la même chose en arrière. Dans ce qui suit, seule la base b = 10 sera considérée.

La décomposition en tant que somme de nombres palindromiques n'est pas unique . Par exemple, 5peut être exprimé directement sous forme de 5, ou sous forme de la somme de 2, 3. De même, 132peut être décomposé comme 44, 44, 44ou comme 121, 11.

Le défi

Avec un entier positif, produisez sa décomposition en trois entiers positifs ou moins qui sont palindromiques en base 10.

Règles supplémentaires

  • L'algorithme utilisé devrait fonctionner pour des entrées arbitrairement grandes. Cependant, il est acceptable que le programme soit limité par des restrictions de mémoire, de temps ou de type de données.

  • L'entrée et la sortie peuvent être prises par n'importe quel moyen raisonnable . Le format d'entrée et de sortie est flexible comme d'habitude.

  • Vous pouvez choisir de produire une ou plusieurs décompositions valides pour chaque entrée, à condition que le format de sortie ne soit pas ambigu.

  • Les programmes ou fonctions sont autorisés, dans n'importe quel langage de programmation . Les failles standard sont interdites.

  • Le code le plus court en octets gagne.

Exemples

Puisqu'une entrée peut avoir plusieurs décompositions, il s'agit d'exemples plutôt que de cas de test. Chaque décomposition est affichée sur une ligne différente.

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
Luis Mendo
la source
32
mmm, jeu de mots dans le titre
Erik the Outgolfer
Je me demande: y a-t-il un entier qui doit être composé en deux palindromes? Cela ferait un cas de test intéressant (sinon, les golfeurs peuvent utiliser ce fait et seulement vérifier k=1et k=3.)
Lynn
@ Lynn semble "peu probable", car il se trouve qu'il y a pas mal de décompositions pour chaque entrée. Mais comme nous le savons, l'intuition en maths peut être tellement trompeuse ...
Luis Mendo
1
@Lynn Si vous autorisez k=1(comme dans le numéro d'origine est déjà un palindrome), cela signifie que vous supposez que les 2 autres nombres sont tous les deux égaux à 0. Donc, si 0 est acceptable comme l'un des nombres, tout nombre devant être effectué with k=2fonctionnerait aussi k=3si l'un des trois nombres est 0.
Darrel Hoffman
Je ne pense pas qu'il y ait des nombres qui peuvent SEULEMENT être exprimés sous la forme d'une somme de 2. Par conséquent, vous pouvez simplement couvrir les cas 3 et 1 et ignorer 2.
Urne Magic Octopus

Réponses:

19

Brachylog , 7 octets

~+ℕᵐ.↔ᵐ

Essayez-le en ligne!

Étonnamment, pas si lent.

Explication

(?)~+  .          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
Fataliser
la source
2
Qu'y a-t-il avec le hasard .dans l'explication, et le (.)? Je ne connais pas vraiment Brachylog.
Urne magique Octopus
3
@MagicOctopusUrn .est la variable de sortie. ~+, ℕᵐet ↔ᵐsont des prédicats qui ont une variable gauche et droite. La duplication de ceux-ci .indique simplement que la sortie est directement impliquée dans chacun de ces 3 appels de prédicats. La dernière (.)est ici pour montrer que la variable de sortie est implicitement la dernière variable du programme. Par conséquent, la dernière relation énoncée est réellement .↔ᵐ.ce qui signifie "l'inverse de la correspondance sur les résultats de sortie dans la sortie" .
Fataliser
Très bien enfin, l'entrée pourrait être> 10000
RosLuP
9

Python 2 , 82 79 octets

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

Essayez-le en ligne!

Dennis
la source
8

Jelly , 12 10 9 8 octets

ŒṗDfU$ṪḌ

Essayez-le en ligne!

Comment ça fonctionne

Œṗ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.
Dennis
la source
5
Je voulais juste soumettre une solution avec environ 140 octets, puis je vois 8 octets et je me dis: "Non, je ne vais pas poster le mien".
YU NO WORK
15
Comparer les scores entre les langues n'a pas beaucoup de sens. J'ai posté un Python répondre moi - même, non pas parce qu'il a une chance de battre cette réponse, mais parce qu'il est le plus court Python réponse que je peux penser.
Dennis
8

Python 2 , 117 octets

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]

Essayez-le en ligne!

Imprime une liste de listes, chacune d’elles constituant une solution. Rod a enregistré 9 octets.

Lynn
la source
-9 octets commutant pour fonctionner, remplacés cpar des soustractions et utilisantfilter
Rod
1
@Rod Merci! filter(Nonem'a frappé aussi pendant que je préparais le dîner, haha. c → n-a-bis cool :)
Lynn
7

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

Retourne toujours un tableau à trois éléments, où les entrées non utilisées sont complétées par des zéros.

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

Cas de test

Arnauld
la source
6

R, 126 octets 145 octets

Merci à Giuseppe pour le golf de 19 octets

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

Essayez-le en ligne!

Explication

R n'a pas de méthode native pour inverser les chaînes et de nombreuses opérations sur les chaînes par défaut ne fonctionnent pas sur les nombres. Nous convertissons donc d'abord la série d'entiers positifs (plus 0) en caractères.

Ensuite, nous produisons un vecteur de 0 et tous les palindromes. L'inversion de chaîne nécessite de scinder chaque nombre en caractères, d'inverser l'ordre du vecteur et de les recoller sans laisser d'espace.

Ensuite, je veux vérifier tous les groupes de trois (voici où les 0 sont importants), heureusement, R possède une fonction de combinaison intégrée qui renvoie une matrice, chaque colonne étant une combinaison.

J'applique la colSumsfonction à la matrice et ne conserve que les éléments qui correspondent à la cible fournie.

Enfin, comme il y a deux 0, tout ensemble de deux entiers positifs sera dupliqué et j'utilise une fonction unique sur les colonnes.

La sortie est une matrice où chaque colonne est un ensemble d’entiers positifs, pallindromiques, dont la somme correspond à la valeur cible. Il est paresseux et renvoie des 0 lorsque moins de 3 éléments sont utilisés.

marque
la source
1
128 octets . +1, bien que, bonne utilisation de Mapgénérer des palindromes!
Giuseppe
oups, trouvé un 126 byter
Giuseppe
4

Gelée , 14 octets

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

Essayez-le en ligne!

Très, très inefficace.

Erik l'Outgolfeur
la source
Cela semble trop lent, même si la cible est la longueur du code, pour moi ce n'est pas seulement la longueur
RosLuP
@RosLuP Ici, votre objectif n'est pas de garder le code efficace, mais votre objectif est de raccourcir le code autant que possible. Cela doit fonctionner en théorie , pas nécessairement en pratique, car il s’agit d’un défi code-golf , et non d’un défi code-golf restreint ou d’ un temps limité .
Erik the Outgolfer
4

Gelée , 17 octets

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

Essayez-le en ligne!

-6 octets grâce à HyperNeutrino.

Sorties de toutes les manières. Cependant, le résultat consiste en des doublons.

utilisateur202729
la source
1
Il y a un is palindromelol intégré
HyperNeutrino
De plus, si vous utilisez une plage normale (surélevée), vous pouvez supprimer vos 4 derniers octets
HyperNeutrino
15 octets
caird coinheringaahing
@cairdcoinheringaahing Still ne peut battre ni Dennis ni Erik. Quoi qu'il en soit je vais déchiffrer tronquée URL Base64-dégonflage-comprimé?
user202729
@ user202729 Hein, ne doit pas avoir copié le lien correctement. Le code étaitRŒḂÐfṗ3R¤YS⁼¥Ðf
Caird coinheringaahing
4

Mathematica, 49 octets

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

Essayez-le en ligne!

renvoie toutes les solutions

-2 ~ MartinEnder ~ octets

J42161217
la source
#~IntegerPartitions~3~Select~AllTrue@PalindromeQ&, Je pense?
Martin Ender
3

Haskell , 90 86 79 octets

-7 octets grâce à Laikoni!

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

Essayez-le en ligne!

Renvoie une liste de toutes les solutions avec des doublons.

H.PWiz
la source
79 octets avec mapMet déclarant f=filter: Essayez-le en ligne!
Laikoni
3

Java (OpenJDK 8) , 185 octets

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

Essayez-le en ligne!

Supprimez 1 octet de TIO pour obtenir le montant correct, car la soumission ne contient pas ;après le lambda.

Olivier Grégoire
la source
À mon avis, cette solution est meilleure que toutes les autres solutions proposées jusqu'à présent
RosLuP
@RosLuP Pourquoi, si je puis me permettre?
Olivier Grégoire
Parce que enfin donner des réponses pour entrée> 500000 (si je me souviens bien)
RosLuP
Proposer au i++<--jlieu de++i<=--j
ceilingcat
2

Proton , 117 octets

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]

Essayez-le en ligne!

Sortie d'une solution

HyperNeutrino
la source
920 en entrée ne pas retourner la sortie en 1 min en tio ... Je ne parle pas de 364757698688 mais seulement 920
RosLuP
1
@RosLuP Cela n'a pas d'importance. L'efficacité n'est pas une chose importante dans le code-golf. Cela fonctionnera théoriquement pour toutes les tailles d'entrées, de sorte que cela n'a pas d'importance; donné assez de temps, il donnera la sortie correcte pour 920.
HyperNeutrino
2

Pyth ,  16 12  10 octets

ef_I#`MT./

Essayez-le ici!

Comment ça fonctionne

ef_I # `MT. / ~ Programme complet.

        ./ ~ Partitions entières.
 f ~ Filtre avec une variable T.
     `MT ~ Mappe chaque élément de T en une représentation sous forme de chaîne.
    # ~ Filtre.
  _I ~ est palindrome? (c.-à-d. invariant sur l'envers?)
e ~ Obtenir le dernier élément.
M. Xcoder
la source
2

05AB1E , 17 octets

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

Essayez-le en ligne!


Affiche le résultat dans trois listes comme suit:

  • Listes palindromiques de longueur 1 (le nombre original IFF est palindromique).

  • Listes palindromiques de longueur 2.

  • Listes palindromiques de longueur 3.

Urne Magique De Pieuvre
la source
2

Axiome, 900 octets

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

code de test

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

Si ce code doit décomposer le nombre X en 1,2,3 palindrome, il essaye près du palindrome N <X et décompose XN en 2 palindrome; si cette décomposition de XN a réussi, renvoyer 3 palindrome trouvé; si cela échoue, essayez le palindrome précédent G <N <X et essayez de décomposer XG en 2 palindromes, etc.

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

résultats:

(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
RosLuP
la source
1

Java (OpenJDK 8) , 605 octets

Imprime des dupes mais elles ne sont pas bannies

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

Essayez-le en ligne!

Roberto Graham
la source
1

05AB1E , 8 octets

ÅœR.ΔDíQ

Essayez-le en ligne!

Explication:

Ŝ          # 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
Grimmy
la source
1

Perl 6 , 51 octets

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

Essayez-le en ligne!

  • grep { $_ eq .flip }, 1 .. $_ produit une liste de tous les nombres palindromiques de 1 au nombre entré.
  • 3 Rxx reproduit cette liste trois fois.
  • [X] réduit cette liste de listes avec l'opérateur multi-produit X , résultant en une liste de tous les 3-uplets de nombres palindrominc de 1 au nombre entré.
  • first *.sum == $_ trouve le premier triplet de ce type qui correspond au nombre saisi.
Sean
la source
Vous pouvez sauvegarder un octet en n’inversant pas le fichier xx 3.
Jo King
1

Python 3 , 106 octets

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]

Essayez-le en ligne!

Dans le lien TIO, j'ai utilisé une version plus rapide (mais une version plus longue d'un octet) prenant le premier résultat valide en tant que générateur, plutôt que de construire la liste complète des combinaisons possibles et de prendre le premier.

Matthew Jensen
la source
0

Ruby , 84 octets

Construit une liste de toutes les combinaisons possibles de 3 palindromes de 0 à n, trouve le premier dont la somme correspond, puis élague les zéros.

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

Essayez-le en ligne!

Valeur d'encre
la source
0

Ajouter ++ , 62 octets

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

Essayez-le en ligne!

~ 50 octets joués au golf lors de la rédaction d'une explication. Définit une fonction lambda qui renvoie une liste de listes contenant les solutions.

Comment ça fonctionne

1,231nn .

1,2,...,ngRÞggUNE pour plus tard.

La section suivante peut être divisée en trois autres parties:

BcB]
Gd‽k
dG‽k€bF

UNE[1 2 3 4 ...][[1] [2] [3] [4] ... ]UNEk

D,k,@@*,

Cette fonction ne fait fondamentalement rien. Il reçoit deux arguments et les encapsule dans un tableau. Cependant, la table rapide, est le tour de magie ici. Il faut deux listes et génère chaque paire d'éléments entre ces deux listes. Donc [1 2 3]et [4 5 6]génère [[1 4] [1 5] [1 6] [2 4] [2 5] [2 6] [3 4] [3 5] [3 6]]. Il prend ensuite son argument fonctionnel (dans ce cask ) et exécute cette fonction sur chaque paire, ce qui, dans ce cas, renvoie simplement les paires telles quelles.

UNE€bF

1,23nln

caird coinheringaahing
la source