13
\$\begingroup\$

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
\$\endgroup\$
15
  • 4
    \$\begingroup\$ Please, run your questions though sandbox before posting. \$\endgroup\$
    – pajonk
    Oct 23 at 9:46
  • 1
    \$\begingroup\$ @pajonk OK. Do you see any problems with this question? \$\endgroup\$
    – Giraffe
    Oct 23 at 9:48
  • 9
    \$\begingroup\$ You should post in your challenge that the sum of absolute values means \$|a|+|b|+|c|+|d|\$ for clarity, I didn't know what meant until I read the comment. That's why, as @pajonk says, you should always post to the sandbox first - you don't know what's unclear until you get feedback. \$\endgroup\$
    – Noodle9
    Oct 23 at 11:36
  • 4
    \$\begingroup\$ Suggested test case: 3 14 62 74 (you'll find [ -2, 3, 3, -3 ] if you just try all values between -m and m and increase m until a solution is found; but [ -2, 4, -2, 1 ] is better). \$\endgroup\$
    – Arnauld
    Oct 23 at 18:41
  • 1
    \$\begingroup\$ @ovs Just one please. It can be any one of them. \$\endgroup\$
    – Giraffe
    Oct 24 at 14:19

13 Answers 13

4
\$\begingroup\$

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.

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

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!

\$\endgroup\$
2
  • \$\begingroup\$ That is very fast! \$\endgroup\$
    – Giraffe
    Oct 24 at 11:13
  • 2
    \$\begingroup\$ @Anush That is PyPy's fault ;). With the standard Python interpreter this is comparable to Arnaulds answer in performance \$\endgroup\$
    – ovs
    Oct 24 at 11:25
4
\$\begingroup\$

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
\$\endgroup\$
5
  • 2
    \$\begingroup\$ As a,b,c,d=-x,w,-z,y is a solution you could use |w|+|x|+|y|+|z| as a bound. \$\endgroup\$
    – loopy walt
    Oct 23 at 18:53
  • \$\begingroup\$ The TIO link doesn't seem to give the right answer for 78, -75, 24, 33. Does it work for you? \$\endgroup\$
    – Giraffe
    Oct 23 at 19:17
  • \$\begingroup\$ @Anush, you're looking at the second link, right? It looks ok to me (having in mind that the the test case in question is in strange order). In the first link it's commented out. \$\endgroup\$
    – pajonk
    Oct 23 at 19:23
  • \$\begingroup\$ @pajonk ah yes, Why bother with the first link? \$\endgroup\$
    – Giraffe
    Oct 23 at 19:25
  • 1
    \$\begingroup\$ @Anush, the first link is to the solution (not terminating in TIO for the test cases). The second link has a modification that allows test cases to run on TIO. \$\endgroup\$
    – pajonk
    Oct 23 at 19:27
3
\$\begingroup\$

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

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
\$\endgroup\$
3
  • \$\begingroup\$ I look forward to learning how you have done this! \$\endgroup\$
    – Giraffe
    Oct 23 at 19:59
  • \$\begingroup\$ @Anush The method is essentially the same as Redwolf's. \$\endgroup\$
    – Arnauld
    Oct 23 at 20:09
  • \$\begingroup\$ You seem to be able to solve the bonus question though. \$\endgroup\$
    – Giraffe
    Oct 23 at 20:14
2
\$\begingroup\$

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)
\$\endgroup\$
3
  • 1
    \$\begingroup\$ œε4£}Ù only produces unique lists which means the second test case doesn't work. Replacing this part with fixes this and saves a few bytes. And IøP can be shortened to * making use of implicit input and implicit vectorization. \$\endgroup\$
    – ovs
    Oct 24 at 7:11
  • \$\begingroup\$ @ovs thanks! I didn't knew about the cartesian power builtin too \$\endgroup\$
    – wasif
    Oct 24 at 7:24
  • 1
    \$\begingroup\$ The ₄4* (4000) can be žD (4096) for -1 byte. Also, your explanation is slightly incorrect, since LD(« isn't the full [-4000,4000] range, since it's skipping the 0 (which is good, but if it was the actual range you say in the explanation, it could have been D(Ÿ instead, which it can't since that includes 0). \$\endgroup\$ Oct 24 at 16:28
2
\$\begingroup\$

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

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

\$\endgroup\$
4
  • \$\begingroup\$ The walrus operator just fine in a lambda, but the condition is evaluated which is why the assignment has to be there. And all(map(bool,x) is equivalent to all all(x): Try it online! \$\endgroup\$
    – ovs
    Oct 24 at 10:28
  • \$\begingroup\$ While not the prettiest code, int.__mul__ works to take the product of two integers, which helps with your first idea: tio.run/##NY3tCoIwFEBf5f7cZIqVRVh7EhOZ6Wq0j@vuBH16E6J/… \$\endgroup\$
    – ovs
    Oct 24 at 10:32
  • \$\begingroup\$ Ah, that makes sense. Nice golf! \$\endgroup\$ Oct 24 at 17:29
  • \$\begingroup\$ Solves the bonus in 2 seconds if you set the range to 20. \$\endgroup\$
    – Giraffe
    Oct 24 at 18:04
2
\$\begingroup\$

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!

\$\endgroup\$
8
  • \$\begingroup\$ Does this solve the bonus question too? \$\endgroup\$
    – Giraffe
    Oct 24 at 11:47
  • \$\begingroup\$ @Anush Yes; I'll add a tio.run link tomorrow; I need to get some sleep! \$\endgroup\$
    – theorist
    Oct 24 at 11:55
  • 1
    \$\begingroup\$ Do I understand correctly, that you assume a,b,c,d to be bounded by 9? Do you have a proof for that? That would shave off some bytes from other answers too. \$\endgroup\$
    – pajonk
    Oct 24 at 13:47
  • \$\begingroup\$ @pajonk Yes, that's my assumption. I don't have a proof. Instead, I couldn't find any examples for which it failed (other than the bonus question). If that's not acceptable (and I understand why it wouldn't be), can you tell me if there is an upper bound for {a,b,c,d} that can be asserted by inspection? If so, I could modify my answer to meet that. I assume I wouldn't need more than one additional byte, since it shouldn't be more than x!, where x<=9. \$\endgroup\$
    – theorist
    Oct 24 at 20:10
  • 1
    \$\begingroup\$ Definitely 4000 is sufficient, and several answers use it (see my answer for explanation). \$\endgroup\$
    – pajonk
    Oct 24 at 20:14
1
\$\begingroup\$

Charcoal, 62 bytes

≔³ηW¬ⅉ«≔⁻…±ηη⟦⁰⟧ζ≦⊕ηFζFζFζ«≔⟦κλμ⟧ε¿‹Σ↔εη«⊞ε⁻ηΣ↔ΣEε×ν§θξ«⎚Iε

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

W¬ⅉ«

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.

FζFζFζ«

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.

¿¬ΣEε×ν§θξ«⎚Iε

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

\$\endgroup\$
1
\$\begingroup\$

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

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

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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