15
\$\begingroup\$

Inspired by this question on Stackoverflow.


The task

Let's have two lists/arrays of integers: L1 and L2 of equal length. You need to identify in L2 the position of first occurrence of each number and remove from L1 the values on the corresponding positions. Then print/output the modified L1.

Any reasonable input/ouput format is accepted as long as the lists are distinguishable.

Example

L1 = [1 2 3 4 5 6 7 8 9]
L2 = [2 3 3 5 5 4 3 7 1]
First occurence of each number in L2:
L2 = [2 3 3 5 5 4 3 7 1]
      ^ ^   ^   ^   ^ ^
Corresponding elements to remove from L1:
L1 = [1 2 3 4 5 6 7 8 9]
      ^ ^   ^   ^   ^ ^
Output result:
[3 5 7]

Test cases

Input -- Output
[1,2,3,4,5,6,7,8,9];[2,3,3,5,5,4,3,7,1] -- [3,5,7]
[1,1,1];[1,2,3] -- []
[2,2,2];[1,1,1] -- [2,2]
[-1,0,2,123456];[-1,0,-1,0] -- [2,123456]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40];[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] -- [2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40]
\$\endgroup\$
4

22 Answers 22

9
\$\begingroup\$

APL(Dyalog Unicode), 8 6 bytes SBCS

/⍨∘~∘≠

Try it on APLgolf!

A function submission which takes L1 on the left and L2 on the right.

-2 bytes from Bubbler.

Explanation

/⍨∘~∘≠
/⍨     remove elements from L! identified by:
   ~   the bitwise negation of
     ≠ unique mask of L2
\$\endgroup\$
2
  • \$\begingroup\$ /⍨∘~∘≠ also works. \$\endgroup\$
    – Bubbler
    Apr 15 '21 at 5:31
  • \$\begingroup\$ I mistakenly thought it'd infer as reduce. Thanks! \$\endgroup\$
    – Razetime
    Apr 15 '21 at 5:33
9
\$\begingroup\$

Python 2, 49 bytes

A cool new approach from @kops, which outputs by modifying the input.

def f(a,b):
 while b:b.pop()in b or a.pop(len(b))

Try it online!

Python 2, 51 bytes

lambda a,b:[x for x in a[::-1]if b.pop()in b][::-1]

Try it online!

We can determine whether an element stays in L1 by whether the corresponding element in L2 is its first occurrence. This is done with b.pop()in b, which pops the last element from L2 and checks if it still exists in the list.

Because we process the elements in reverse, [::-1] needs to be used twice. It makes the final code a lot larger than I had hoped, but I am not able to come up with a shorter approach.

\$\endgroup\$
3
  • \$\begingroup\$ That's clever.. nicely done. \$\endgroup\$ Apr 15 '21 at 7:48
  • \$\begingroup\$ 49 bytes by output via modifying input \$\endgroup\$
    – kops
    Apr 16 '21 at 11:20
  • \$\begingroup\$ @kops Thanks! I almost never see this trick in Python, so it's nice to see it put to good use. \$\endgroup\$ Apr 16 '21 at 17:57
7
\$\begingroup\$

Haskell, 65 52 51 bytes

f[]
f z(a:s)(b:t)=[a|b`elem`z]++f(b:z)s t
f _[]_=[]

Try it online!

The solution is the anonymous function which calls f applied to the empty list: f[]. f keeps track of which elements of L2 we've seen already and only adds the corresponding element of L1 to the result if we haven't seen L2's head yet.

import Data.List for the builtins turns out to be too expensive:

Haskell, 65 bytes

((map fst.((\\)<*>nubBy((.snd).(==).snd))).).zip
import Data.List

Try it online!

How?

((map fst.((\\)<*>nubBy((.snd).(==).snd))).).zip
                                             zip -- zip the lists
           (\\)                                  -- delete from the zipped lists
                  nubBy                          -- the first occurence of each element under the equivalence class defined by:
                        ((.snd).(==).snd)        -- equality of the second element of each pair
  map fst                                        -- take the first element of each pair from the resulting list

and then a lot of punctuation to send the right arguments to the right places...

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

Jelly, 5 bytes

ŒQ¬Tị

Try it online!

Explanation

ŒQ¬Tị   Main dyadic link
ŒQ      Distinct sieve - replace first occurences with 1 and other occurences with 0
  ¬     Negate
   T    Get the indices with truthy elements
    ị   Index into the other array
\$\endgroup\$
6
\$\begingroup\$

J, 6 bytes

#~1-~:

Try it online!

Filter by #~ the complement of 1- the nub sieve ~:

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

R, 29 bytes

function(x,y)x[duplicated(y)]

Try it online!

A rare case, where obscure duplicated function appears to be useful...

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

R, 59 35 34 bytes

Edit: -1 byte thanks to Giuseppe ...but now outgolfed by Kirill L's answer

function(a,b)a[match(b,b)<seq(!b)]

Try it online!

match(x,y) finds the index of the first element in y equal to each element of x.

So, match(b,b) is equal to the index of each element if it's the first one with a particular value, otherwise it it'll be equal to an earlier index where that value was previously encountered.

seq(!b) is golfy shorthand for seq_along(b), and returns a sequence of integers 1...b (in other words, the indices of each element of b). Note that we need the ! because seq defaults to outputting a sequence of b integers if b contains only a single numeric element; therefore, we use ! to first convert the argument to a logical-type vector (where this can't happen).

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

AWK, 30 29 bytes

{a[++n]=b[$1]++}n>FNR&&a[++m]

Try it online! (Thanks very much to Jonah for the TIO link)

Takes input as two files L1 and L2, with one number per line in each (or, with the -v RS=' ' option, space-separated on a single line).

\$\endgroup\$
6
  • \$\begingroup\$ Clever idea to store the list of numbers as one per line! I had to read this a few times to figure it out. :) \$\endgroup\$
    – cnamejj
    Apr 15 '21 at 8:36
  • 1
    \$\begingroup\$ @cnamejj - On re-reading I realized that it's accidentally obfuscated: {a[NR]=b[$1]++}NR>FNR&&a[FNR] would have been easier to understand and the same number of bytes... \$\endgroup\$ Apr 15 '21 at 8:49
  • \$\begingroup\$ Working TIO (uses bash, but you can manually edit the title): Try it online! \$\endgroup\$
    – Jonah
    Apr 15 '21 at 17:45
  • \$\begingroup\$ by just casually reading, don't you just treat the first test case where the first tist is 1 to 9 in order? Does it really work with the other test cases? \$\endgroup\$ Apr 16 '21 at 3:16
  • 1
    \$\begingroup\$ @Jonah - Thanks very much for showing how to do this on TIO! That's perfect! \$\endgroup\$ Apr 16 '21 at 21:08
5
\$\begingroup\$

Haskell, 44 43 bytes

x!y=[a|(i,a)<-zip[0..]x,y!!i`elem`take i y]

Try it online!

How?

x!y=                        -- (!) is a function that takes lists x and y as input
    [a|                     -- and returns the list of all the elements a
    (i,a)<-zip[0..]x,       -- where a is the i-th element of x
    y!!i`elem`take i y]     -- and the i-th element of y is not a "first occurrence" in y
\$\endgroup\$
2
  • \$\begingroup\$ -1 if you rearrange (a,i)<-zip x[0..] to (i,a)<-zip[0..]x \$\endgroup\$ May 14 '21 at 10:28
  • 1
    \$\begingroup\$ @UnrelatedString How did I miss that! Thanks :) \$\endgroup\$
    – Delfad0r
    May 14 '21 at 13:08
4
\$\begingroup\$

JavaScript (Node.js), 40 bytes

a=>b=>a.filter((_,i)=>b.indexOf(b[i])<i)

Try it online!

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

Red, 69 bytes

func[a b][foreach c unique b[change at a index? find b c none]trim a]

Try it online!

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

Arturo, 67 bytes

$[a b][loop reverse unique map b'x[index b x]'i[remove.index'a i]a]

Try it on the Arturo Playground!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Great! The entire Arturo site + Playground looks good - I might start learning :) \$\endgroup\$ Apr 15 '21 at 9:22
3
\$\begingroup\$

05AB1E, 8 bytes

DÙõ.;.ïÏ

I have the feeling this could be shorter, but 05AB1E's builtin might not be the most suitable for this challenge.

\$L2\$ as first input, \$L1\$ as second.

Try it online or verify all test cases.

Explanation:

D         # Duplicate the first (implicit) input-list L2
 Ù        # Uniquify the values in the copied list
  õ.;     # Replace the first occurrences of the values in L2 to an empty string
     .ï   # Check for each item whether it's an integer (1 if an integer; 0 if an empty
          # string)
       Ï  # Only keep the values at the truthy indices in the (implicit) input-list L1
          # (after which the resulting list is output implicitly)
\$\endgroup\$
2
\$\begingroup\$

Python 3, 76 bytes

f=lambda a,b,c=[],i=0:i<len(a)and f(a,b,c+[a[i]]*(b.index(b[i])!=i),i+1)or c

Try it online!

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

Charcoal, 10 bytes

IΦθ›κ⌕η§ηκ

Try it online! Link is to verbose version of code. Explanation: Port of @tsh's JavaScript answer.

  θ         First list
 Φ          Filtered where
    κ       Current index
   ›        Is greater than
     ⌕      First index of
         κ  Current index
       §    Element of
        η   Second list
      η     In second list
I           Cast to string
            Implicitly print
\$\endgroup\$
2
\$\begingroup\$

Vyxal, 5 bytes

ÞU†Tİ

Try it Online!

Same as the APL and Jelly answer.

Explained

ÞU†Tİ
ÞU    # unique mask over second list
  †   # vectorised not over that
   Tİ # and index the truthy indices into the first list
\$\endgroup\$
2
\$\begingroup\$

Python 3.8 (pre-release), 53 bytes

lambda a,b:[x for x,y in zip(a,b)if b==(b:={*b}-{y})]

Try it online!

A little better

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

Husk, 9 bytes

M!-m←ηk¹ŀ

Try it online!

Explanation

M!-m←ηk¹ŀ
      k   key
     η     the indices of each element on their value.
   m←     take the first index of each key
  -       remove this from
        ŀ the input, converted to indices.
M         map each index to
 !         the respective element in the second array
\$\endgroup\$
1
\$\begingroup\$

Python 3, 108 bytes

k={y.index(x)for x in y};n='z=[v for i,v in enumerate(z)if i not in k]';exec(n);n=n.replace("z","y");exec(n)

Try it online!

Define two lists z and y

\$\endgroup\$
1
  • 6
    \$\begingroup\$ Assuming two predefined variables is not an allowed I/O format. \$\endgroup\$
    – Bubbler
    Apr 15 '21 at 5:18
1
\$\begingroup\$

Pyth, 8 7 bytes

.DExLQ{

Input is L2 and L1, separated by newlines

-1 because Pyth has a built-in for evaluated input I forgot about

Try it online!

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

Perl 5, 36 bytes

sub{my%s;grep$s{+shift}++,@{+shift}}

Try it online!

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

Wolfram Language (Mathematica), 35 bytes

#[[Union@@Rest/@PositionIndex@#2]]&

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.