# The Urinal Protocol

## Background

The so-called "Urinal Protocol", describing the order in which individual urinals are picked in a men's bathroom, has been discussed in multiple places. One version is given in this xkcd blog post. This question concerns a slight variation:

Arrangement: n urinals in a line.
Protocol: each new person selects one of the urinals most distant from those already in use.

Note that this places no restrictions on which urinal is picked by the first person.

Update: The sequence of the number of different ways in which n people can select n urinals starts with 1, 2, 4, 8, 20... Note that this not the same as OEIS A095236, which describes slightly stricter restrictions than in this question.

## Task

Given an integer n between 0 and 10, output (in any order) all the possible orderings in which n people can occupy n urinals. Each ordering should be printed as the final arrangement: a sequence of digits representing the people (1-9 for the first 9 people, 0 for the tenth), starting from the leftmost urinal, with optional non-alphanumeric separators between (but not before or after) the digits. For example, the following outputs are both valid:

>> 3
132
213
312
231

>> 4
1|3|4|2
1|4|3|2
3|1|4|2
4|1|3|2
2|3|1|4
2|4|1|3
2|3|4|1
2|4|3|1


You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument. Results should be printed to STDOUT (or closest alternative).

## Scoring

Shortest code wins. Standard terms & conditions apply.

• Hm. For 5 urinals I get this. It should be 16 rows instead. Would anyone please elaborate which of those solutions are wrong? This is currently implementing: Choose any one of the urinals with maximum distance to anybody else. – knedlsepp Mar 18 '15 at 16:59
• So much for sandboxing :-( Spec is as described in the task, not the sequence definition. I'll update as soon as I get to a computer. – Uri Granta Mar 18 '15 at 17:41
• @knedlsepp Rows 3, 4, 17, 18 are incorrect. In these, you place person #3 in a span of length 1, where there is a span of length 2 available. I've suddenly managed to confuse myself. It would appear the OP is intentionally derived from the link, and thus the link should be followed? – BrainSteel Mar 18 '15 at 17:47
• Updated spec to note that the task is not the same as A095236. – Uri Granta Mar 18 '15 at 18:13
• Is it allowed to output the format in [1, 3, 2], where each such solution is seperated by newlines? (so not only a seperator of ", ", but also a start of "[" and end of "]") – orlp Mar 18 '15 at 21:43

# Pyth, 53 51

MhSm^-dG2HjbmjdmehxkbQusmm+dkfqgTdeSmgbdQUQGUtQm]dQ


This is an iterative approach. Given a possible partially filled in ordered sets of locations, we find all the optimal further locations, then generate the corresponding location list, and repeat.

Results are generated in the form [<first person's location>, <second person's location> ...], then this is transformed into the desired format. MhSm^-dG2H defines a helper function which finds the minimum distances from a given stall to an occupied stall (squared). Amusingly, the separator is free.

Example run.

Explanation:

First, the helper function g, which finds the minimum squared distance between G and any value in H.

MhSm^-dG2H
M             def g(G,H): return
hS           min(                         )
m     H        map(lambda d:        , H)
^-dG2                      (d-G)**2


Next, we find the maximum over urinal locations of the minimum squared distance between that urinal and any occupied urinal:

(Q is the input.)

eSmgbdQ
eS          max(                                   )
m   Q         map(lambda b:      , range(len(Q)))
gbd                       g(b,d)


d in this case is the list of occupied urinals, while b iterates over urinal locations.

Next, we find all urinal locations whose minimum squared distance from the nearest occupied urinal is equal to the maximum value found above.

fqgTdeSmgbdQUQ
f           UQ    filter(lambda T:                             , range(len(Q)))
qgTd                             g(T,d) ==
eSmgbdQ                                <value found above>


Next, we will generate the urinal location lists created by adding the urinal locations found above to d. We will do this for each previous list of urinal locations, thus extending the lists from length N to N+1. G is the list of legal lists of occupied urinal locations of a given length.

smm+dkfqgTdeSmgbdQUQG
sm                  G    sum(map(lambda d:                               ,G)
m+dk                                   map(lambda k:d+[k],            )
fqgTdeSmgbdQUQ                                        <above list>


Next, we will apply the above expression repeatedly, to generate the complete list of lists of occupied urinal locations. u, the reduce function, does exactly this, as many times as there are elements in its second argument.

usmm+dkfqgTdeSmgbdQUQGUtQm]dQ
usmm+dkfqgTdeSmgbdQUQG           reduce(lambda G,H: <the above expression)
UtQ        repeat Q-1 times
m]dQ    starting with [[0], [1], ... [Q-1]].


Convert from the above representation, which goes [<1st location>, <2nd location>, ... ], to the desired output form, [<person in slot 1>, <person in slot 2>, ... ]. Then, the output form is joined into the output string and printed. Printing is implicit.

jbmjdmehxkbQ
jbm             '\n'.join(map(λ k:                                    ,<above>)
jdm     Q                      ' '.join(map(λ b:                ,Q)
xkb                                        b.index(k)
eh                                                     +1 %10


• Damnit, I should stop writing recursive solutions in Pyth. I always get beat out :P – orlp Mar 18 '15 at 23:02
• kajsdlkas^23asdjkla1lasdkj~JZasSSA - almost half the size. – Optimizer Mar 19 '15 at 6:20
• @Optimizer I'll add an explanation when I'm less busy. – isaacg Mar 19 '15 at 6:22

# Pyth, 7571 67

DcGHFk_UQJf!s:GeS,0-TkhS,h+TklGUQIJRsmcX>G0dhHhHJ)R]Gjbmjdmebkcm0Q0


Recursive combinatorial solution.

It's a fairly direct translation from this Python solution:

N = int(input())

def gen(l, p):
for d in reversed(range(N)):
s = []
for i in range(N):
if not sum(l[max(0,i-d):min(i+d+1, len(l))]):
s.append(i)

if s:
r = []
for possib in s:
j = l[:]
j[possib] = p+1
r += gen(j, p+1)

return r

return [l]

print("\n".join(" ".join(str(x % 10) for x in sol) for sol in gen([0] * N, 0)))

• How does that work? In more detail than "recursive combinatorial solution". – tbodt Mar 18 '15 at 22:46
• @tbodt Added the Python code which I wrote before translating to Pyth. – orlp Mar 18 '15 at 22:58

# C, 929 878 bytes

This one's a monster, guys. Sorry.

typedef unsigned long U;typedef unsigned char C;U f(int*u,n){C c[8],a[8];*(U*)(&c)=-1;int i,b=0,l=-9,s=-2,f=0,d;for (i=0; i<n; i++) {if (!u[i]&&s<0)s=i,l=0;if(!u[i])l++;if(u[i]&&s>=0){if(!s)l=2*l-1;d=(l-1)/2;if(b<d)*(U*)(a)=0,*(U*)(c)=-1,*c=s,*a=l,f=1,b=d;else if(b==d)c[f]=s,a[f++]=l;s=-1;}}if(s>=0&&l){l=2*l-1;d=(l-1)/2;if(b<d)*(U*)(c)=-1,*c=s,*a=l,f=1,b=d;else if(b==d)c[f]=s,a[f++]=l;}d=f;for(i=0;i<d;i++){if((c[i]+1)&&c[i]){if(c[i]+a[i]==n)c[i]=n-1;else{if(!(a[i]%2))c[f++]=b+c[i]+1;c[i]+=b;}}}return*(U*)c;}void P(int*u,n,i,c,m){for(i=0;i<n;i++){if(!u[i])c++;if(u[i]>m)m=u[i];}if(!c){for(i=0;i<n;i++)printf("%d",u[i]==10?0:u[i]);printf("\n");}else{int s[8][n];for(i=0;i<8;i++)for(c=0;c<n;c++)s[i][c]=u[c];U t=f(u,n);C*H=&t;for(i=0;i<8;i++)if((C)(H[i]+1))s[i][H[i]]=m+1,P(s[i],n,0,0,0);}}void L(n){int u[n],i,j;for(i=0;i<n;i++){for(j=0;j<n;j++)u[j]=j==i?1:0;P(u,n,0,0,0);}}


Defines 3 functions, f(int*,int),P(int*,int,int,int,int), and L(int). Call L(n), and it outputs to STDOUT.

Output for n=5:

14352
15342
31452
31542
41352
51342
41532
51432
24153
25143
34152
35142
23415
23514
24513
25413
24315
25314
24351
25341


Update: I removed separators and fixed up the code. The old code not only failed for n=7+, but failed to output anything at all for n=10 (oops!). I've more thoroughly tested this bunch. It now supports input of up to n=13 (though the "%d" should be changed to "%x"so it prints in hexadecimal). The size of input depends on sizeof(long) and it is assumed to be 8 in practice.

Here's some explanation of how it works, and why such an odd restriction exists:

These were used a lot, so we define them to save a couple bytes:

typedef unsigned long U; typedef unsigned char C;

Here is f:

U f(int*u,n){
C c[8],a[8];
*(U*)(&c)=-1;
int i,b=0,l=-9,s=-2,f=0,d;
for (i=0; i<n; i++) {
if (!u[i]&&s<0)
s=i,l=0;
if(!u[i])
l++;
if(u[i]&&s>=0){
if(!s)
l=2*l-1;
d=(l-1)/2;
if(b<d)
*(U*)(a)=0,
*(U*)(c)=-1,
*c=s,
*a=l,
f=1,
b=d;
else if(b==d)
c[f]=s,a[f++]=l;
s=-1;
}
}
if(s>=0&&l){
l=2*l-1;
d=(l-1)/2;
if(b<d)
*(U*)(c)=-1,
*c=s,
*a=l,
f=1,
b=d;
else if(b==d)
c[f]=s,a[f++]=l;
}
d=f;
for(i=0;i<d;i++){
if((c[i]+1)&&c[i]){
if(c[i]+a[i]==n)
c[i]=n-1;
else{
if(!(a[i]%2))
c[f++]=b+c[i]+1;
c[i]+=b;
}
}
}
return*(U*)c;
}


f takes an array of integers of size n, and n itself. The only clever bit here is that it returns an unsigned long, which is converted into a char[8] by the calling function. Each character in the array is thus set either to 0xFF or to an index pointing to a valid urinal for the next person. For n<10, we never need more than 5 bytes to hold every valid urinal the next person can use.

Here is P:

void P(int*u,n,i,c,m){
for(i=0;i<n;i++){
if(!u[i])c++;
if(u[i]>m)m=u[i];
}
if(!c){
for(i=0;i<n;i++)
printf("%d",u[i]==10?0:u[i]);
printf("\n");
}
else{
int s[8][n];
for(i=0;i<8;i++)
for(c=0;c<n;c++)
s[i][c]=u[c];
U t=f(u,n);
C*H=&t;
for(i=0;i<8;i++)
if((C)(H[i]+1))
s[i][H[i]]=m+1,P(s[i],n,0,0,0);
}
}


P takes an array u of size n wherein exactly one element is set to 1, and the rest are 0. It then finds and prints every permutation possible recursively.

Here is L:

void L(n){
int u[n],i,j;
for(i=0;i<n;i++){
for(j=0;j<n;j++)
u[j]=j==i?1:0;
P(u,n,0,0,0);
}
}


L simply calls P n times with different starting positions each time.

For the interested, this (less golfed) f will generate the sequence in A095236.

U f(int*u,n) {
C c[8];
*(U*)(&c) = -1;
int i,b=0,l=-10,s=-2,f=0,d;
for (i=0; i<n; i++) {
if (!u[i]&&s<0) {
s=i,l=0;
}
if(!u[i]){
l++;
}
if (u[i]&&s>=0) {
if (!s) {
l=2*l-1;
}
if (b<l) {
*(U*)(&c)=-1;
c[0]=s;
f=1;
b=l;
}
else if (b==l)
c[f++]=s;
s=-1;
}
}
if (s>=0&&l) {
l=2*l-1;
if (b<l) {
*(U*)(&c)=-1;
c[0]=s;
f=1;
b=l;
}
else if (b==l)
c[f++]=s;
}
d=f;
for (i=0; i<d; i++) {
if ((c[i]+1)&&c[i]) {
if (c[i]+b==n) {
c[i]=n-1;
}
else{
if (!(b%2)) {
c[f++]=(b-1)/2+c[i]+1;
}
c[i]+=(b-1)/2;
}
}
}
return *(U*)c;
}

• "1 4 ..." at the start seems to be against the spec: if the first number is 1, the next one should be 5. – anatolyg Mar 18 '15 at 21:32
• @anatolyg No. Here's a step-by-step explanation of how "1 4" can happen: gist.github.com/orlp/a5706ba664b70209b48a – orlp Mar 18 '15 at 21:35
• Remember, the separators are optional. You can save 1 byte(!) by removing the space after the %d :-) – Uri Granta Mar 18 '15 at 21:41
• @UriZarfaty Thanks! Actually, there are a ton of bytes to be saved here. I'm currently writing a better solution up and an explanation. – BrainSteel Mar 18 '15 at 21:53
• @yo' I think you're confusing the output a little bit. An output of 14352 means person #1 chose the left-most urinal. Person #2 chose the right-most one, which then forced #3 into the middle. It's not the number of the urinal picked next that should be output. – BrainSteel Mar 19 '15 at 0:16

# Python 2, 208

n=input()
r=range(n)
l=[0]*n
def f(a,d=-1):
if a>n:print''.join(l);return
for i in r:
t=min([n]+[abs(i-j)for j in r if l[j]])
if t==d:p+=[i]
if t>d:p=[i];d=t
for i in p:l[i]=a%10;f(a+1);l[i]=0
f(1)


Recursive approach.

# JavaScript (ES6) 153 160 169

Edit Using Math.min to find (of course) the max distance: streamlined code and 16 bytes saved.

Recursive search, can work with n > 10, just remove % 10 (and be prepared to wait while the console unrolls all its output).

I use a single array to store the slot in use (positive numbers) or the current distance from the nearest slot (negative numbers so < and > are swapped in code).

F=n=>{(R=(m,d,t,x=Math.min(...d=m?
d.map((v,i)=>(c=i<t?i-t:t-i)?v<c?c:v:m%10)
:Array(n).fill(-n)))=>
x<0?d.map((v,i)=>v>x||R(-~m,d,i)):console.log(d+[]))()}


Ungolfed

F=n=>{
var R=(m, // current 'man', undefined at first step
d, // slot array
t // current position to fill
) =>
{
if (m) // if not at first step
{
d[t] = m % 10; // mark slot in use, (10 stored as 0 )
d = d.map((v,i) => { // update distances in d[]
var c = i<t ? i-t : t-i; // distance from the current position (negated)
return v < c ? c : v; // change if less than current distance
});
}
else
{
d = Array(n).fill(-n) // fill distance array with max at first step
// negative means slot free, value is the distance from nearest used slot
// >= 0 means slot in use by man number 1..n
}
var x = Math.min(...d);
if ( x < 0 ) // if there is still any free slot
{
d.forEach((v,i) => { // check distance for each slot
if (v <= x) // if slot is at max distance, call recursive search
R(-~m, [...d], i) // ~- is like '+1', but works on undefined too
});
}
else
{
console.log(d+[]); // no free slot, output current solution
}
}

R() // first step call
}


Test In Firefox/FireBug console

F(5)


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

# Mathematica, 123 104

f[n_,s_:{}]:=If[Length@s<n,f[n,s~Join~{#}]&/@MaximalBy[Range@n,Min@Abs[#-s]&];,Print@@Ordering@s~Mod~10]

• @MartinBüttner n~f~s~Join~{#} will become Join[f[n,s],{#}]. – alephalpha Mar 19 '15 at 11:09
• Oh right, I thought it was right associative. – Martin Ender Mar 19 '15 at 11:48

## MATLAB, 164

function o=t(n),o=mod(r(zeros(1,n)),10);function o=r(s),o=[];d=bwdist(s);m=max(d);J=find(d==m);if~d,o=s;J=[];end,n=max(s)+1;for j=J,o=[o;r(s+n*(1:numel(s)==j))];end


# Perl, 174

Not very short, but fun. I'm not counting use feature 'say'; towards the byte total.

$n=pop;@u="_"x$n." "x$n."_"x$n;for$p(1..$n){@u=map{my@r;for$x(reverse 0..$n){
s/(?<=\D{$x}) (?=\D{$x})/push@r,$_;substr$r[-1],pos,1,$p%10/eg and last; }@r}@u}y/_//d&&say for@u  De-golfed: $n = pop; # Get number of urinals from commandline
@state = ( "_" x $n . " " x$n . "_" x $n ); for my$person (1 .. $n) { # Replace each state with its list of possible next states. @state = map { my @results; for my$distance (reverse 0 .. $n) { # If there are any spots with at least$distance empty on
# both sides, then add an entry to @results with the current
# $person number in that spot, for each spot. Note that this # is only used for its side-effect on @results; the modified$_
# is never used.
s{
(?<=\D{$distance}) [ ] (?=\D{$distance})
}{
push @results, $_; substr$results[-1], pos(), 1, $person % 10; }xeg # If we found any spots, move on, otherwise try # with$distance one lower.
and last;
}
# New state is the array we built up.
@results;
} @state;
}

# After adding all the people, remove underscores and print the results
for my $result (@state) {$result =~ tr/_//d;
say $result; }  # C, 248 bytes This code uses a recursive algoritm to generate the desired outcome. void q(char*f,int l,int d,char*o){char*c=f;while(f<c+l){if(!*f){sprintf(o+4*d,"%03i,",f-c);*f=1;q(c,l,d+1,o);*f=0;}f++;}if(d+1==l){o[4*d+3]=0;printf("%s\n",o);}}int main(int i,char**v){int k=atoi(v[1]);char*c=calloc(k,5),*o=c+k;q(c,k,0,o);free(c);}  Expanded: void printperms(char* memory,int length,int offset,char*output) { char*temp_char=memory; while(memory<temp_char+length) { if(!*memory) { sprintf(output+4*offset,"%03i,",memory-temp_char); *memory=1; printperms(temp_char,length,offset+1,output); *memory=0; } memory++; } if(offset+1==length) { output[4*offset+3]=0; printf("%s\n",output); } } int main(int i,char**v) { int argument=atoi(v[1]); char*t=calloc(argument,5),*output=t+argument; printperms(t,argument,0,output); free(t); }  # Bash, 744 674 bytes This is still way too long :). I use a string to represent the row of urinals and a flooding algorithm to find the most distant urinals in each phase of recursion. The ungolfed code is almost self-explanatory. The number of urinals is read from keyboard. Code (golfed): read l;u=----------;u=-${u::$l}- s(){ u=${u:0:$1}$2${u:$((1+$1))};} m(){ local u=$1;a=();while :;do [ 0 -ne expr index - ${u:1:$l} ]||break;t=$u;y=$u;for i in seq $l;do [${y:$i:1} = - ]||{ s$(($i-1)) X;s$(($i+1)) X;};done;done;while :;do k=expr index$t -;[ 0 != $k ]||break;t=${t:0:$(($k-1))}X${t:$k};if [ 1 -ne $k ]&&[$(($l+2)) -ne$k ];then a+=($(($k-1)));fi;done;}
e(){ local u f b v;u=$1;f=$2;if [ 1 -eq $l ];then echo 1;return;fi;if [ 1 =$f ];then for i in seq $l;do v=$u;s $i 1;e$u 2;u=$v;done;else m$u;b=(${a[@]});if [ 0 -eq${#b} ];then echo ${u:1:$l};else for i in ${b[@]};do v=$u;s $i$(($f%10));e$u $(($f+1));u=$v;a=(${b[@]});done;fi;fi;}
e $u 1  Use: $ source ./script.sh
input number of urinals from keyboard


And ungolfed it goes:

read l  # read number of urinals
u=----------
u=-${u:0:$l}- #row is two positions longer (it will be helpful when finding the most distant urinals)

# So, for the end, with 6 men, u might look like this:
# -143652-

# subu no fellow_no => set urinal [number] occupied by [fellow_no]
# this is just convenience for resetting a character inside a string
subu(){ u=${u:0:$1}$2${u:$((1+$1))};}

# this will be iterated in longest to find the remotest places:
# -1---3---2- => spreadstep => X1X-X3X-X2X => spreadstep => X1XXX3XXX2X
# see longest() to get more explanation.
spreadstep()
{
y=$u for i in seq 1$l
do
if [ "${y:$i:1}" != "-" ]
then
subu $(($i-1)) X
subu $(($i+1)) X
fi
done
}

# Find the urinals with the longest distance. It uses spreadstep() - see above.
# -1---3---2- => spreadstep => X1X-X3X-X2X => spreadstep => X1XXX3XXX2X
# ---> last state with free ones was X1X-X3X-X2X ,
#                                     123456789
# free urinals are no. 3 and no. 7 => save them to arr
longest()
{
local u=$1 arr=() while true do if [ 0 -eq expr index -${u:1:$l} ] then break fi save=$u
spreadstep
done

while true
do
index=expr index $save - if [ 0 ==$index ]
then
break
fi

save=${save:0:$(($index-1))}X${save:$index} if [ 1 -ne$index ] && [ $(($l+2)) -ne $index ] then arr+=($(($index-1))) fi done } # main function, recursively called # the first fellow may take any of the urinals. # the next fellows - only those with the longest distance. placements_with_start() { local u=$1
local fellow=$2 if [ 1 -eq$l ] # special case - there is no 2nd fellow, so below code would work incorrect
then
echo "1"
return
fi
if [ 1 == $fellow ] # may take any of urinals then for i in seq 1$l
do
local _u=$u subu$i 1                     # take the urinal
placements_with_start $u 2 # let the 2nd fellow choose :) u=$_u
done
else
longest $u # find the ones he can take local _arr=(${arr[@]})
if [ 0 -eq ${#_arr} ] then echo${u:1:$l} # no more free urinals - everyone took one - print the result else for i in${_arr[@]}
do
local _u=$u subu$i $(($fellow % 10))                # take urinal
placements_with_start $u$(($fellow+1)) # find locations for for next fellow u=$_u
arr=(${_arr[@]}) done fi fi } placements_with_start$u 1