Yo chico, debe resumir

67

Cada entero positivo puede expresarse como la suma de como máximo tres enteros positivos palindrómicos en cualquier base b ≥5.   Cilleruelo et al., 2017

Un entero positivo es palindrómico en una base dada si su representación en esa base, sin ceros a la izquierda, lee lo mismo al revés. A continuación, solo se considerará la base b = 10.

La descomposición como una suma de números palindrómicos no es única . Por ejemplo, 5se puede expresar directamente como 5, o como la suma de 2, 3. Del mismo modo, 132se puede descomponer como 44, 44, 44o como 121, 11.

El reto

Dado un entero positivo, produce su descomposición de suma en tres o menos enteros positivos que son palindrómicos en la base 10.

Reglas adicionales

  • El algoritmo utilizado debería funcionar para entradas arbitrariamente grandes. Sin embargo, es aceptable si el programa está limitado por restricciones de memoria, tiempo o tipo de datos.

  • La entrada y la salida se pueden tomar por cualquier medio razonable . El formato de entrada y salida es flexible como de costumbre.

  • Puede elegir producir una o más descomposiciones válidas para cada entrada, siempre que el formato de salida sea inequívoco.

  • Se permiten programas o funciones , en cualquier lenguaje de programación . Las lagunas estándar están prohibidas.

  • El código más corto en bytes gana.

Ejemplos

Como una entrada puede tener muchas descomposiciones, estos son ejemplos en lugar de casos de prueba. Cada descomposición se muestra en una línea diferente.

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
fuente
32
mmm, juego de palabras en el título
Erik the Outgolfer
Me pregunto: ¿hay algún número entero que deba estar compuesto en dos palíndromos? Esto sería un buen caso de prueba (si no, oye, los golfistas pueden usar este hecho y solo verificar k=1y k=3.)
Lynn
@Lynn parece "poco probable", ya que hay bastantes descomposiciones para cada entrada. Pero como sabemos, la intuición en matemáticas puede ser muy engañosa ...
Luis Mendo
1
@ Lynn Si está permitiendo k=1(como en el número original ya es un palíndromo), eso significa que está asumiendo que los otros 2 números son ambos 0. Entonces, si 0 es aceptable como uno de los números, cualquier número que deba hacerse con k=2también funcionaría k=3si uno de los tres números es 0.
Darrel Hoffman
No creo que haya ningún número que SOLO pueda expresarse como una suma de 2. Por lo tanto, puede cubrir el caso 3 y 1 e ignorar 2.
Urna de pulpo mágica

Respuestas:

19

Brachylog , 7 bytes

~+ℕᵐ.↔ᵐ

Pruébalo en línea!

Sorprendentemente no tan lento.

Explicación

(?)~+  .          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
Fatalizar
fuente
2
¿Qué pasa con el azar .en la explicación y el (.)? Realmente no conozco Brachylog.
Urna mágica del pulpo
3
@MagicOctopusUrn .es la variable de salida. ~+, ℕᵐy ↔ᵐson predicados que tienen una variable izquierda y derecha. La duplicación de esos .simplemente indica que la salida está involucrada directamente en cada una de esas 3 llamadas predicadas. La final (.)está aquí para mostrar que la variable de salida es implícitamente la última variable del programa. Por lo tanto, la última relación establecida es realmente lo .↔ᵐ.que significa "mapeo inverso en los resultados de salida en la salida" .
Fatalize
Muy bueno, por fin, la entrada podría ser> 10000
RosLuP
8

Jalea , 12 10 9 8 bytes

ŒṗDfU$ṪḌ

Pruébalo en línea!

Cómo funciona

Œṗ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
fuente
55
Solo quería enviar una solución con ~ 140 bytes, luego veo 8 bytes y digo: "No, no voy a publicar la mía".
NO TRABAJAS
15
Comparar puntajes entre idiomas no tiene sentido. He publicado una respuesta de Python , no porque tenga la oportunidad de superar esta respuesta, sino porque es la respuesta de Python más corta que se me ocurre.
Dennis
8

Python 2 , 117 bytes

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]

Pruébalo en línea!

Imprime una lista de listas, cada una de las cuales es una solución. Rod ahorró 9 bytes.

Lynn
fuente
-9 bytes cambiando a función, reemplazando ccon sustracciones y usandofilter
Rod
1
@ Rod ¡Gracias! filter(Nonetambién me golpeó mientras preparaba la cena, jaja. c → n-a-bes genial :)
Lynn
7

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

Siempre devuelve una matriz de tres elementos, donde las entradas no utilizadas se rellenan con ceros.

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

Casos de prueba

Arnauld
fuente
6

R, 126 bytes 145 bytes

Gracias a Giuseppe por jugar golf en 19 bytes

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

Pruébalo en línea!

Explicación

R no tiene una forma nativa de revertir cadenas y muchas operaciones de cadena predeterminadas no funcionan en números. Entonces, primero convertimos la serie de enteros positivos (más 0) en caracteres.

A continuación, producimos un vector de 0 y todos los palíndromos. La inversión de la cadena requiere dividir cada número por caracteres, revertir el orden del vector y pegarlos nuevamente sin espacios.

A continuación, quiero verificar todos los grupos de tres (aquí es donde los 0 son importantes), afortunadamente R tiene una función de combinación incorporada que devuelve una matriz, cada columna en una combinación.

Aplico la colSumsfunción a la matriz y mantengo solo los elementos que son iguales al objetivo suministrado.

Finalmente, debido a que hay dos ceros, cualquier conjunto de dos enteros positivos se duplicará, por lo que utilizo una función única en las columnas.

La salida es una matriz donde cada columna es un conjunto de enteros positivos y palíndromos que suman el valor objetivo. Es vago y devuelve 0 cuando se usan menos de 3 elementos.

marca
fuente
1
128 bytes . ¡+1, sin embargo, es un buen uso Mappara generar palíndromos!
Giuseppe
Uy, encontré un byter 126
Giuseppe
4

Jalea , 14 bytes

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

Pruébalo en línea!

Muy, muy ineficiente.

Erik el Outgolfer
fuente
Parece demasiado lento, incluso si el objetivo es la longitud del código, para mí no es solo la longitud
RosLuP
@RosLuP Aquí no tiene como objetivo mantener el código eficiente, aquí tiene como objetivo acortar el código tanto como sea posible. Tiene que funcionar en teoría , no necesariamente en la práctica, ya que este es un desafío de código de golf , no un desafío de código restringido de complejidad compleja o código de golf de tiempo restringido .
Erik the Outgolfer
4

Jalea , 17 bytes

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

Pruébalo en línea!

-6 bytes gracias a HyperNeutrino.

Salidas de todas las formas. Sin embargo, la salida consta de algunos duplicados.

usuario202729
fuente
1
Hay un is palindromelol incorporado
HyperNeutrino
Además, si usa el rango normal (elevado), puede eliminar sus últimos 4 bytes
HyperNeutrino
15 bytes
caird coinheringaahing
@cairdcoinheringaahing Aún no puede vencer a Dennis ni a Erik. De todos modos, ¿voy a descifrar la URL truncada , codificada en Base64, codificada y comprimida?
user202729
@ user202729 Huh, no debe haber copiado el enlace correctamente. El código eraRŒḂÐfṗ3R¤YS⁼¥Ðf
caird coinheringaahing
4

Mathematica, 49 bytes

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

Pruébalo en línea!

devuelve todas las soluciones

-2 ~ MartinEnder ~ bytes

J42161217
fuente
#~IntegerPartitions~3~Select~AllTrue@PalindromeQ&, ¿Yo creo que?
Martin Ender
3

Haskell , 90 86 79 bytes

-7 bytes gracias a Laikoni!

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

Pruébalo en línea!

Devuelve una lista de todas las soluciones con alguna duplicación.

H.PWiz
fuente
79 bytes con mapMy declarando f=filter: ¡ Pruébelo en línea!
Laikoni
3

Java (OpenJDK 8) , 185 bytes

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

Pruébalo en línea!

Elimine 1 byte de TIO para obtener la cantidad correcta porque el envío no contiene el ; después de lambda.

Olivier Grégoire
fuente
En mi opinión, esto es mejor que cualquier otra solución publicada hasta ahora
RosLuP
@RosLuP ¿Por qué es eso, si puedo preguntar?
Olivier Grégoire
Porque por fin dar respuestas para entrada> 500000 (si no recuerdo
mal
Sugerir en i++<--jlugar de++i<=--j
ceilingcat
2

Protón , 117 bytes

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]

Pruébalo en línea!

Produce una solución

Hiperneutrino
fuente
920 como entrada no devuelve la salida en 1 minuto en tio ... No hablo de 364757698688 sino solo 920
RosLuP
1
@RosLuP Eso no importa. La eficiencia no es una cosa importante en el golf de código. Teóricamente funcionará para todos los tamaños de entrada, por lo que no importa; dado el tiempo suficiente, dará la salida correcta para 920.
HyperNeutrino
2

Pyth ,  16 12  10 bytes

ef_I#`MT./

Pruébalo aquí!

Cómo funciona

ef_I # `MT. / ~ Programa completo.

        ./ ~ Particiones enteras.
 f ~ Filtro con una variable T.
     `MT ~ Asigna cada elemento de T a una representación de cadena.
    # ~ Filtro.
  _I ~ ¿Es palíndromo? (es decir, ¿Invariante sobre el reverso?)
e ~ Obtener el último elemento.
Sr. Xcoder
fuente
2

05AB1E , 17 bytes

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

Pruébalo en línea!


Emite el resultado en tres listas de la siguiente manera:

  • Listas palindrómicas de longitud 1 (el número original IFF es palindrómico).

  • Listas palindrómicas de longitud 2.

  • Listas palindrómicas de longitud 3.

Urna de pulpo mágico
fuente
2

Axioma, 900 bytes

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

código de prueba

--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 este código tiene que descomponer el número X en 1,2,3 palíndromo, lo que hace este código es intentar cerca del palíndromo N <X y descomponer XN en 2 palíndromo; si esta descomposición de XN tiene éxito, devuelve 3 palíndromos encontrados; si falla, pruebe el palíndromo anterior G <N <X e intente descomponer XG en 2 palíndromes, etc. Código Ungolf (pero es posible que haya algún error)

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

resultados:

(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
fuente
1

Java (OpenJDK 8) , 605 bytes

Imprime engañados pero no están prohibidos 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]);}}}

Pruébalo en línea!

Roberto Graham
fuente
1

05AB1E , 8 bytes

ÅœR.ΔDíQ

Pruébalo en línea!

Explicación:

Ŝ          # 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
Mugriento
fuente
1

Perl 6 , 51 bytes

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

Pruébalo en línea!

  • grep { $_ eq .flip }, 1 .. $_ produce una lista de todos los números palindrómicos del 1 al número de entrada.
  • 3 Rxx replica esa lista tres veces.
  • [X]reduce esa lista de listas con el operador de productos cruzados X, lo que da como resultado una lista de todas las 3 tuplas de números de palindrominc del 1 al número de entrada.
  • first *.sum == $_ encuentra la primera de esas 3 tuplas que suma al número de entrada.
Sean
fuente
Puede guardar un byte al no invertir el xx 3.
Jo King
1

Python 3 , 106 bytes

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]

Pruébalo en línea!

En el enlace TIO utilicé una versión más rápida (pero de 1 byte más larga) que toma el primer resultado válido como generador, en lugar de construir la lista completa de combinaciones posibles y tomar la primera.

Matthew Jensen
fuente
0

Ruby , 84 bytes

Crea una lista de todas las combinaciones posibles de 3 palíndromos de 0 a n, encuentra la primera cuya suma coincide y luego elimina los ceros.

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

Pruébalo en línea!

Tinta de valor
fuente
0

Agregar ++ , 62 bytes

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

Pruébalo en línea!

~ 50 bytes de golf mientras escribía una explicación. Define una función lambda que devuelve una lista de listas que contienen las soluciones.

Cómo funciona

1,231nortenorte

1,2,...,nortegRÞggUNA

La siguiente sección se puede dividir en tres partes más:

BcB]
Gd‽k
dG‽k€bF

UNA[1 2 3 4 ...][[1] [2] [3] [4] ... ]UNAk

D,k,@@*,

Esta función básicamente no hace nada. Recibe dos argumentos y los envuelve en una matriz. Sin embargo, la tabla rápida es el truco de magia aquí. Toma dos listas y genera cada par de elementos entre esas dos listas. Entonces [1 2 3]y [4 5 6]genera [[1 4] [1 5] [1 6] [2 4] [2 5] [2 6] [3 4] [3 5] [3 6]]. Luego toma su argumento funcional (en este caso k) y ejecuta esa función sobre cada par, que, en este caso, simplemente devuelve los pares tal como están.

UNA€bF

1,23nortelnorte

caird coinheringaahing
fuente