Previous page Next page Navigation bar

Puzzles

In memoriam: Edsger W. Dijkstra

The Computational Plan, part 1

The first part of our computation is to “consider all possible outcomes.” Remember that an “outcome” is a collection of bridges that remain after a storm passes. So we need to consider all possible sets of bridges.

Well, first we need to be able to tell the bridges apart. There is an old saying about names: you don’t need names for individual things until there are at least two of them you need to tell apart. Well, we have 13 bridges we need to tell apart, and the easiest way to tell them apart is to give them names. We also have a simple, and infinite, supply of names: the positive integers. We will number the bridges, 1 through 13, and tell them apart that way. Does it matter which bridge is which? Not at present.

We need to consider all possible subsets of {1, 2, ..., 13}, and each subset will name a collection of bridges and hence identify an outcome. For this, we can use the following “trick of the trade:”

a magician showing a card trick

Tricks of the Trade

A boolean value is a value that takes one of two states: false and true. Boolean values are also sometimes called logical values. Because a boolean value has only two possible values, it can be represented by a single bit, a binary digit, that has possible values 0 and 1.

A vector or tuple is an ordered collection of possibly equal values known by a single collective name, where the individual values are identified (indexed) by a single value. The possible index values are generally a contiguous subset of the integers; frequently the lowest possible index value is 0 or 1.

We can represent a subset of set of n elements by a boolean vector of length n: we associate the i-th element of the set with the i-th element of the boolean vector, and set the i-th element of the boolean vector to true if and only if the i-th element of the set is in the subset. For example, suppose E = {e1, e2, ..., e10} is the base set. For each subset, we define a vector P = (p1, p2, ..., p10) where pi is true if and only if ei is in the subset. Thus, we would represent the subset S = {e2, e7, e8} as (false, true, false, false, false, false, true, true, false, false).

The Casio calculators discussed by this site have a construct known as a list, an indexed set of values. The available lists are creatively named “List 1” through “List 6.” Each list can have up to 255 elements. The individual element of a list can be accessed by giving the list name, followed by an expression in brackets (“[” and “]”). The expression must be an integer between 1 and the number of elements in the list. We will use a list to represent a set of bridges that is an outcome: the element [i] is 1 if i is the name of a bridge in the set, and 0 if i is not the name of a bridge in the set.

How, though, can we consider all possible subsets of {1, 2, ..., 13}? We know we can represent a subset with a list, but how do we generate a subset? For this, we depend on another trick of the trade:

a magician showing a card trick

Tricks of the Trade

In order to generate all possibilities for something, you need to be able to do exactly three things:

  1. Start with a first possibility;
  2. Given a possibility, recognize whether there is a next possibility;
  3. If there is a next possibility, determine what it is.

You can wrap these around per-possibility processing as follows:

Flowchart showing logic to iterate through possibilities

and the processing (shown by the blue box labeled “Process the possibility P” will occur for every possibility.

So we need to be able to (i) generate a first subset of {1, 2, ..., 13}; (ii) given a subset, recognize whether there is a next subset; and (iii) given a subset, if there is a next subset, generate it. We can combine (ii) and (iii) if we can generate the next subset if it exists, and recognize success or failure at this operation. Our “processing” of a set of bridges will be to count it if it leaves the shores of the river connected, and not to count it otherwise.

We could generate the subsets in an order such as:

{}, {1}, {2}, {3}, ..., {13}, {1, 2}, {1, 3}, ... {1, 13}, {2, 3}, {2, 4}, ...

But it turns out there is a much easier way to generate the subsets, and it depends on this trick of the trade:

a magician showing a card trick

Tricks of the Trade

Counting from 0 to 2n-1 creates every possible bit pattern of length n in the least significant (“low order”) n bits. For example, consider counting from 0 to 7 in binary: 000, 001, 010, 011, 100, 101, 110, 111.

Adding 1 to a binary number does two things: (i) changes all low-order 1 bits to 0, and (ii) changes the lowest-order 0 bit to 1. Subtracting 1 from a binary number does the reverse: it (i) changes all low-order 0 bits to 1, and (ii) changes the lowest-order 1 bit to 0. You can see this in three-bit values above.

We can easily generate all subsets of {1, 2, ..., 13} by considering List 1, our vector of boolean values, to be the bits of a binary number; and by using it to count in binary. So now we know how to do “set P to the first possibility” (create a list filled with zeroes) and “advance P to the next possibility” (add 1 to the binary number). The operation of adding 1 can fail if there is no “lowest-order 0 bit.” This, in turn, means that all the bits are 1; which in turn means we are at the highest possible binary value; which in turns means we have finished counting, and there is no “next” value.

The only thing left to figure out is “process the possibility P.” In our case, this means to count the sets of bridges that leave the two shores are connected.

We are examining each possible subset of the bridges, one at a time; and we need to determine the number of these subsets that leave the shores connected. We apply the following trick of the trade:

a magician showing a card trick

Tricks of the Trade

A program can determine a property of a collection of items by (i) considering each item in turn, and (ii) determining the property of the set of items seen so far. When all items in the collection have been considered, the property has been determined for the collection as a whole.

As an example, consider the problem of adding up a list of numbers. A program can determine the total by (i) initializing a “total seen so far” value to zero, and (ii) for each element in the list of numbers, replacing the “total seen so far” value with the sum of the element and the former “total seen so far” value. Before any numbers in the list have been considered, the “total” value is zero; after the first number in the list has been considered, the “total” will equal the first number in the list; after the second number in the list has been considered, the “total” will be the sum of the first two numbers in the list; after the third number in the list has been considered, the “total” will be the sum of the first three numbers in the list; and so forth. After the program considers the last number in the list, the “total seen so far“ value will be the sum of the numbers in the list.

The variable holding the “property of the set of items seen so far” is called the accumulator of the property.

So a simple counter, initialized at 0 and incremented by 1 whenever the program observes a subset of bridges that leaves the shores connected, will do. After the program has examined all possible subsets of the bridges, the counter will have the number of subsets of bridges that leave the shores connected. Dividing this count by 8192 will yield the probability we want. (Remember the problem? “What is the probability that the shores remain connected?”)

Now, if we can only tell whether a subset of bridges leaves the two shores connected, our planning will be done. So on to determining connectness!

[ Previous page | Top of page | Next page ]

Previous page Top of page Next page Navigation bar

Copyright © 2002 Brian Hetrick
Page last updated 9 April 2006.

Brian’s Casio Calculator Corner

Home

Programs

Tutorial

Puzzles

Index

2001/2002

Previous years

In memoriam: Dijkstra

Introduction

Interpretation

Plan, part 1

Plan, part 2

Code

Extension 1

Extension 2

Final Modification

Bridge Collections

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data