Gluttonous Colluding Numbers

Question

Here's an easy one, with just enough complexity to make golfing non-trivial.

Input

1. A list of non-negative numbers representing people waiting in line for Thanksgiving dessert. The first (leftmost) number is first in line, and the list can contain repeats (think of each number as a person's first name):

Note: Pie not part of actual input.

        (
         )
    __..---..__
,-='  /  |  \  `=-.
:--..___________..--;   6 4 3 1 2 3 0
\.,_____________,./

2. A non-empty subset of that list, representing a group of colluding friends who will "chat and cut" to skip ahead in line. All colluders will move just behind the friend already closest to the front of the line, but otherwise retain their relative positions. Everyone they skip past will also retain their relative position.

Output

The new list, after a successful (possibly multi-way) chat and cut. For example, in the list above, for a friend group of 0 2 4, the output would be:

6 4 2 0 3 1 3

If the friend group was 4 3, the output would be:

6 4 3 3 1 2 0

Notes

This is code golf with standard site rules.

• A single colluder x in the colluder list makes everyone in line with that number a colluder.
• The list of people waiting may contain repeats.
• The colluder list will not contain repeats.
• The colluder list may not be sorted.
• The colluder list will have between 2 and U items, where U is the number of unique elements in the queuer list.

Test Cases

The format is:

1. People in line.
2. List of colluders.
3. Output.

5 4 3 2 1 0
3 1
5 4 3 1 2 0

1 2 1 3 1 9 
1 9
1 1 1 9 2 3

1 2 3 4 5
4 5
1 2 3 4 5

7 6 1 5 2 4 3
4 5 6
7 6 5 4 1 2 3

7 6 1 5 2 4 3
1 2 3
7 6 1 2 3 5 4

7 6 1 5 2 4 3
3 6
7 6 3 1 5 2 4

1 2 3 4
1 2 3 4
1 2 3 4

1 2 3 4 5 4
5 4
1 2 3 4 5 4

Answer 1

J, 12 bytes

-1 thanks to FrownyFrog!

[/:OR\@e.-e.

Try it online!

For 6 4 3 1 2 3 0 and 0 2 4:

[/:OR\@e.-e.
   OR        OR …
     \       each prefix of …
      @e.    the bitmask of friends, or:
   OR\@e.    after the first friend? (0 1 1 1 1 1 1)
          e. the bitmask of friends  (0 1 0 0 1 0 1)
         -   minus                   (0 0 1 1 0 1 0)
[/:          (stable) sort the people based on the list
                                     (6 4 3 1 2 3 0)

Answer 2

05AB1E, 9 8 bytes

ΣåDi©}®‹

-1 byte thanks to @ovs.

Try it online or verify all test cases.

Explanation:

Σ        # (Stable) sort the first (implicit) input-list by:
 å       #  Check that the current item is in the second (implicit) input-list
         #  (1 if truthy; 0 if falsey)
  Di }   #  Duplicate it, pop this copy, and if it's 1:
    ©    #   Store 1 in variable `®` (without popping) (variable `®` is -1 by default)
      ®‹ #  Check that the duplicated check is smaller than `®`
         #  (1 if truthy; 0 if falsey)

Here the same TIOs with map instead of sort-by, so you can see any leading non-friends become 0, all friends become 0 as well, and any non-friends after the first friend become 1:
Try it online or verify all test cases.

Answer 3

R, 49 47 45 42 bytes

Edit: -2 bytes, and then -3 more bytes, thanks to Giuseppe

function(l,f)l[order(cummax(p<-l%in%f)-p)]

Try it online!

Commented:

function(l,f`           # function with arguments:
                        # l = line
                        # f = friends
p=l%in%f)               # define p as TRUE at positions of friends in the line
l[order                 # now output l, in the order of (lowest>highest):
-(                      # minus (so now highest>lowest)
p                       # 1 for each friend
+2*!cumsum(p)           # +2 for anyone ahead of the first friend
))]                     # (so, in the end, anyone ahead of all friends gets -2,
                        # the friends get -1, 
                        # and anyone else behind the first friend gets zero).

---

Previous approach: R, 67 59 54 bytes

Edit: -8 bytes thanks to Giuseppe, then -5 more bytes thanks to Robin Ryder

function(l,f,p=which(l%in%f))c(l[z<-c(1:p-1,p)],l[-z])

Try it online!

Answer 4

Python 2, 79 72 bytes

def f(x,y):m=min(map(x.index,y));print x[:m]+sorted(x[m:],cmp,y.count,1)

-7 bytes thanks to @ovs

Try it online! All testcases.

I take a unique approach here using Python's sorted function, which performs a stable sort. Might not be the shortest Python approach, but it is interesting.

def f(x,y):  # x = input line, y = list of colluders
  m = min(map(x.index,y)) # index of the first colluder in line
  print
    x[:m] # The first m people do not change positions
    sorted(
      x[m:],   # we sort the people after the first m
      cmp,    # default comparison function
      y.count, # key function is y.count: returns 0 for numbers not in y
                 # and 1 for numbers in y
      1        # sort in descending order
    )

Answer 5

Haskell, 59 bytes

(h:t)%c|all(/=h)c=h:t%c
l%c=[x|b<-[1<0..],x<-l,elem x c/=b]

Try it online!

Test cases and inspiration from ovs's solution.

We use [1<0..] to generate the list [False,True]. Having handled the prefix of non-colluding numbers, we then pass over the remainder twice, first to take colluding numbers, then to take non-colluding ones. A same-length alternative is:

59 bytes

(h:t)%c|all(/=h)c=h:t%c
l%c=[x|b<-[id,not],x<-l,b$elem x c]

Try it online!

Answer 6

Jelly, 9 bytes

e€»\_$Ụị⁸

Try it online!

More or less a translation of xash's J answer.

e€           For each person in line, are they a friend?
    _        Subtract that from
  »\ $       its cumulative maxima,
      Ụ      sort the indices,
       ị⁸    index back into the line.

iⱮ»\_$Ụị almost saves a byte by taking colluders on the left and the line on the right, but it doesn't succeed at preserving the order of duplicate colluders in cases such as [1,2,3,4,5,4], [5,4].

Jelly, 12 bytes

iⱮṂœṖ⁸e¬¥Þ€F

Try it online!

Answer 7

Factor, 62 bytes

[ '[ _ member? ] 2dup find . swapd cut rot partition 3append ]

Try it online!

The extensive sequences library is quite helpful here. Takes line cheaters on the stack, and returns the modified line through the stack. Prints a garbage to stdout each time it is run.

Ungolfed

[                  ! ( line cheaters ) start anonymous lambda definition
  '[ _ member? ]   ! ( line fun ) convert cheaters array to membership function
  2dup find .      ! ( line fun idx ) find index of first cheater
  swapd cut        ! ( fun left right ) cut line at that index
  rot partition    ! ( left cheaters rest ) partition the right into
                   !   cheaters and non-cheaters, using the membership function
  3append          ! ( ans ) concatenate the three arrays
]                  ! end anonymous lambda definition

---

Factor, 74 bytes

[ dupd '[ _ member? 1 0 ? ] map dup cum-max swap v- zip sort-values keys ]

Try it online!

Factor's standard library is feature-rich enough that it can almost directly replicate xash's J solution. Except that it's 5~10 times bloated byte-count-wise.

Ungolfed

: glutton ( line cheaters -- line' )  ! takes two arrays on the stack
                                      ! and returns the cheated line as an array
  dupd                       ! duplicate line under cheaters
  '[ _ member? 1 0 ? ] map   ! for each number in line, 1 if it is a cheater,
                             ! 0 otherwise
  dup cum-max swap v-        ! cumulative maximum minus self (of the above)
  zip sort-values keys       ! sort line by the above
;

Answer 8

Haskell, 65 bytes

q!c|f<-(`elem`c),(h,t)<-span(not.f)q=h++((`filter`t)=<<[f,not.f])

Try it online!

Commented:

q!c|
    f<-(`elem`c),        -- f is a function to check whether a number is a colluder
    (h,t)<-span(not.f)q  -- h is the longest prefix of non-colluders, t the remaining list
   =
    h++                  -- the result is h and ...
    (  =<<               -- ... the concatenation of the results of ...
     (`filter`t)         -- ... filtering the remaining list by ...
         [f,not.f])      -- ... f and not f (colluders and not colluders in t)

---

Haskell, 66 bytes

With some inspiration from xnor's and AZTECCO's answers I came up with a pointfree function that is just 1 byte longer.

(takeWhile<>g.(not.)<>((.).g<*>dropWhile)).flip(all.(/=))
g=filter

Try it online! In GHC version 8.4.1 and above (<>) is included in the Prelude, in the old version on TIO it has to be imported manually.

Answer 9

Racket, 145 bytes

(λ(a b)(let([m(apply min(map(λ(x)(index-of a x))b))])(append(take
a m)(call-with-values(λ()(partition(λ(x)(member x b))(drop a m)))append))))

Try it online!

That's even longer than my Red solution :)

It's insane that partition returns two separate values rather than a list with two sublists - that's why I need to use call-with-values and put partition within an additional lambda...

Answer 10

Ruby 2.7, 39 bytes

->q,c{q.flat_map{c-[_1]!=c ?q-q-=c:_1}}

Try it online! (40 bytes because TIO's Ruby version doesn't support numbered block parameters)

Relies on the Array::- method, which returns all elements of the first array not present in the second. Given a queue q and colluders c, the ordered lists of non-colluders and colluders are q-c and q-(q-c), respectively.

->q,c{
  q.flat_map{ # For each person in the queue
    c-[_1]!=c # Are they a colluder?
      ?q-q-=c # If they are the first colluder, replace them with all colluders (in same order as they appear in the queue) and remove remaining colluders from the queue in one fell swoop. Second and subsequent colluders will be replaced by an empty array.
      :_1     # If not a colluder, leave them alone
  }
}

Answer 11

K (oK), 20 bytes

{x@<{(|\x)-x}x in y}

Try it online!

An experiment in making a K port of xash's J answer - please upvote his/hers solution!

Answer 12

Haskell, 83 72 bytes

import Data.List.Split
q?c|h:t<-splitOneOf c q=id=<<h:filter(`elem`c)q:t

Try it online!

• Longer than @xnor and @ovs great answers but I think it's worth posting because it's quite short and it has a simple and interesting approach.

• Thanks to @ovs for the precious advices, saved a lot and looks more golfy now!

q?c ... =             - infix function taking q-ueue and c-olluders lists
|h:t<-splitOneOf c q  - split queue at colluders 
id=<<                 - concat map :
h:filter(`elem`c)q:t    - first split, colluders and the remaining 

Answer 13

Perl 5, 75 bytes

sub{$f=1;map$_%1e5,sort map$_+1e5*++$r+1e9*($_~~@_&&($f=2)?1:$f),@{+shift}}

Try it online!

sub{
  $f=1;           #f = 1 if first colluder not found, = 2 after 1st colluder
  map$_%1e5,      #remove part used for sort, input elems remain in sorted order
  sort            #sorts numerically as all elems have same number of digits now
  map             #converts each elem in input queue to sum of:
    $_            #the elem itself
   +1e5 * ++$r    #plus 100000 times the input rank in the queue
   +1e9 * (       #plus 1 billion times the "rank overriding number" which is:
      $_~~@_&&($f=2) #true if current elem is colluder (if so, set $f=2)
      ? 1         #...1 if colluder
      : $f        #...or $f if not colluder (f is 1 before 1st colluder, 2 after)
    ),
    @{+shift}     #input queue
}

Works for input elems 0-99999 and for queues up to 10000 elems. Increase 1e5 and 1e9 to 1e8 and 1e16 accordingly (spending one more byte of code) to avoid this, after which computer memory size becomes a bottleneck for most setups I guess.

Answer 14

JavaScript (ES10), 60 bytes

Expects (people)(subset), where people is an array and subset is a Set.

a=>b=>a.flatMap(i=>b.has(i)?j=a.filter(x=>j&b.has(x)):i,j=1)

Try it online!

Or Try it with map() to get a better picture of the process.

How?

The variable j is initially set to 1.

We walk through the queue with flatMap(). Each identifier i that is not included in the group of friends is copied as-is:

b.has(i) ? … : i

As soon as a guy from the group of friends is reached, we append all friends at once in their order of appearance in the queue, and assign the result to j:

j = a.filter(x => j & b.has(x))

Arrays holding at least two elements are turned into NaN when coerced to a number. So the next time a friend is encountered, j & b.has(x) will be falsy⁽¹⁾ and filter() will return an empty array. As a result, all following friends are ignored as expected.

---

^{(1): It could actually be truthy if j is updated to a singleton array holding an odd identifier. But that would mean that there's only one friend in the queue, so the test b.has(i) would not be triggered another time in that case anyway.}

Answer 15

C (gcc), ^{201 \$\cdots\$ 172} 171 bytes

Saved 12 a whopping 29 30 bytes thanks to ceilingcat!!!

#define z 0;for(i=-1;++i<n;
#define P&&printf("%d ",l[i]
q;p;i;j;f(l,n,c,m)int*l,*c;{q=p=z!p P))for(j=m;j--;)l[i]==c[j]?q=p?q:i,l[i]^=p=-1:z)0>l[i]P^-1);z)i>=q&0<=l[i]P);}

Try it online!

Function takes a list of people waiting in line, its length, a list of colluding friends, and its length. Prints the new list to stdout.

Answer 16

Charcoal, 26 bytes

≔⁻θ⁻θηε≔⌕θ§ε⁰ζＩ…θζＩεＩ✂⁻θηζ

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

≔⁻θ⁻θηε

Get the sublist of the colluding friends. This is actually calculated by removing the entries of colluding friends from the original list, then removing those entries from the original list.

≔⌕θ§ε⁰ζ

Get the position of the first of the colluding friends in the original list.

Ｉ…θζ

Output everyone ahead of the first of the colluding friends.

Ｉε

Output the colluding friends.

Ｉ✂⁻θηζ

Output everyone else who wasn't ahead. (We already calculated this list but it actually costs a byte to save this rather than recalculating it.)

Answer 17

Red, 124 bytes

func[a b][m: 0 until[m: m + 1 find b a/:m]rejoin[take/part a m - 1
collect[foreach c a[if find b c[keep c]]]difference a b]]

Try it online!