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
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 – 2015-03-18T16:59:50.4971So 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 – 2015-03-18T17:41:52.513
1@knedlsepp Rows 3, 4, 17, 18 are incorrect. In these, you place person #3 in a
span
of length 1, where there is aspan
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 – 2015-03-18T17:47:50.860Updated spec to note that the task is not the same as A095236. – Uri Granta – 2015-03-18T18:13:44.717
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 – 2015-03-18T21:43:01.860
No, it's just separators between digits that are allowed (partly for aesthetics, partly to make it easier to print arrays in some languages). I'll clarify that in the instructions. – Uri Granta – 2015-03-18T21:46:10.160
@BrainSteel: Thanks for clarifying! Somehow I also think the 'real' series should be used. But in this case it's quite an odd constraint. As for my personal taste as #3, I wouldn't feel a need to avoid situations 3,4,17,18. – knedlsepp – 2015-03-18T23:13:54.187
Is the difference between this sequence and A095236 that if you have a choice between being N urinals away from both your neighbors or being N urinals away from one neighbor and N+1 urinals away from the other, you don't have to pick the second option? – user2357112 supports Monica – 2015-03-19T07:47:28.763
@user2357112: yes, that's it. Had I noticed this originally, I would have probably phrased the task accordingly. However, given that I'd already posted the question it seemed best to go with the definition that I'd used. Also, as knedlsepp notes, it's not an obvious constraint. – Uri Granta – 2015-03-19T08:26:25.947
At a glance I thought output 3,1,2 meant "first the 3rd, then the 1st, then the 2nd urinal". For n=3, this works for all 4 example output lines. Maybe it's good to add an example for larger n, to prevent people (like myself) from making dumb comments. – freekvd – 2015-03-19T22:35:56.500
@freekvd: sorry about that. I've replaced one of the examples with n=4. – Uri Granta – 2015-03-19T22:53:33.180