The Optimal Urinal Strategy

Question

Here is an interactive page describing the problem and an academic paper going over the mathematics.

The problem can be roughly described as follows.

Given an arbitrary-length array of boolean values representing n adjacent urinals, with values of true indicating occupied and values of false indicating vacant, how would you construct an algorithm to populate this array, given any configuration, while:

• Maximizing the 'privacy' of each occupant by keeping one as far as possible from other urinators on either side.

• Maintaining this privacy for as long as possible by ensuring the configuration becomes saturated at the last possible time.

• Faced with multiple suboptimal choices, prioritizing urinals without an adjacent urinal on either side over a merely unoccupied adjacent urinal.

I marked this javascript for simplicity, but any code or pseudo-code would be fine.

var urinals = Array
    .apply(null, new Array(n))
    .map(Boolean.prototype.valueOf,false);

---

edit - found a related problem here:

Optimal Seating Arrangement Algorithm

Answer 1

As close as I have to a solution:

var urinalFinder = function(urinals){
    var gaps = new Array(), last = null;
    for(var i = 0; i < urinals.length; i++){
        last = gaps.length ? gaps[gaps.length - 1] : 0;
        if(last < 0 && !urinals[i] || last > 0 && !!urinals[i] || last == 0) 
            gaps.push(0); // push if new sequence of vacant or occupied
        // negatives are occupied count & positives vacant count
        gaps[gaps.length - 1] += !!urinals[i] ? -1 : 1; 
    }

    // find the first index of the largest gap
    var maxGapSize = Math.max.apply(Math, gaps),
        maxGapGapsIdx = gaps.indexOf(maxGapSize),
        isFirst = maxGapGapsIdx === 0,
        isLast = maxGapGapsIdx === gaps.length - 1,
        maxGapIdx = 0;

    if(maxGapSize < 1) return false; // no gaps available

    var gapPoint = maxGapSize > 3 
            ? Math.ceil(maxGapSize / 3) // per xkcd suggestion
            : isFirst && maxGapSize === 2
                ? 1
                : isLast && maxGapSize === 2 ? 2 : Math.ceil(maxGapSize / 2);

    // find where our chosen gap begins in input array
    for(var i = 0; i < maxGapGapsIdx; i++)
        maxGapIdx += Math.abs(gaps[i]);

    var result = maxGapIdx + gapPoint - 1; // arrays are zero-indexed

    return result;
};

For example, applied to filling an array of 9 vacant spaces will fill them like this:

var foo = [0,0,0,0,0,0,0,0,0]; // nine values
for(var i = 0; i < foo.length; i++)
    foo[urinalFinder(foo)] = i+1;

[4, 6, 1, 7, 2, 8, 3, 9, 5]

Does not always produce optimal results (sometimes a different placement could allow saturation a few moves later) and does not favor end urinals, but does a pretty good job fanning values around and keeping a minimum buffer for just about as long as possible.