29
\$\begingroup\$

Given a string of the characters +=- where there is at least one =, insert positive integers between all the symbols and at the start and the end such that the math equations are satisfied.

For example, given the input

+-=-=

you need to insert positive integers A through F like this

A+B-C=D-E=F

such that the equations are all satisfied, i.e. A + B - C and D - E and F are all the same number.

There are many possible ways to do this since, as long as the equations work out, any set of positive integers may be used. Each line here is a possible valid output to input +-=-=:

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

Note that the value of the expressions is not required to be a positive integer like the inserted numbers are. For example, given input -=- the outputs 1-10=8-17 (evals to -9) and 10-1=17-8 (evals to 9) are both equally valid. Of course for some inputs such as = it's impossible to have a negative as the expression since only positive numbers like 5=5 can be inserted.

Note also that zero is not a positive integer.

The shortest code in bytes wins.

You may output the numbers as a list instead of inserting them directly into the string. If you do output the string there may be spaces separating symbols and numbers. So, for input +-=-=, outputting

2, 3, 4, 6, 5, 1

or

2 + 3 - 4 = 6 - 5 = 1

is equivalent to outputting

2+3-4=6-5=1

Test Cases

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
\$\endgroup\$
3
  • \$\begingroup\$ Related. \$\endgroup\$ Mar 9, 2017 at 19:15
  • \$\begingroup\$ Can we assume any upper bound on the length of the formula? \$\endgroup\$
    – xnor
    Mar 9, 2017 at 19:41
  • 2
    \$\begingroup\$ @xnor You may assume the input is less than 2^16 characters long if that helps. \$\endgroup\$ Mar 9, 2017 at 19:44

10 Answers 10

16
\$\begingroup\$

Retina, 58 bytes

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

1+
$.&

Try it online!

Alternative solution at the same byte count:

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

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

Try it online!

Explanation

The basic idea is to turn all the +s and -s into simple +1 and -1 operations and then to prepend a sufficiently large number that makes all the equations work. To make the equations match, we can simply prepend the same number to each of them, and then reduce it by one for each +1 and increase it by one for each -1 after it. Since we'll be working with unary numbers, the only catch is that the first number needs to be large enough that we can reduce it by 1 enough times.

[-+]
$&1

We start by inserting a 1 after each - or +.

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

The \B ensures that these matches are either at the beginning of the input, or between a = and a + or -, i.e. all the positions where we want to insert the leading number of an expression. The ((\+1)|(-1))* part then simply counts the number of +1s and -1s in groups 2 and 3 respectively. Now let's break down the substitution string:

$._$*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_

Repeatedly drop 1_ from the string, applying the required cancellation from the +1s.

1+
$.&

Finally, replace all the strings of 1s with their lengths to convert from unary to decimal.

\$\endgroup\$
8
\$\begingroup\$

Python 2, 76 bytes

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

Try it online!

\$\endgroup\$
2
  • 3
    \$\begingroup\$ Can you add an explanation? \$\endgroup\$ Mar 10, 2017 at 0:44
  • 1
    \$\begingroup\$ @HelkaHomba The idea is fairly simple: first take each chunk of the input split by equal signs. Choose the first number of each chunk to be eqtn_len + plus_signs + minus_signs - 2 * plus_signs = eqtn_len + minus_signs - plus_signs. Then since all the other numbers in the chunk are ones, the total for the chunk works out to eqtn_len + minus_signs - plus_signs - minus_signs + plus_signs = eqtn_len. The equation length has to be positive, so everything works out. \$\endgroup\$ Mar 10, 2017 at 4:28
6
\$\begingroup\$

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

Way too long, but the solution was easy to create.

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

Try it online

This will try every possibility until it finds a solution. The program is extremely slow. It also performs the string replacement every iteration. The "172" edit made it drastically slower, since rather than starting with a small range it starts at the max. For example, the inputs -= or =+ have to try 2**32 attempts before reaching a solution.

To speed up the program, use the version with 178 bytes from the edit history.

\$\endgroup\$
12
  • \$\begingroup\$ Doesn't range in python2 create the whole range as a list immediately? IIRC you could speed it up by using xrange instead, as I think that's the lazy-loading version (Python3 uses lazy as the default range) \$\endgroup\$
    – Delioth
    Mar 9, 2017 at 21:54
  • 1
    \$\begingroup\$ @Delioth That uses another byte, though. The goal is to remove bytes. Also, that wouldn't actually provide much speedup, since the majority of the slowdown is from the number of iterations, not the creation of the list, which only occurs once. I ran print range(1,65537) and it completed in 0.034 s. \$\endgroup\$
    – mbomb007
    Mar 9, 2017 at 21:54
  • \$\begingroup\$ Well, of course- more of a "this could speed it up with exactly the same methodology," on the worry of it taking so long. Memory thrashing could cause significant slowdown. Also, you could cut some bytes (maybe only 1) by not setting l=..., but putting that right in the product(range(...),repeat=len(s)+1). If you need parentheses it only saves one byte (\n) \$\endgroup\$
    – Delioth
    Mar 9, 2017 at 22:03
  • \$\begingroup\$ @Delioth Even if I needed parens around len(s)+1, I could use -~len(s) instead, which wouldn't require parens. \$\endgroup\$
    – mbomb007
    Mar 9, 2017 at 22:10
  • \$\begingroup\$ Ah, right. I always forget about bitwise operations and tricks- must be the toll working on frontend javascript is taking on my Python expertise! \$\endgroup\$
    – Delioth
    Mar 9, 2017 at 22:12
5
\$\begingroup\$

JavaScript (ES6), 92 82 bytes

Golfed 8 bytes with a trick from @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>

The trick here is to insert a 1 after every + or -, then prepend to each expression the number that makes the expression equal the length of the input. This way we can guarantee that the number is always positive; since there's always at least 1 = in the string, the number of +s can never reach the length of the string, so the remainder is always at least 1. You can verify this by typing in an arbitrary number of +s in the snippet above.

\$\endgroup\$
5
\$\begingroup\$

Python 2, 120 119 bytes

-1 byte thanks to 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)

Try it online! or Verify all test cases

First I insert 1 in every position, to check the highest value, then add it as offset on every equation. This work because you can't add negative numbers, so the minimum result is given by the amount of + in the equation that only have +.

\$\endgroup\$
1
  • \$\begingroup\$ You can remove a couple spaces. \$\endgroup\$
    – mbomb007
    Mar 9, 2017 at 21:03
5
\$\begingroup\$

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

Explanation

We've got a bunch of equations to solve, so why not use an actual equation solver?

x is basically an equation evaluator for equations of the form +-+; in addition to the equation itself, it has two additional arguments (a difference list L,R that contains the values of the equation, and a value V that the equation evaluates to). As usual in Prolog, it can be used any way round (e.g. you can specify V and get an L,R, specify L,R and get a V, specify both and verify that the value is correct, or specify neither in which case appropriate constraints will be placed on both V and L,R). The "current element" of L,R is named E, and we also include an assertion that E is greater than 0 (because the question requires the use of positive numbers). This function is slightly more verbose than I'd like, e.g. I had to write the [E|R] pattern match/unmatch twice, due to the fact that lists are right-associative but addition and subtraction are left-associative. Sadly, we need to use an actual list, rather than inventing our own left-associative list type out of cons cells, for fd_labeling to work.

q is similar to x, but also includes =. It basically just calls x, and itself recursively. Incidentally, it's a very clear demonstration of how difference lists work, showing that you can concatenate two difference lists L,T and T,R into a single difference list L,R. The basic idea is that a difference list is a partial function that takes an argument R and returns a value L which is R with the list itself prepended to it. Thus, by identifying the argument of one difference list and the return value of another, we can compose the functions, and thus concatenate the lists.

Finally, s, which is the funciton that actually solves the task in the question, is a wrapper function that calls q with arguments. We convert the difference list to a regular list by supplying [] as its argument, and use fd_labeling to find a solution to the equation we built up. (By default, it appears to like setting values to 1 if there's no reason to set them to something else. However, it can be configured; value_method(random) gives more "interesting" solutions than putting 1s everywhere, for example, and is still very fast.)

Sample output

With the program as written:

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

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

If I make the program a bit longer to add a value_method(random), the outcome varies, but looks something like this:

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

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

In both cases, the ? at the end of the output means that there may be more than one solution. (Of course, in this case, we know that there's a lot more than one solution!)

\$\endgroup\$
0
4
\$\begingroup\$

Mathematica, 116 bytes

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

Pure function taking a string as input and returning a list of positive integers. Basic strategy: we only ever add 1 and subtract 1, and we choose the initial numbers in each expression to make everything equal.

c=Characters@StringSplit[#,"="]/."+"->-1/."-"->1 would split the input string at every equals sign, then replace each + by -1 and each - by 1. However, if there's an equals sign at the beginning or end, then it would get ignored. Therefore we artificially add a new character at each end ("0"<>#<>"0") and make it go away after the string-splitting is complete (/."0"->Nothing).

The total of each sublist now equals an integer that we can put in front of the +s and -s to make each expression equal. 1-Min[Tr/@c] is the smallest integer that we can add to each total to make them all positive. So Prepend[#^2,1-Min[Tr/@c]+Tr@#]& takes each sublist (the ^2 turns all their entries to 1) and prepends its total shifted by this smallest compensating integer. The resulting lists are Joined together to produce the output.

\$\endgroup\$
3
\$\begingroup\$

Ruby, 76

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

The target value for the expressions is fixed at 5**8 minus 1 for golfing reasons! Originally I was using s.size+1 minus 1.

Ungolfed in test program

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

Output

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
\$\endgroup\$
3
\$\begingroup\$

PHP, 207 204 197 114 bytes

direct approach: much shorter and faster

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

Run with echo '<input>' | php -nR '<code>' or test it online.

breakdown

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"
  • !$c is true in the first iteration, cast to 1 for string indexing; "="[1] is empty.
    After that, $c is set and !$c false, cast to 0 and "="[0] is the first character.
  • The maximum value for any term needs not exceed the number of pluses +1;
    so we´re definitely safe with the length of the input. All terms will evaluate to that.
  • chunk_split($s,$n,$i) inserts $i after every $n characters of $s - and at the end.
    To prevent empty terms turning to 1, an error is forced by setting the chunk length to 0.
\$\endgroup\$
1
\$\begingroup\$

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

Try it online!

The split function did not work as I intended with this program. For example, split("", sep="") returns one empty string instead of nothing. How is that logical? Due to this the program is nearly 20 bytes larger than what it could be if the split semantics were ideal.

The idea of this answer is that we know that the length of the input string must be greater or equal to the value of the equation, so we define the value of the equation to be the length of the string. For every part of the equation, we think every operator being +1 or -1 and subtract and add them to value of the equation.

Ungolfed:

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 ("="). */
}
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.