Fortune
April 5, 2011
It is possible to read the entire fortunes file into an array of lines, then select one line at random, but instead we choose a streaming algorithm: choose the first line with probability 1/1, then replace it with the second line with probability 1/2, then replace it with the third line with probability 1/3, and so on, so that when all the lines have been read each line will have been chosen with probability 1/n, where n is the number of lines in the file. Here’s the code:
(define (fortune file-name)
(with-input-from-file file-name
(lambda ()
(let loop ((line (read-line)) (n 1) (fort ""))
(if (eof-object? line) fort
(loop (read-line) (+ n 1)
(if (< (rand) (/ n)) line fort)))))))
The key is the expression (< (rand) (/ n)). If the random fraction is less then 1/n, fort is replaced by the current line.
We need to reseed the random number generator so that every run of the program produces a different aphorism. We use the current date and time, which Chez Scheme returns in the standard Unix date format Sat Apr 2 12:06:22 2011 when calling (date-and-time); other Scheme systems have other conventions. We also have to check if the user entered a filename on the command line. Here’s the main program:
(define (get-digits str)
(string->number (list->string (filter char-numeric? (string->list str)))))
(rand (get-digits (date-and-time)))
(display (fortune
(if (null? (cdr (command-line)))
"/usr/games/lib/fortunes"
(cadr (command-line)))))
(newline)
We used filter, read-line and rand from the Standard Prelude. You can see the entire program, complete with the Chez Scheme header that invokes a program from the command line, at http://programmingpraxis.codepad.org/X3dRp0va.
The original C source code of the Unix V7 fortune command is shown below:
#include <stdio.h>
char line[500];
char bline[500];
main()
{
double p;
register char * l;
long t;
FILE *f;
f = fopen("/usr/games/lib/fortunes", "r");
if (f == NULL) {
printf("Memory fault -- core dumped\n");
exit(1);
}
time(&t);
srand(getpid() + (int)((t>>16) + t));
p = 1.;
for(;;) {
l = fgets(line, 500, f);
if(l == NULL)
break;
if(rand() < 32768./p)
strcpy(bline, line);
p += 1.;
}
fputs(bline, stdout);
return(0);
}
Programming Praxis 
[…] today’s Programming Praxis exercise, our goal is to implement the fortune Unix command line tool. […]
My Haskell solution (see http://bonsaicode.wordpress.com/2011/04/05/programming-praxis-fortune/ for a version with comments):
import Control.Monad import System.Environment import System.Random chance :: Int -> Int -> a -> a -> IO a chance x y a b = fmap (\r -> if r < x then a else b) $ randomRIO (0, y-1) fortune :: [a] -> IO a fortune = foldM (\a (n,x) -> chance 1 n x a) undefined . zip [1..] main :: IO () main = putStrLn =<< fortune . lines =<< readFile . head . (++ ["fortunes.txt"]) =<< getArgsA Python solution:
import random,sys filename = sys.argv[1] if len(sys.argv) > 1 else '/usr/games/lib/fortunes' with open(filename) as fortunes: print random.choice(list(fortunes)),Beauty of awk :
#!/bin/awk BEGIN{srand()} {if(rand()<=1/++n)l=$0} END{print l}My first solution is similar to Dave Webb’s, but I also wrote up an iterative
function that will use less resources if the fortune file is large.
#!/usr/bin/env python from random import choice, randrange, seed from sys import argv def whole_file(f): # easily written, good if f is smallish return choice(f.readlines()) def iter_file(f): # good if f is large curr_line, n = None, 0 for line in f: n += 1 i = 0 if randrange(n) > 1 else 1 curr_line = [curr_line, line][i] return curr_line def main(f, func=iter_file): print func(f) return None if __name__ == "__main__": seed() f_name = argv[1] if len(argv) > 1 else "fortunes.txt" with open(f_name) as f: main(f)Woops, line 14 should read
i = 0 if randrange(n) >= 1 else 1After writing my above solution, I took this as an opportunity to play
with pylint a sourcecode analyzer.
My new version is available here.
Another variation on solutions posted by Dave and Graham.
Nice one Mike; I need to learn more about the itertools module.
Quick question, though:
randint(0, n)uniformly picks a random integer from[0, n](inclusive), so doesn’t this use the probability
1/(n + 1)instead of1/n?@Graham. Yes, my program calculates the probability as 1/(n+1). However, n starts at 0.
So, for fortune lines 0, 1, 2, …, the probabilities are 1/1, 1/2, 1/3, ….
This is the same as n starting at 1 and calculating the probability as 1/n.
An version in Common Lisp:
and a completely golfed command line Perl version
perl -ne 'rand($.)<1&&($l=$_)}{print$l'just because the awk version was still readable.@Mike: My mistake! Thanks for clearing that up.
In F#,
open System let rnd = new Random() let lines = System.IO.File.ReadAllLines("fortunes.txt") Seq.nth (rnd.Next(Seq.length lines)) lines[…] reimplemented a basic version of Fortune. This version prints to the standard output a randomly chosen line from a text file. You can […]