cresjoy - 2 months ago 13x
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.

Comments