35
\$\begingroup\$

Of course, the SE network is very knowledgeable about how to be respectful in the restroom, but for those of you who need a recap, being respectful means flushing the toilet, etc. Most importantly, though, it means using the stall as far away from others as possible.

The challenge

Given a blueprint of a set of stalls with indications of which ones are in use as a string, you must return or print from a function or program where the most respectful place to do your business is.

The input

 0 1 2 3 4 5    <- The stall number which is not actually visible in the input. 
| | |-| |-|-|   <- the stalls

The stalls are numbered in ascending order from left to right. There will always be at least one empty stall. There can be up to 50 stalls in an input. You can also take the input as an array or string of 0s and 1s or booleans if you prefer to do so.

Stalls in use have - in them (in between the pipes).

The output

The most respectful stall to go to is the one that is on average farthest away from the ones in use. The distance between two stalls is the absolute value of the difference of the numbers above them.

Just to be clear: you are finding the average distance from all of the stalls—not just the neighboring ones.

You must output the lowest number of the most respectful stall to go to that is empty.

Examples

Input:
|-| |-| OR 101
Output:
1

Input:
| | |-| |-|-| OR 001011
Output:
0

Input:
|-| |-| | | | |-|-| OR 101000011
Output:
1

Input: 
|-| | | | | |-|-| | | | | OR 100000110000
Output:
11

Input:
|-|-|-|-| | | | | | |-| OR 11110000001
Output:
9

Input:
|-| | OR 10
Output:
1

Input:
|-| | |-| OR 1001
Output:
1

This is , so shortest code in bytes wins!

You can use 0 or 1 based indexing in your answer — whichever you prefer; if you use 1 based indexing, then you must say so explicitly in your answer.

\$\endgroup\$
  • 35
    \$\begingroup\$ "Of course, the SE network is very knowledgeable about how to be respectful in the restroom" [citation needed] \$\endgroup\$ – Alex A. Aug 9 '16 at 16:33
  • 7
    \$\begingroup\$ @AlexA.: Have a look at the toilet questions and answers on travel.stackexchange to assess the level of education of the SE network (or to educate yourself). \$\endgroup\$ – Jonas Aug 9 '16 at 17:05
  • 30
    \$\begingroup\$ But everyone knows that the respectfulness criterion is to maximize the minimun distance, not the average :-) \$\endgroup\$ – Luis Mendo Aug 9 '16 at 17:26
  • 2
    \$\begingroup\$ @Dopapp You should add [1,0,0,1] as a test case. None of the current test cases verifies if ties are broken correctly. \$\endgroup\$ – Dennis Aug 9 '16 at 17:52
  • 8
    \$\begingroup\$ Why does 101000011 return 1 (instead of 4 or 5)? \$\endgroup\$ – Amani Kilumanga Aug 10 '16 at 4:02

15 Answers 15

11
\$\begingroup\$

Jelly, 10 9 bytes

JạþTS׬MḢ

Uses 1-based indexing. Try it online! or verify all test cases.

How it works

JạþTS׬MḢ  Main link. Argument: A (array of Booleans)

J          Yield all indices of A.
   T       Yield all truthy indices of A.
 ạþ        Compute the table of absolute differences.
    S      Compute the sums of all columns.
           For each index, this yields the sum of all distances to occupied stalls.
     ׬    Multiply each sum by the logical NOT of the corresponding Boolean in A.
           This zeroes sums that correspond to occupied stalls.
       M   Maximal; yield an array of all indices of maximal sums.
        Ḣ  Head; extract the first index.
\$\endgroup\$
  • \$\begingroup\$ I believe that's 9 characters, not 9 bytes. \$\endgroup\$ – René Nyffenegger Aug 11 '16 at 7:05
  • \$\begingroup\$ Jelly uses a custom code page that encodes the only characters it understands as a single byte each. The bytes link in the header points to it. \$\endgroup\$ – Dennis Aug 11 '16 at 15:06
  • \$\begingroup\$ I was unaware of this... thanks for pointing it out. \$\endgroup\$ – René Nyffenegger Aug 11 '16 at 19:45
  • \$\begingroup\$ @Dennis Did you make an auto-comment userscript so you can just click on "Jelly bytes comment" and it will post it? \$\endgroup\$ – NoOneIsHere Aug 12 '16 at 16:02
  • \$\begingroup\$ @NoOneIsHere I do have that userscript (not mine), but I didn't add this one yet. I probably should though... \$\endgroup\$ – Dennis Aug 12 '16 at 16:04
6
\$\begingroup\$

Swift, 158, 157, 128, 100 Bytes

Takes input from the Array<Bool> variable i, returns answer from the last expression.

let e=i.characters.map{$0>"0"}.enumerate()
e.flatMap{$1 ?nil:$0}.map{a in(a,e.flatMap{$1 ?$0:nil}.map{abs(a-$0)}.reduce(0){$0+$1})}.maxElement{$0.1 < $1.1}!.0

Edit 1:

Saved a byte by converting to bools via string comparison

let e=i.characters.map{$0=="1"}.enumerate()
e.flatMap{$1 ?nil:$0}.map{a in(a,e.flatMap{$1 ?$0:nil}.map{abs(a-$0)}.reduce(0){$0+$1})}.maxElement{$0.1 < $1.1}!.0

Edit 2:

Reworked my algorithm:

let e=i.characters.map{$0=="1"}.enumerate()
e.map{x in(x.0,x.1 ?0:e.reduce(0){$1.1 ?$0+abs(x.0-$1.0):$0})}.max{$0.1<$1.1}!.0

Edit 3:

Took advantage of new rule that allows taking input directly from a boolean array.

let e=i.enumerated()
e.map{x in(x.0,x.1 ?0:e.reduce(0){$1.1 ?$0+abs(x.0-$1.0):$0})}.max{$0.1<$1.1}!.0

Ungolfed:

// for the sake of easier copy/pasting of input, take it as string
let s = "100000110000"

// convert input to true for taken, false for free
// this is the input the golfed version actually uses
let input = s.characters.map{$0>"0"}

// Returns an array of tuples storing the array values (vacancy of the stall) and their index (their location)
let valueIndexPairs = bools.enumerated()

// Returns an array of pairs of locations and their avg distance to others
let locationDistancePairs = valueIndexPairs.map{(valueIndexPair: (Int, Bool)) -> (Int, Int) in

    let averageDistance = valueIndexPairs.reduce(0) {partialSum, otherStall in

        let otherStallIsTaken = otherStall.1

        if otherStallIsTaken {
            //don't let other stalls effect average if they're taken
            return partialSum
        }
        else {
            let thisStallLocation = valueIndexPair.0
            let otherStallLocation = otherStall.0
            let distanceToOtherStall = abs(thisStallLocation - otherStallLocation)
            return partialSum + distanceToOtherStall 
        }       
    }

    //if this stall is taken, treat its average distance to others as 0
    let thisStallsLocation = valueIndexPair.0
    let isThisStallTaken = valueIndexPair.1
    return (thisStallsLocation, isThisStallTaken ? 0 : averageDistance)
}

//find location where average distance is maxiumum
let bestLocationIndexPair = locationDistancePairs.max{$0.1 < $1.1}!

let bestLocation = bestLocationIndexPair.0

print(bestLocation)
\$\endgroup\$
  • 2
    \$\begingroup\$ I like swift answers \$\endgroup\$ – downrep_nation Aug 10 '16 at 10:22
  • \$\begingroup\$ It's fun to learn :) Although it tends to be a pretty painful language for golfing. The standard library is truly minimal (you're intended to use Foundation most of the time), the language is meant to be very expressive, and it's statically typed. The closure syntax is REALLY good though \$\endgroup\$ – Alexander Aug 10 '16 at 14:18
  • \$\begingroup\$ I should probably explain how this code works lol \$\endgroup\$ – Alexander Aug 10 '16 at 14:19
  • 1
    \$\begingroup\$ @downrep_nation I added the ungolfed verison, in case you're interested \$\endgroup\$ – Alexander Aug 10 '16 at 19:44
  • \$\begingroup\$ Perhaps save 3 bytes by removing "let" idk if you do need it or not, but from what I understand you do not need "let" which only serves as an indicator of a constant value \$\endgroup\$ – Rohan Jhunjhunwala Aug 11 '16 at 1:08
5
\$\begingroup\$

Jelly, 13 bytes

1-indexed.

³Tạ⁸S
JUÇÞḟTṪ

Try it online!

Algorithm

Naive implementation of the question.

\$\endgroup\$
  • \$\begingroup\$ lol around 16 times shorter than my answer + 1! (1!==1) \$\endgroup\$ – Rohan Jhunjhunwala Aug 9 '16 at 17:01
  • \$\begingroup\$ @RohanJhunjhunwala What did you say? \$\endgroup\$ – Leaky Nun Aug 9 '16 at 17:03
  • \$\begingroup\$ Essentially Java can never compete with Jelly Seeing answers that are 12 bytes long (shorter than any possible java program) is hilarious. So have an upgoat.. \$\endgroup\$ – Rohan Jhunjhunwala Aug 9 '16 at 17:04
  • \$\begingroup\$ @LeakyNun lol missed the golf :D \$\endgroup\$ – Rohan Jhunjhunwala Aug 9 '16 at 17:05
  • 2
    \$\begingroup\$ 1001 outputs 3 when it should return 2 \$\endgroup\$ – Daniel Aug 9 '16 at 19:06
5
\$\begingroup\$

Java "only" 270 200 196 187 196 138 148 146 bytes!

saved 4 13 countless bytes thanks to Leaky Nun! 1 byte thanks to Micheal Golfed

int m(boolean[]b){int r=0,l=b.length,i,j,k=0,z=r;for(i=0;i<l;i++){if(b[i])for(j=0,k=0;j<l;j++)if(!b[j])k+=i>j?i-j:j-i;if(k>z){r=i;z=k;}}return r;}

Ungolfed

int m(int[] s) {
        int l=s.length,i,j=0,k=0;
    boolean[] b = new boolean[l];
    int[] a = new int[l];
    //see what stalls are open
    for (i = 0; i < s.length; i++) {
        if (s[i] == 0){
            b[i] = true;
        }
    }
    //assign the sum of distance to the a[]
    for (i = 0; i < l; i++) {
        if (b[i]) {
            for (j = 0; j < l; j++) {
                if (!b[j]) {
                    a[i]+= Math.abs(i - j);
                }
            }
        }
    }
    //find the stall the greatest distance away breaking ties based on the furthest left
    for (i = 0; i < l; i++) {
        if (b[i] && (a[i] > k || k == 0)) {
            k = a[i];
            j=i;
        }
    }
    //return the index
    return j;
}

input as an boolean array where true implies an open stall.

\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Alex A. Aug 9 '16 at 18:20
  • \$\begingroup\$ You don't need the array a. \$\endgroup\$ – Leaky Nun Aug 10 '16 at 8:24
  • \$\begingroup\$ @LeakyNun how do I remove it? \$\endgroup\$ – Rohan Jhunjhunwala Aug 10 '16 at 11:06
  • \$\begingroup\$ By finding the minimum in one iteration (combine the outer for loops) \$\endgroup\$ – Leaky Nun Aug 10 '16 at 11:07
  • \$\begingroup\$ oh @LeakyNun will do when I get back today \$\endgroup\$ – Rohan Jhunjhunwala Aug 10 '16 at 11:26
4
\$\begingroup\$

Ruby, 79 78 76 + n flag = 77 bytes

Output is 0-based indexing. Input is STDIN line of 0's and 1's.

p (r=0...~/$/).max_by{|i|k=0;$_[i]>?0?0:r.map{|j|k+=$_[j]<?1?0:(j-i).abs};k}
\$\endgroup\$
  • 1
    \$\begingroup\$ 0...~/$/ is a nice trick. 👍🏻 \$\endgroup\$ – Jordan Aug 10 '16 at 1:26
2
\$\begingroup\$

MATL, 14 bytes

~ftGf!-|Xs&X>)

Try it online!

Output is 1-based.

Explanation

~f     % Implicitly take input. Compute row vector with indices of zeros
t      % Duplicate that
Gf!    % Push input again. Compute column vector of indices of ones
-|     % Absolute differences with broadcast. Gives 2D array with all combinations
Xs     % Sum of each column
&X>    % Arg max. Gives the index of the first maximizer if there are several
)      % Index into row vector of indices of zeros. Implictly display
\$\endgroup\$
2
\$\begingroup\$

Perl 84 + 3 (-alp flags) = 87 bytes

for$i(0..$#F){$t=0;map{$t+=abs($i-$_)*$F[$_]}0..$#F;($m,$_)=($t,$i)if$m<$t&&!$F[$i]}

Needs -alp flags to run. Takes a string of 1 and 0 separated by spaces as input. For instance :

perl -alpe '$m=0;for$i(0..$#F){$t=0;map{$t+=abs($i-$_)*$F[$_]}0..$#F;($m,$_)=($t,$i)if$m<$t&&!$F[$i]}' <<< "1 0 1
0 0 1 0 1 1
1 0 1 0 0 0 0 1 1
1 0 0 0 0 0 1 1 0 0 0 0
1 1 1 1 0 0 0 0 0 0 1
1 0"

Note that I added $m=0 at the begining, but that's only to test it on multiple entries.

\$\endgroup\$
  • \$\begingroup\$ I count +7: F'' alp. -s aren't counted. \$\endgroup\$ – NoOneIsHere Aug 9 '16 at 17:09
  • \$\begingroup\$ @NoOneIsHere Hum, indeed, that would be my bad. Thanks \$\endgroup\$ – Dada Aug 9 '16 at 17:13
2
\$\begingroup\$

Matlab, 87 bytes

n=input('');k=numel(n);[a b]=ndgrid(1:k);[x y]=max(sum(abs(a-b).*repmat(n,k,1)').*~n);y

Takes array of ones and zeros; uses 1-based indexing.
Like some other answers maximises total not average distance.
Probably there's some more golfing possible...

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 87 86 82 75 bytes

a=>a.map((u,i)=>u||(a.map((v,j)=>u+=v*(i>j?i-j:j-i)),u>x&&(x=d,r=i)),x=0)|r

Takes a boolean array (true/false or 1/0). No point calculating the average distance since they're all using the same common factor, so just calculating the total distance for each stall and finding the first index of the highest one. Edit: Saved 1 byte by using * instead of &&. Saved 5 bytes by finding the highest distance manually based on a comment by @Dendrobium. Saved 7 bytes by reusing u as the pseudo-reduce accumulator based on a comment by @edc65.

\$\endgroup\$
  • \$\begingroup\$ 79 bytes: a=>(x=0,a.map((o,i)=>x<(t=a.reduce((r,u,j)=>r+(b=i-j)*b*u*!o,0))&&(x=t,r=i)),r) \$\endgroup\$ – Dendrobium Aug 9 '16 at 19:54
  • \$\begingroup\$ @Dendrobium The question asks for absolute distance; you seem to be calculating RMS distance. \$\endgroup\$ – Neil Aug 9 '16 at 20:45
  • 1
    \$\begingroup\$ Using an array as input - good idea. Calculating total instead of average - good idea. Using reduce instead of map - mmmm \$\endgroup\$ – edc65 Aug 9 '16 at 21:22
  • \$\begingroup\$ 75: s=>s.map((u,i)=>u||(s.map((w,j)=>u-=w*Math.abs(j-i)),u<x&&(x=u,r=i)),x=0)|r \$\endgroup\$ – edc65 Aug 9 '16 at 21:29
  • \$\begingroup\$ @Neil Not quite RMS, just squared distances, which shouldn't effect the outcome of the solution unless there are ties in total distances of nonsymmetric inputs (for example 1100011101 ties at 2 and 8 when using absolute, 8 when using squared), not that it matters since it seems that the rules have been clarified and ties are now resolved with the left-most stall... \$\endgroup\$ – Dendrobium Aug 9 '16 at 22:15
1
\$\begingroup\$

J, 27 bytes

(#{:@-.~]/:[:+/]|@-/~#)i.@#

Online interpreter.

\$\endgroup\$
1
\$\begingroup\$

Ruby, 87 76 bytes

Threw this first draft quickly together, but in the meantime Value Ink had already posted an 80 byte Ruby answer...

edit: took off some bytes with help from Value Ink:

->a{(r=0...a.size).max_by{|i|a[i]?0:r.map{|j|a[j]?(i-j).abs: 0}.reduce(:+)}}

It's an anonymous function that takes an array of truthy/falsy values, like for instance so:

f=->->a{(r=0...a.size).max_by{|i|a[i]?0:r.map{|j|a[j]?(i-j).abs: 0}.reduce(:+)}}
# Test case number 5:
p f[[1, 1, 1, 1, nil, nil, nil, nil, nil, nil, 1]] # => 9
\$\endgroup\$
  • 1
    \$\begingroup\$ Assign the initial range to a variable (r=0...a.size) and then map on that instead of using with_index: r.map{|j|a[j]?(i-j).abs: 0}. This should get you 78 bytes. \$\endgroup\$ – Value Ink Aug 9 '16 at 19:07
  • \$\begingroup\$ @ValueInk Awesome, thanks! With only the function, no assignment, I get 76 bytes \$\endgroup\$ – daniero Aug 9 '16 at 19:49
1
\$\begingroup\$

Mathematica, 53 bytes

MaximalBy[a=PositionIndex@#;a@0,Tr@Abs[#-a@1]&][[1]]&

Uses 1-based indexing and takes input as a list of 0s and 1s.

\$\endgroup\$
0
\$\begingroup\$

Javascript ES6 - 98 95 91 86 84 88 bytes

Edit: Seems that the leftmost-stall should be used in the case of a tie. Squared distances no longer work, reverted to absolute distance.

(r,x=0,f=g=>r.reduce(g,0))=>f((p,o,i)=>x<(o=f((p,c,j)=>p+c*!o*Math.abs(i-j)))?(x=o,i):p)

Ungolfed:

(r,                            // string input
 x=0,                          // current max distance
 f=g=>r.reduce(g,0))=>         // iterator function
   f((p,o,i)=>                 // for each stall
     x<(o=f((p,c,j)=>          // iterate through all stalls and
       p+c*!o*Math.abs(i-j)))? //   calculate sum of distances from current stall
     (x=o,i):                  // if total dist is greater than x, update x, return index
     p)                        //   else return previous max index

Test runs:

f=(r,x=0,f=g=>r.reduce(g,0))=>f((p,c,i)=>x<(c=+c?0:f((p,c,j)=>p+c*Math.abs(i-j)))?(x=c,i):p)
f([1,0,1])                   // 1
f([0,0,1,0,1,1])             // 0
f([1,0,1,0,0,0,0,1,1])       // 1
f([1,0,0,0,0,0,1,1,0,0,0,0]) // 11
f([1,1,1,1,0,0,0,0,0,0,1])   // 9
f([1,0])                     // 1
\$\endgroup\$
0
\$\begingroup\$

Lua, 165150 Byes

n=arg[1]n=n:gsub("%|%-","1"):gsub("%| ","0")i=0 for s in n:gmatch("0+")do i=(i<#s)and(#s)or(i)end n,l=n:find(("0"):rep(i))print(n+math.floor((l-n)/2))

This cheats a little using the fact that generally, lua passes a table called arg containing any command line inputs to it.

I'm a bit disappointed that I used a for in loop, but I couldn't think of a smaller way to pull it off.

Also, Because lua, 1 based indexing was used.

Edit Snipped 15 bytes from a wasteful gsub.

\$\endgroup\$
0
\$\begingroup\$

C#, 127 bytes

public int G(char[]s){int i=0;var l=s.ToLookup(b=>b,b=>i++);return l['0'].OrderBy(j=>l['1'].Average(p=>Math.Abs(p-j))).Last();}

Test Bed

public static void Main() {
    var respectful = new Respectful();
    foreach (var kvp in testCases) {
        $"{kvp.Key}: Expected {kvp.Value} Actual {respectful.G(kvp.Key.ToCharArray())}".Dump();
    }
}

public static readonly List<KeyValuePair<string, int>> testCases = new List<KeyValuePair<string, int>> {
    new KeyValuePair<string, int>("101", 1),
    new KeyValuePair<string, int>("001011", 0),
    new KeyValuePair<string, int>("101000011", 1),
    new KeyValuePair<string, int>("100000110000", 11),
    new KeyValuePair<string, int>("11110000001", 9),
    new KeyValuePair<string, int>("10", 1),
    new KeyValuePair<string, int>("1001", 1),
};

public class Respectful {
    public int G(char[]s){int i=0;var l=s.ToLookup(b=>b,b=>i++);return l['0'].OrderBy(j=>l['1'].Average(p=>Math.Abs(p-j))).Last();}
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.