Solved

# Algoriothm/puzzle

Posted on 2008-10-03
426 Views
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.
0
Question by:shwetasingh206
• 2

LVL 84

Accepted Solution

ozo earned 168 total points
ID: 22632035
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

LVL 53

Assisted Solution

Infinity08 earned 166 total points
ID: 22632041
>> 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

LVL 84

Expert Comment

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

LVL 22

Assisted Solution

ID: 22636477
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

## Featured Post

Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…
You have products, that come in variants and want to set different prices for them? Watch this micro tutorial that describes how to configure prices for Magento super attributes. Assigning simple products to configurable: We assigned simple products…