Find the smallest solution for this simple equation

Question

Input

4 integers w, x, y, z from the range -999 to 999 inclusive where none of the values is 0.

Output

4 integers a, b, c, d so that aw + bx + cy + dz == 0 where none of the values is 0.

Restrictions

Your output should be the solution with the smallest sum of absolute values possible. That is the smallest value of \$|a|+|b|+|c|+|d|\$. If there is more than one solution with the same sum of absolute values you can choose any one of them arbitrarily.

Examples

Input: 78 -75 24 33
Output: b = -1, d = 1, a = -2, c = 2

Input: 84 62 -52 -52
Output: a = -1, d = -1, b = -2, c = -3

Input: 26 45 -86 -4
Output: a = -3, b = -2, c = -2, d = 1

Input: 894 231 728 -106
Output: a = 3, b = -8, c = -1, d = 1

Input: -170 962 863 -803
Output: a = -5, d = 8, c = 2, b = 4

Added thanks to @Arnauld
Input: 3 14 62 74
Output: -2, 4, -2, 1 

Unassessed bonus

Not in the challenge but does your code also work on this?

Input:  9923 -9187 9011 -9973

Answer 1

Python 3 (PyPy), 139 137 bytes

Assumes no boundary and runs fine for the additional test case.

f=lambda x,b=4,t=0:[[s*~i]+v for i in range(b)for s in(1,-1)for v in f(x[1:],b-i,t+s*~i*x[0])][:1]or x[3:]and f(x,b+1)if x else[x]*(t==0)

Try it online!

Answer 2

JavaScript, 221 205 bytes

(w,x,y,z)=>(g=n=>[...g+""].flatMap((_,k)=>(i=(x,a=[1,1,1,1])=>x?a.flatMap((_,z)=>((b=[...a])[z]++,i(x-1,b))):[a])(n).map(a=>a.map((r,s)=>(k>>s-1&2)*r-r))).find(c=>w*c[0]+x*c[1]+y*c[2]==-z*c[3])||g(n+1))(0)

Try it online!

How it works:

I count up from 0, and for each number, I increment all possible combinations of items in an array which is initially [1, 1, 1, 1]. I then find all 16 signs of this array. I then just have to check for the one that is correct. That guarantees the minimum absolute value.

This is actually really fast for most of the test cases, with the speed being determined by the sum of the absolute values of the correct output rather than by the size of the input. It runs near-instantly for most of the test cases, takes about 20s with the 894 one, and times out for the -170 one.

I think I found the world's most cursed golf. Instead of using [...Array(16)] to get an array (the indices of which I'd use to find the various signs), it seems [...g+""] works...by casting g (a function) into a string and splitting it into characters. Since there's modulo stuff going on with the indices, going over 16 doesn't matter since it just results in some duplicate arrays in the possible outputs that are checked.

Answer 3

Wolfram Language (Mathematica), 52 51 bytes

ArgMin[{Tr[d=Abs@v],v.#==0<d},v={a,b,c,},Integers]&

Try it online!

Input the list of numbers.

ArgMin[                      ,                   ]  find:
                              v={a,b,c,},Integers     integers {a, b, c, n}
       {           ,        }                         such that:
        Tr[d=Abs@v]                                     |a|+|b|+|c|+|n| is minimal,
                    v.#==0<d                            satisfying the output conditions

Answer 4

R, 136 118 110 104 102 bytes

function(v,r=combn(rep(c(1:4e3,-4e3:-1),4),4),s=r[,order(colSums(abs(r)))])s[,!apply(s,2,`%*%`,v)][,1]

Try it online!

Searches solutions in space bounded by sum of absolute values of the inputs (as input is bounded, we simply take 4e3). This however makes the code run forever for the test cases.
This bound is sufficient, as a,b,c,d=-x,w,-z,y is a solution (courtesy of @loopy walt).

Here is a version (with lower fixed upper bound) that terminates in reasonable time: Try it online!.

Explanation:

function(v,          # take the input vector
m=4e3,               # calculate the upper bound for solutions
r=combn(             # combine potential solutions into one matrix (potentially with repetitions)
 rep(c(1:m,-m:-1),4) # get 4 times the range from -m to m excluding 0
 ,4)                 # combinations of length 4
,s=r[,order(         # sort the potential solutions
  colSums(abs(r))    # by sums of absolute values
  )]
)
s[,                  # take from that array
 !apply(s,2,`%*%`,v) # rows which dot-multiplied by input are zero
][,1]                # and the first one from that

Answer 5

05AB1E, 19 bytes

₄4*LD(«4ãʒ*O_}ΣÄO}н

Try it online!

Finishes in unreasonable time. Uses [-4000, 4000] as the bound. The code is verified with changing ₄4* with 3 for the first test case.

₄4*                     Push 4000  (1000*4)
   LD(«                 Make range of [-4000, 4000] (joining two seperate lists)
       4ã               All 4-combos (Cartesian power of 4)
         ʒ*O_}          Filter who dot producted with input cast 0
              ΣÄO}н     Sort by sum of abs and head (No min by builtin)

Answer 6

Jelly, 17 bytes

³²R;N$ṗ4ḋÐḟµAS$ÞḢ

Try it online! (Replaced 100 with 3 to actually have this finish in finite time)

³²                 -- 100² = 10000
  R                -- range from 1 to 10000
     $             -- apply the two-atom function to this range
   ;N              --   append the negative
      ṗ4           -- 4th cartesian power
        ḋÐḟ        -- discard all values which have a non-zero dot product with the input
            AS$Þ   -- sort the remaining 4-tuples by the sum of the absolute values
                Ḣ  -- get the first value

Answer 7

JavaScript (ES6), 156 bytes

Expects an array of 4 integers.

f=(A,n)=>(g=(a,s=n,q=n=>--n?g([...a,n],s-n)||q(n):0)=>a[3]?!s&&(h=i=>a.map((v,j)=>t+=A[j]*(b[j]=i>>j&1?v:-v),b=[t=0])|t?i--&&h(i):b)(15):q(n))([])||f(A,-~n)

Try it online!

Commented

f = (A, n) => (               // A[] = input / n = sum of absolute values
  g = (                       // g is a recursive function taking:
    a,                        //   a[] = partition of n in 4 integers
    s = n,                    //   s = n - sum of partition
    q = n =>                  //   q is another recursive function which
      --n ?                   //   works together with g to build the
        g([...a, n], s - n)   //   partition
        || q(n)               //   we stop as soon as a solution is found
      :                       //
        0                     //
  ) =>                        //
  a[3] ?                      // if the partition is complete:
    !s && (                   //   abort if s is not 0; otherwise:
      h = i =>                //     h is yet another recursive function:
        a.map((v, j) =>       //       for each value v at position j in a[]:
          t += A[j] * (       //         add to t: A[j] multiplied by
            b[j] =            //           b[j] which is
              i >> j & 1 ? v  //           either v or -v
                         : -v //           depending on the j-th bit of i
          ),                  //
          b = [t = 0]         //         start with t = 0 and b = [ 0 ]
        ) | t ?               //       end of map(); if t is not 0:
          i-- && h(i)         //         try again with i - 1
        :                     //       else:
          b                   //         success: return b[]
    )(15)                     //     initial call to h with i = 15
  :                           // else:
    q(n)                      //   invoke q to get the next partition term
)([])                         // initial call to g with a = []
|| f(A, -~n)                  // if failed, try again with n + 1

Answer 8

JavaScript (Node.js), 115 bytes

f=([h,...t],p=r=[],s=0,m=0,i)=>h?eval("for(i=-4e3;++i<4e3;)i&&f(t,[...p,i],i>0?s+i:s-i,m+i*h)"):m|s>r.s?r.p:r={p,s}

Try it online!

It works in theory. The tio link replaced 4e3 by 1e1 so it won't time out. It just need \$2.56×10^{10}\$ times current time usage to run. (So don't try it at home.) But as we are targeted to code-golf, why not make it a bit slower as long as it could be shorter.

f=(
[h,...t], // input array
p=r=[], // `p` is array of \$[a, b, c, d]\$
        // `r` is an object `{ p: number[], s: number }`
        // `r.p` is the best answer found, `r.s` is sum of abs of `r.p`
s=0, // sum of abs of `p`
m=0, // dot product of `p` and input vector
i // loop variable used in the function body
)=>
h?eval(`
for(i=-4e3;++i<4e3;)i&& // loop from -4000 to +4000 exclusive 0
f(t,[...p,i],i>0?s+i:s-i,m+i*h) // apply i
`):
m|s>r.s?
r.p: // output the best answer we ever found
r={p,s} // if dot product is 0 and current abs sum is less than prev one
        // we update the best answer we ever found

Answer 9

Python 3.8, 180 150 bytes

-30 bytes thanks to ovs.

import itertools as t;lambda*x,q=4000:min([s for s in t.product(*[range(-q,q)]*4)if sum(map(int.__mul__,x,s))==0<all(s)],key=lambda p:sum(map(abs,p)))

Try it online!

I am fairly certain there are some bytes to be shaved off. Here are some clever tricks that are close to working, but don't:

You can define the lambda function to be lambda q=8,*x, but there isn't a builtin prod function similar to sum that would allow us to take the product of the zip of (a,b,c,d) and x. You could try using math.prod perhaps.

You can try to use Python 3.8's walrus operator inside the list comprehension to avoid having to use (a,b,c,d) everywhere like this: min([s:=(a,b,c,d) for (a,b,c,d) in ... and all(map(bool, s)), but unfortunately this gives a NameError while inside a lambda (see PEP 572).

Answer 10

Wolfram Language (Mathematica), 83 84 bytes

MinimalBy[{a,b,c,d}/.Solve[a#+b#2+c#3+d#4==0<Abs@{a,b,c,d}<7!,Integers],Total@*Abs]&

How it works:

Solve[eqn, restrictions] solves the given equation, with the restrictions that Abs@{a,b,c,d}<7!, and that the solutions are all integers.

{a,b,c,d}/. removes the a->, b->, etc. from the solution set, leaving only the numbers

MinimalBy....Total@*Abs takes the solution set, and finds the solutions whose values are the smallest according to the criterion Total@*Abs, which was specified by the OP.

I've run it with an upper bound of Abs@{a,b,c,d}<20, which is sufficient to answer all test cases plus the bonus. That's the bound I've used on Try It Online!, to avoid a timeout.

However, for codegolf purposes, I've changed the upper bound to 7! (=5040), which adds a byte, and is sufficient to exceed the 4000 upper bound others have specified. Unfortunately, this exceeds the memory capacity of my machine, and thus I can't actually run the code with this bound.

Try It online!

Answer 11

Charcoal, 62 bytes

≔³ηＷ¬ⅉ«≔⁻…±ηη⟦⁰⟧ζ≦⊕ηＦζＦζＦζ«≔⟦κλμ⟧ε¿‹Σ↔εη«⊞ε⁻ηΣ↔ΣＥε×ν§θξ«⎚Ｉε

Try it online! Link is to verbose version of code. Not terribly efficient. Takes input as an array. Only outputs a solution with positive d (trivially the signs of a, b, c and d can always be flipped simultaneously). Explanation:

≔³η

Start with a sum of absolute values of 3 (which is impossible, but this gets incremented at the start of the loop).

Ｗ¬ⅉ«

Repeat until something has been printed.

≔⁻…±ηη⟦⁰⟧ζ

Create a range that more than suffices for the integers to test, but delete 0 from it.

≦⊕η

Increment the desired absolute sum.

ＦζＦζＦζ«

Loop a, b and c over the range.

≔⟦κλμ⟧ε

Make them into an array.

¿‹Σ↔εη

If the absolute sum of the array is less than the desired absolute sum, then:

⊞ε⁻ηΣ↔ε

Add positive d to give the desired absolute sum.

¿¬ΣＥε×ν§θξ«⎚Ｉε

If this list is a solution then clear any previous solution of the same sum and print it.

Answer 12

MathGolf, 20 bytes

◙╤ç■■m─gÆêm*Σ┌áűΣ├Þ

Unfortunately 'minimum by filter' isn't implemented yet despite being mentioned in the docs, otherwise the áűΣ├Þ could have been ╓űΣ for -2 bytes.

Try it online (with 10 instead of 4096 as range).

Explanation:

◙                    # Push 4096
 ╤                   # Pop and push a list in the range [-4096,4096]
  ç                  # Remove the 0 with a falsey filter
   ■                 # Take the cartesian product with itself to create pairs
    ■                # Do it again to create pairs of pairs
     m               # Map over each pair of pairs
      ─              #  Flatten it to a single quadruple-list
       g             # Filter this list of quadruplets by,
        Æ            # using the following five characters as inner code-block:
         ê           #  Push the inputs as integer-list
          m*         #  Multiply the values at the same positions in the two lists
            Σ        #  Sum it
             ┌       #  Check that it's equal to 0
              á      # Sort the remaining quadruplets by,
               Å     # using two characters as inner code-block:
                ±    #  Take the absolute value on each
                 Σ   #  And sum them together
                  ├  # After the sort-by, pop the first item from the list
                   Þ # Discard the list itself, only keeping this first item
                     # (after which the entire stack is output implicitly as result)

Answer 13

Ruby, 104 bytes

f=->a,z=4{r=[*-z..z]-[0];r.product(r,r,r).find{|w|z==w.sum(&:abs)&&w.zip(a).sum{|x,y|x*y}==0}||f[a,z+1]}

Try it online!