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:
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).
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.
The next person will take the next tallest, but if there is a tie, choose the urinal furthest from any already taken urinal.
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
But what about a situation like this:
The logic above applies until this state is reached:
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:
The first two people come, and the third person sees this:
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
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
- The output numbers can start at 0 instead of 1.
- There will be no skipped urinal heights.