Random Line Filter

This is a special tool I hacked together to solve a very specific problem. It is basically a filter that will select one random line of the input and print it. The naive way of solving this would be to store all the lines in memory and then randomly select one of them, but the problem with this method is it's O(n) memory usage. Fortunately, I discovered another interesting algorithm that does the same thing, but with O(1) memory usage, and yet provides perfectly balanced randomness.

Take a look at the code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>

int consume_line(FILE *fh)
{
  int c;
  while ((c = fgetc(fh)) != EOF) {
    if (c == '\n')
      return 0;
  }
  return -1;
}

int main(void)
{
  char file[PATH_MAX];
  int eof = 0, count = 2;

  srandom(time(NULL));

  if (fgets(file, PATH_MAX, stdin) == NULL)
    return 1;

  while (! eof) {
    if (random() % count == 0) {
      if (fgets(file, PATH_MAX, stdin) == NULL)
        eof = 1;
    } else {
      if (consume_line(stdin) == -1)
        eof = 1;
    }
    count++;
  }

  printf("%s", file);
  return 0;
}
          

The tool can provide a simple way of playing random MP3 files, without the need for a shuffle function in the playback program. Like this example, using mplayer:

while true; do mplayer "`find . -name "*.mp3" | ./randline`"; done
          

This was the original intention of the tool, but I later discovered that mplayer does in fact have a shuffle mode! Well, it's too late now, as the tool has already been created.