35
\$\begingroup\$

The so-called Will Rogers phenomenon describes a way to tweak statistics by raising the average in two (multi)sets when one element is moved between the two sets. As a simple example, consider the two sets

A = {1, 2, 3}
B = {4, 5, 6}

Their arithmetic means are 2 and 5, respectively. If we move the 4 to A:

A = {1, 2, 3, 4}
B = {5, 6}

Now the averages are 2.5 and 5.5, respectively, so both averages have been raised through a simple regrouping.

As another example, consider

A = {3, 4, 5, 6} --> A = {3, 5, 6}
B = {2, 3, 4, 5} --> B = {2, 3, 4, 4, 5}

On the other hand, it's not possible to raise both averages for the sets

A = {1, 5, 9}
B = {4, 5, 7, 8}

The Challenge

Given two lists of non-negative integers, determine whether it is possible to raise both averages by moving a single integer from one list to the other.

The average of an empty list is not defined, so if one of the lists contains only one element, this element cannot be moved.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Input may be taken in any convenient string or list format.

You must not assume that the elements in each list are unique, nor that they are sorted. You may assume that both lists contain at least one element.

Output should be truthy if both averages can be raised by moving a single integer and falsy otherwise.

This is code golf, so the shortest answer (in bytes) wins.

Test Cases

Truthy:

[1], [2, 3]
[1, 2, 3], [4, 5, 6]
[3, 4, 5, 6], [2, 3, 4, 5]
[6, 5, 9, 5, 6, 0], [6, 2, 0, 9, 5, 2]
[0, 4], [9, 1, 0, 2, 8, 0, 5, 5, 4, 9]

Falsy:

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

Leaderboards

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

# Ruby, <s>104</s> <s>101</s> 96 bytes

<script>site = 'meta.codegolf'; postID = 5314; isAnswer = true; QUESTION_ID = 53913</script><script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)</code></pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>

\$\endgroup\$
  • \$\begingroup\$ As a mathematician and not a coder, I can't really address the challenge, but I am interested by the following question: If both averages can be raised by shifting some finite collection of integers (say five) from the one set to the other, does it always follow that both averages may be raised by shifting just one integer? Thus showing that the challenge really covers all the cases. \$\endgroup\$ – Trevor Richards Jul 28 '15 at 12:48
  • 3
    \$\begingroup\$ @TrevorRichards I think the last falsy test case covers this. You could move a 1 and 9 over, which would raise both averages, but you can't do so by moving a single one. \$\endgroup\$ – Martin Ender Jul 28 '15 at 12:52
  • \$\begingroup\$ @TrevorRichards In general, if the sets A & B have averages a & b with a < b then both averages can be raised if there is a subset C of B which has average c such that a < c < b. On the other hand, if you require all elements moved from B to A to have values < b then your hypothesis would be true. \$\endgroup\$ – Alchymist Aug 3 '15 at 12:35

13 Answers 13

10
\$\begingroup\$

Pyth, 29 28 26 24 bytes

Thanks to @Jakube for saving me 3 bytes with .p and L.

Very simple, checks if any elements in list 2 are greater than mean of list 1 and less than mean of list 2, then repeats with list 1 and list 2 switched.

Lcsblbff&>YyhT<YyeTeT.pQ

Prints an a non-empty list for truthy, and [] for falsey.

L                    Define y(b). Pyth has no builtin for mean
 c                   Float div
  sb                 Sum of b
  lb                 Length of b
f        .pQ         Filter all permutations of input
 f     eT            Filter the last element of the filter var
  &                  Logical and
   >Y                Inner filter var greater than
    y                Call the mean function we defined earlier
     hT              First element of outer filter var
   <Y                Inner filter var less than
    y                Mean of
     eT              Last element of outer filternvar

Try it online here.

Test Suite.

\$\endgroup\$
7
\$\begingroup\$

Python 3, 74

lambda*L:any(sum(C)/len(C)>x>sum(D)/len(D)for(C,D)in[L,L[::-1]]for x in C)

Takes two lists as input. Checks if the first list has an element that's bigger than it's average but smaller than the other one's. Then, does the same for the two inputs swapped. Having a two-layer list comprehension was shorter than defining a separate function to try the two orders (82):

f=lambda A,B:any(sum(A)/len(A)>x>sum(B)/len(B)for x in A)
lambda A,B:f(A,B)|f(B,A)
\$\endgroup\$
7
\$\begingroup\$

Haskell, 58 57

x%y=any(\n->(\g->g x<0&&g y>0)$sum.map(n-))x
x?y=x%y||y%x

we can check if we enlarge or lower the average by checking whether the element to remove or include is bigger or smaller than the average.

we can check that by checking if the average is smaller or bigger than an element by removing that element from the array, and checking whether the new array's average is negative or positive, which in turn is just as checking whether the sum is positive or negative.

checking that is put very simply as sum.map(-n+).

\$\endgroup\$
6
\$\begingroup\$

Mathematica, 49 47 bytes

m=Mean;MemberQ[#2,x_/;m@#<x<m@#2]&@@#~SortBy~m&

Evaluates to a pure function that expects input in the form {list1, list2}.

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

APL, 45 40 bytes

Saved 5 bytes thanks to Moris Zucca!

{U←∊⍺⍵[⊃⍒M←(+/÷≢)¨⍺⍵]⋄1∊(U<⌈/M)∧(U>⌊/M)}

This creates an unnamed dyadic function that accepts arrays on the left and right and returns 1 or 0.

{
  M←(+/÷≢)¨⍺⍵          ⍝ Compute the mean of each array
  U←∊⍺⍵[⊃⍒M]           ⍝ Get the array with the larger mean
  1∊(U<⌈/M)∧(U>⌊/M)    ⍝ Any smaller mean < U < larger mean
}

You can try it online.

\$\endgroup\$
  • 1
    \$\begingroup\$ you can write the mean as: (+/÷≢) \$\endgroup\$ – Moris Zucca Jul 28 '15 at 8:48
  • \$\begingroup\$ @MorisZucca Thanks! Edited to use your suggestion. \$\endgroup\$ – Alex A. Jul 28 '15 at 14:25
3
\$\begingroup\$

R, 66 52 Bytes

As an unnamed function, that accepts 2 vectors. Got rid of some spurious whichs.

function(a,b)any(a<(m=mean)(a)&a>m(b),b<m(b)&b>m(a))

Tests

> f=
+ function(a,b)any(a<(m=mean)(a)&a>m(b),b<m(b)&b>m(a))
> f(c(1), c(2, 3))
[1] TRUE
> f(c(1, 2, 3), c(4, 5, 6))
[1] TRUE
> f(c(3, 4, 5, 6), c(2, 3, 4, 5))
[1] TRUE
> f(c(6, 5, 9, 5, 6, 0), c(6, 2, 0, 9, 5, 2))
[1] TRUE
> f(c(0, 4), c(9, 1, 0, 2, 8, 0, 5, 5, 4, 9))
[1] TRUE
> 
> f(c(1), c(2))
[1] FALSE
> f(c(2, 4), c(5))
[1] FALSE
> f(c(1, 5), c(2, 3, 4, 5))
[1] FALSE
> f(c(2, 1, 2, 3, 1, 3), c(5, 1, 6))
[1] FALSE
> f(c(4, 4, 5, 2, 4, 0), c(9, 2, 10, 1, 9, 0))
[1] FALSE
> 
\$\endgroup\$
3
\$\begingroup\$

SAS/IML, 67

start m(a,b);return((a>b[:]&&a<a[:])||(b>a[:]&&b<b[:]))[<>];finish;

It uses subscript reduction operators to get the answer, returning 0 if no element is found that matches the requirements or 1 if one is found.

Non-golfed, here I return the actual value itself using matrix multiplication:

proc iml;
  b={1 2 3 4 5 6 7 8 9 };
  a={2 3 4 5 6};
  start m(a,b);
  return (a#(a>b[:] && a < a[:]) || b#(b>a[:] && b < b[:]))[<>];
  finish;

  z= m(a,b);
  print z;
quit;

Tests:

%macro test(a,b,n);
  z&n=m({&a},{&b});
  print z&n;
%mend test;

proc iml;
  b={1 2 3 4 5 };
  a={2 3 4 5 6 7};
start m(a,b);return((a>b[:]&&a<a[:])||(b>a[:]&&b<b[:]))[<>];finish;

* True;
 %test(1,2 3,1);
 %test(1 2 3,4 5 6,2);
 %test(3 4 5 6, 2 3 4 5,3);
 %test(6 5 9 5 6 0,6 2 0 9 5 2,4);
 %test(0 4, 9 1 0 2 8 0 5 5 4 9,5);
* False;
 %test(1,2,6);
 %test(2 4, 5,7);
 %test(1 5, 2 3 4 5,8);
 %test(2 1 2 3 1 3, 5 1 6,9);
 %test(4 4 5 2 4 0, 9 2 10 1 9 0,10);

quit;

(Condensed for readability)

z1 1

z2 1

z3 1

z4 1

z5 1

z6 0

z7 0

z8 0

z9 0

z10 0

\$\endgroup\$
2
\$\begingroup\$

Python 2.7, 102 98 96

lambda p:any([1for i in 0,1for e in p[i]if g[i^1]<e<g[i]]for g in[[sum(l)*1./len(l)for l in p]])

Takes the input as array of the 2 inputs and returns boolean.
The logic is -find the avg of the 2 lists, then find an element such that it's less than the avg of its own list and but greater than the average of the other list.

Testing it for the given inputs is demo-ed here

\$\endgroup\$
  • 2
    \$\begingroup\$ You can do *1. instead of *1.0 to save a byte. Alternatively, if you do this in Python 3, division will return a float by default, so you wouldn't need that multiplication at all. (I don't think you'd have to change your code at all to use Python 3.) \$\endgroup\$ – mathmandan Jul 27 '15 at 22:24
  • \$\begingroup\$ @mathmandan Saved me a byte. Thanks :) \$\endgroup\$ – Kamehameha Jul 27 '15 at 22:56
  • \$\begingroup\$ You can make it an anonymous function by removing f= and change in[0,1]for to in 0,1for. Since you're actually at 101 bytes, this brings you down to 98. \$\endgroup\$ – Kade Jul 28 '15 at 1:24
  • \$\begingroup\$ @Vioz- Thanks, didn't know I could do that :) \$\endgroup\$ – Kamehameha Jul 28 '15 at 5:07
2
\$\begingroup\$

CJam, 28 bytes

{{_:+1$,d/\+}%$~(m],@0=i)>&}

This is an anonymous function that pops a two-dimensional array from the stack and leaves an array of movable elements in return.

In supported browsers, you can verify all test cases at once in the CJam interpreter.

Test cases

Code

q~]{{_:+1$,d/\+}%$~(m],@0=i)>&}%:p

Input

[[1] [2 3]]
[[1 2 3] [4 5 6]]
[[3 4 5 6] [2 3 4 5]]
[[6 5 9 5 6 0] [6 2 0 9 5 2]]
[[0 4] [9 1 0 2 8 0 5 5 4 9]]
[[1] [2]]
[[2 4] [5]]
[[1 5] [2 3 4 5]]
[[2 1 2 3 1 3] [5 1 6]]
[[4 4 5 2 4 0] [9 2 10 1 9 0]]

Output

[2]
[4]
[4]
[5]
[4]
""
""
""
""
""

How it works

If A and B are the arrays and avg(A) ≤ avg(B) we simply check if B ∩ {⌊avg(A)⌋+1, …, ⌈avg(B)⌉-1} is non-empty. Any element in this intersection could be moved from B to A to increase both averages.

{          }%              e# For each of the arrays:
 _:+                       e#   Compute the sum of its elements.
    1$,                    e#   Compute its length.
       d/                  e#   Cast to Double and perform division.
         \+                e#   Prepend the computed average to the array.
             $             e# Sort the arrays (by the averages).
              ~            e# Dump both arrays on the stack.
               (           e# Shift out the higher average.
                m]         e# Round up to the nearest integer b.
                  ,        e# Push [0 ... b-1].
                   @0=     e# Replace the array with lower average by its average.
                      i)   e# Round down to the nearest integer a and add 1.
                        >  e# Skip the first a integer of the range.
                           e# This pushes [a+1 ... b-1].
                         & e# Intersect the result with the remaining array.

This pushes the array of all elements of the array with higher average that can be moved to increase both averages. This array is empty/falsy if and only if no elements can be moved to achieve this result.

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

Ruby, 86

A=->x{x.reduce(0.0,:+)/x.size}
F=->q{b,a=q.sort_by{|x|A[x]};a.any?{|x|x<A[a]&&x>A[b]}}

Takes as input an array containing the two arrays.

Tries to find a sub average item from the group with the higher average that is greater than the average of the other group.

Test: http://ideone.com/444W4U

\$\endgroup\$
  • \$\begingroup\$ Started working on this without noticing there was already a Ruby solution, ended up with something very similar but it nets two fewer characters by having the function assume the first list is 'better', then call itself the other way around. f=->a,s=1{i,j=a.map{|x|x.inject(0.0,:+)/x.size};a[0].any?{|y|i>y&&j<y}||s&&f[b,a,p]} \$\endgroup\$ – histocrat Jul 27 '15 at 22:53
  • \$\begingroup\$ @histocrat Nice approach! I get a NameError regarding the variable b though. I think the recursive call should be something like f[a.rotate,p]. \$\endgroup\$ – Cristian Lupascu Jul 28 '15 at 7:39
  • 1
    \$\begingroup\$ Oops, so that's how I got a better score, by cheating. \$\endgroup\$ – histocrat Jul 28 '15 at 12:40
1
\$\begingroup\$

Matlab, 54

Using an anonymous function:

f=@(A,B)any([B>mean(A)&B<mean(B) A>mean(B)&A<mean(A)])

Examples:

>> f=@(A,B)any([B>mean(A)&B<mean(B) A>mean(B)&A<mean(A)])
f = 
    @(A,B)any([B>mean(A)&B<mean(B),A>mean(B)&A<mean(A)])

>> f([1 2 3],[4 5 6])
ans =
     1

>> f([3 4 5 6],[2 3 4 5])
ans =
     1

>> f([1 5 9],[4 5 7 8])
ans =
     0
\$\endgroup\$
1
\$\begingroup\$

C#, 104

bool f(int[]a,int[]b){double i=a.Average(),j=b.Average();return a.Any(x=>x<i&&x>j)||b.Any(x=>x<j&&x>i);}

Example Calls:

f(new []{1,2,3}, new []{4,5,6})
f(new []{1}, new []{2, 3})
f(new []{1, 2, 3}, new []{4, 5, 6})
f(new []{3, 4, 5, 6}, new []{2, 3, 4, 5})
f(new []{6, 5, 9, 5, 6, 0}, new []{6, 2, 0, 9, 5, 2})
f(new []{0, 4}, new []{9, 1, 0, 2, 8, 0, 5, 5, 4, 9})

f(new []{1}, new []{2})
f(new []{2, 4}, new []{5})
f(new []{1, 5}, new []{2, 3, 4, 5})
f(new []{2, 1, 2, 3, 1, 3}, new []{5, 1, 6})
f(new []{4, 4, 5, 2, 4, 0}, new []{9, 2, 10, 1, 9, 0})
\$\endgroup\$
0
\$\begingroup\$

C++14, 157 bytes

As unnamed lambda, returns by the last parameter r. Assumes A,B to be containers like vector<int> or array<int,>.

[](auto A,auto B,int&r){auto m=[](auto C){auto s=0.;for(auto x:C)s+=x;return s/C.size();};r=0;for(auto x:A)r+=x<m(A)&&x>m(B);for(auto x:B)r+=x<m(B)&&x>m(A);}

Ungolfed:

auto f=
[](auto A,auto B,int&r){
  auto m=[](auto C){
   auto s=0.;
   for(auto x:C) s+=x;
   return s/C.size();
  };
  r=0;
  for (auto x:A) r+=x<m(A)&&x>m(B);
  for (auto x:B) r+=x<m(B)&&x>m(A);
}
;

Usage:

int main() {
  std::vector<int>
    a={1,2,3}, b={4,5,6};
  //  a={1,5,9}, b={4,5,7,8};
  int r;
  f(a,b,r);
  std::cout << r << std::endl;
}
\$\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.