Unsorted majorization of two lists

Question

Definition

A vector a containing n elements is said to majorize or dominate a vector b with n elements iff for all values k such that 1 ≤ k ≤ n, the sum of the first element of a^↓ through the kth element of a^↓ is greater than or equal to the sum of the first through kth elements of b^↓, where v^↓ represents the vector v sorted in descending order.

That is,

                          a_1 >= b_1
                    a_1 + a_2 >= b_1 + b_2
              a_1 + a_2 + a_3 >= b_1 + b_2 + b_3
                              ...
      a_1 + a_2 + ... + a_n-1 >= b_1 + b_2 + ... + b_n-1
a_1 + a_2 + ... + a_n-1 + a_n >= b_1 + b_2 + ... + b_n-1 + b_n

where a and b are sorted in descending order.

For the purpose of this challenge, we will be using a slight generalization of majorization: we will say a list is an unsorted majorization of another if all of the above inequalities are true without sorting a and b. (This is, of course, mathematically useless, but makes the challenge more interesting.)

Challenge

Given an input of two distinct lists a and b of integers in the range 0 through 255 (inclusive), both lists of length n ≥ 1, output whether the first list unsorted-majorizes the second (a > b), the second unsorted-majorizes the first (b > a), or neither.

You may optionally require the length of the two lists to be provided as input. The output must always be one of three distinct values, but the values themselves may be whatever you want (please specify which values represent a > b, b > a, and neither in your answer).

Test cases for a > b:

[255] [254]
[3,2,1] [3,1,2]
[6,1,5,2,7] [2,5,4,3,7]

Test cases for b > a:

[9,1] [10,0]
[6,5,4] [7,6,5]
[0,1,1,2,1,2] [0,1,2,1,2,1]

Test cases for no majorization:

[200,100] [150,250]
[3,1,4] [2,3,3]
[9,9,9,9,9,0] [8,8,8,8,8,9]

Answer 1

Jelly, 10 8 6 bytes

2 bytes thanks to @orlp.

2 bytes thanks to @Dennis.

_+\ṠQS

Try it online!

1 for a>b, -1 for a<b, 0 for no majorization.

_+\ṠQS

_       Difference (vectorized)
 +\     Cumulative sum.
   Ṡ    Sign of every difference
    Q   Deduplicate
     S  Sum

If there were both 1 and -1 present (some cumulative sums are bigger, some smaller), then the last step would produce 0.

Answer 2

ngn/apl, 11 bytes

{+/∪×+\⍺-⍵}

Based on the method in @Leaky Nun's answer.

Given two lists A and B, find the difference between each value elementwise, or let C = A - B. Then, find the cumulative sums of C and take the sign of each. The sum of the unique sign values will be the result. If A > B, the result is 1, if A < B the result is -1, and if there is no majority the result is 0.

Try it online.

Answer 3

Julia, 30 bytes

a^b=sum(sign(cumsum(a-b))∪0)

Saved 4 bytes thanks to @Dennis!

Answer 4

Python 3.5, 85 bytes:

lambda*e:[all(sum(g[:k])>=sum(h[:k])for k in range(1,-~len(h)))for g,h in[e,e[::-1]]]

An anonymous lambda function. Returns [True,False] if a>b, [False,True] if b>a, or [False,False] if neither of those are true. I hope this is okay.

Try It Online! (Ideone)

Answer 5

Cheddar, 118 114 bytes

n->[n.map(i->i[0]-i[1]).map((j,k,l)->l.slice(0,k+1).sum).map(i->i>0?1:i<0?-1:0)].map(j->j has 1?j has-1?0:1:-1)[0]

Basically a port of my Jelly answer.

The fact that scope inside function is broken causing inability to define variable inside function means that I would need to do [xxx].map(i->yyy)[0] instead of var a=xxx;yyy.

Takes transposed array as input.

n->[n
.map(i->i[0]-i[1])                     Difference (vectorized)
.map((j,k,l)->l.slice(0,k+1).sum)      Cumulative sum.
.map(i->i>0?1:i<0?-1:0)]               Sign of every difference
.map(j->j has 1?j has-1?0:1:-1)[0]     Deduplicate and Sum

Answer 6

Python 2, 73 bytes

a,=b,=r={0}
for x,y in zip(*input()):a+=x;b+=y;r|={cmp(a,b)}
print sum(r)

Test it on Ideone.

Answer 7

Ruby, 72 59 bytes

Returns 1 for a>b, -1 for a<b, 0 for neither.

-13 bytes from cribbing the sum trick off of @Dennis in their Python answer

Try it online!

->a,b{x=y=0;a.zip(b).map{|i,j|(x+=i)<=>y+=j}.uniq.inject:+}

Answer 8

Python 2, 59 bytes

t=r=0
for x,y in zip(*input()):t+=x-y;r|=cmp(t,0)%3
print r

Outputs:

• 1 for a>b
• 2 for b>a
• 3 for neither

Iterates through the list, tracking the running sum t of differences. The number s tracks what signs have been seen as a two-bit number r: positives in the right bit and negatives in the left bit. This happens via cmp(t,0)%3, which gives

• t>0 → +1 → 1
• t==0 → 0 → 0
• t<0 → -1 → 2

Taking the or of this and the current value of r updates the 2 bits with or, with zero values having no effect.

Answer 9

Javascript (using external library-Enumerable) (123 bytes)

(a,b)=>(z=(c,d)=>_.Range(1,c.length).All(x=>_.From(c).Take(x).Sum()>=_.From(d).Take(x).Sum()))(a,b)==z(b,a)?0:(z(a,b)?1:-1)

Link to lib: https://github.com/mvegh1/Enumerable

Code explanation: Pass in vector a and b, create global function z. z will begin by creating an array of integers from 1, for a count of a.length. .All will verify that the predicate is true for every member belonging to a. That predicate says to load a as an enumerable, take a count of that enumerable equivalent to the current iteration value of that range we made, and sum that up. Check if that >= the same logic from array "b". So, we call z in the order of (a,b), and compare that to the order of (b,a)...if equal we return 0 to signify there is no major. Otherwise, we return 1 if (a,b) is true, else -1