14
\$\begingroup\$

For another challenge I am writing, I need to verify that test cases are solveable with bounded integers. Specifically, I need to verify the following, for a non-empty array of integers A and an integer bit width n:

  1. All integers a in A satisfy -2**(n-1) <= a < 2**(n-1) (representable with n-bit two's complement integers).
  2. The length of A is less than 2**n.
  3. The sum of A satisfies -2**(n-1) <= sum(A) < 2**(n-1).
  4. All combinations of elements in A satisfy all of the above conditions.

Naturally, I've decided to outsource this problem to you!

Given an array of integers A and a positive integer bit width n, verify that A satisfies the conditions above.

Test Cases

[0, 0, 0], 2: True
[0, 0, 0, 0], 2: False (violates #2)
[1, 2, 3, 4, 5], 8: True
[1, 2, 3, 4, 5], 2: False (violates all conditions)
[1, 2, 3, 4, 5], 5: True
[-3, 4, 1], 4: True
[10, 0, -10], 4: False (violates #1 and #4)
[27, -59, 20, 6, 10, 53, -21, 16], 8: False (violates #4)
[-34, 56, 41, -4, -14, -54, 30, 38], 16: True
[-38, -1, -11, 127, -35, -47, 28, 89, -8, -12, 77, 55, 75, 75, -80, -22], 7: False (violates #4)
[-123, -85, 6, 121, -5, 12, 52, 31, 64, 0, 6, 101, 128, -72, -123, 12], 12: True

Reference Implementation (Python 3)

#!/usr/bin/env python3
from itertools import combinations
from ast import literal_eval


def check_sum(L, n):
  return -2**(n-1) <= sum(L) < 2**(n-1)


def check_len(L, n):
  return len(L) < 2**n


def check_elems(L, n):
  return all(-2**(n-1) <= a < 2**(n-1) for a in L)


A = literal_eval(input())
n = int(input())
OUTPUT_STR = "{}, {}: {}".format(A, n, "{}")

if not (check_elems(A, n) and check_len(A, n) and check_sum(A, n)):
  print(OUTPUT_STR.format(False))
  exit()

for k in range(1, len(A)):
  for b in combinations(A, k):
    if not check_sum(b, n):
      print(OUTPUT_STR.format(False))
      exit()

print(OUTPUT_STR.format(True))

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Sandbox \$\endgroup\$ – Mego Dec 13 '17 at 4:02
  • \$\begingroup\$ Must we handle the empty list? \$\endgroup\$ – Mr. Xcoder Dec 14 '17 at 5:18
  • \$\begingroup\$ @Mr.Xcoder No, I'll clarify. \$\endgroup\$ – Mego Dec 14 '17 at 5:19

11 Answers 11

7
\$\begingroup\$

Wolfram Language (Mathematica), 40 bytes

Max[x=2Tr/@Subsets@#,-x-1,Tr[1^#]]<2^#2&

Try it online!

Condition 1 is implied by checking condition 3 for all subsets, including the one-element ones. So we take the max of

  • twice the sum of each subset,
  • one less than twice the negative of the sum of each subset, and
  • the length of the whole set

and check if that's less than 2^#2 (where #2 is the bit-width input).

At the cost of only 6 more bytes, we can replace Subsets@# with GatherBy[#,Arg], which is much more efficient because it computes only the two worst-case subsets: the subset of all nonnegative values, and the subset of all negative values. (This works because Arg has a value of 0 on the former and π on the latter.)

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

Jelly, 19 bytes

ŒPS€;⁸L¤ḟ⁹’2*$ŒRṖ¤Ṇ

Try it online!

It suffices to check that mapped sum of powerset + length of set is in the required range.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think (though I am not sure) you can use ÆẸ instead of 2*$ (untested) \$\endgroup\$ – Mr. Xcoder Dec 13 '17 at 13:11
  • \$\begingroup\$ @Mr.Xcoder It does work. \$\endgroup\$ – user202729 Dec 14 '17 at 1:00
3
\$\begingroup\$

05AB1E, 13 12 11 bytes

Saved 1 byte thanks to Mr. Xcoder

æO·D±¹gMIo‹

Try it online!

Explanation

æ             # powerset of first input
 O            # sum each subset
  ·           # multiply each element by 2
   D          # duplicate
    ±         # bitwise negation of each element in the copy
     ¹g       # push length of first input
       M      # get the maximum value on the stack
        Io    # push 2**<second input>
          ‹   # compare
\$\endgroup\$
  • \$\begingroup\$ @Mr.Xcoder: Oh yeah, thanks! (I keep forgetting about ±) \$\endgroup\$ – Emigna Dec 13 '17 at 13:12
2
\$\begingroup\$

JavaScript (ES6), 75 63 58 bytes

a=>n=>!a.some(e=>(a.length|2*(e<0?l-=e:u+=e))>>n,u=0,l=-1)

The sum of any subset of a lies between the sums of the negative and nonnegative elements, so checking the two sums suffices for everything except case 2. Edit: Saved 12 17 bytes thanks to @Arnauld.

\$\endgroup\$
  • \$\begingroup\$ Far much better than my naive approach. :-) This could be shortened down to 61 bytes \$\endgroup\$ – Arnauld Dec 13 '17 at 11:41
  • \$\begingroup\$ Actually, we can just process the test within the loop for 56 bytes. \$\endgroup\$ – Arnauld Dec 13 '17 at 12:08
  • \$\begingroup\$ Hacked on ([-2,-1,-2])(3) \$\endgroup\$ – l4m2 Dec 13 '17 at 17:44
  • \$\begingroup\$ @l4m2 Good catch. Suggested fix (57 bytes) \$\endgroup\$ – Arnauld Dec 13 '17 at 18:10
  • \$\begingroup\$ @Arnauld The problem here is that [-2, -2], 3 should be true, no? \$\endgroup\$ – Neil Dec 13 '17 at 20:53
1
\$\begingroup\$

Jelly, 21 20 bytes

»0,«0$S€~2¦Ḥ;LṀ<2*Ɠ¤

Try it online!

Linear time complexity solution. Turns out that I over-estimated the time complexity

in The Nineteenth Byte, 2017-12-11 13-15-03Z, by user202729

@NewSandboxedPosts "Real" subset sum problem are much harder. This one can be done in linearithmic time...

because now I realize sorting the array is completely unnecessary.


Explanation:

»0,«0$S€~2¦Ḥ;LṀ<2*Ɠ¤    Main link. Example list: [-1, 0, 1]
»0                      Maximize with 0. Get [0, 0, 1]
  ,                     Pair with
   «0$                    minimize with 0. Get [-1, 0, 0]
      S€                Sum €ach. Get [1, -1]
        ~               Inverse
          ¦               at element
         2                2. (list[2] = ~list[2]) Get [-1, 2]
           Ḥ            Unhalve (double, ×2). Get [-2, 4]
            ;           Concatenate with
             L            Length (3). Get [-2, 4, 3]
              Ṁ         Maximum of the list (4).
               <   ¤    Still less than
                2         two
                 *        raise to the power of
                  Ɠ       eval(input())

\$\endgroup\$
  • \$\begingroup\$ Seems that ~2¦ can be ;~. EDIT: Done. \$\endgroup\$ – user202729 Dec 13 '17 at 9:39
  • \$\begingroup\$ @user202729 Wrong. Still, ;~$ will work. \$\endgroup\$ – user202729 Dec 13 '17 at 9:45
1
\$\begingroup\$

JavaScript (ES6), 114 bytes

Takes input in currying syntax (A)(n). Returns a boolean.

A=>n=>!(A.reduce((a,x)=>[...a,...a.map(y=>[x,...y])],[[]]).some(a=>(s=eval(a.join`+`),s<0?~s:s)>>n-1)|A.length>>n)

Test cases

let f =

A=>n=>!(A.reduce((a,x)=>[...a,...a.map(y=>[x,...y])],[[]]).some(a=>(s=eval(a.join`+`),s<0?~s:s)>>n-1)|A.length>>n)

console.log('[Truthy]')
console.log(f([0, 0, 0])(2))
console.log(f([1, 2, 3, 4, 5])(8))
console.log(f([1, 2, 3, 4, 5])(5))
console.log(f([-3, 4, 1])(4))
console.log(f([-34, 56, 41, -4, -14, -54, 30, 38])(16))
console.log(f([-123, -85, 6, 121, -5, 12, 52, 31, 64, 0, 6, 101, 128, -72, -123, 12])(12))

console.log('[Falsy]')
console.log(f([0, 0, 0, 0])(2)) // violates #2
console.log(f([1, 2, 3, 4, 5])(2)) // violates all conditions
console.log(f([10, 0, -10])(4)) // violates #1 and #4
console.log(f([27, -59, 20, 6, 10, 53, -21, 16])(8)) // violates #4
console.log(f([-38, -1, -11, 127, -35, -47, 28, 89, -8, -12, 77, 55, 75, 75, -80, -22])(7)) // violates #4

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

Pyth, 20 bytes

>EleS++KyMsMyQmt_dKl

Try it here!

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

Clojure, 121 117 bytes

#(let[l(int(Math/pow 2(dec %2)))](every?(set(range(- l)l))(cons(count %)(for[i(vals(group-by pos? %))](apply + i)))))

Well that was a bit dumb, splitting into positive and negative values is a lot better than sorting. Original, but surprisingly not much longer:

#(let[l(int(Math/pow 2(dec %2)))S(sort %)R reductions](every?(set(range(- l)l))(concat[(count S)](R + S)(R +(into()S)))))

This works by checking prefix sums of the sequence in ascending and descending order, I think it isn't necessary to generate all combinations of elements in A.

(into () S) is in effect same as (reverse S), as lists grow from the head. I couldn't figure out a way to use cons instead of concat when there are two lists to cons to. :/

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

Jelly, 15 bytes

ŒPS€Ḥ;~$;LṀl2<Ɠ

Try it online!

Explanation

ŒPS€Ḥ;~$;LṀl2<Ɠ ~ Monadic full program.

ŒP              ~ Powerset.
  S€            ~ The sum of each subset.
    Ḥ           ~ Double (element-wise).
     ;~$        ~ Append the list of their bitwise complements.
        ;L      ~ Append the length of the first input.
          Ṁ     ~ And get the maximum.
           l2   ~ Base-2 logarithm.
             <Ɠ ~ Is smaller than the second input (from stdin)?

Saved 1 byte thanks to caird coinheringaahing (reading the second input from STDIN instead of CLA).

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

Husk, 14 bytes

≥Lḋ▲ṁ§eLöa→DΣṖ

Going with brute force by looping over all sublists, since splitting into positive and negative parts takes more bytes. Try it online!

Explanation

≥Lḋ▲ṁ§eLöa→DΣṖ  Implicit inputs, say A=[1,2,3,4,5] and n=5
             Ṗ  Powerset of A: [[],[1],[2],[1,2],..,[1,2,3,4,5]]
    ṁ           Map and concatenate:
                  Argument: a sublist, say S=[1,3,4]
            Σ     Sum: 8
           D      Double: 16
          →       Increment: 17
        öa        Absolute value: 17
     §eL          Pair with length of S: [3,17]
                Result is [0,1,1,3,1,5,2,7,..,5,31]
   ▲            Maximum: 31
  ḋ             Convert to binary: [1,1,1,1,1]
 L              Length: 5
≥               Is it at most n: 1
\$\endgroup\$
0
\$\begingroup\$

Python 2, 72 71 70 bytes

def f(x,n):t=2*sum(k*(k<0)for k in x);max(2*sum(x)-t,~t,len(x))>>n>0>_

Output is via presence/absence of an error.

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.