Resuelve una ecuación con (casi) cualquier número que quieras

27

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
Pasatiempos de Calvin
fuente
Relacionado.
Martin Ender
¿Podemos suponer algún límite superior en la longitud de la fórmula?
xnor
2
@xnor Puede suponer que la entrada tiene menos de 2 ^ 16 caracteres de largo si eso ayuda.
Calvin's Hobbies

Respuestas:

16

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.

Martin Ender
fuente
8

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!

xnor
fuente
3
¿Puedes agregar una explicación?
Calvin's Hobbies
1
@HelkaHomba La idea es bastante simple: primero tome cada parte de la entrada dividida por signos iguales. Elija el primer número de cada fragmento para ser eqtn_len + plus_signs + minus_signs - 2 * plus_signs = eqtn_len + minus_signs - plus_signs. Entonces, dado que todos los otros números en el fragmento son unos, el total para el fragmento resulta eqtn_len + minus_signs - plus_signs - minus_signs + plus_signs = eqtn_len. La longitud de la ecuación debe ser positiva, por lo que todo funciona.
FryAmTheEggman
6

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.

mbomb007
fuente
¿ rangeEn python2 no se crea todo el rango como una lista de inmediato? IIRC puede acelerarlo usando en su xrangelugar, ya que creo que esa es la versión de carga diferida (Python3 usa lazy como valor predeterminado range)
Delioth
1
@Delioth Eso usa otro byte, sin embargo. El objetivo es eliminar bytes. Además, eso en realidad no proporcionaría mucha aceleración, ya que la mayoría de la desaceleración se debe al número de iteraciones, no a la creación de la lista, que solo ocurre una vez. Corrí print range(1,65537)y se completó en 0.034 s.
mbomb007
Bueno, por supuesto, más de "esto podría acelerarlo con exactamente la misma metodología", con la preocupación de que demore tanto. La pérdida de memoria podría causar una desaceleración significativa. Además, puede cortar algunos bytes (tal vez solo 1) no configurando l=..., pero colocando eso en el product(range(...),repeat=len(s)+1). Si necesita paréntesis, solo guarda un byte (\ n)
Delioth
@Delioth Incluso si necesitara parens len(s)+1, podría usar -~len(s)en su lugar, lo que no requeriría parens.
mbomb007
Ah bien. Siempre me olvido de las operaciones y los trucos a nivel de bits: ¡debe ser el costo que funciona en frontend javascript está adquiriendo mi experiencia en Python!
Delioth
5

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.

ETHproducciones
fuente
5

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 +.

Barra
fuente
Puedes eliminar un par de espacios.
mbomb007
5

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


fuente
4

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.

Greg Martin
fuente
3

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
Level River St
fuente
2

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.
Titus
fuente
1

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 ("="). */
}
fergusq
fuente