6.8. The problem of a label

(A part from the book Mathcad 8 Pro for Students and Engineers)

Valery Ochkov http://twt.mpei.ac.ru/ochkov

(Translation into English by R.Girvin)

This problem of a label or more correctly, problem of disposing with a label - we'll look at in solving an ancient English puzzle about fishermen and fish:

"Three fishermen lay down to sleep, not having counted or divided their catch. In the night, one of them woke up, and (not quite trusting the others) decided to divide the pile of fish and take his share. But the number of fish wasn't visible by three. However, he found he could throw one fish away, then take exactly a third. This he did (noting, in the true spirit of fairness, that an even number of fish was left for his comrades) and went back to sleep. Later, the second and third fishermen woke in turn, and each went through the same process. The question is, what is the minimum number of fish in the catch that fulfils these conditions?"

The reader might like first to try to solve this task by hand; but we'll involve the computer in this for two reasons. Firstly, it lets us consider some ways to structuralize programs in the Mathcad environment: methods of clearing programs of labels, and 'squeezing' them into the rigorous framework of structural design. Secondly, we'll show that the Fishermen's Problem has, until now, been solved incorrectly...

Fig. 6.22. The Fishermen's Problem: 'unprogrammed' Mathcad solution (6_21_fisherman.mcd)

This problem can be solved in Mathcad without resorting to programming. Fig. 6.22 shows how this might be done how by successive manual approximations, with Mathcad just automating the division procedure. We set a first guess at 50 fish and see if the division works; if not, we try 49; and so on, decrementing the guess by one if the division produces a non-integer at any stage. Eventually, we guess at 25 fish, and this proves to be a solution. The first fisherman throws away a fish, and takes eight, leaving 16 (eight each for the others, he thinks). The second (not knowing what the first has done) leaves ten; and the third, six.

This solves the task but by applying 'manual' work in setting the value of the variable Catch and decrementing the value of the variable Answer. (Note that duplicating the block of operators fixing the actions of the three fishermen, though done for clarity in Fig 6.22, isn't necessary. It's sufficient to decrement Answer and keep track of Catch).

Let's try to automate the search for a solution to this task.

'1 Initial unstructured BASIC program

Input "Guess"; Answer

label: Catch = Answer

For Fisherman = 1 To 3

Catch = Catch 1

Catch = Catch - Catch / 3

If Catch > Int(Catch) Then Answer = Answer - 1: Goto label

Next

Print "Answer "; Answer; fish

 

'2. First stage of structuralization: a start

Input "Guess"; Answer

Answer = Answer + 1 step backward

label: Answer = Answer - 1 step forward

Catch = Answer

For Fisherman = 1 To 3

Catch = Catch 1

Catch = Catch - Catch / 3

If Catch > Int(Catch) Goto label

Next

Print "Answer "; Answer; fish

 

'3. Second stage of structuralization: addition of an attribute

Input "Guess"; Answer

Answer = Answer + 1

label: Answer = Answer 1

Catch = Answer

Divided = "yes" indicates catch divided

For Fisherman = 1 To 3

Catch = Catch 1

Catch = Catch - Catch / 3

If Catch > Int(Catch) Then Divided = no

Next

If Divided = no" Goto label

Print "Answer "; Answer; fish

 

4. Third step of structuralization: disposal of the label

Input "Guess"; Answer

Answer = Answer + 1

Do start loop with checking on exit

Answer = Answer 1

Catch = Answer

Divided = "yes"

For Fisherman = 1 To 3

Catch = Catch 1

Catch = Catch - Catch / 3

If Catch > Int(Catch) Then Divided = no

Next

Loop Until Divided = "yes" end loop

Print "Answer "; Answer; fish

Fig. 6.23. BASIC programs for solving the Fishermen's Problem

Fig. 6.23 shows four BASIC programs to automate the solution of the Fishermen's Problem. In all four, the operator Input requests the first guess (50 fish, for example) and the operator Print gives out the answer: 25 fish.

The first program follows exactly our 'manual' algorithm. Inside the loop for the three fishermen's successive leavings, we watch until we find fractional 'tails': that is, the parameter Catch is not an integer (the built-in BASIC function Int chops off these tails; the Mathcad analogue is the floor function). Then the guess decrements by one (Answer = Answer - 1) and the program control passes to the labelled statement (Goto label).

Before this program can be translated to Mathcad's programming language, we need to get rid of the label. And not only because in Mathcad's programming arsenal there is no facility to jump to a label, either conditionally or unconditionally, but for other reasons unconnected with Mathcad. In our 'toy' program (item 1 in a Fig. 6.23) the label is quite pertinent and natural, but if a program with labels expands, it becomes difficult to understand and practically impossible to debug and develop. The result, as structural programming wizards rightly emphasise, becomes like spaghetti: try pulling out a block of statements for separate debugging or compilation, and you find adhering strings of Goto links. Besides, such program can't be created by a group of developers ('bottom-up' technology). The first implementations of the Pascal language had no labels at all, as Pascal was developed by Niklaus Wirth for training students in structural programming. The label has appeared only in the late versions. So I think our view on learner programmers and the label must be, "Hide matches from children"!

The first step in structuralizing the BASIC program (see item 2 in Fig. 6.23) is moving the decrement code from the conditional statement to the label. That is:

If Catch > Int (Catch) Then Answer = Answer - 1: Goto label

becomes

label: Answer = Answer - 1

...

If Catch > Int(Catch) Goto label

There is another necessary change. Rather like an athlete taking a step back before a jump, we must insert Answer = Answer + 1, because when the program is run, label begins by decrementing Answer. Structuralizing generally complicates the algorithm a little: remember that "There's no such thing as a free lunch", "Beauty is only achieved by suffering", and so on.

The second step in structuralizing (see item 3) is extracting the conditional jump from the body of the For loop. For this purpose, we introduce an auxiliary binary variable, Divided, indicating successful or unsuccessful division. Inside the loop, the conditional jump to label is replaced by an "alternative with one shoulder" (that is, Divided stores the result of the binary choice, carrying it to a single exit from the loop one of the basic structural managing designs). The conditional jump 'slips' down and outside the loop.

After this (see item 4) the program can be modified with one more basic of structural design: a loop with checking on exit, which performs the same function as label and If ... Goto label in item 3. This finally enables the program to completely dispense with labels: the outer loop with exit checking, containing an inner For loop with its 'alternative with one shoulder'.

After all these manipulations, the fourth variant of the BASIC program is the one possible to copy to Mathcad (see Fig. 6.24). It's necessary to define it as a user function, as there are no Input and Print operators in the Mathcad language. Their analogues (the operators [ ]:= [ ] and [ ]=) work, alas, only outside of programs.

Fig. 6.24. Mathcad program for solving the Fishermen's Problem (6_22_fisherman.mcd)

In Fig. 6.24 the result of calling the function Answer are shown for various input values: 50, 24, -3 and even -30 fish. The English physicist and early quantum theorist Paul Dirac postulated not only antiparticles but "antifish". In one version of a well-known story[1], he is remembered as saying that 25 fish was an incorrect solution to this problem, and that the correct answer is -2 fish (or two antifish). If we start with two antifish, throwing away one away gives three antifish; we take our share of one antifish, leaving two antifish .. and so on indefinitely. Our computer solution of the problem shows that even Dirac was mistaken: "Paul, you are not right!" The conditions of the problem are fulfilled by an infinity of numbers we'll call it a Dirac of fish with a step of 27 (i.e. -2, 25, 52, etc).

To avoid being an ultra-pedant[2], it's possible to insert at the end of the for loop in Fig. 6.24 a statement break if Divided = "no" to interrupt the loop's operation even before all the fishermen have taken their share. If there aren't three fishermen but more (for example, thirty-three a task for the reader), this device essentially speeds up the program's operation (see the heading "Optimization of Mathcad programs"). The task can be complicated even more, generalizing to any number of fisherman sharing, or discarding, any number of fish.

The Fishermen's Problem can be solved in another way, by reversing it. Rather than making an initial guess for the catch, we can assume that the last fisherman leaves two fish (it can't be fewer) and increment that number by one until the conditions of the task can be fulfilled. This will solve the problem faster, and we won't ever get solutions of -2 or -29 fish (the paradigm "Keep it simple, stupid!" applies here). It's psychologically difficult for humans to appreciate negative solutions, but the machine does it quietly, without any prejudices. A more thought-out analytical solution of this task the search for integer roots of one equation with two unknowns doesn't give the negative answer.



[1]In another version, the story involves shipwrecked sailors dividing a heap of coconuts, the spare coconuts being thrown to a monkey. As the 'Monkey and Coconut Problem', this has been analysed in detail using the number theory of Diophantine equations. For five sailors, the minimum positive number of coconuts is 15621 (Martin Gardner comments that with a Dirac-type solution of four anticoconuts, the monkey benefits most from the process, as it receives a positive coconut at each stage of the division).

[2]There's a Russian word , meaning "boringly pedantic to the point of irrationality".