Previous page Next page Navigation bar

Puzzles

In memoriam: Edsger W. Dijkstra

Code (finally!)

Now, finally, we have all our plans in place, and we can write code.

We use list 1 to describe the bridges.

{1003,1004,1005,...}→List 1End of line

We use List 2 as a vector of boolean values indicating which bridges remain; we initialize it to as many zeros as there are bridges, to indicate the absence of all bridges. Note that the expression Dim List 1 is the number of elements in List 1, which is the number of bridges.

Seq (0,A,1,Dim List 1,1)→List 2End of line

List 3 we use as a vector of boolean values indicating the locations a set of bridges let us reach. We initialize this to an 8-element vector, as there are 8 locations.

Seq(0,A,1,8,1)→List 3End of line

Variable D we use to count the number of sets of bridges that leave the shores connected; we initialize it to 0 to indicate we have yet to encounter any such sets of bridges.

0→DEnd of line

Variable E we used to count the number of sets of bridges we analyze. This should be equal to 8192 when we are through.

0→EEnd of line

Now we start the processing for a subset of bridges.

DoEnd of line

We initialize List 3 to show location 1 as known reachable, and the other locations as not known reachable.

Fill(0,List 3)End of line
1→List 3[1]End of line

Now we are going to see where we can get to from where we are. We will continue adding locations to the set of locations we know we can reach, until we can not add any new locations.

DoEnd of line

We need a flag indicating we found a new location. We call that flag F.

0→FEnd of line

We go through the list of bridges.

For 1→A To Dim List 1End of line

We determine if the bridge is present; if so, we will consider it.

If List 2[A]End of line
ThenEnd of line

We get the endpoints of the bridge into B and C.

List 1[A]÷1000→BEnd of line
1000Frac B→CEnd of line
Int B→BEnd of line

We determine if we know we can get to location B, the first endpoint of the bridge that is present; if so, we will consider the other end.

If List 3[B]End of line
ThenEnd of line

We determine if we already know we can get to location C, the second endpoint of the bridge that is present; if not, we will process location C.

If List 3[C]=0End of line
ThenEnd of line

We note that we can get to location C.

1→List 3[C]End of line

We also note that we have added a location to the set of locations we know we can get to.

1→FEnd of line

That is all we want to do for processing location C.

IfEndEnd of line

That is all we want to do based on the first endpoint B.

IfEndEnd of line

Now we do the same thing, but for the situation where we know we can get to location C and we do not yet know we can get to location B.

If List 3[C]End of line
Then If List 3[D]=0End of line
Then 1→List 3[D]End of line
1→FEnd of line
IfEndEnd of line
IfEndEnd of line

That is all we want to do if the bridge is present.

IfEndEnd of line

And that is all we want to do for the A'th bridge.

NextEnd of line

Now, if location 2 is reachable, then we can quit determining which locations are reachable; but we must increment the count of subsets where location 2 is reachable.

If List 3[2]End of line
Then D+1→DEnd of line
BreakEnd of line
IfEndEnd of line

At this point in the program, location 2 is not yet known to be reachable. If we did not discover a new reachable location in this pass through the bridge list, then we are done: we have determined all locations reachable from location 1, and as it happens location 2 not one of them.

LpWhile FEnd of line

We have processed a subset of bridges, and determined whether the subset of bridges leaves the shores connected.

E+1→EEnd of line

We now need to compute the description of the next subset of bridges from the description of this subset of bridges.

1→AEnd of line
While A≤Dim List 1End of line
If List 2[A]End of line
Then 0→List 2[A]End of line
A+1→AEnd of line
ElseEnd of line
1→List 2[A]End of line
BreakEnd of line
IfEndEnd of line
WhileEndEnd of line

The above code leaves A as the index of what was the lowest-order zero that was turned to a 1. If there is no lowest-order zero, A is left as 1+Dim List 1. So the value of A signifies whether the process generated another subset of the set of bridges; if A is at most Dim List 1, then the program has a new subset and the program should examine it, and otherwise the program has examined all possible subsets.

LpWhile A≤Dim List 1End of line

At this point, the program has examined all subsets of bridges. D has the number of subsets that leave the shores connected; E has the number of subsets in total; and D/E is the probability that the storm leaves the shores connected. We compute the probability and let the calculator display it as the value of the program.

D÷EEnd of line

And that is all there is, really. Put all together, the program is:

{1003,1004,1005,3004,4005,3006,4007,5008,6007,7008,6002,7002,8002}→List 1End of line
Seq(0,A,1,Dim List 1,1)→List 2End of line
Seq(0,A,1,8,1)→List 3End of line
0→DEnd of line
0→EEnd of line
DoEnd of line
Fill(0,List 3)End of line
1→List 3[1]End of line
DoEnd of line
0→FEnd of line
For 1→A To Dim List 2End of line
If List 2[A]End of line
Then List 1[A]÷1000→BEnd of line
1000Frac B→CEnd of line
Int B→BEnd of line
If List 3[B]End of line
Then If List 3[C]=0End of line
Then 1→List 3[C]End of line
1→FEnd of line
IfEndEnd of line
IfEndEnd of line
If List 3[C]End of line
Then If List 3[B]=0End of line
Then 1→List 3[B]End of line
1→FEnd of line
IfEndEnd of line
IfEndEnd of line
IfEndEnd of line
NextEnd of line
If List 3[2]End of line
Then D+1→DEnd of line
BreakEnd of line
IfEndEnd of line
LpWhile FEnd of line
E+1→EEnd of line
1→AEnd of line
While A≤Dim List 1End of line
If List 2[A]End of line
Then 0→List 2[A]End of line
A+1→AEnd of line
Else 1→List 2[A]End of line
BreakEnd of line
IfEndEnd of line
WhileEndEnd of line
LpWhile A≤Dim List 1End of line
D÷EEnd of line

We run this program, and after several hours, the program produces an answer. The answer it produces is, unsurprisingly, 0.5.

After roughly 5,000 words of exposition, much clever programming, and hours of computation, we are just where we started: we knew the probability was ½, and we computed it at ½. We have computationally verified Dijkstra’s proof. Big, as they say, deal.

But now we can redeem our efforts by extending Dijkstra’s problem.

[ 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