# Algoriothm/puzzle

Assume your computer is reading characters one by one from a stream (you don't know the length of the stream before ending). Note that you have only one character of storage space (so you cann't save the characters you've read to a something like a strong). When you've finished reading you should return a character out of the stream with equal probability.
###### Who is Participating?

Commented:
perldoc -q "How do I select a random line from a file"
How do I select a random line from a file?

Here's an algorithm from the Camel Book:

rand(\$.) < 1 && (\$line = \$_) while <>;

This has a significant advantage in space over reading the whole file
in.  You can find a proof of this method in The Art of Computer
Programming, Volume 2, Section 3.4.2, by Donald E. Knuth.
0

Commented:
>> a character out of the stream with equal probability.

with equal probability ? What do you mean ? You want a uniformly random character from the stream without knowing the size of the stream ?

If so, simply do something like this :

1st character : save it in the buffer
2nd character : save it in the buffer with 1/2 probability
3rd character : save it in the buffer with 1/3 probability
...
nth character : save it in the buffer with 1/n probability
...
0

Commented:
So for single characters
stream | perl -ne 'BEGIN{\$/=\1}\$char = \$_ if rand(\$.) < 1;END{print \$char}'
0

Commented:
This is the way to do it, but it requires additional storage to hold the count of the number of characters you've read.  There is a counter behind \$., or perl is using ftell() and the counter is hidden in the runtime libraries.

So really you need something like ceil(lg(n)) + 8 bits of storage to handle up to n characters of input.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.