Positional Bathroom Etiquette
MATL, 19 18 17 bytes
lyf!Gn:-H_^Xs&X<(
Try it online! Or verify all test cases (slightly modified code).
Explanation
It suffices to compute the distance from each potential new position to the already occupied ones. The remaining distances are do not depend on the potential new position, and so constitute a constant term, which can be ignored.
Let's take input [1 0 0 0 0 0 1]
as an example.
l % Push 1
% STACK: 1
y % Take input implicitly. Duplicate from below
% STACK: [1 0 0 0 0 0 1], 1, [1 0 0 0 0 0 1]
f! % Indices of nonzero elements, as a column array
% STACK: [1 0 0 0 0 0 1], 1, [1 7]
Gn: % Push [1 2 ... n], where n is input size (array of possible positions)
% STACK: [1 0 0 0 0 0 1], 1, [1; 7], [1 2 3 4 5 6 7]
- % Matrix with all pairs of differences
% STACK: [1 0 0 0 0 0 1], 1, [1; 7], [0 -1 -2 -3 -4 -5 -6;
6 5 4 3 2 1 0]
H_^ % Raise each entry to -2
% STACK: [1 0 0 0 0 0 1], 1, [ Inf 1.0000 0.2500 0.1111 0.0625 0.0400 0.0278;
0.0278 0.0400 0.0625 0.1111 0.2500 1.0000 Inf]
Xs % Sum of each column
% STACK: [1 0 0 0 0 0 1], 1, [Inf 1.04 0.3125 0.2222 0.3125 1.04 Inf]
&X< % Index of minimum. Takes the first if there is a tie
% STACK: [1 0 0 0 0 0 1], 1, 4
( % Assign: write 1 at the position of the minimizer
% STACK: [1 0 0 1 0 0 1]
% Implicitly display
JavaScript (ES6), 89 bytes
a=>a[a.map((e,i)=>!e&&(t=0,a.map((e,j)=>t+=(j-=i)&&e/j/j),t<m&&(m=t,k=i)),k=0,m=1/0),k]=1
Outputs by modifying the input array.
R, 83 76 67 bytes
Just realized that I can save several bytes by not bothering to check if the candidate urinals are empty. Non-empty urinals will always return an Inf
discomfort value, so they're excluded in the course of the calculation. Also, just using direct indexing rather than replace
, so it's shorter but less elegant.
x=scan()
x[which.min(rowSums(outer(seq(x),which(!!x),`-`)^-2))]=1
x
Explanation
x=scan()
We read the current state from stdin and call it x
. We assume that the input is a sequence of 1
s and 0
s separated by spaces or newlines. For the purposes of the explanation, let's say we input 1 0 0 0 0 0 1
.
x[which.min(rowSums(outer(seq(x),which(!!x),`-`)^-2))]=1
We replace a value of x
at a particular index with 1. Everything between the [ ]
is figuring out what the best index is.
Since the existing urinals are immutable, we don't need to consider the distances between them. We only need to consider the distances between the occupied urinals and the possible new one. So we determine the indices of the occupied urinals. We use which
, a function to return the indices of a logical vector which are TRUE
. All numbers in R, when coerced to type logical
, are TRUE
if nonzero and FALSE
if zero. Simply doing which(x)
will result in a type error, argument to 'which' is not logical
, as x
is a numeric vector. We therefore have to coerce it to logical. !
is R's logical negation function, which automatically coerces to logical. Applying it twice, !!x
, yields a vector of TRUE
and FALSE
indicating which urinals are occupied. (Alternative byte-equivalent coercions to logical involve the logical operators &
and |
and the builtins T
and F
, e.g. F|x
or T&x
and so on. !!x
looks more exclamatory so we'll use that.)
which(!!x)
This is paired with seq(x)
, which returns the integer sequence from 1
to the length of x
, i.e. all urinal locations (and thus all possible locations to consider).
seq(x)
Now we have the indices of our occupied urinals: 1 7
and our empty urinals 1 2 3 4 5 6 7
. We pass `-`
, the subtraction function, to the outer
function to get the "outer subtraction", which is the following matrix of distances between all urinals and the occupied urinals:
[,1] [,2]
[1,] 0 -6
[2,] 1 -5
[3,] 2 -4
[4,] 3 -3
[5,] 4 -2
[6,] 5 -1
[7,] 6 0
outer(seq(x),which(!!x),`-`)
We raise this to the -2
th power. (For those who are a little lost, in the OP, "discomfort" is defined as 1 / (distance(x, y) * distance(x, y))
, which simplifies to 1/d(x,y)^2
, i.e. d(x,y)^-2
.)
outer(seq(x),which(!!x),`-`)^-2
Take the sum of each row in the matrix.
rowSums(outer(seq(x),which(!!x),`-`)^-2)
Get the index of the smallest value, i.e. the optimal urinal. In the case of multiple smallest values, the first (i.e. leftmost) one is returned.
which.min(rowSums(outer(seq(x),which(!!x),`-`)^-2))
And voilà, we have the index of the optimal urinal. We replace the value at this index in x
with 1
. In the case of 1111
as input, it doesn't matter which one we replace, we'll still have a valid output.
x[which.min(rowSums(outer(seq(x),which(!!x),`-`)^-2))]=1
Return the modified input.
x