19
\$\begingroup\$

Related.

Given a list of 3 or more positive integers, remove every number X for which there is another number Y in the list and the average of X and Y is also in the list. In other words, if X, Y, and the average of X and Y are all in the input, neither X nor Y should appear in the output.

Note: Pairs of numbers are not successively removed from the list, rather all at once. This avoids ambiguity. A pair of numbers whose average is in the list will be removed even if one or both of the numbers are already part of another such pair.

The average of two numbers is their sum divided by two.

Examples:

input => output
explanation

[1, 2, 3] => [2]
1 and 3 are removed because their average (2) is in the list.

[1, 2, 3, 4] => []
1 and 3 are removed because their average (2) is in the list,
2 and 4 are removed because their average (3) is in the list.

[1, 3, 4, 5] => [4]
1 and 5 are removed because their average (3) is in the list,
3 and 5 are removed because their average (4) is in the list.

[1, 5, 10, 20, 40] => [1, 5, 10, 20, 40]
No numbers are removed; No pair of numbers also has their average in the list.

[1, 5, 6, 10] => [1, 5, 6, 10]

[1, 2, 3, 4, 10, 52, 100, 200] => [10, 52, 200]

[1, 2, 3, 5, 8, 13, 21, 34] => []

You may assume numbers are given in ascending order with no duplicates.

Shortest code wins.

\$\endgroup\$
13
  • \$\begingroup\$ why is 100 removed in 1, 2, 3, 4, 10, 52, 100, 200? \$\endgroup\$
    – Jonah
    Jun 23 at 18:05
  • 2
    \$\begingroup\$ @Jonah (100+4)/2 = 52 \$\endgroup\$ Jun 23 at 18:08
  • 2
    \$\begingroup\$ Ah, now I got it, it's not about removing pairs successively, but about removing all such elements at once, thanks! \$\endgroup\$ Jun 23 at 19:24
  • 1
    \$\begingroup\$ @GammaFunction you can assume the numbers are given with no duplicates in ascending order \$\endgroup\$ Jun 24 at 12:36
  • 1
    \$\begingroup\$ So in 1,2,3,4,5 all numbers are removed, correct? \$\endgroup\$ Jun 24 at 13:59

23 Answers 23

6
\$\begingroup\$

R, 48 46 bytes

\(v)v[!v%in%combn(v,2)[,combn(v,2,mean)%in%v]]

Attempt This Online!

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

Jelly, 9 7 bytes

+HfḊʋÐḟ

Try it online!

     Ðḟ    Remove elements for which
+          that element plus each element of the list
 H         halved
   Ḋ       has more than one element
  f ʋ      after being filtered to only elements of the original list.
\$\endgroup\$
6
\$\begingroup\$

K (ngn/k), 17 bytes

{x^/x+(x-\:x)^'0}

Try it online!

Dang, Jonah's solution translates very well to K.

{x^/x+(x-\:x)^'0}
      (x-\:x)      self difference table
             ^'0   remove zeros from each row
    x+             add i-th item of x to i-th row of matrix above
 x^/               seeded reduce: remove all numbers that appear
                   in the matrix from x

K (ngn/k), 22 bytes

{((*>^/^\+\2#,x-)')_x}

Try it online!

I think this idea is not touched well yet (or at least not explained well in other answers).

The idea here is: given an element E of list X, E is to be removed from the result if:

  • there exists two other elements E2 and E3 of X such that E2 = (E + E3)/2
  • ⇔ E, E2, E3 forms an arithmetic progression
  • ⇔ E2 = E + k, E3 = E + 2k for some nonzero k
  • ⇔ X-E (elementwise) contains k and 2k for some nonzero k
{((*>^/^\+\2#,x-)')_x}
{((             )')_x}  apply to each element E and keep those that gives 0
              x-    L = X-E
         +\2#,      (L, 2L)
     ^/^\           set intersection of L and 2L
   *>      first of grade down (index of max)
           all k's (including zero) are found in increasing order;
           index of max is nonzero iff there exist some nonzero k's
\$\endgroup\$
1
  • \$\begingroup\$ Does the first solution need the (...)^'0? Or can the answer just be {x^/x+x-\:x} \$\endgroup\$
    – coltim
    4 hours ago
5
\$\begingroup\$

J, 27 22 15 14 bytes

-.&,~:/~*+:-/]

Try it online!

Consider 1 3 4 5.

  • +:-/] We note that if c = (a + b)/2, then 2c - a = b. So we can double the input, and create a subtraction table between that doubled input and the original input:

    1 _1 _2 _3
    5  3  2  1
    7  5  4  3
    9  7  6  5
    

    Now any element in that table not on the diagonal is the a or b giving rise to a c in the original list, and thus invalid.

  • ~:/~* So zero out the diagonal:

    0 _1 _2 _3
    5  0  2  1
    7  5  0  3
    9  7  6  0
    
  • -.&, Flatten, and then remove all the table elements from the original list:

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

Haskell, 39 bytes

f a=[x|x<-a,[1]==[1|z<-a,elem(2*z-x)a]]

Attempt This Online!

ovs and Wheat Wizard each saved a byte. Thanks!

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

JavaScript (ES6), 50 bytes

a=>a.filter(x=>!a.some(y=>x-y&&a.includes(y*2-x)))

Try it online!

Commented

a =>            // a[] = input
a.filter(x =>   // for each value x in a[]:
  !a.some(y =>  //   test whether there is a value y in a[]:
    x - y &&    //     which is not equal to x
    a.includes( //     and is the average of x and
      y * 2 - x //     another value 2y - x that exists in a[]
    )           //
  )             //   end of some()
)               // end of filter()
\$\endgroup\$
4
\$\begingroup\$

K (ngn/k), 20 bytes

{x^/a*~=#a:-x-\:2*x}

Try it online!

Switched to @Jonah's approach.

-1 byte thanks to @ovs!

Explanation

Input is x.

  • a:-x-\:2*x subtraction table of 2x - x stored as a
  • a*~=# multiply a by inverse of eye of a (i.e. zero out a's diagonals)
  • x^/ remove table elements from x
\$\endgroup\$
1
  • 1
    \$\begingroup\$ A assignment is shorter than the lambda: {x^/a*~=#a:(2*x)-\:x} \$\endgroup\$
    – ovs
    Jun 24 at 8:37
3
\$\begingroup\$

Scala, 52 bytes

s=>s.filter(i=>s.forall(j=>i==j|s.forall(_*2!=i+j)))

Try it online!

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

Husk, 12 10 bytes

f(εn¹Mo½+¹

Try it online!

f(          )  # filter the input to keep only elements that satisfy:
         ½+    # half the sum  
       Mo  ¹   # with each other element of the input 
    ε          # has only 1 element
     n¹        # shared with any elements of the input
\$\endgroup\$
3
\$\begingroup\$

Vyxal, 9 7 bytes

'?+½?↔₃

Try it Online or verify all test cases.

-2 bytes by porting Unrelated String's Jelly answer

How?

'?+½?↔₃
'       # Filter for:
 ?+     #  Add the input (vectorizes)
   ½    #  Halve each
    ?↔  #  Remove elements that are not in the input
      ₃ #  Is the length equal to 1?
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 10 5 bytes

ʒ+;Ãg

Byte-count halved thanks to @Steffan by porting @UnrelatedString's Jelly answer.

Try it online or verify all test cases.

Explanation:

ʒ      # Filter the (implicit) input-list by:
 +     #  Add the current value to each in the (implicit) input-list
  ;    #  Halve each
   Ã   #  Only keep those values from the (implicit) input-list
    g  #  Pop and push the length to get the amount of remaining values
       #  (only 1 is truthy in 05AB1E)
       # (after which the filtered result is output implicitly)
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Porting the Jelly answer is 5 bytes \$\endgroup\$
    – Steffan
    Jun 24 at 18:29
3
\$\begingroup\$

Python 3

58 bytes with unordered sets

Thanx to Jitse!

lambda l:{*l}-{a for a in l for b in{*l}-{a}if(a+b)/2in l}

Try it online!

62 61 bytes with ordered lists

lambda l:[a for a in l if{(a+b)/2in l for b in{*l}-{a}}=={0}]

Try it online!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ My entry started to look very much like yours, so I suppose it's yours to take. You can save 4 bytes with lambda a:{*a}-{i for i in a for j in{*a}-{i}if(i+j)/2in a} \$\endgroup\$
    – Jitse
    Jun 24 at 12:42
  • \$\begingroup\$ Nice, but I'm unsure whether returning unordered sets complies with the question. The task is to "remove from the list", on the other hand, the order of items does not matter for the task. \$\endgroup\$
    – movatica
    Jun 26 at 16:51
  • 1
    \$\begingroup\$ I think that is a technicality and is therefore allowed by the default I/O-rules. \$\endgroup\$
    – Jitse
    Jun 27 at 7:45
2
\$\begingroup\$

Jelly, 10 bytes

ŒcSe¥ƇḤFḟ@

A monadic Link that accepts a list of positive integers and yields the filtered list.

Try it online!

How?

ŒcSe¥ƇḤFḟ@ - Link: list L
Œc         - ordered pairs (L)
      Ḥ    - double (L) (vectorises)
     Ƈ     - filter the pairs keeping those for which:
    ¥      -   last two links as a dyad - f(pair, doubled L)
  S        -     sum (pair)
   e       -     exists in (doubled L)?
       F   - flatten (this list of pairs whose sum is in the doubled L)
         @ - with swapped arguments:
        ḟ  -   filter discard (take L and remove the pair elements)
\$\endgroup\$
2
\$\begingroup\$

Pyth, 12 10 bytes

-Qs-L-LydQ

Try it online! or Verify all test cases

-Qs-L-LydQ
    L     (Q) # Left map over the implicit input with variable `d`:
      L  Q    #   Left map over the input with variable `k`:
     - yd     #     d*2 - k
   -          #   Remove d from the resulting list
  s           # Flatten
-Q            # Remove elements of the resulting list from the input

12-byte solutions

fqFf}-yYTQQQ
-Qsf}.OT-QT*
\$\endgroup\$
2
\$\begingroup\$

Factor + math.unicode, 57 51 50 bytes

[| s | s [ s n+v 2 v/n s ∩ length 1 > ] reject ]

Attempt This Online!

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

[T-SQL] 111 bytes

DELETE FROM T WHERE EXISTS(Select*From T Y Join T Z ON T.ID NOT IN(Y.ID,Z.ID)And Y.ID<>Z.ID And T.N+Y.N=2*Z.ID)

Formatted:

DELETE FROM T
WHERE EXISTS(
    Select *
    From T as Y
    Join T as Z
        ON T.ID NOT IN(Y.ID, Z.ID)
        And Y.ID <> Z.ID
        And T.N+Y.N = 2*Z.ID)

I could save one more byte by using the excremental SQL-89 joins, but my soul is worth more than one byte.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I'm not too familiar with T-SQL, but can you remove the two spaces at Y.ID, Z.ID) And to save 2 bytes? \$\endgroup\$ Jun 24 at 23:28
  • \$\begingroup\$ @KevinCruijssen Yep, you are correct. \$\endgroup\$ Jun 25 at 0:27
  • 1
    \$\begingroup\$ Can you remove the space before * after Select ? \$\endgroup\$
    – Steffan
    Jun 25 at 18:20
  • \$\begingroup\$ @Steffan Yes, thanks! \$\endgroup\$ Jun 25 at 18:51
2
\$\begingroup\$

Ruby, 39 bytes

->l{l-l.permutation(2).map{|a,b|a*2-b}}

Try it online!

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

Burlesque, 26 bytes

Js12CB:U_f{avg1j~[}g1jFL\\

Try it online!

Takes input as block of doubles

J          # Duplicate
s1         # Store as 1
2CB        # Combinations of length 2
:U_        # Filter for unique (guaranteed safe by no dups)
f{avg1j~[} # Filter for average contained in original list (1)
g1         # Get 1
j          # Reorder stack
FL         # Flatten
\\         # Remove elements contained in (1) also in averages
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 16 bytes

IΦθ¬⊙θ∧⁻κμ№⊗θ⁺ιλ

Try it online! Link is to verbose version of code. Explanation:

  θ                 Input list
 Φ                  Filtered where
     θ              Input list
   ¬⊙               No elements satisfy
       ⁻κμ          Indices differ
      ∧             Logical And
            θ       Input list
           ⊗        Doubled
          №         Does not contain
             ⁺ιλ    Sum of current elements
I                   Cast to string
                    Implicitly print
\$\endgroup\$
1
  • 1
    \$\begingroup\$ @thejonymyster Sorry, I put it on the wrong line, it should be on the "Cast to string" line... thanks for pointing it out. \$\endgroup\$
    – Neil
    Jun 23 at 20:01
1
\$\begingroup\$

Haskell, 67 bytes

f a=[z|z<-a,not$elem z[x|x<-a,y<-a,x/=y,even$x+y,div(x+y)2`elem`a]]

Attempt This Online!

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

Zsh, 75 bytes

for x;for y;((s=x+y,s%2||x==y))||a+=(${=${(M)@:#$[s/2]}:+$x $y})
<<<${@:|a}

Try it online!

Not as compact as I was expecting...

for x;for y   # for $x, $y in the Cartesian product of the list with itself
    ((s=x+y,s%2||x==y)) ||          # test if the sum is odd or x == y. If not,
    a+=(${=${(M)@:#$[s/2]}:+$x $y})
#          ${(M)@:#$[s/2]}          # substitute the average if found in $@
#       ${                :+$x $y}  # if non-empty, substitute "$x $y"
#   a+=(${=                      }) # split on spaces and add it to $a

<<<${@:|a}                          # set difference
\$\endgroup\$
1
\$\begingroup\$

Python + NumPy, 50 bytes

lambda a:a[((a+[[a]]).T==a+a[:,1>0]).sum((0,1))<2]

Attempt This Online!

Straightforward masking with a few tricks to shorten the required indexing operations without having to explicitly import numpy.

How?

Construct 3d table of z,y,x each running through the input list a. Each cell is True if 2z=y+x and False otherwise. Fixing x=a count solutions z,y. If a is not part of an averaging pair there is only solution z=a,y=a, otherwise there are more. Use boolean indexing to filter a accordingly.

(a+[[a]]).T is a shorter surrogate for 2*a[:,None,None] and a[:,1>0] is shorter than the more natural a[:,None].

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

Desmos, 80 76 bytes

f(l)=l[[[(.5k-l)^2.minfork=l[m]+l[(L-m)^2>0]].minform=L]>0]
L=[1...l.length]

This is probably a terrible way of doing it, but whatever. Also, the "words" minfork and minform that appear in the code are very much intentional, though you will quickly see what they actually parse as in the graph links :P.

Try It On Desmos!

Try It On Desmos! - Prettified

\$\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.