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);
}

About these ads

Pages: 1 2 3

13 Responses to “Fortune”

  1. [...] today’s Programming Praxis exercise, our goal is to implement the fortune Unix command line tool. [...]

  2. 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"]) =<< getArgs
    
  3. Dave Webb said

    A 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)),
    
  4. arturasl said

    Beauty of awk :

    #!/bin/awk
    BEGIN{srand()}
    {if(rand()<=1/++n)l=$0}
    END{print l}
    
  5. Graham said

    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)
    
  6. Graham said

    Woops, line 14 should read i = 0 if randrange(n) >= 1 else 1

  7. Graham said

    After writing my above solution, I took this as an opportunity to play
    with pylint a sourcecode analyzer.
    My new version is available here.

  8. Mike said

    Another variation on solutions posted by Dave and Graham.

    from collections import deque
    from itertools import count, compress
    from random import randint
    from sys import argv
    
    FORTUNES = 'fortunes.txt'
    
    with open(argv[1] if argv[1:] else FORTUNES, 'rt') as f:
       print deque(compress(f, (not randint(0,n) for n in count())), maxlen=1).pop()
    
  9. Graham said

    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 of 1/n?

  10. Mike said

    @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.

  11. Ross said

    An version in Common Lisp:

    (defun fortune (filename)
      "Return a Unix V7 fortune"
      (with-open-file (s filename :direction :input)
        (loop :with fortune
              :for line = (read-line s nil)
              :while line
              :counting line :into counter
              :do (when (< (random counter) 1) (setq fortune line))
              :finally (return fortune))))

    and a completely golfed command line Perl version perl -ne 'rand($.)<1&&($l=$_)}{print$l' just because the awk version was still readable.

  12. Graham said

    @Mike: My mistake! Thanks for clearing that up.

  13. Khanh Nguyen said

    In F#,

    open System
    let rnd = new Random()
    let lines = System.IO.File.ReadAllLines("fortunes.txt")
    Seq.nth (rnd.Next(Seq.length lines)) lines
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 616 other followers

%d bloggers like this: