12
\$\begingroup\$

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.
Improve this question
\$\endgroup\$
9
  • \$\begingroup\$ In the case of 3,2,2,2,3,2,2,1, which urinal is used third? \$\endgroup\$ Commented Nov 3, 2023 at 21:05
  • \$\begingroup\$ @Neil 1,_,_,_,_,_,_,_ 1,_,_,_,2,_,_,_ 1,_,3,_,2,_,_,_ 1,_,3,_,2,_,4,_ 1,5,3,_,2,_,4,_ 1,5,3,6,2,_,4,_ 1,5,3,6,2,7,4,_ 1,5,3,6,2,7,4,8 \$\endgroup\$ Commented Nov 3, 2023 at 21:15
  • 1
    \$\begingroup\$ @NickKennedy That was a bad example since the output for 1,1,1 is already 1,3,2 but no, I think I'll stick with this format. \$\endgroup\$ Commented Nov 3, 2023 at 22:44
  • 1
    \$\begingroup\$ Suggested test case: 2,1,1,3,1 to test the "implicit empty urinal" at the right. \$\endgroup\$ Commented Nov 4, 2023 at 23:01
  • 1
    \$\begingroup\$ I look forward to advances in Pee Queue (PQ) theory. Next up: balancing men's and women's rooms. \$\endgroup\$ Commented Nov 5, 2023 at 2:00

5 Answers 5

Reset to default
4
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Hopefully fixed now, thanks for spotting. It related to Ṭ only producing a list as long as the max of its argument. I’ve replaced it with Je€ using both arguments. \$\endgroup\$ Commented Nov 5, 2023 at 0:22
3
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Use of ¹ÐṂ;2 is clever. That one change would have saved me seven bytes if I’d spotted it. \$\endgroup\$ Commented Nov 5, 2023 at 1:08
  • \$\begingroup\$ ...except it doesn't quite work, see my latest. This has been making my head spin :p \$\endgroup\$ Commented Nov 5, 2023 at 1:27
  • \$\begingroup\$ This saves one: tio.run/#%23y0rNyan8/9/… \$\endgroup\$ Commented Nov 5, 2023 at 9:31
  • \$\begingroup\$ Nice chaining, that gave me one more by sorting in reverse by replacing the no-op ¹ with negation N. \$\endgroup\$ Commented Nov 6, 2023 at 0:29
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ I don’t know charcoal but is it possible that it’d be shorter to assign urinals by moving left and right in the canvas? \$\endgroup\$ Commented Nov 4, 2023 at 10:50
  • \$\begingroup\$ @noodleman I tried it and it was 64 bytes. (And only works up to lists of length 9.) \$\endgroup\$ Commented Nov 4, 2023 at 11:21
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ You can move the while loop onto a single line. \$\endgroup\$ Commented Nov 5, 2023 at 1:51
  • \$\begingroup\$ @noodleman Yes indeed, updated \$\endgroup\$ Commented Nov 5, 2023 at 1:55
  • \$\begingroup\$ 207 bytes \$\endgroup\$ Commented Aug 28 at 17:43

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.