Dice

dice.c is a snippet of C code that allows you to exhaustively test simple protocols. (guy.cpp has a C++ version of the Dice class, configured to solve 12 guys on an island with a see-saw.) You fill in function init() (which initializes a context) and driver() (which implements the protocol), calling the routine choose(n) whenever you have one of n choices to make.

The current code in init() and driver() implements tossing a 6-sided die ten times, testing whether it is possible to get 3 every time. Although there are over 60 million ways to roll 10 dice, this program only has to try 51 combinations, because it short-circuits when it sees the first non-3. Its output is

  1
  2
  3 1
  3 2
  3 3 1
  3 3 2
  3 3 3 1
  3 3 3 2
  3 3 3 3 1
  3 3 3 3 2
  3 3 3 3 3 1
  3 3 3 3 3 2
  3 3 3 3 3 3 1
  3 3 3 3 3 3 2
  3 3 3 3 3 3 3 1
  3 3 3 3 3 3 3 2
  3 3 3 3 3 3 3 3 1
  3 3 3 3 3 3 3 3 2
  3 3 3 3 3 3 3 3 3 1
  3 3 3 3 3 3 3 3 3 2
  3 3 3 3 3 3 3 3 3 3
  Yes, it is possible to roll 3 ten times in a row!
  3 3 3 3 3 3 3 3 3 4
  3 3 3 3 3 3 3 3 3 5
  3 3 3 3 3 3 3 3 3 6
  3 3 3 3 3 3 3 3 4
  3 3 3 3 3 3 3 3 5
  3 3 3 3 3 3 3 3 6
  3 3 3 3 3 3 3 4
  3 3 3 3 3 3 3 5
  3 3 3 3 3 3 3 6
  3 3 3 3 3 3 4
  3 3 3 3 3 3 5
  3 3 3 3 3 3 6
  3 3 3 3 3 4
  3 3 3 3 3 5
  3 3 3 3 3 6
  3 3 3 3 4
  3 3 3 3 5
  3 3 3 3 6
  3 3 3 4
  3 3 3 5
  3 3 3 6
  3 3 4
  3 3 5
  3 3 6
  3 4
  3 5
  3 6
  4
  5
  6

Most of what you could do with dice could be done easier with recursion, but sometimes not, and dice allows you to write it as if it were a normal program, rather than the convoluted way you'd have to write and think about the problem to do it recursively.

Internally, it keeps a really big counter. Each choose(n) subdivides the range of the counter into n choices. If you recurse too deep the counter gets subdivided into increments of less than 1 and it gives you an error. The program advances to the next choice by incrementing the counter by the appropriate amount.