Seat gangs as far as possible

Question

Imagine there are \$n\$ people \$\{a_1, a_2, \ldots, a_n\}\$ who enter a room in order and sit down in \$n\$ seats, arranged in a row. Each of these people belong to some gang, indicated by an integer \$\{1, 2, \ldots, k\}\$. These gangs hate the members of the other gangs, so they want to sit as far away from those people as possible; specifically, they sit in the set which maximizes the minimum distance from anyone in a different gang who is already seated. They break ties by sitting in the seat furthest to the left.¹

For example, suppose \$n=6\$, and there are \$k=3\$ gangs \$\{1, 2, 3\}\$. Now imagine that the first person that enters is in gang 1, the next two are in gang 2, the next two are in gang 3, and the final person is in gang 1 again -- i.e. the order is [1, 2, 2, 3, 3, 1]. Then the people will sit down in the following order:

   _ _ _ _ _ _
1: 1 _ _ _ _ _ 
2: 1 _ _ _ _ 2
2: 1 _ _ _ 2 2
3: 1 _ 3 _ 2 2
3: 1 3 3 _ 2 2
1: 1 3 3 1 2 2 

Your challenge is, given a sequence of numbers \$\{a_1, a_2, \ldots, a_n\}\$, where each \$a_i \in \{1, 2, \ldots, k\}\$ is some positive integer representing a person in some gang, output the final arrangement of the \$n\$ people in \$n\$ seats as described above. (If useful, you can take \$n\$ and \$k\$ as extra inputs.) You can assume that no gang number will be skipped - e.g. \$\{1, 2, 4\}\$ would not be a valid input.

Test Cases

[1] -> [1]
[1, 2] -> [1, 2]
[1, 1, 1] -> [1, 1, 1]
[1, 2, 1, 2, 1] -> [1, 1, 1, 2, 2]
[1, 2, 2, 3, 3, 1] -> [1, 3, 3, 1, 2, 2]
[1, 2, 4, 3, 2, 1, 4] -> [1, 3, 1, 4, 4, 2, 2]
[4, 4, 4, 3, 3, 2, 1] -> [4, 4, 4, 2, 1, 3, 3]
[1, 2, 3, 4, 5, 6, 7] -> [1, 4, 5, 3, 6, 7, 2]

Standard loopholes are forbidden. As this is code-golf, shortest program wins.

¹ This is a variation of the "urinal protocol".

Answer 1

Uiua, 32 bytes

∧⋄∸(⍜⊏+⊢⍏×-1,/↧⌵∺-⇡⊃⧻⊚×⊃±≠,,)≠..

Try it online!

∧⋄∸(⍜⊏+⊢⍏×-1,/↧⌵∺-⇡⊃⧻⊚×⊃±≠,,)≠..  input: array of gang ids
∧⋄∸(  )≠..  fold over the input, using [0 ... 0] as the initial accumulator
  (   )      inner function: placed gang ids, next gang id -> placed gang ids
  ⊃±≠       sign (is occupied?), not equal (is not the current gang?)
  ×          multiply (has a person under a different gang?)
  ⇡⊃⧻⊚     all indices (all positions), indices of ones (positions of enemies)
  /↧⌵∺-     for each position, minimum distance from enemies
             (infinity if no enemies)
  ×-1,       multiply (placed gang ids - 1) to make valid distances negative
             infinity * 0 is NaN, whose sort order is after infinities
  ⊢⍏        first index of minimum (the index of maximum distance from enemies)
  ⍜⊏+  ,,   add the new gang id at the found index

Answer 2

Python3, 218 bytes

def f(g):
 R=[0]*len(g)
 for i in g:
  d=[[],[]]
  for j,k in enumerate(R):
   if k!=i:d[k==0]+=[j]
  if d[0]:R[max([(j,min(abs(j-J)for J in d[0]))for j in d[1]],key=lambda x:x[1])[0]]=i
  else:R[min(d[1])]=i
 return R

Try it online!

Answer 3

Jelly, 22 20 bytes

¬,an¥T€ạṂNɗÞ/Ḣ
+禃¬

Try it online!

A pair of links which is called with a single argument of a list of integers and returns a list of integers.

Explanation

¬,an¥T€ạṂNɗÞ/Ḣ  # ‎⁡Helper link: take a current list of seated people as the left argument and the next person to seat; returns the index of the best available seat
¬               # ‎⁢Not (vectorises)
 ,  ¥           # ‎⁣Pair with:
  an            # ‎⁤- The result of anding the current seating plan with the result of checking which ones don’t equal the new person
     T€         # ‎⁢⁡For each of these, generate a vector of truthy indices
          ɗÞ/   # ‎⁢⁢Reduce this list of lists; generate a sorted version of the first list (the indices of empty seats) sorted by the following:
       ạ        # ‎⁢⁣- Absolute difference between a given index of an empty seat and the indices of all of the seats filled with rival gang members
        Ṃ       # ‎⁢⁤- Minimum
         N      # ‎⁣⁡- Negate
             Ḣ  # ‎⁣⁢Head (I.e. the index of the best available seat)


+禃¬           # ‎⁣⁣Main link: takes a list of people to seat and returns the seating plan
   ƒ¬           # ‎⁣⁤Reduce the list of people to seat, using a list of zeros of the same length as the starting left argument and the following:
+               # ‎⁤⁡- Add the new person
 ç¦             # ‎⁤⁢ - Specifically just at the index given by using the helper link
💎

Created with the help of Luminespire.

Answer 4

R, 94 84 bytes

\(x,y=!x){for(z in x)y[which.max(sapply(v<-seq(y),\(w)min((w-v[y-z&y])^2))*!y)]=z;y}

Attempt This Online!

A function that takes an integer vector and returns an integer vector. Works similarly to my Jelly answer, but golfed differently to reflect the differences in language.

Thanks to @pajonk for saving three bytes!

Ungolfed version

find_closest_distance <- function(seat_index, current_seats, next_person) {
 distances <- abs(seat_index - seq(current_seats)[current_seats & current_seats != next_person])
 min(distances)
}

find_best_seat_and_allocate <- function(current_seats, next_person) {
 closest_distances <- sapply(seq(current_seats), find_closest_distance, current_seats = current_seats, next_person = next_person)
 best_seat <- which.max(closest_distances * !current_seats)
 current_seats[best_seat] <- next_person
 current_seats
}

f <- function(people) {
 Reduce(find_best_seat_and_allocate, people, init = !people)
}

Attempt This Online!

Answer 5

JavaScript (V8), 102 bytes

x=>x.map(c=>s[x.map((_,k)=>x.some((_,i)=>s.some((v,j)=>(i-j)**2<k*k&v!=c|i==j)?0:[A=i])),A]=c,s=[])&&s

Try it online!

Seems quite unpolished

pseudo-code:

s = []
for c in x:
  for k in range(len(x)):
    for i in range(len(x)):
      if at position i distance k:
        A = i
        break
  s[A] = c

Answer 6

J, 49 bytes

0"0]F..([`(0{&\:~:*[:<./@(I.|@-/i.@#)~:**@])`]})]

Attempt This Online!

• 0"0]F..(fold verb) A single forward fold that we seed with a list of zeros as long as the input
• To find the new position of each person in line, we...
  • ~:**@] First create an array which is 1 only in positions of rival gang members, and 0 elsewhere
  • I.|@-/i.@# Create a table of absolute differences between the indexes of those ones and all indexes
  • <./@ And min the resulting rows of that table. This gives us a list showing the distance to the closest rival gang member at each position.
  • ~:* Zero out any position holding one of our own gang members.
  • 0{&\: Take the first element of the grade down. This gives us the first of all the "farthest" positions, as needed.
• [ Update that position with the value we're folding.

Answer 7

Charcoal, 41 bytes

Ｆθ⊞υ⁰Ｆθ«≔Ｅυ∧¬κ⌊Ｅυ⎇∧μ⁻ιμ↔⁻νλＬθη§≔υ⌕η⌈ηι»Ｉυ

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

Ｆθ⊞υ⁰

Create an array of empty seats of the same length as the input.

Ｆθ«

Loop over the input.

≔Ｅυ∧¬κ⌊Ｅυ⎇∧μ⁻ιμ↔⁻νλＬθη

For each seat, if it is empty, calculate the distance to the nearest rival.

§≔υ⌕η⌈ηι

Place this person in the seat furthest away from any rival.

»Ｉυ

Output the resulting seating arrangement.

Answer 8

05AB1E, 31 bytes

_IvÐĀUyÊX*āsƶ0KδαεIgªß}X<*Wkysǝ

Port of @Bubbler's Uiua's answer, so make sure to upvote that answer as well!

Try it online or verify all test cases.

Explanation:

_               # Convert each value in the (implicit) input-list to 0
 Iv             # Push the input-list again, and loop over its items `y`:
   Ð            #  Triplicate the current list
    Ā           #  Pop one, and check which positions are occupied
     U          #  Pop and store this list in variable `X`
    yÊ          #  Pop another copy, and check all positions NOT filled with gang `y`
      X*        #  Multiply it to list `X`, so we have a list with 1s at enemy positions
        ā       #  Push a list in the range [1,length] (without popping)
         s      #  Swap so the earlier enemy positions list is at the top again
          ƶ     #  Multiply each value by its 1-based index
           0K   #  Remove all 0s
             δα #  Pop both lists, and create an absolute difference table
    ε    }      #  Map over this list of lists
     Igª        #   Append the input-length to the list (edge case for empty lists)
        ß       #   Pop and push the minimum
          X     #  Push list `X` again
           <    #  Subtract each value by 1 (0s for enemy positions; -1 otherwise)
            *   #  Multiply it to the values of the mapped list
    W           #  Push the minimum (without popping the list)
     k          #  Pop both, and push the (first) (0-based) index of this minimum
      ys        #  Push the current gang `y`, and swap
        ǝ       #  Insert the current gang `y` at this index into the list
                # (after the loop, the resulting list is output implicitly)

Answer 9

Scala, 207 bytes

207 bytes, it can be golfed much more. Golfed version. Try it online!

(c,n)=>{val d=c.indices.map{i=>if(c(i)==0){val d=c.indices.collect{case j if c(j)!=0&&c(j)!=n=>Math.abs(i-j)};if(d.isEmpty)Int.MaxValue else d.min}else -1};c.updated(d.zipWithIndex.maxBy{case(d,_)=>d}._2,n)}

Ungolfed version. Try it online!

object Main {
  def main(args: Array[String]): Unit = {
    val inputData = List(
      List(1),
      List(1, 2),
      List(1, 1, 1),
      List(1, 2, 1, 2, 1),
      List(1, 2, 2, 3, 3, 1),
      List(1, 2, 4, 3, 2, 1, 4),
      List(4, 4, 4, 3, 3, 2, 1),
      List(1, 2, 3, 4, 5, 6, 7)
    )

    inputData.foreach { people =>
      val result = people.foldLeft(List.fill(people.size)(0)) { (currentSeats, nextPerson) =>
        findBestSeatAndAllocate(currentSeats, nextPerson)
      }
      println(s"${people.mkString(", ")} -> ${result.mkString(", ")}")
    }
  }

  def findClosestDistance(seatIndex: Int, currentSeats: List[Int], nextPerson: Int): Int = {
    val distances = currentSeats.indices.collect {
      case idx if currentSeats(idx) != 0 && currentSeats(idx) != nextPerson => Math.abs(seatIndex - idx)
    }
    if (distances.isEmpty) Int.MaxValue else distances.min
  }

  def findBestSeatAndAllocate(currentSeats: List[Int], nextPerson: Int): List[Int] = {
    val closestDistances = currentSeats.indices.map { idx =>
      if (currentSeats(idx) == 0) findClosestDistance(idx, currentSeats, nextPerson) else -1
    }
    val bestSeat = closestDistances.zipWithIndex.maxBy { case (distance, _) => distance }._2
    currentSeats.updated(bestSeat, nextPerson)
  }
}