Computer related puzzles and questions

[Sip]

Ok smart people ... here's an algorithmic problem:

 

Problem

----------

There are four people who have to cross a bridge. They all begin on the same side. You have 17 minutes to get them all across to the other side. It is night, and they have one flashlight. A maximum of two people can cross the bridge at one time. Any party that crosses, either one or two people, must have the flashlight with them. The flashlight must be walked back and forth; it cannot be thrown, for example.

 

Each person walks at a different speed. Here's how long it takes each to cross the bridge:

 

Person 1: 1 minute

Person 2: 2 minutes

Person 3: 5 minutes

Person 4: 10 minutes.

 

A pair must walk together at the rate of the slower person's pace. For example, if person 1 and person 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If person 4 returns the flashlight, a total of 20 minutes have passed and you have failed the mission.

 

How?

[Twilight Bark]

Ok smart people ... here's an algorithmic problem:

 

Problem

----------

There are four people who have to cross a bridge. They all begin on the same side. You have 17 minutes to get them all across to the other side. It is night, and they have one flashlight. A maximum of two people can cross the bridge at one time. Any party that crosses, either one or two people, must have the flashlight with them. The flashlight must be walked back and forth; it cannot be thrown, for example.

 

Each person walks at a different speed. Here's how long it takes each to cross the bridge:

 

Person 1: 1 minute

Person 2: 2 minutes

Person 3: 5 minutes

Person 4: 10 minutes.

 

A pair must walk together at the rate of the slower person's pace. For example, if person 1 and person 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If person 4 returns the flashlight, a total of 20 minutes have passed and you have failed the mission.

 

How?

1 & 2 cross first (2 min.)

1 goes back with the flashlight (3 min.)

3 & 4 cross (13 min.)

2 goes back with the flashlight (15 min.)

1 & 2 cross (17 min.)

 

Edited October 10, 2003 by Twilight Bark

[Sip]

Well done sir! needless to say, I was getting ready to prove it's impossible and it was after spending considerable amount of time not being able to prove such a thing that I realized there is a solution!!!!!

[Harut]

get a random real number from x to y inclusive?

[Sip]

suppose r() is a function that returns a random real value between 0.0 and 1.0 inclusive. In C/C++, you can for example have:

 

r = (float) (rand() % 1001) / 1000.0

 

To get between x and y, you want:

 

if (x

else R = (x-y) * r + y

 

 

You can also use RAND_MAX to get r but I usually just rely on the above. So the question is, how random do you want it! Obviously this is not truely random since we have at most precison of 3 digits after the decimal. Oh and note here that if x and y are very far apart, this is not a good way to do it.

[Harut]

hmm, i was thinking VB. how would you do that in VB?

yes, it's relatively easy in C++ for smaller ranges. but VB... i'm having a hard time.

[Sip]

Doesn't rnd() in VB give a random number between 0 and 1? (I think less than 1)

 

Why can't you do the same thing as in C?

[Harut]

how about

i = ((Rnd * 1001) Mod 1001) / 1000

 

am i taking the long way?

[Sip]

why not just RND? Are you worried about the inclusive/exclusive thing?

 

Here's a brief reminder from statistics ... if you have a uniform random variable X between range 0-1 (inclusive let's say), the Probability P(X=a) = 0 for a given real value a. So in other words, the probability that you get 1 (or 0) or any other given value a is 0.

 

So if you just want a floating point random value between 0 and 1, just use RND. Between x and y, just use (y-x) * RND + x

 

Of course all these are "pseudorandom" anyway. So what are you trying to do that you are so worried about the inclusive/exclusive end points? Is possibility of getting exactly 1 really that important to what you are doing? Because most often this is a non issue.

[Azat]

hmmm. it seems like a very simple problem

 

lowerBound = 100

upperBound = 500

 

randomize ' to make sure you get a true random number

 

randNum=Int((Upperbound - Lowerbound + 1) * Rnd + Lowerbound)

[Sip]

Azat, he wants a real value. You don't want the "int". Although for integers that works fine, if you take "INT" out, with what you wrote you have values from lowerb (inclusive) to upperb + 1 (non inclusive).

[Harut]

ay ay ay

i'm not trying to do anything. it's just that while writing a literary analysis essay, i started having a thought on the back of my head as "how would i get a random real number from x to y inclusive in VB"?

 

yes

P(X=a) = 0

but is that really true for simple computational languages such as VB, with the limited precision digits?

 

btw, in what kind of situations would we ever want to have a random real number? what is it useful for?

[Azat]

Well, I have always felt that peoples paycheck should be a real random number based on a min and max. to give us incentive to open up the envelop each time we get paid. Wouldn't that be cool?

[Sasun]

Since you are talking about random numbers, I have always wondered: how does a computer generate a random number? I mean, all these random functions in different languages - what is the randomness based on?

[DominO123]

Since you are talking about random numbers, I have always wondered: how does a computer generate a random number? I mean, all these random functions in different languages - what is the randomness based on?

From the stupid programming C++ course I had, the most simplistic way was to use time(clock) as a random generator... I suppose most of the simple prgrams do that.

Edited November 20, 2003 by Fadix

[Sasun]

From the stupid programming C++ course I had, the most simplistic way was to use time(clock) as a random generator... I suppose most of the simple prgrams do that.

I guess that would be uniform random - but I doubt it is completely random. What about random normal?

[Sasun]

By the way, the language that I use (SAS) works the following way. RANUNI(t) generates a random univariate number, it is based on the clock when t>0, but not on the clock when t=0. I get the feeling that clock is not a perfect random number generator, so I always us t=0. But I have no idea what is used in this case (my book doesn't say anything).

[DominO123]

By the way, the language that I use (SAS) works the following way. RANUNI(t) generates a random univariate number, it is based on the clock when t>0, but not on the clock when t=0. I get the feeling that clock is not a perfect random number generator, so I always us t=0. But I have no idea what is used in this case (my book doesn't say anything).

I don't know what they use else, but if it was of me, I would use a clock system where there is many different times taken and from a number corresponding another series of times taken etc... a kind of complext configuration, where for each number found, there is another clock generated number...

 

But still, I do not think that there is real perfect random generators... I heard in the past that heat generated random would be implammented in some chips... maybe Sip could unlighten about if it has been finaly done.

Edited November 20, 2003 by Fadix

[Sip]

I'll post a detailed answer soon about the true randomness but for now, just take my word that what is generated is random enough (i.e. mathematically they can prove that there is no pattern to it for very very very long sequences). However, depending on where the "seed" is (i.e. where you start taking numbers from the sequenc) things will be the same.

 

In other words, if you seed the random number generator at 10, every time you wil get the same sequence of random numbers. This is why it's pseudo random. In order to get randomness, people use tricks like Domino is saying which is seeding the generator by the current clock value which will be different every time a program is run.

 

But more on this later.

[Sasun]

Oh... I lied above.. actually it is the other way around with the RANUNI function. When you give a non-sero number it uses it as a seed, and like Sip says if you use the same seed every time you will get the same results. If you give a 0 seed then it will use the clock time as seed.

[Sip]

Ok fellas ... a bit more on this if you are interested

 

These functions that we are talking about, generate "pseudorandom" sequences. This means by repeatedly calling the funtion you get a sequence of values that is random. But wherever you start in the sequence of numbers, you will get the same set of numbers in order. The seeding (or randomizing) just decides where to start in the sequence.

 

This is good for when you are writing a simulation or a program or a game that needs random things, but should be repeatable. In other words, next time you run the simulation with a different set of parameters, you may want the same random data to see how your simulation is behaving.

 

Here is an example of such a pseudorandom generator ... it is for a uniform distribution ... transforming this to other distributions like to "normal" is not that hard. There are many different kinds some providing different levels of randomness ... the "size" of your number representation will determine how your function should work ... so this is probably for a 32-bit machine.

 

#define MODULUS    2147483647 /* DON'T CHANGE THIS VALUE                  */
#define MULTIPLIER 48271      /* DON'T CHANGE THIS VALUE                  */
#define CHECK      399268537  /* DON'T CHANGE THIS VALUE                  */
#define STREAMS    256        /* # of streams, DON'T CHANGE THIS VALUE    */
#define A256       22925      /* jump multiplier, DON'T CHANGE THIS VALUE */
#define DEFAULT    123456789  /* initial seed, use 0 < DEFAULT < MODULUS  */
     
static long seed[STREAMS] = {DEFAULT};  /* current state of each stream   */
static int  stream        = 0;          /* stream index, 0 is the default */
static int  initialized   = 0;          /* test for stream initialization */


  double Random(void)
/* ----------------------------------------------------------------
* Random returns a pseudo-random real number uniformly distributed 
* between 0.0 and 1.0. 
* ----------------------------------------------------------------
*/
{
 const long Q = MODULUS / MULTIPLIER;
 const long R = MODULUS % MULTIPLIER;
 long t;

 t = MULTIPLIER * (seed[stream] % Q) - R * (seed[stream] / Q);
 if (t > 0) 
   seed[stream] = t;
 else 
   seed[stream] = t + MODULUS;
 return ((double) seed[stream] / MODULUS);
}

 

As you can see, basically the function does a bunch of long multiplication, division, and then modulous on BIG numbers and basically the "remainder" can be shown to be "random". It will repeat but after like 2^32 (I am guessing) or some huge number of iterations.

 

These are done in "software". If you are still interested, I can tell you how in hardware one can generate random numbers ... and for example what kinds of things they are doing in Vegas machines to get "true" randomness.

 

Interestingly enough, I had a question on this in my last midterm I gave on linear feed back registers

[Sasun]

Sip, very interesting. If I am not mistaken, human errors are distributed with a normal distribution. If I undertand correctly what you are saying, the randomness is generated by the deviations(errors) of calculation. That means computer errors are distributed uniformly?

[Sip]

No what I am saying is that that particular function can be used to generate a uniformly pseudorandom sequence of numberes that will not repeat until a VERY large number of iterations.

 

Given that get_rand() can produce a random variable with uniform random value from 0 to 1, here's how you can get a gaussian (normal) distribution using two such random variables t1 and t2.

 

double gauss () { 
double t1=get_rand();
double t2=get_rand();
if (t1<TOLERANCE) t1=TOLERANCE;
return (sqrt(-2.0* log(t1))*cos(t2 * TWOPI));
}

 

Tolerance is a very small number but you basically need that since log(0) is undefined. Again, when dealing with computers you always have finite precison problems but for all practical purposes such things are more than accurate (and random) enough.

 

But keep in mind there are many ways to do these things. The math part is not my strength and I just know enough to have been able to use them over and over for different simulations and things.

[DominO123]

Sip, I've heard some times ago that(if my memory is not failing) Intel was to implament a random generator based on heat... have you some news about that? If it was for me, I would place in a chip, a radioactive ellement, and use the radioactive decay as a random generator.... it's cheap, and it is one of the best way that physicists use to creat randomnity...

[Sasun]

I think I understand now. So basically what we have are numbers that are artificially (meaning no actual physical/hardware random processes involved) created to be randomly distributed. Actually now that I look more carefully you had made it clear in your previous post. I agree, that degree of randomness should be more than enough. In fact, any natural random distribution is not perfectly distributed normally/uniformly or any other way. So even if hardware generated randomness is more random it will be less perfect than software generated one. But maybe not, who knows...