Infer pluses and minuses

Question

The problem

Consider an equation such as      "3 ± 2 ± 4 ± 1 = 4"      and determine if there exists a sequence of pluses and minuses that makes it arithmetically correct. If it exists, exhibit it. For instance, [-, +, -] works in this case:      "3 - 2 + 4 - 1 = 4".

• Sometimes it's impossible: e.g.      "3 ± 5 = 7"      has no solution. Your code needs to determine this.

• Other times, multiple solutions are possible: for      "1 ± 2 ± 4 ± 3 ± 1 = 1"      , both [-, +, -, +] and [+, -, +, -] are valid. Your code only needs to exhibit one but may also exhibit all.

The challenge

Code golf: write the shortest function or program that solves the problem.

Assumptions

• All numbers (both left and right of the equal sign) are non-negative integers. There may be zeroes.

• There is just one number to the right of the equal sign.

• There is no ± at the left of the first number.

  (2 ± 3 = 1 has no solution)

• Partial sums may be negative (but the total sum will be non-negative).

• There are at least 3 numbers in the input (i.e. at least 2 on the left hand side, plus the result).

I/O

• You will take a sequence of N numbers ([a₁, a₂, ...a_N-1, a_N]), where a₁, a₂, ...a_N-1 are addends and a_N is the result.

  Alternatively, you may choose to get a_N separately from the rest.

• You are free to choose what is a "sequence" (a list, or an array, or literals via stdin separated by space or newline or comma, or ...).

• If there is a solution, you should output a sequence of N-2 "plus"-signifying and "minus"-signifying constants, which may be represented as you prefer (("+", "-"), or (+1, -1,), or (+1, 0), or (NaN, 4), or ...).

  There are N-2 symbols total. You must not output the (implicit) "plus" to the left of the first addend.

• If there is no solution, you should have a predictable behaviour that signifies "no solution". This can be returning/printing a specific constant or throwing an exception or terminating without output.

  Having a program that predictably doesn't terminate is also acceptable.

Examples

• 3 2 4 1 4 → - + -
• 3 5 7 → none
• 1 2 4 3 1 1 → + - + - or - + - + or both
• 2 3 1 → none
• 11 3 0 8 → - + or - - or both
• 0 15 15 → +
• 4 9 6 1 → - +
• 8 2 3 3 → - -
• 8 4 5 1 16 → + + -

Answer 1

K (ngn/k), 14 bytes

-1 thanks to naffetS

&~*{x-/:y,-y}/

Attempt This Online!

Return a 2d list with solutions in reverse order. -+ are denoted by 01.

   {x-/:y,-y}/  all values obtainable by inserting -/+
  *             enforce last op is -
&~              locate 0s

Answer 2

Perl 5 + -a -M5.10.0, 43 bytes

Outputs all valid solutions. Outputs nothing if there's no solution.

$n=<>;$"="{-,+}";eval==$n&&say/\D/g for<@F>

Try it online!

Explanation

Initial list of numbers is implicitly stored in @F thanks to -a, target value is then stored in $n and the field separator ($") is set to "{-,+}". For each value in the glob <@F> (when interpolating a list into a string, the field separator is used which expands 3 2 4 1 into 3{-,+}2{-,+}4{-,+}1 which as a glob returns all permutations interpolating - and +. The string is then evaluated as code (eval works on $_ by default) and if it matches $n is output (say - which prints $_ by default).

Answer 3

Python 3,  75   67  64 bytes

-8 bytes thanks to Jitse (by placing the output in r - a very smart golf!).

f=lambda a,b,*r:f(a+b,*r,-2)or f(a-b,*r,-3)if-1<r[0]else(a==b)*r

A recursive function that accepts the full sequence of non-negative integers as arguments in order \$a_1, a_2, \cdots, a_N\$ and returns a tuple of instructions as integers, where -2 means add and -3 means subtract, representing one way that works, or an empty tuple if not possible.

Try it online!

How?

The first two terms of the sequence are a and b, the rest of the sequence is r.
If r's first element is greater than -1 the function is called with the first two terms added and -2 "instruction" is appended to r but if that results in an empty tuple then the function is called with the second term subtracted from the first along an additional -3 "instruction".
However, if r's first element is -2 or -3 then r is returned if a==b otherwise an empty tuple is returned.

Answer 4

J, 26 24 bytes

(##:@i.@#)@(=]F..(+,-~))

Attempt This Online!

Outputs all solutions or an empty list when none exists. 1 = -, 0 = + .

• ]F..(+,-~) Fold forward +/-, catting both options to the accumulated result each time
• = Where does that equal the left input? Returns boolean list.
• # Use that 0-1 list to filter...
• #:@i.@# The numbers 0 1 2 ... <len of list - 1> converted to binary

Worth noting this is a similar idea to att's nicer K solution... what makes that more elegant is K's ability to "find" 1s in a multidimensional list, return a lookup path directly to that list as a list of indexes for each axis. This can also be thought of as the result of a binary search algorithm.

J's I., on the other hand, only works for 1 dimensional lists, so we have to deal with some boring mechanics manually to accomplish the same thing.

Answer 5

R, 85 82 bytes

\(a,s=expand.grid(rep(list(c(-1,1)),sum(a|1)-2)))s[apply(s,1,\(x)!c(1,x,-1)%*%a),]

Attempt This Online!

Takes input as a vector \$[a_1, a_2, \ldots, a_{N-1}, a_N]\$ and returns a matrix of ±1s with solutions in rows. For "none", the function outputs numeric(0).

Answer 6

R, 55 bytes

Takes \$a_N\$ as a separate argument, returns a matrix of all solutions with 1/2 for -/+.

\(a,b)which(Reduce(\(x,y)x%o%c(1/y,y),2^a)==2^b,T)[,-1]

Attempt This Online!

The size of numbers this can handle is fairly limited by the powers of 2 a double value can represents.

Answer 7

JavaScript (ES6), 66 bytes

Returns either a binary string (with 0 for - / 1 for +) or undefined if there's no solution.

f=([n,...a],s=0,o)=>a+a?f(a,s+n,o?o+1:[])||o&&f(a,s-n,o+0):s==n&&o

Try it online!

Commented

f = (          // f is a recursive function taking:
  [ n,         //   n = next value from input array
       ...a ], //   a[] = remaining values
  s = 0,       //   s = sum
  o            //   o = output (initially undefined)
) =>           //
a + a ?        // if a[] is not empty:
  f(           //   do a 1st recursive call:
    a,         //     pass a[]
    s + n,     //     add n to s
    o ?        //     if o is defined:
      o + 1    //       append '1' for '+' to o
    :          //     else:
      []       //       initialize o to [] (coerced to
               //       an empty string, but truthy)
  ) ||         //   end of recursive call
  o &&         //   if o is defined,
  f(           //   do a 2nd recursive call:
    a,         //     pass a[]
    s - n,     //     subtract n from s
    o + 0      //     append '0' for '-' to o
  )            //   end of recursive call
:              // else:
  s == n && o  //   if s = n, return o

Answer 8

Uiua 0.11.0, ²⁷12 bytes ^SBCS

≡⇌⊚=/(⊟⊃-+:)

Try on Uiua Pad!

Similar to @att's K answer, so upvote that one too. Takes the list and \$a_N\$ on stack and returns all possible +/- choices as an array of 1s and 0s, with an empty list if not possible.

Explanation

≡⇌⊚=/(⊟⊃-+:)
    /(     ) # fold the list by
       ⊃-+:  # a-b and a+b
      ⊟      # combine as two rows of a new array
   =         # test equal to a_N element-wise
  ⊚          # get coordinates of 1s
≡⇌           # reverse each row

Old solution

⊡⊗:/+⍉⊙:⊃×∘¬×2☇1⇡×2⊃±¤⊙-:°⊂

Try on Uiua Pad!

Explanation

°⊂  # take first element off of list
:   # swap the top two of stack 
⊙-  # subtract a1 from aN
⊃±¤ # get the signs of the list (all 1s)
    # and a copy with an axis added
⇡×2 # *2 (all 2s) and range: all binary lists
☇1  # make it rank 2
¬×2 # not(x*2), changes 0,1 to 1,-1
⊃×∘ # multiply by list, keeping 1,-1 array
⊙:  # flip positions 2 and 3 on stack
/+⍉ # sum each row
⊗:  # find the index of the first aN-a1
⊡   # pick that from the 1,-1 array, error if no solution

Answer 9

Python, 105 91 bytes

- 14 bytes thanks to xnor

def f(l,n,o=[]):
 if[n]==l:print(o)
 if l[1:]:c,d,*r=l;[f([c+a*d]+r,n,o+[a])for a in[1,-1]]

I have very little experience of golfing in Python, so any tips would be appreciated.

Attempt This Online!

Answer 10

Vyxal, 78 bits^v2, 9.75 bytes

L‹k+↔'1p¹*∑⁰=

Try it Online!

Bitstring:

011000010011100110100110111001010111110001011011110111001100010101101101001001

A silly little answer that might be golfable with a better algorithm. Outputs all possible solutions, or an empty list for no solutions. Represents - as -1 and + as 1.

Explained

L‹k+↔'1p¹*∑⁰=­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣‏⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁣⁣‏⁠‎⁡⁠⁤⁡‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁣⁤‏‏​⁡⁠⁡‌­
L‹  ↔          # ‎⁡Combinations with replacement of length (a0...a(n-1) length - 1) of
  k+           # ‎⁢the list [1, -1]
     '         # ‎⁣Filtered to keep combinations where:
      1p       # ‎⁤  Prepending 1
        ¹*     # ‎⁢⁡  and transferring the signs of the combination to a0...a(n-1)
          ∑ =  # ‎⁢⁢  sums to
           ⁰   # ‎⁢⁣  a(n)
💎

Created with the help of Luminespire.

Answer 11

Charcoal, 32 bytes

ＩＥΦＥ…Ｘ²⁻Ｌθ²Ｘ²⊖Ｌθ⊖⊗↨⊗鲬Σ×ιθ✂ι¹±¹

Attempt This Online! Link is to verbose version of code. Outputs a list of 1s and -1s for the signs with each solution double-spaced. Explanation:

      ²                             Literal integer `2`
     Ｘ                              Raised to power
         θ                          Input list
        Ｌ                           Length
       ⁻                            Subtract
          ²                         Literal integer `2`
    …                               Range to
            ²                       Literal integer `2`
           Ｘ                        Raised to power
               θ                    Input list
              Ｌ                     Length
             ⊖                      Decremented
   Ｅ                                Map over values
                    ι               Current value
                   ⊗                Doubled
                  ↨                 Converted to base
                     ²              Literal integer `2`
                 ⊗                  Vectorised doubled
                ⊖                   Vectorised decremented
  Φ                                 Filtered where
                         ι          Current list
                       Σ×           Dot product with
                          θ         Input list
                      ¬             Is zero
 Ｅ                                  Map over solutions
                           ✂ι¹±¹    Slice off leading and trailing signs
Ｉ                                   Cast to string
                                    Implicitly print

Answer 12

Python, 215 209 bytes

-6 bytes by using another input format.

lambda*n,p,r=range,t=len:(x:=[bin(i)[2:].rjust(t(n)-1,'0').replace('1','-').replace('0','+')for i in r(2**~-t(n))],[x[j]for j in r(t(x))if eval(n[0]+"".join([x[j][l]+n[1:][l]for l in r(t(n)-1)])+"==%s"%p)])[1]

The first part of the lambda creates a list with the signs, and the second part evaluates them. Returns [] if there is no solution. Takes input as parameters of stringified ints, followed by a keyword argument taking the RHS value.

Answer 13

Google Sheets, 275 bytes

=let(d,tocol(A:A,1),ø,tocol(,1),regexreplace(reduce(d,index(mod(sequence(6^5),rows(d)-1)+2),lambda(a,i,if(a=a&"",a,let(r,{chooserows(a,sequence(i-1));index(a,i)*(2*(rand()<0.5)-1);iferror(chooserows(a,sequence(rows(a)-i,1,i+1)),ø)},if(sum(r)=B1,join("+",r),r))))),"\+-","-"))

Put operands in column A, the expected result in cell B1 and the formula in cell B2.

Gives the solution as in 3-2+4-1, or an error when a solution was not found. Works probabilistically up to 7776 rounds which seems plenty with up to 100 small operands or several dozen operands of any size.

Ungolfed:

=regexreplace( 
  reduce(tocol(A1:A, 1), index(mod(sequence(6^5), rows(tocol(A1:A, 1)) - 1) + 2), lambda(a, i, 
    if(istext(a), a, let( 
      null, tocol(æ, 2), 
      head, chooserows(a, sequence(i - 1)), 
      try, index(a, i) * (2 * (rand() < 0.5) - 1), 
      tail, iferror(chooserows(a, sequence(rows(a) - i, 1, i + 1)), null), 
      result, vstack(head, try, tail), 
      if(sum(result) = B1, join("+", result), result) 
    )
  ))), 
  "\+-", "-" 
)

Answer 14

Jelly, 7 bytes

_,+ɗ/œẹ

A dyadic Link that accepts a list of non-negative^* integers^*, the summands \$[a_1, a_2, \cdots, a_{N-1}]\$, on the left and a non-negative^* integer^*, the goal \$a_N\$, on the right and yields a list of reversed lists of instructions. 1 means subtract while 2 means add.

Try it online! Or see the test-suite.

^{* Not a necessary restriction, any numbers will do.}

How?

_,+ɗ/œẹ - Link: list of numbers, Summands; number, Goal
    /   - reduce {Summands} by:
   ɗ    -   last three links as a dyad - f(L, R):
_       -     {L} subtract {R} (vectorises) -> L-R
  +     -     {L} add {R} (vectorises) -> L+R
 ,      -     {L-R} pair {L+R} -> [L-R, L+R]
     œẹ - all multidimensional indices of {Goal}

Answer 15

Brachylog, 15 bytes

{+.∧1w₄|-.∧w₄}ˡ

Try it online!

Outputs + as 1 and - as 0. Empty output for impossible test cases.

The first n-1 numbers are given as an input list, and the expected result is given as the output variable.

Explanation

{             }ˡ    Left fold on the input list:
                      Either…
 +.                     Add the 2 numbers together
   ∧1w₄                 And delayed write a 1 to stdout
       |              Or…
        -.              Subtract the 2 numbers together
          ∧w₄           And delayed write an unknown variable (defaults to 0) to stdout
                    The output of the left fold must match the given output

This predicate will try different combinations of + and - in a left fold over the input list until the result is equal to the expected result given as output.

Once this predicate succeeds, the delayed writes w₄ will be printed out to stdout. If we were to use normal write commands, then it would write everytime it tries a choice, instead of writing the final correct choices.

If the test case is impossible, the predicate will eventually fail after trying everything, and the delayed writes will not be called. Nothing is thus printed to stdout.

Answer 16

Haskell, 64 bytes

f(x:w:y)=[q|q<-mapM(\_->[-1,1])y,sum(zipWith(*)q$w:y)==last y-x]

Try it online!

Answer 17

T-SQL, 3378 bytes

I saw this a few days ago, and was thinking of languages I could use to solve this problem. Ended up deciding to write the entire thing in a query on data.stackexchange.com because I had a lot of free time today and was willing to hardcode each and every one of the cases.

This runs in ~3ms on my Chromebook so I think it is as optimized runtime-wise as it gets.

Also note that loops don't exactly work in T-SQL, so I ended up having to brute-force all 33 cases (32 different ways to arrange +/- and the case where nothing works).

Although it is cool that it actually rounds down if one of the inputs is a decimal, I was afraid that might not happen.

DECLARE @a INT
DECLARE @b INT
DECLARE @c INT
DECLARE @d INT
DECLARE @e INT
DECLARE @f INT
DECLARE @g INT
SET @a = ##a##
SET @b = ##b##
SET @c = ##c##
SET @d = ##d##
SET @e = ##e##
SET @f = ##f##
SET @g = ##g##
IF @a + @b + @c + @d + @e + @f = @g
SELECT CONCAT(@a,'+',@b,'+',@c,'+',@d,'+',@e,'+',@f,'=',@g)
ELSE IF @a + @b + @c + @d + @e - @f = @g
SELECT CONCAT(@a,'+',@b,'+',@c,'+',@d,'+',@e,'-',@f,'=',@g)
ELSE IF @a + @b + @c + @d - @e + @f = @g
SELECT CONCAT(@a,'+',@b,'+',@c,'+',@d,'-',@e,'+',@f,'=',@g)
ELSE IF @a + @b + @c + @d - @e - @f = @g
SELECT CONCAT(@a,'+',@b,'+',@c,'+',@d,'-',@e,'-',@f,'=',@g)
ELSE IF @a + @b + @c - @d + @e + @f = @g
SELECT CONCAT(@a,'+',@b,'+',@c,'-',@d,'+',@e,'+',@f,'=',@g)
ELSE IF @a + @b + @c - @d + @e - @f = @g
SELECT CONCAT(@a,'+',@b,'+',@c,'-',@d,'+',@e,'-',@f,'=',@g)
ELSE IF @a + @b + @c - @d - @e + @f = @g
SELECT CONCAT(@a,'+',@b,'+',@c,'-',@d,'-',@e,'+',@f,'=',@g)
ELSE IF @a + @b + @c - @d - @e - @f = @g
SELECT CONCAT(@a,'+',@b,'+',@c,'-',@d,'-',@e,'-',@f,'=',@g)
ELSE IF @a + @b - @c + @d + @e + @f = @g
SELECT CONCAT(@a,'+',@b,'-',@c,'+',@d,'+',@e,'+',@f,'=',@g)
ELSE IF @a + @b - @c + @d + @e - @f = @g
SELECT CONCAT(@a,'+',@b,'-',@c,'+',@d,'+',@e,'-',@f,'=',@g)
ELSE IF @a + @b - @c + @d - @e + @f = @g
SELECT CONCAT(@a,'+',@b,'-',@c,'+',@d,'-',@e,'+',@f,'=',@g)
ELSE IF @a + @b - @c + @d - @e - @f = @g
SELECT CONCAT(@a,'+',@b,'-',@c,'+',@d,'-',@e,'-',@f,'=',@g)
ELSE IF @a + @b - @c - @d + @e + @f = @g
SELECT CONCAT(@a,'+',@b,'-',@c,'-',@d,'+',@e,'+',@f,'=',@g)
ELSE IF @a + @b - @c - @d + @e - @f = @g
SELECT CONCAT(@a,'+',@b,'-',@c,'-',@d,'+',@e,'-',@f,'=',@g)
ELSE IF @a + @b - @c - @d - @e + @f = @g
SELECT CONCAT(@a,'+',@b,'-',@c,'-',@d,'-',@e,'+',@f,'=',@g)
ELSE IF @a + @b - @c - @d - @e - @f = @g
SELECT CONCAT(@a,'+',@b,'-',@c,'-',@d,'-',@e,'-',@f,'=',@g)
ELSE IF @a - @b + @c + @d + @e + @f = @g
SELECT CONCAT(@a,'-',@b,'+',@c,'+',@d,'+',@e,'+',@f,'=',@g)
ELSE IF @a - @b + @c + @d + @e - @f = @g
SELECT CONCAT(@a,'-',@b,'+',@c,'+',@d,'+',@e,'-',@f,'=',@g)
ELSE IF @a - @b + @c + @d - @e + @f = @g
SELECT CONCAT(@a,'-',@b,'+',@c,'+',@d,'-',@e,'+',@f,'=',@g)
ELSE IF @a - @b + @c + @d - @e - @f = @g
SELECT CONCAT(@a,'-',@b,'+',@c,'+',@d,'-',@e,'-',@f,'=',@g)
ELSE IF @a - @b + @c - @d + @e + @f = @g
SELECT CONCAT(@a,'-',@b,'+',@c,'-',@d,'+',@e,'+',@f,'=',@g)
ELSE IF @a - @b + @c - @d + @e - @f = @g
SELECT CONCAT(@a,'-',@b,'+',@c,'-',@d,'+',@e,'-',@f,'=',@g)
ELSE IF @a - @b + @c - @d - @e + @f = @g
SELECT CONCAT(@a,'-',@b,'+',@c,'-',@d,'-',@e,'+',@f,'=',@g)
ELSE IF @a - @b + @c - @d - @e - @f = @g
SELECT CONCAT(@a,'-',@b,'+',@c,'-',@d,'-',@e,'-',@f,'=',@g)
ELSE IF @a - @b - @c + @d + @e + @f = @g
SELECT CONCAT(@a,'-',@b,'-',@c,'+',@d,'+',@e,'+',@f,'=',@g)
ELSE IF @a - @b - @c + @d + @e - @f = @g
SELECT CONCAT(@a,'-',@b,'-',@c,'+',@d,'+',@e,'-',@f,'=',@g)
ELSE IF @a - @b - @c + @d - @e + @f = @g
SELECT CONCAT(@a,'-',@b,'-',@c,'+',@d,'-',@e,'+',@f,'=',@g)
ELSE IF @a - @b - @c + @d - @e - @f = @g
SELECT CONCAT(@a,'-',@b,'-',@c,'+',@d,'-',@e,'-',@f,'=',@g)
ELSE IF @a - @b - @c - @d + @e + @f = @g
SELECT CONCAT(@a,'-',@b,'-',@c,'-',@d,'+',@e,'+',@f,'=',@g)
ELSE IF @a - @b - @c - @d + @e - @f = @g
SELECT CONCAT(@a,'-',@b,'-',@c,'-',@d,'+',@e,'-',@f,'=',@g)
ELSE IF @a - @b - @c - @d - @e + @f = @g
SELECT CONCAT(@a,'-',@b,'-',@c,'-',@d,'-',@e,'+',@f,'=',@g)
ELSE IF @a - @b - @c - @d - @e - @f = @g
SELECT CONCAT(@a,'-',@b,'-',@c,'-',@d,'-',@e,'-',@f,'=',@g)
ELSE SELECT 'Error'

Try it online (also commented out version)

Answer 18

Python, 132 bytes

lambda e,f,*a:{p for p in permutations("+-"*len(a),len(a))if f+eval("".join(x+str(y)for x,y in zip(p,a)))==e}
from itertools import*

Attempt This Online!

Answer 19

05AB1E, 14 bytes

®X‚Ig<ãʒ1š¹*OQ

Two separated inputs \$[a_0,...,a_{n-1}]\$ and \$a_n\$. Output as a list of all possible results, with -1 for - and 1 for +.

Try it online or verify all test cases.

Explanation:

®X‚            # Push pair [-1,1]
   Ig<         # Push the length-1 of the first input-list
      ã        # Take the cartesian product of the two
       ʒ       # Filter this list:
        1š     #  Prepend a 1
          ¹*   #  Multiply the values at the same positions to the first input-list
            O  #  Sum them together
             Q #  Check whether it equals the (implicit) second input-integer
               # (after which the filtered list is output implicitly)