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 1

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 2

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 3

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→D

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→E

Now we start the processing for a subset of bridges.

Do

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

Fill(0,List 3)
1→List 3[1]

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.

Do

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

0→F

We go through the list of bridges.

For 1→A To Dim List 1

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

If List 2[A]
Then

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

List 1[A]÷1000→B
1000Frac B→C
Int B→B

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]
Then

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]=0
Then

We note that we can get to location C.

1→List 3[C]

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

1→F

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

IfEnd

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

IfEnd

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]
Then If List 3[D]=0
Then 1→List 3[D]
1→F
IfEnd
IfEnd

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

IfEnd

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

Next

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]
Then D+1→D
Break
IfEnd

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 F

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

E+1→E

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

1→A
While A≤Dim List 1
If List 2[A]
Then 0→List 2[A]
A+1→A
Else
1→List 2[A]
Break
IfEnd
WhileEnd

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 1

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÷E

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 1
Seq(0,A,1,Dim List 1,1)→List 2
Seq(0,A,1,8,1)→List 3
0→D
0→E
Do
Fill(0,List 3)
1→List 3[1]
Do
0→F
For 1→A To Dim List 2
If List 2[A]
Then List 1[A]÷1000→B
1000Frac B→C
Int B→B
If List 3[B]
Then If List 3[C]=0
Then 1→List 3[C]
1→F
IfEnd
IfEnd
If List 3[C]
Then If List 3[B]=0
Then 1→List 3[B]
1→F
IfEnd
IfEnd
IfEnd
Next
If List 3[2]
Then D+1→D
Break
IfEnd
LpWhile F
E+1→E
1→A
While A≤Dim List 1
If List 2[A]
Then 0→List 2[A]
A+1→A
Else 1→List 2[A]
Break
IfEnd
WhileEnd
LpWhile A≤Dim List 1
D÷E

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 ]

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