Dada una cadena de caracteres +=-donde hay al menos uno =, inserte enteros positivos entre todos los símbolos y al principio y al final de modo que se satisfagan las ecuaciones matemáticas.

Por ejemplo, dada la entrada

+-=-=

necesita insertar enteros positivos de A a F como este

A+B-C=D-E=F

de modo que las ecuaciones estén todas satisfechas, es decir, A + B - Cy D - Ey Fsean todos el mismo número.

Hay muchas formas posibles de hacer esto, ya que, siempre que las ecuaciones funcionen, se puede usar cualquier conjunto de enteros positivos. Cada línea aquí es una posible salida válida para ingresar +-=-=:

2+3-4=6-5=1
1+1-1=2-1=1
4+2-4=4-2=2
100+1-10=182-91=91
89+231-77=1024-781=243

Tenga en cuenta que no se requiere que el valor de las expresiones sea un número entero positivo como lo son los números insertados. Por ejemplo, dada la entrada, -=-las salidas 1-10=8-17(evals a -9) y 10-1=17-8(evals a 9) son igualmente válidas. Por supuesto, para algunas entradas, como =es imposible tener un negativo como expresión, ya que solo 5=5se pueden insertar números positivos como .

Tenga en cuenta también que cero no es un entero positivo.

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

Puede generar los números como una lista en lugar de insertarlos directamente en la cadena. Si saca la cadena, puede haber espacios que separan símbolos y números. Entonces, para entrada +-=-=, salida

2, 3, 4, 6, 5, 1

o

2 + 3 - 4 = 6 - 5 = 1

es equivalente a la salida

2+3-4=6-5=1

Casos de prueba

Input | One Possible Output
= | 1=1
== | 2=2=2
+= | 1+3=4
=+ | 2=1+1
-= | 30-10=20
=- | 1=2-1
=-= | 3=7-4=3
=+= | 2=1+1=2
=== | 100=100=100=100
+=- | 3+2=7-2
-=+ | 7-2=3+2
+=+ | 3+3=3+3
-=- | 1-10=8-17
--= | 60-1-1=58
++= | 60+1+1=62
-+= | 60-9+1=52
+-= | 60+9-1=68
+-=-= | 2+3-4=6-5=1
--=-- | 2-1-1=2-1-1
==-== | 47=47=50-3=47=47
=++=+-=-+=--= | 3=1+1+1=3+1-1=1-1+3=5-1-1=3
+--++-=-+-+- | 35+10-16-29+20+107-1000=5-4+3-2+1-876
====== | 8=8=8=8=8=8=8

Retina , 58 bytes

[-+]
$&1
\B((\+1)|(-1))*
$._$*1$#3$*1$#2$*_$&
+`1_

1+
$.&

Pruébalo en línea!

Solución alternativa al mismo número de bytes:

((\+)|(-))*
$._$*1$#3$*1$#2$*_$&
+`1_

([+-])1*
$+1
1+
$.&

Pruébalo en línea!

Explicación

La idea básica es convertir todas las +s y -s en simples +1y -1operaciones y luego a anteponer un número suficientemente grande que hace todo el trabajo ecuaciones. Para que las ecuaciones coincidan, simplemente podemos anteponer el mismo número a cada una de ellas, y luego reducirlo en uno para cada uno +1y aumentarlo en uno para cada uno -1después. Como trabajaremos con números unarios, el único problema es que el primer número debe ser lo suficientemente grande como para que podamos reducirlo en 1 veces.

[-+]
$&1

Comenzamos insertando un 1después de cada -o +.

\B((\+1)|(-1))*
$._$*1$#3$*1$#2$*_$&

Esto \Basegura que estas coincidencias estén al principio de la entrada, o entre a =y +ao -, es decir, todas las posiciones donde queremos insertar el número inicial de una expresión. La ((\+1)|(-1))*parte a continuación, simplemente cuenta el número de +1s y -1s en grupos 2y 3respectivamente. Ahora analicemos la cadena de sustitución:

$._$*1   # For each character in the current string, insert a 1. This is
         # an offset which is the same for each expression and is guaranteed
         # to be large enough that all subsequent +1s can be cancelled.
$#3$*1   # For each -1, insert a 1.
$#2$*_   # For each +1, insert a _.
$&       # Re-insert the string of +1s and -1s.

+`1_

Caída repetida 1_de la cadena, aplicando la cancelación requerida desde el +1s.

1+
$.&

Finalmente, reemplace todas las cadenas de 1s con sus longitudes para convertir de unario a decimal.

Python 2 , 76 bytes

lambda e:sum([[len(e+s)-2*s.count('+')]+[1]*len(s)for s in e.split('=')],[])

Pruébalo en línea!

Python 2, 199 179 178 172 162 158 156 152 151 bytes

Demasiado tiempo, pero la solución fue fácil de crear.

from itertools import*
i=input()
k='%s'
s=k+k.join(i)+k
for p in product(*[range(1,65537)]*-~len(i)):
    if eval((s%p).replace('=','==')):print s%p;break

Pruébalo en línea

Esto intentará todas las posibilidades hasta que encuentre una solución. El programa es extremadamente lento. También realiza el reemplazo de la cadena cada iteración. La edición "172" lo hizo drásticamente más lento, ya que en lugar de comenzar con un rango pequeño, comienza al máximo. Por ejemplo, las entradas -=o =+tienen que intentar 2 ** 32 intentos antes de llegar a una solución.

Para acelerar el programa, use la versión con 178 bytes del historial de edición.

JavaScript (ES6), 92 82 bytes

Golfó 8 bytes con un truco de @xnor

let f =
x=>x.split`=`.map(q=>(x+q).length-2*~-q.split`+`.length+[...q,''].join(1)).join`=`

<input oninput="if(/^[+=-]+$/.test(value))O.innerHTML=f(value)" value="="><br>
<pre id=O>1=1</pre>

El truco aquí es insertar un 1después de cada +o -, luego anteponer a cada expresión el número que hace que la expresión sea igual a la longitud de la entrada. De esta manera podemos garantizar que el número sea siempre positivo; Como siempre hay al menos 1 =en la cadena, el número de +s nunca puede alcanzar la longitud de la cadena, por lo que el resto siempre es al menos 1. Puede verificar esto escribiendo un número arbitrario de +s en el fragmento de arriba.

Python 2 , 120 119 bytes

^{-1 byte gracias a mbomb007}

a=['1'+(n and('1'.join(n)+'1'))for n in input().split('=')]
print'='.join(`max(map(eval,a))-eval(c)+1`+c[1:]for c in a)

Pruébalo en línea! o Verificar todos los casos de prueba

Primero inserto 1en cada posición, para verificar el valor más alto, luego lo agrego como desplazamiento en cada ecuación. Esto funciona porque no puede agregar números negativos, por lo que el resultado mínimo viene dado por la cantidad de +ecuaciones que solo tiene +.

GNU Prolog, 156 bytes

x(L,R,V)-->{E#>0},({L=[E|R],E=V};x(L,[E|R],X),("+",{V#=X+E};"-",{V#=X-E})).
q(L,R,V)-->x(L,T,V),({T=R};"=",q(T,R,V)).
s(Q,L):-q(L,[],_,Q,[]),fd_labeling(L).

Explicación

Tenemos un montón de ecuaciones para resolver, entonces, ¿por qué no usar un solucionador de ecuaciones real?

xes básicamente un evaluador de ecuaciones para ecuaciones de la forma +-+; Además de la ecuación en sí, tiene dos argumentos adicionales (una lista de diferencias L,Rque contiene los valores de la ecuación y un valor Vque la ecuación evalúa). Como es habitual en Prolog, se puede usar de cualquier manera (por ejemplo, puede especificar Vy obtener un L,R, especificar L,Ry obtener un V, especificar ambos y verificar que el valor sea correcto, o no especificar ninguno, en cuyo caso se impondrán restricciones apropiadas en ambos Vy L,R) Se L,Rnombra el "elemento actual" de E, y también incluimos una afirmación de queEes mayor que 0 (porque la pregunta requiere el uso de números positivos). Esta función es un poco más detallada de lo que me gustaría, por ejemplo, tuve que escribir el [E|R]patrón de coincidencia / no coincidencia dos veces, debido al hecho de que las listas son asociativas a la derecha pero la suma y la resta son asociativas a la izquierda. Lamentablemente, necesitamos usar una lista real, en lugar de inventar nuestro propio tipo de lista asociativa izquierda fuera de las celdas de cons, para fd_labelingtrabajar.

qes similar a x, pero también incluye =. Básicamente solo llama x, y se recursivamente. Por cierto, es una demostración muy clara de cómo funcionan las listas de diferencias, mostrando que puede concatenar dos listas de diferencias L,Ty T,Rformar una sola lista de diferencias L,R. La idea básica es que una lista de diferencias es una función parcial que toma un argumento Ry devuelve un valor Lque está Rantepuesto a la lista misma. Por lo tanto, al identificar el argumento de una lista de diferencias y el valor de retorno de otra, podemos componer las funciones y así concatenar las listas.

Finalmente, sque es la función que realmente resuelve la tarea en la pregunta, es una función envolvente que llama qcon argumentos. Convertimos la lista de diferencias en una lista regular al proporcionarla []como argumento, y la usamos fd_labelingpara encontrar una solución a la ecuación que construimos. (De forma predeterminada, parece que le gusta establecer valores en 1 si no hay razón para establecerlos en otra cosa. Sin embargo, se puede configurar; value_method(random)ofrece soluciones más "interesantes" que poner 1s en todas partes, por ejemplo, y sigue siendo muy rápido. )

Salida de muestra

Con el programa como está escrito:

| ?- s("=++=+-=-+=--=", V).

V = [3,1,1,1,3,1,1,3,1,1,5,1,1,3] ?

Si hago que el programa sea un poco más largo para agregar un value_method(random), el resultado varía, pero se ve más o menos así:

| ?- s("=++=+-=-+=--=", V).

V = [68,6,12,50,85,114,131,45,3,26,71,1,2,68] ? 

En ambos casos, ?al final de la salida significa que puede haber más de una solución. (Por supuesto, en este caso, sabemos que hay un montón más de una solución!)

Mathematica, 116 bytes

Join@@(Prepend[#^2,1-Min[Tr/@c]+Tr@#]&/@(c=Characters@StringSplit["0"<>#<>"0","="]/."+"->-1/."-"->1/."0"->Nothing))&

Función pura que toma una cadena como entrada y devuelve una lista de enteros positivos. Estrategia básica: solo sumamos 1 y restamos 1, y elegimos los números iniciales en cada expresión para que todo sea igual.

c=Characters@StringSplit[#,"="]/."+"->-1/."-"->1dividiría la cadena de entrada en cada signo igual, luego reemplazaría cada +por -1y cada -por 1. Sin embargo, si hay un signo igual al principio o al final, entonces sería ignorado. Por lo tanto, agregamos artificialmente un nuevo carácter en cada extremo ( "0"<>#<>"0") y lo hacemos desaparecer después de que se complete la división de cadenas ( /."0"->Nothing).

El total de cada sublista ahora es igual a un número entero que podemos poner delante de +sy -s para que cada expresión sea igual. 1-Min[Tr/@c]es el número entero más pequeño que podemos agregar a cada total para que todos sean positivos. Entonces Prepend[#^2,1-Min[Tr/@c]+Tr@#]&toma cada sublista ( ^2convierte todas sus entradas 1) y antepone su total desplazado por este entero compensador más pequeño. Las listas resultantes se Joineditan juntas para producir la salida.

Ruby, 76

->s{(?1+s.gsub(/./){|a|a+?1}).split(?=).map{|e|e[0]="#{5**8-eval(e)}";e}*?=}

¡El valor objetivo para las expresiones se fija en 5**8menos 1 por razones de golf! Originalmente estaba usando s.size+1menos 1.

Sin golf en el programa de prueba

f=->s{(?1+s.gsub(/./){|a|a+?1}).           #add a 1 at the beginning and after every symbol
       split(?=).                          #split into an array of expressions at = signs
       map{|e|                             #for each expression string
         e[0]="#{5**8-eval(e)}";e          #change the first number to 5**8-eval(e)
       }*?=                                #and rejoin the strings
}


puts f["="] 
puts f["=="] 
puts f["+="] 
puts f["=+"]
puts f["-="]
puts f["=-"]
puts f["=-="]
puts f["=+="]
puts f["==="]
puts f["+=-"]
puts f["-=+"]
puts f["+=+"]
puts f["-=-"]
puts f["--="]
puts f["++="]
puts f["-+="]
puts f["+-="]
puts f["+-=-="]
puts f["--=--"]
puts f["==-=="]
puts f["=++=+-=-+=--="]
puts f["+--++-=-+-+-"]
puts f["======"]

Salida

390624=390624
390624=390624=390624
390623+1=390624
390624=390623+1
390625-1=390624
390624=390625-1
390624=390625-1=390624
390624=390623+1=390624
390624=390624=390624=390624
390623+1=390625-1
390625-1=390623+1
390623+1=390623+1
390625-1=390625-1
390626-1-1=390624
390622+1+1=390624
390624-1+1=390624
390624+1-1=390624
390624+1-1=390625-1=390624
390626-1-1=390626-1-1
390624=390624=390625-1=390624=390624
390624=390622+1+1=390624+1-1=390624-1+1=390626-1-1=390624
390624+1-1-1+1+1-1=390625-1+1-1+1-1
390624=390624=390624=390624=390624=390624=390624

PHP, 207 204 197 114 bytes

enfoque directo: mucho más corto y rápido

foreach(explode("=",$argn)as$t)echo"="[!$c],strlen($argn)+($c=count_chars($t))[45]-$c[43],@chunk_split($t,!!$t,1);

Ejecutar echo '<input>' | php -nR '<code>'o probarlo en línea .

Descompostura

foreach(explode("=",$argn)as$t) // loop through terms
    echo                            // print ...
        "="[!$c],                       // 1. "=" if not first term
        strlen($argn)                   // 2. maximum number
            +($c=count_chars($t))[45]   //    + number of "-"
            -$c[43],                    //    - number of "+"
        @chunk_split($t,!!$t,1);        // 3. each operator followed by "1"

• !$ces verdadero en la primera iteración, convertida en 1para indexación de cadenas; "="[1]esta vacio.
  Después de eso, $cse establece y es !$cfalso, se lanza 0y "="[0]es el primer personaje.
• El valor máximo para cualquier término no necesita exceder el número de más +1;
  así que definitivamente estamos seguros con la longitud de la entrada. Todos los términos se evaluarán a eso.
• chunk_split($s,$n,$i)inserta $idespués de cada $ncarácter de $s- y al final.
  Para evitar que los términos vacíos se conviertan en 1, se forza un error al establecer la longitud del fragmento en 0.

Röda , 112 110 109 bytes

f x{[(`:$x:`/"=")()|{|p|p~=":",""a=p;a~=`\+`,""b=p;b~="-","";["=",#x-#b+#a];{(p/"")|{|o|[o,"1"*#o]}_}}_][1:]}

Pruébalo en línea!

La función de división no funcionó como pretendía con este programa. Por ejemplo, split("", sep="")devuelve una cadena vacía en lugar de nada. ¿Cómo es eso lógico? Debido a esto, el programa es casi 20 bytes más grande de lo que podría ser si la semántica dividida fuera ideal.

La idea de esta respuesta es que sabemos que la longitud de la cadena de entrada debe ser mayor o igual al valor de la ecuación, por lo que definimos el valor de la ecuación como la longitud de la cadena. Para cada parte de la ecuación, creemos que cada operador es +1o -1y resta y suma al valor de la ecuación.

Sin golf:

function f(x) {
    /* Adds ":"s around the string to prevent "=" being split wrong. */
    [split(`:$x:`, sep="=") | for p do
        p ~= ":", ""          /* Removes colons. */
        a := p; b := p        /* Initializes a and b to be p. */
        a ~= "\\+", ""        /* The lengths of a and are now equal to the */
        b ~= "-", ""          /* numbers of "-" and "+" characters in x. */
        push("=", #x-#b+#a)   /* Prints "=" and the value of the equation */
                              /* minus number of "+"s plus number of "-"s. */
        split(p, sep="") | for o do /* For each operator: */
            push(o)                 /* Prints the operator. */
            push(1) if [o != ""]    /* Prints 1 unless the operator is "". */
        done
    done][1:] /* Removes the first character of the output ("="). */
}