Java- Walking on a Bridge

[Malymieczek]

Hi all,
Im having trouble with a program wheree a person starts in the middle of a 7 foot bridge. Heres the description:

Someone is standing at the center of a bridge that is 7 ft bridge long. Their stride is exactly one foot. They can’t control the direction they are going but the bridge is very narrow and they can only go forward or backward with each step.

Write a program that calculates how many steps the person will walk before exiting the bridge. Have the program execute this simulation 1000 times and as your output display the average and greatest number of steps taken. (Hint: generate a random number that is either 0 or 1 and let one equal forward and the other backward). Do this 20 times so that you can make comparative observations.

This is what I have so far:

import java.util.Random;
public class prog214a
{
     public static void main (String[] args)
        {
          Random generator = new Random();
          System.out.println("1000 iterations");
          int runs=0;
          int iter=1000;
          int count=7/2;
          int random;
          System.out.println("Run\tAvarage\tGreatest Number of Steps");
          for(runs=1;runs<20; runs+=1)
          {
            for(iter=1000;iter>1;iter-=1)
            {
             double avg= count/iter;
             random = generator.nextInt(2);
             if(random==0)
             {count-=1;}
             if(random==1)
             {count+=1;}
              if(count<=0 || count>=7)
              {System.out.println("#" +runs +":\t" +avg +"\t" +count);
               count =0;}
            }

            }

        }
}

What do I need to fix? Im not sure of the problem here. A fast reply would be great because I need to have this program done today >.<
Thanks!

[Taywin]

OK, your problem is about using random number generator. When you think about staying in a middle of a 7-foot bridge, it means the precision is important! Do not use int data type to represent where you are. Currently, you place yourself at location 3 which is NOT the middle (int data type will truncate any decimal). It is a bias and unfair to the higher number (incremental side).

If you are off the bridge, it means either you are at the lenght of less than 0 or greather than 7. So change your int type to a data type that accepts decimal -- either float or double. That's one issue to be fixed. Also, watch out not to use 7/2 because it will still be equal to 3. Use 7.0/2 or 7/2.0 instead.

Next you need to go back to the basic math. It is a simple arithmatic which talks about average.

your output display the average and greatest number of steps taken.

Do you understand what this statement mean? It means you must keep track of
1)The highest steps taken in order to get out of the bridge from 1000 tests and
2)The average steps in order to get out of the bridge after 1000 tests.

/*
Let's say total tries is equal to 1000
Each try, there will be a number of steps needed in order to get out of the bridge.
Therefore, has a variable to keep the total sum of the steps each try.
Then divide the total sum with the total tries, which will be the average.
While testing, has another variable keeps track of the highest steps taken in a try.
*/

That's all you need to do.

At the end of the requirement is not really misleading but confusing. The 20 times is just a sample but not what you are supposed to do. What you are supposed to do is 1000 times. Inside the 1000-time loop, you need to keep generating a random number and keep moving until the person is off the bridge (<0 or >7).

[Malymieczek]

Im not sure I understand, I think i fixed all that you have described, yet the program still will not work.
heres my code:

import java.util.Random;
import java.util.Scanner;
import java.text.DecimalFormat;
public class prog214a
{
     public static void main (String[] args)
        {
          Random generator = new Random();
          System.out.println("1000 iterations");
          int runs=0;
          int iter=1000;
          double count=7.0/2.0;
          int random;

          System.out.println("Run\tAvarage\tGreatest Number of Steps");
          //for(runs=1;runs<20; runs+=1)
          //{
            for(iter=1000;iter>1;iter-=1)
            {
            double tries = 1;
            double avg= count/tries;
             random = generator.nextInt(2);
             if(random==0)
             {count-=1;}
             if(random==1)
             {count+=1;}
             if(count<=0 || count>=7)
             {System.out.println("#" +runs +":\t" +avg +"\t" +count);
              count =0;
             runs+=1;}
               tries+=1;
            }

          //  }

        }
}

[JamesCherrill]

I have to disagree with Taywn. This is absolutely an integer problem that needs an integer solution.
The positions are described as in the middle of a 1 foot section, but that's irrelevant. YOu don't need to know where the step comes to the nearest inch. There are only 7 possible positions for the person on the bridge. Number them 1-7. The starting position is 4. Any value <1 or >7 is off the bridge. Represent the position by an integer value.
Use the Random method nextBoolean() to determine whether to ++ or -- the position, repeat until it's off the bridge. (Use a 1/0 int if your tutor doesn't understand booleans)
Count the tries, number of steps, and the totals in integer variables - they are integers! The only time you may want a floating point value is when you calculate averages or percentages.

[Taywin]

James, I have to disagree with your simplicity. If you say a middle, it is 3.5 of a 7-foot long bridge. In other words, there will equally be 4 steps to go either backward or forward in order to get off the bridge. If the person is standing at location 3-foot, there will be 4 steps v. 3 steps. The same apply to location 4-foot. This problem is to test random number generation. So in order to test it correctly, a bias should not be applied to the problem. Besides, the program can easily test with a number with precision.

@Malymicek, you will need 2 loops. One will be the 1000-time you already have, and the other will be inside that 1000-time loop. The inner one will keep randoming a direction to go either forward or backward. While inside the loop, keep counting the steps. If the person is finally off the bridge, get out of the loop. A pseudo code could be as follows:

higestStepNumber <- 0
totalStepNumber <- 0
numberOfLoop <- 1000
for loop up to numberOfLoop times
  eachRoundStepNumber <- 0
  personLocation <- 3.5    // from 7.0/2

  // The reason why using only > and < because the person location will never be
  // equal to the value of 0 or 7.
  while personLocation>0 and personLocation<7
    if random number indicates to go forward
      increment personLocation by 1
    else
      decrement personLocation by 1
    end if
    increment eachRoundStepNumber by 1
  end while

  // now deal with the highest step
  if highestStepNumber is less than eachRoundStepNumber
    highestStepNumber <- eachRoundStepNumber
  end if

  // now deal with total
  add eachRoundStepNumber to totalStepNumber
end for

// now deal with average
averageStep <- totalStepNumber/numberOfLoop

// after this, you can display the result

Theoretically, the program will be stuck inside the inner loop if and only if the random number generator is very good (50% chance of either direction). In practice, there is no such a random number generator.

[JamesCherrill]

I think you misunderstood my point. Feet and half-feet are irrelevant to the problem as stated. There are exactly 7 positions on the bridge where the person can stand, and the fourth of those 7 is the center position, 3 away from each end.
Anyway, i won't interrupt this thread any further. ;)
J

[Taywin]

Hmm... James, you are talking about edges, but the problem is asking about vertices. :) There are 7 edges, but there are 8 vertices.

  e0   e1   e2   e3   e4   e5    e6     <--- 7 edges is 7-foot   
0----1----2-----3----4----5----6----7
v0   v1   v2   v3   v4   v5   v6   v7   <--- 8 vertices is 8-location

Now, look at the above graph diagram, you will see that at position 4 (v4), you will walk to the right 3 steps and you are at the edge of the bridge (v7), but require 4 steps to get to the left edge (v0). A similar situation but in reverse applies to position 3 (v3) that you need only 3 steps to get to the left edge of the bridge but require 4 steps to get to the right edge. :)

PS: It is a good idea to have your input because it helps indirectly. :)

[JamesCherrill]

Sorry, I'm not talking about edges, vertices, bridges, feet, strides or anything else like that.
This is simply a 9-state problem. The 9 states and the 16 permitted transitions are
0 <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> 7 <-> 8
State 4 is the initial state. States 0 and 8 are the terminal states.
At every pass of the loop you perform one transition chosen at random from the two possibles.
All the stuff about bridges is just window dressing to confuse you. You could dress it up in terms of journeys between train stations, or as a gambling game based on one-dollar coin tosses that terminates when you win or lose 4 dollars, and the math would be exactly the same.
I suggested an int representation because the states do fall along a linear transiiton map, but if the problem were slightly more interesting (eg a number of bridges between various islands - how long before you reach the mainland) then you would have to use some kind of generalised state and transition map.

[Taywin]

Number them 1-7. The starting position is 4. Any value <1 or >7 is off the bridge.

You are correct on the dress up of the problem, and also you are correct on talking about states. However, could you answer me what the 4th state in your list represet a location on the bridge?

Represent the problem with graph still stands corrected. I think you have the right solution, However, your first answer, which I disagree and quoted above, cannot apply to [0,7] (or (0,7)) but will be (0,7] or [0,7) problem. Your state explanation is now (0,8) which can be use with [0,7]. It is a bit too deep for beginners.

To get rid of the [0,7], represent it with decimal would eliminate the inclusive range. So if shift the integer into a decimal, it actually makes the problem clearer.

 s0 <-> s1 <-> s2 <-> s3 <-> s4 <-> s5 <-> s6 <-> s7 <-> s8
-0.5    0.5    1.5    2.5    3.5    4.5    5.5    6.5    7.5

As you can see that it is clear that the distance of 0.5 and 6.5 are still on the bridge. It is more visualisable.

 s0 <-> s1 <-> s2 <-> s3 <-> s4 <-> s5 <-> s6 <-> s7 <-> s8
  0      1      2      3      4      5      6      7      8

For this integer, it is clear that 0 and 7 are questional. If you allow 0 to be on the bridge (active), why can't you allow 7 to be on the bridge as well? If you don't allow 0 to be on the bridge (active), then you should not allow 7 to be on the bridge as well. Then if you don't allow 1 and 7, you are shortening active states and that will not cover the whole 7 active states that represent the 7-foot bridge (the problem).

PS: I edited the post many times to make it clearer after reread it. :(

[JamesCherrill]

The state numbered 4 in both posts corresponds to "standing at the center of a 7 foot bridge".

It is, of course, completely arbitrary whether you measure distances from one end of the bridge or from its center, and what units you chose to measure in, although measuring from the center in units of one step has the advantage of reducing all the positions to integral numbers of steps left or right of the starting position.

[Taywin]

OK, that is much clearer. :) You are totally correct on the concept but your description, which would be applied to the application (problem), in the first post is incorrect. The number you would want to talk about should be between 0 to 8 exclusive instead of 1 to 7 exclusive. :) State number could be confusing for beginners when applies them to certain applications. Anyway, that's good to get it out.

[JamesCherrill]

I believe my original post numbered the positions on the bridge as 1-7 and "any value <1 or >7 is off the bridge". The only change in the later posts was to use 0 instead of <1, and 8 instead of >7.
Anyway... enough?

[Taywin]

No hard feeling. I just want to clarify it because the number would confuse beginners. They may not be able to chew the concept. :)