The too-short urinal problem

Question

The well-known Urinal Protocol states that each person that takes a urinal will take the one furthest from any other taken urinal. But this fails to account for short urinals; in many cases, a person would prioritize taking a taller urinal in addition to distance.

In the real world, you might struggle to find a restroom with urinals of arbitrary height (besides a “short” and a “tall”) but fortunately for us this is the internet. To my knowledge, there are no guidelines for building internet bathrooms :P

For this challenge, you will be given a list of urinal heights and will have to determine the order in which they will be taken.

You might be given the following list:

3,2,4,3,1,4

The first person will choose the tallest urinal. In this case, there is a tie, so the leftmost urinal is taken, in this case urinal 3 (1-indexed).

_,_,1,_,_,_

The next person will take the tallest urinal that is further from any already taken urinal. Here, the tallest is urinal 6, and there is no tie.

_,_,1,_,_,2

The next person will take the next tallest, but if there is a tie, choose the urinal furthest from any already taken urinal.

3,_,1,_,_,2

We repeat the previous step until all slots are filled:

3,_,1,_,_,2
3,_,1,4,_,2
3,5,1,4,_,2
3,5,1,4,6,2

So the final answer here would be 3,5,1,4,6,2.

But what about a situation like this:

3,2,1,2,1,1,3

The logic above applies until this state is reached:

1,4,_,3,_,_,2

Which of the three empty slots is preferable? They all have the same height, and are equidistant from the nearest taken urinal. Well, slot 3 is next to taken urinals on both sides, while slots 5 and 6 each have a side open, so they are preferable to slot 3. Now that the competition has narrowed to just two, the leftmost urinal is taken.

1,4,_,3,_,_,2
1,4,_,3,5,_,2
1,4,6,3,5,_,2
1,4,6,3,5,7,2

Importantly, the slots touching the edges (here 1 and 7) should be always be treated as though they have at least one side open. Consider this example:

1,2,1,1,3

The first two people come, and the third person sees this:

_,2,_,_,1

Here, the three remaining slots are actually all tied, because each has an open slot next to it, so the leftmost slot is taken:

_,2,_,_,1
3,2,_,_,1
3,2,4,_,1
3,2,4,5,1

The final result is 3,2,4,5,1.

Test cases:

1 -> 1
1,1,1 -> 1,3,2
1,2 -> 2,1
1,2,1,1,3 -> 3,2,4,5,1
3,2,4,3,1,4 -> 3,5,1,4,6,2
1,3,3,2,4 -> 5,2,3,4,1
1,1,1,2,2 -> 3,4,5,1,2
1,1,1,1,1,1 -> 1,5,3,4,6,2
1,2,3,4,5 -> 5,4,3,2,1
2,1,1,3,1 -> 2,3,5,1,4
1,1,1,2,1,1,1,1,1,3,1,1,1 -> 3,6,10,2,7,11,4,8,12,1,9,13,5

Clarifications

• The output numbers can start at 0 instead of 1.
• There will be no skipped urinal heights.

Answer 1

Jelly, 33 bytes

żJạṂ¥€¥_Je€ṖŻ+ḊƲɗɗNỤḟḣ1⁹;
“”ç@ƬṪỤ

Try it online!

A pair of links which is called with a single argument of urinal heights and returns the list of people at each urinal, as per the question spec.

Thanks to @JonathanAllan for pointing out an error related to the use of Ṭ.

Explanation

żJạṂ¥€¥_Je€ṖŻ+ḊƲɗɗNỤḟḣ1⁹;  # ‎⁡Helper link: takes the list of heights as the left argument and the current sequence of urinals used as the right; returns the updated sequence
ż                ɗ         # ‎⁢Zip the urinal lengths with the following:
      ¥                    # ‎⁣- Following as a dyad:
 J                         # ‎⁤  - Sequence 1..number of urinals
  ạṂ¥€                     # ‎⁢⁡  - For each of those, minimum absolute distance from the existing people
       _        ɗ          # ‎⁢⁢- Subtract the following run as a dyad on the original two arguments:
        Je€                # ‎⁢⁣  - Generate a list of 1 in each used urinal position and 0 in those unused (sequence along original list, check whether each in current list)
               Ʋ           # ‎⁢⁤  - Following as a monad
           Ṗ               # ‎⁣⁡    - Remove last list member
            Ż              # ‎⁣⁢    - Prepend zero
             +Ḋ            # ‎⁣⁣    - Add to the untruthied list with the first member removed
                  N        # ‎⁣⁤Negate
                   Ụ       # ‎⁤⁡Indices in ascending value order (break ties from the left)
                    ḟ      # ‎⁤⁢Filter out used indices
                     ḣ1    # ‎⁤⁣First list member (can’t use Ḣ because this returns zero if list is empty)
                       ⁹;  # ‎⁤⁤Append to existing list
‎⁢⁡⁡
“”ç@ƬṪỤ                   # ‎⁢⁡⁢Main link: take a list of urinal heights and return the list of people
“”ç@Ƭ                     # ‎⁢⁡⁣Starting with an empty list, call the helper link repeatedly with the current list on the right and the urinal heights on the left until there’s o change, gathering intermediate values
     Ṫ                    # ‎⁢⁡⁤Final version of list
      Ụ                   # ‎⁢⁢⁡Indices of list sorted by list values (takes sequence of urinals used and returns the people using the urinals as per spec)
💎

Created with the help of Luminespire.

Answer 2

Jelly, 24 bytes

-1 which led to one more thanks to Nick Kennedy!

Mạ¹ÐṂ;»Nḣʋ2ʋÞẹ0$ḢṬ¬aµƬṠS

A monadic Link that accepts the urinal heights as a list of positive integers and yields the urinal grading as a list of positive integers.

Try it online! Or see the test-suite.

How?

Repeatedly chooses the next urinal, marking it occupied by changing its height to zero until all urinals are occupied, then recovers the grading from the results.

Mạ¹ÐṂ;»Nḣʋ2ʋÞẹ0$ḢṬ¬aµƬṠS - Main Link: Heights
                    µƬ   - start with X=Heights and collect while distinct, applying:
M                        -   maximal indices -> Highest
               $         -   last two links as a monad:
              0          -     zero
             ẹ           -     indices of {zero} -> Occupied
            Þ            -   sort {Highest} by:
           ʋ             -     last four links as a dyad - f(OneOfHighest, Occupied)
 ạ                       -       absolute differences
  ¹ÐṂ                    -       keep minimal values
         ʋ2              -       last four links as a dyad - f(Minimals, 2):
      »                  -         max with two (vectorises)
     ;                   -         {Minimals} concatenate {Minimals max 2}
       N                 -         negate
        ḣ                -         keep (up to) the first {2}
                Ḣ        -   head -> leftmost of farthest of highest -> Chosen
                 Ṭ       -   untruth (e.g. 5 -> [0,0,0,0,1])
                  ¬      -   logical NOT
                   a     -   logical AND {X} -> X with a zero at Chosen urinal
                      Ṡ  - signs
                       S - sum columns

Answer 3

Charcoal, 63 58 bytes

Ｗ∧⌈θＥθ∧⁼κ⌈θ⁻⁺χ⌊Ｅθ⎇›μ⁰↔⁻λνＬθΣＥθ∧‹μ¹‹↔⁻λν²§≔θ⌕ι⌈ι±ＬΦθ‹κ¹Ｉ⁻¹θ

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

Ｗ∧⌈θＥθ∧⁼κ⌈θ⁻⁺χ⌊Ｅθ⎇›μ⁰↔⁻λνＬθΣＥθ∧‹μ¹‹↔⁻λν²

Until all of the urinals are occupied, calculate the desirability of each urinal, which is zero for all urinals shorter than the tallest, or 10 plus the distance to the nearest occupied urinal minus the number of adjacent occupied urinals for the tallest urinals.

§≔θ⌕ι⌈ι±ＬΦθ‹κ¹

Mark the leftmost urinal of those of equal maximum desirability as occupied using the negation of the number of previously occupied urinals. The first of these will be zero, which will cause the loop to exit once all of the urinals are marked as occupied.

Ｉ⁻¹θ

Output the final list of orders.

Answer 4

R, 113 bytes

\(x,s=seq(x),y=!x){for(i in s)y[order((.5/(sapply(s,\(w)min((w-s[!!y])^2))+!c(y[-1],0)*c(0,y)[s])-x)*!y)[1]]=i;y}

Attempt This Online!

A function taking a vector of urinal heights and returning a vector of people. The warnings generated occur on the first pass through when the people vector has no one in but do not affect the result.

Answer 5

Python3, 219 bytes

E=enumerate
def f(u):
 c,C=1,[0]*len(u)
 while 0==all(C):I=max([i for i,a in E(C)if 0==a],key=lambda i:(u[i],min([abs(I-i)for I,A in E(C)if A]or[0]),(i-1<0 or 0==C[i-1])+(i+1>=len(u)or 0==C[i+1])));C[I]=c;c+=1
 return C

Try it online!