Pocas operaciones hasta 100

15

Visión general

Dada una lista de dígitos, encuentre la menor cantidad de operaciones para hacer 100

Entrada

Una cadena de dígitos, que puede o no estar en orden numérico. El orden de los dígitos no se puede cambiar, sin embargo, se pueden agregar operadores más (+) o menos (-) entre cada uno para que la suma total sea igual a 100.

Salida

El número de operadores agregados, seguido de la secuencia completa de dígitos y operadores. Los dos pueden estar separados por un espacio, una pestaña o una nueva secuencia de línea.

Ejemplos

válido

Entrada: 123456789
Salida:3 123–45–67+89


Entrada no válida: 123456789
Salida:
6 1+2+34-5+67-8+9
(Hay formas de resolver esto con menos operaciones)

CyberJacob
fuente
Relacionado
Adám
¿Tenemos que usar todos los dígitos? ¿Solo podemos usar +y -? ¿Podemos suponer que siempre podremos hacer 100desde la entrada?
TheLethalCoder
66
Algunos casos de prueba más serían bienvenidos.
Arnauld
2
¿Puede confirmar que los signos no pueden anteponerse al primer dígito? Es decir, dada la entrada 299399, ¿ -299+399sería válido?
Luis Mendo
1
¿Es '0' un dígito? Por ejemplo, ¿es '10808' una entrada válida? ¿Es '1 108-08' una respuesta válida?
Chas Brown

Respuestas:

10

JavaScript (ES6), 153 176 bytes

EDITAR: en modo no estricto, JS interpreta las expresiones numéricas con prefijo 0 como octales (por ejemplo, 017se analiza como 15 en decimal). Esta es una versión fija que admite ceros a la izquierda.

let f =

s=>[...Array(3**(l=s.length,l-1))].map((_,n)=>m=eval((x=s.replace(/./g,(c,i)=>c+['','+','-'][o=(n/3**i|0)%3,j-=!o,o],j=l)).replace(/\b0+/g,' '))-100|j>m?m:(S=x,j),m=l)&&m+' '+S

console.log(f("123456789"))
console.log(f("20172117"))

Arnauld
fuente
Bien, ¿qué pasa con 20172117 como entrada?
mdahmoune
@LuisMendo En realidad, creo que la respuesta esperada es 2-017-2+117. Pero 017es una notación octal en JS, que da 15 en decimal. Entonces mi código actual solo se encuentra 2-0-17-2+117. Trataré de abordar ese problema más tarde hoy.
Arnauld
@Arnauld Ah, no había visto esa otra solución. Eliminando mi comentario
Luis Mendo
@mdahmoune Gracias por mencionar esto. Ahora arreglado.
Arnauld
3**(l=s.length,l-1)=>3**~-(l=s.length)
l4m2
5

MATL , 37 36 bytes

n'+-'OhZ^!t2\s&SZ)"G@!vXzU100=?@z3M.

El caso de prueba tarda unos 6 segundos en TIO.

Pruébalo en línea!

Cómo funciona

n        % Implicitly input a string. Number of elements, say k
'+-'     % Push this string
Oh       % Append char 0. This is treated like ' ' (space)
Z^       % Cartesian power of the three-char string '+- ' raised to k.
         % Gives a matrix where each row is a Cartesian k-tuple
!        % Transpose
t        % Duplicate
2\       % Modulo 2. This turns '+' and '-' into 1, and ' ' into 0
s        % Sum of each column: number of '+' and '-' symbols
&S       % Sort and push the indices of the sorting
Z)       % Apply as column indices. This sorts the columns (k-tuples)
         % by the number of '+' and '-' they contain
"        % For each column, i.e. each k-tuple formed by '+', '-' and ' '
  G      %   Push input string again
  @!     %   Push k-tuple as row vector (string)
  v      %   Concatenate vertically into a 2×k char array
  Xz     %   Remove space (and char 0). Gives a string as result. In this
         %   process, the 2×k array is linearized in column major order 
         %   (down, then across). So the '+' and '-' signs are between 
         %   digits of the input, or at the end
  U      %   Convert to number. This performs the operation determined by
         %   by the '+' and '-' signs and returns the result. A trailing
         %   '+' or '-' sign makes the input invalid, which causes an
         %   empty result
  100=   %   Is it equal to 100?
  ?      %   If so
    @    %     Push current k-tuple
    z    %     Number of nonzeros, i.e. of '+' and '-' signs
    3M   %     Push linearized string without spaces again
    .    %     Break for loop
         %   Implicit end
         % Implicit end
         % Implicitly dispplay stack
Luis Mendo
fuente
Genial, ¿qué pasa con 299399 como entrada?
mdahmoune
1
@mdahmoune 299399no tiene solución y, por lo tanto, no es una entrada válida (los operadores fueron especificados para ir "entre" los dígitos, esa entrada requeriría -299+399donde -no está entre los dígitos).
Jonathan Allan
@mdahmoune Si los signos solo se pueden insertar entre los dígitos (como dice el texto de desafío), creo que no hay solución. Si también pueden anteponerse al primer dígito, la solución es -299+399, y en ese caso necesito un pequeño cambio en mi código . Le pedí una aclaración al OP
Luis Mendo
También cabe destacar que si se pretendiera que fuera tanto antes como entre entonces, el ejemplo 123456789debería tener un recuento de operadores de 4no 3.
Jonathan Allan
@mdahmoune El OP ha confirmado que los signos solo pueden estar entre dígitos. Entonces, mi código es correcto y 299399es una entrada no válida porque, como el OP también ha aclarado, cada entrada debe tener al menos una solución
Luis Mendo
3

[Python 2], 164158 bytes

from itertools import*
f=lambda N:min((len(s)-len(N),s)for s in(''.join(sum(zip(N,p+('',)),()))for p in product(('+','-',''),repeat=len(N)-1))if eval(s)==100)

Pruébalo en línea!

Tome N como una cadena de dígitos; devuelve una tupla (numOps, expressionString).

Básicamente el mismo enfoque que otros; usa itertools.product para construir los "casos" individuales, por ejemplo, para N == '1322', un "caso" sería ('-','','+')y evaluaría '1-32 + 2'.

Lanza un ValueError si la entrada no es válida (pero creo que OP no garantizó entradas no válidas).

Chas Brown
fuente
3

PHP, 166 171 bytes

for(;$n<3**$e=strlen($x=$argn);eval("return $s;")-100?:$r[]=sprintf("%2d $s",strlen($s)-$e))for($i=0,$s="",$k=$n++;a&$c=$x[$i];$k/=3)$s.="+-"[$i++?$k%3:2].$c;echo min($r);

Ejecutar como tubería con -nRo probarlo en línea .

utiliza números formateados para ordenar los resultados ->
puede imprimir espacios en blanco iniciales (y puede fallar para la entrada con más de 99 dígitos; aumente el número %2dpara corregir).

no más de 10 dígitos, 161 bytes

for(;$n<3**$e=strlen($x=$argn);eval("return $s;")-100?:$r[]=(strlen($s)-$e)." $s")for($i=0,$s="",$k=$n++;a&$c=$x[$i];$k/=3)$s.="+-"[$i++?$k%3:2].$c;echo min($r);

Descompostura

for(;$n<3**$e=strlen($x=$argn); # loop $n up
    eval("return $s;")-100?:        # 2. evaluate term, if 100 then
                                    # prepend number of operations, add to results
        $r[]=sprintf("%2d $s",strlen($s)-$e)
)
                                # 1. create term
    for($i=0,$s="",$k=$n++;         # init variables, increment $n
        a&$c=$x[$i];$k/=3)          # loop through digits/operator index
        $s.="+-"[$i++?$k%3:2].$c;   # prepend operator for base-3 digit (nothing for 2)
echo min($r);                   # print lowest result
Titus
fuente
3

Jalea , 32 bytes

L’⁾+_ṗż@€
ŒṖÇ€ẎµFV=ȷ2µÐfLÞḢFṄḟ³L

Un programa completo que se muestra utilizando los operadores Jelly (en _lugar de -).

Nota: Para mostrar -en la salida en lugar de _(no es un requisito), agregue ⁾_-yentre Fy ( ⁾_-es un par de caracteres literal ['_','-']y yes el átomo "traducir" diádico).

¿Cómo?

L’⁾+_ṗż@€ - Link 1, form all sums from a partition: list of lists of characters
                                     e.g. ["12","345","67"]
L         - length                        3
 ’        - decremented                   2
  ⁾+_     - literal ['+','_']
     ṗ    - Cartesian power               ["++","+_","_+","__"]
      ż@€ - zip for €ach (swap @rguments) ["12+345+67","12+345_67","12_345+67","12_345_67"]

ŒṖÇ€ẎµFV=ȷ2µÐfLÞḢFṄḟ³L - Main link: list of characters
ŒṖ                     - all partitions
  Ç€                   - call the last link (1) as a monad for €ach
    Ẏ                  - tighten (flatten by 1 level)
     µ     µÐf         - filter keep if:
      F                -   flatten
       V               -   evaluate as Jelly code (perform the sum)
         ȷ2            -   literal 100
        =              -   equal?
               Þ       - sort by:
              L        -  length
                Ḣ      - head
                 F     - flatten
                  Ṅ    - print that and a newline
                   ḟ³  - filter out the characters from the input
                     L - length (number of operators)
                       - implicit print

Pruébalo en línea!

Jonathan Allan
fuente
2

Mathematica, 136 146 149 156 165 166 bytes

#&@@Sort[{StringLength@#-e+9!(ToExpression@#-100)^2,#}&/@StringJoin/@(Riffle[b,#]&)/@Tuples[{"","+","-"},(e=Length[b=Characters@#])-1]]&

Devoluciones {3, 123-45-67+89}por ejemplo.

El caso de prueba tarda aproximadamente 0,09 segundos en completarse.

Keyu Gan
fuente
2

Python 2 , 256 230 208 205 172 171 170 165 bytes, método iterativo

  • 33 gracias a Chas Brown
  • Un byte guardado cuando se reemplaza len(a)porw
  • Un byte guardado cuando se reemplaza z-=1;d=zpord=z=z-1
q=[];a=input()
w=len(a);z=n=3**w
while z-n/3:
 d=z=z-1;j=0;b=''
 while d:r=d%3;d/=3;b+=a[j]+chr(r+43)*(d>0!=r-1);j+=1
 if eval(b)==100:q+=[(len(b)-w,b)]
print min(q)

Pruébalo en línea!

Pequeña explicación Usando la representación en la base 3, el código intercala los dígitos con los operadores {'+', '-', concatenación} de acuerdo con todas las combinaciones posibles.

Python 2 , 167 bytes, método recursivo

def f(s):
 if len(s)==1:return[s]
 b=s[0];q=[]
 for z in f(s[1:]):q+=[b+'+'+z,b+'-'+z,b+z]
 return q
a=input()
print min((len(x)-len(a),x)for x in f(a)if eval(x)==100)

Pruébalo en línea!

Algunas salidas

"399299"    --> (1, '399-299')
"987654321" --> (4, '98-76+54+3+21')
"1111111"   --> (3, '1+111-1-11')
mdahmoune
fuente
1
Me gusta el uso de divmod! Puedo ver algunos campos de golf: reemplace list(input())con solo input(), ya que una cadena ya es iterable para guardar 6 bytes; reemplazar b.count('+')+b.count('-')con len(b)-len(a)para guardar 12 bytes; y reemplace chr(r+43)con chr(r+43)*(d>0!=r-1)y luego puede eliminar la línea b=b[:-1].replace(',','')para ahorrar 15 bytes netos ( (d>0!=r-1)es equivalente a (d>0 and 0!=r-1)).
Chas Brown
2

Brachylog , 36 bytes

~cịᵐ{|ṅ}ᵐ{+100&{ℕṫ,"+"↻|ṫ}ᵐcbE&kl;E}

Pruébalo en línea!

Sin embargo, más de la mitad de esto es obtener el formato de salida correcto. La lógica central real es solo:

15 bytes

~cịᵐ{|ṅ}ᵐ.+100∧

Pruébalo en línea!

Esto devuelve una lista como [123, –45, –67,89]. La expresión es la suma de los elementos, y el número de operadores es 1 menor que la longitud de la lista.

~cLhℕ∧100~+Lcasi funciona para 12 bytes (¡ Pruébelo en línea! ), pero es demasiado lento para manejar la entrada completa de 9 dígitos en TIO y, lo que es más importante, falla para entradas como 10808: Brachylog es demasiado inteligente para dividir números para tener ceros a la izquierda, así que no t vea la partición [108, -08].

sundar - Restablecer a Monica
fuente
1

Haskell , 180 178 bytes

m#[a]=[[a]]
m#(b:r)|s<-m#r=m(b:)=<<[s,m('+':)s,m('-':)s]
o '-'=(-)
o _=(+)
(p:r)?a|[(b,s)]<-lex r=s?o p a(read b)
_?a=a
g s=minimum[(sum[1|c<-t,c<'0'],t)|t<-map#s,('+':t)?0==100]

Pruébalo en línea! Uso: g "123456789"rendimientos (3,"123-45-67+89").

#crea una lista de todos los términos posibles, ?evalúa un término y gfiltra los términos que evalúan a 100 y devuelve el que tiene el número mínimo de operandos.

Laikoni
fuente
0

Jalea , 27 bytes

L’““+“_”ṗ⁸żF¥ⱮV⁼ȷ2ƊƇLÞḢṄḟ⁸L

Pruébalo en línea!

No puedo decir que no tomé algunas pistas de la respuesta anterior de Jonathan Allan. ;-)

En comparación con su respuesta, esta es solo dos bytes más corta (30), no cinco, si hacemos la comparación justa debido a las actualizaciones de idioma:

L’““+“_”ṗ⁸żF¥Ð€V⁼ȷ2$$ÐfLÞḢṄḟ⁸L

Si comparamos a la inversa (la versión más nueva en lugar de la anterior), la diferencia es la misma (se convierte en 29 bytes, como se ve a continuación):

ŒṖżⱮL’⁾+_ṗƲ$€ẎFV=ȷ2ƲƇLÞḢFṄḟ³L
Erik el Outgolfer
fuente