cresjoy cresjoy - 3 months ago 16
Java Question

Filling stalls within an Array ( Big Java Ex 7.22)

For Some background here is the problem statement.


It is a well-researched fact that men in a restroom generally prefer
to maximize their distance from already occupied stalls, by occupying
the middle of the longest sequence of unoccupied places. For example,
consider the situation where ten stalls are empty.

_ _ _ _ _ _ _ _ _ _ The first visitor will occupy a middle position:

_ _ _ _ _ X _ _ _ _ The next visitor will be in the middle of the empty area at the left.

_ _ X _ _ X _ _ _ _

Write a program that reads the number of stalls and then prints out diagrams in the format given above when the stalls become filled, one at a time. Hint: Use an array of boolean values toindicate whether a stall is occupied.


I have also found the solution for which I understand for the most part but am having trouble understanding a bit. Here it is

import java.util.Scanner;
class StallLogic
{
public void printStalls(boolean [] b)
{
for(boolean s:b)
{
System.out.print((s?"X" : "_") + " ");
}
System.out.print("\n");
}

public boolean giveFlag(boolean [] b)
{
for(boolean s : b)
{
if(!s) return false;
}
return true;
}

public int getLongest(boolean [] b)
{
int length = 0, temp = 0;
int len = b.length;
for(int i = 0; i < len ; i++)
{
if (b[i] == false)
{
temp++;
}
else{
temp = 0;
}
if (length < temp)
length = temp;
}
return length;
}

public int checkIndex(boolean [] b)
{
int length = 0 , temp = 0, ind = 0;
int len = b.length;
for (int i = 0 ; i < len ; i++)
{
if(b[i] == false)
{
temp++;
}
else{
temp = 0;
}
if (length < temp)
{
ind = i -length;
length = temp;
}
}
return ind;
}

public void findStalls(boolean [] b)
{
int loc = checkIndex(b);
int len = getLongest(b);
int ind = loc + len / 2;
b[ind] = true;
}
}

public class checkStall
{
public static void main(String [] args)
{
StallLogic stallin = new StallLogic();
System.out.print("Enter number of stalls");
Scanner in = new Scanner(System.in);
int i = in.nextInt();
boolean [] stalls = new boolean [i];
while(!stallin.giveFlag(stalls))
{
stallin.findStalls(stalls);
stallin.printStalls(stalls);
}

}


}


My Struggles

I'm having trouble understand what the point of
checkIndex
really is. I understand that
getLongest
, will tell us which parts of the arraylist have the most successive
_
's

For example in
_ _ _ _ _ X _ _ _ _
We check that the left side has more
_
with
getLongest
. Now the problem is we need an actual index to put the
X
in. How Will our program know whether to put it on the left side or the right side of every pre-existing X? This is where I PRESUME the
checkIndex
comes in.

Particularly What I am confused about is why I am taking the maximum count of how many _'s there are and adding it with the specific index? I.e
int ind = loc + len / 2;


What is
checkIndex
and
int ind = loc + len / 2,
exactly doing here? Is there some algorithm for this I am not realizing?

Answer

Without writing out the algorithm, it would appear that getLongest is returning the length of the longest empty section of stalls.

Then, checkIndex gets the left-most empty stall of that same section.

With those two numbers, you simply split the difference, and occupy that stall left + (length / 2).


It's a less efficient approach by "scanning" the stalls twice. The getLongest and checkIndex methods could be combined to return an int[] of both positions because the inclusion of int ind is the only change between the two methods.