Remove first encountered elements from a second list

Question

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]

Answer 1

APL(Dyalog Unicode), ⁸ 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

Answer 2

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.

Answer 3

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

Answer 4

R, 29 bytes

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

Try it online!

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

Answer 5

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

Answer 6

J, 6 bytes

#~1-~:

Try it online!

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

Answer 7

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).

Answer 8

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).

Answer 9

Haskell, ⁴⁴ 43 bytes

• -1 byte thanks to Unrelated String.

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

Answer 10

JavaScript (Node.js), 40 bytes

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

Try it online!

Answer 11

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!

Answer 12

Red, 69 bytes

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

Try it online!

Answer 13

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

Answer 14

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)

Answer 15

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!

Answer 16

Charcoal, 10 bytes

ＩΦθ›κ⌕η§ηκ

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
Ｉ           Cast to string
            Implicitly print

Answer 17

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

Answer 18

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

Answer 19

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

Answer 20

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!

Answer 21

Wolfram Language (Mathematica), 35 bytes

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

Try it online!

Answer 22

Perl 5, 36 bytes

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

Try it online!

Answer 23

Arturo, 44 bytes

$[a,b][i:0select a=>[in? b\[i]take b i'i+1]]

Try it

$[a,b][                    ; a function taking two lists a and b
    i:0                    ; set i to 0
    select a=>[            ; select elements from a where...
        in? b\[i]take b i  ; the ith element of b is found in b's elements that come before index i
        'i+1               ; increment i
    ]                      ; end select
]                          ; end function

Answer 24

Japt, 8 bytes

gVðÏÀVbX

Try it

k϶VbVgY

Try it